Merklen allekirjoitus

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 27. marraskuuta 2016 tarkistetusta versiosta . tarkastukset vaativat 46 muokkausta .

Merkle -allekirjoitus on postkvantti- ja uudelleenkäytettävä digitaalinen allekirjoitusalgoritmi , joka perustuu Merkle-puun käyttöön ja jonkinlaiseen kertaluonteiseen digitaaliseen allekirjoitukseen. [yksi]

Historia

Ralph Merkle julkaisi allekirjoituksen ensimmäisen kerran vuonna 1979 artikkelissaan "Secrecy, authentication and public key systems" [2] uudelleenkäytettävänä digitaalisena allekirjoituksena käyttäen Lamportin kerta-allekirjoitusta . [3]

Algoritmin kuvaus

Valmistelu

Merklen allekirjoitus perustuu jo olemassa olevaan kertaluonteiseen digitaaliseen allekirjoitukseen, jonka kryptografisen vahvuuden tulee perustua kryptografisesti turvalliseen hajautustoimintoon . Esimerkkejä tällaisista allekirjoituksista ovat Winternitzin kertaluonteinen allekirjoitusjärjestelmä tai Lamportin allekirjoitus . [4] Kertaluonteisen digitaalisen allekirjoituksen tulisi sisältää kolme päätoimintoa: [5]

Salaisen avaimen ja julkisen avaimen luominen . $X$ $Y$
Allekirjoituksen luominen viestistä salaisella avaimella . $b$ $d$ $X$
Allekirjoituksen vahvistus julkisella avaimella . $b$ $Y$

On myös tarpeen päättää kryptonkestävästä hash-funktiosta , jota käytetään myöhemmin julkisen avaimen laskemiseen. [neljä] ${\displaystyle H:\{0,1\}^{*}\rightarrow \{0,1\}^{s))$

Avaimen luominen

Näppäinten ja pituuksien joukot luodaan . Pituus valitaan potenssiksi kaksi, koska Merkle-puun rakentaminen on välttämätöntä. Jokaista paria käytetään yksityisen ja julkisen avaimen parina kertaluonteiseen perusallekirjoitukseen. Array - on Merkle-allekirjoituksen yksityinen avain, Merkle-puu on rakennettu luomaan julkista avainta: $X$ $Y$ $N=2^{n}$ ${\näyttötyyli (X_{i},Y_{i})}$ $X$

Jokaiselle lasketaan hash-arvo - tämä on puun nollakerros eli sen lehdet. Kutsutaan tätä kerrosta . Yhteensä sisältää kohteita. Sen jälkeen lasketaan seuraava kerros, jonka koko on : kerroksen jokainen -. elementti lasketaan kahden edellisen kerroksen elementin kautta , jossa on ketjutusoperaatio. Siten jokaisella seuraavalla i :nnellä kerroksella on pituus ja se lasketaan i :nnen kerroksen kautta. Tuloksena tulemme puun viimeiseen kerrokseen , jolla on pituus ja joka on puun juuri. $Y_{i}$ $H(Y_{i})$ $a_{0}$ $a_{0}$ ${\displaystyle l_{0}=2^{n))$ $a_{1}$ $l_{1}=2^{n-1}$ $j$ $a_{1}$ $a_{1,j}=H(a_{0,j*2}||a_{0,j*2+1})$ $||$ $i$ ${\displaystyle l_{i}=2^{ni))$ $i-1$ $a_n$ $l_{n}=1$

Rakennetun Merkle-puun juuri otetaan julkiseksi avaimeksi: . [6] ${\displaystyle pub\_key=a_{n))$

Allekirjoituksen luominen

Allekirjoituksen luomiseksi taulukoista ja valitaan -. avainpari Viesille lasketaan yksityisellä avaimella kertaluonteinen digitaalinen allekirjoitus . Harkitse seuraavaksi polkua Merkle-puun juuresta avainta vastaavaan lehteen . Merkitään pisteet, joiden kautta tämä polku kulkee taulukona , jonka pituus on , jossa on puun juuri ja on . Kunkin huippupisteen arvo paitsi , lasketaan muodossa , missä ja ovat välittömiä jälkeläisiä . Näin ollen polun laskemiseksi puun juuresta riittää, että tunnetaan kärkijoukko , jota kutsumme autentikointipoluksi. Näin ollen viestin allekirjoitus sisältää: vahvistusavaimen , kertaluonteisen allekirjoituksen ja todennuspolun polun laskemiseksi puun juureen. [7] $X$ $Y$ $i$ ${\näyttötyyli (X_{i},Y_{i})}$ $d$ $b_{i}$ $X_{i}$ ${\näyttötyyli a_{0,n))$ $a_{0,i}$ $Y_{i}$ $A$ $n+1$ $A_{n}$ $A_0$ $a_{0,i}$ $A_{j}$ $A_{0}=H(Y_{i})$ $H(A_{j-1}||auth_{j-1})$ $auth_{j-1}$ $A_{j-1}$ $A_{{j}}$ $Y_{i}$ ${\displaystyle auth_{1},auth_{2},...,auth_{n))$ $d$ $Y_{i}$ $b_{i}$

Allekirjoituksen vahvistus

Ensin vastaanottaja vertaa kertaluonteisen allekirjoituksen viestiin . Jos tarkistus onnistui, se alkaa rakentaa polkua puun juurelta. Ensin , sitten , ja niin edelleen. Jos , allekirjoituksen vahvistus onnistui. [kahdeksan] $b_{i}$ $d$ $H(Y_{i})$ $A_{0}=H(Y_{i})$ $A_{1}=H(A_{0}||auth_{0})$ $A_{n}=pub\_key$

Edut

Post-kvantti

Yleisesti käytetyt digitaalisen allekirjoituksen algoritmit, kuten RSA ja DSA , hyödyntävät lukukertoimien monimutkaisuutta ja diskreetin logaritmin laskemisen monimutkaisuutta . Kuitenkin käyttämällä Shorin algoritmia ja kvanttitietokonetta nämä allekirjoitukset voidaan rikkoa polynomiajassa. Sitä vastoin Merklen allekirjoitus on postkvantti, koska sen kryptografinen vahvuus perustuu kryptografisen hajautusfunktion vahvuuteen ja kertaluonteisen digitaalisen allekirjoituksen vahvuuteen. [yksi]

Uudelleenkäytettävyys

Yksi vahvoihin hajautustoimintoihin perustuvien digitaalisten allekirjoitusten suurimmista ongelmista on, että niitä käytetään tyypillisesti kertaluonteisten digitaalisten allekirjoitusten yhteydessä, eli allekirjoituksissa, joissa yhdellä avainparilla allekirjoitetaan vain yksi viesti. On kuitenkin olemassa tapoja laajentaa tällaisia allekirjoituksia uudelleenkäytettäviksi. Yksi tällainen tapa on rakentaa Merkle-puu, jota käytetään erilaisten kertaluonteisten allekirjoitusten todentamiseen . [9]

Haitat

Puun läpikulkuongelma

Tämä ongelma liittyy tehokkaan algoritmin löytämiseen todennustietojen laskemiseen. Triviaali ratkaisu - pitää kaikki tiedot muistissa - vaatii liikaa muistia. Toisaalta lähestymistapa todennuspolun laskemiseksi alueella, jossa sitä tarvitaan, tulee olemaan liian kallista joillekin puusolmuille. [10] Jos X- ja Y-taulukoiden pituus on suurempi kuin 2^25, Merklen allekirjoituksen käytöstä tulee epäkäytännöllistä. [kahdeksan]

Kryptanalysis

Merklen digitaalisen allekirjoituksen algoritmin on osoitettu olevan kryptografisesti vahva adaptiivista viestinvalintahyökkäystä vastaan, jos se käyttää hash-funktiota, joka kestää tyypin 2 törmäyksiä . [11] [12] Merklen allekirjoituksen murtamiseksi kryptanalyytikon on kuitenkin joko rekonstruoitava hash-funktion esikuva tai laskettava tyypin I törmäys. Tämä tarkoittaa, että käytännössä Merklen allekirjoituksen kryptografinen vahvuus perustuu käytetyn hash-funktion peruuttamattomuuteen ja sen kestävyyteen ensiluokkaisia törmäyksiä vastaan. [12]

Muistiinpanot

↑ 12 CMSS , 2006 , s. 349-350.
↑ Merkle, 1979 .
↑ Turvallisuus, 2005 , s. yksi.
↑ 12 CMSS , 2006 , s. 352.
↑ CMSS, 2006 , s. 351.
↑ Turvallisuus, 2005 , s. 3.
↑ CMSS, 2006 , s. 352-353.
↑ 12 CMSS , 2006 , s. 353.
↑ dods2005hash, 2005 , s. 96.
↑ szydlo2004merkle, 2004 , s. 541.
↑ Turvallisuus, 2005 , s. neljä.
↑ 1 2 rohde2008fast, 2008 , s. 109.

Kirjallisuus

Merkle, Ralph Charles. Salassapito-, todennus- ja julkisen avaimen järjestelmät : Tekninen raportti nro. 1979-1. - Citeseer, 1979. - doi : 10.1.1.637.3952 .

Garcia, LC Coronado. Merklen allekirjoitusjärjestelmän turvallisuudesta ja tehokkuudesta : Tekninen raportti 2005/192. - Cryptology ePrint Archive, 2005.

Buchmann, Johannes. CMSS – parannettu Merklen allekirjoitusjärjestelmä // Kansainvälinen kryptologiakonferenssi Intiassa. - Springer Berlin Heidelberg, 2006. - S. 349-363 . - doi : 10.1007/11941378_25 . (linkki ei saatavilla)

Dods, Chris ja Smart, Nigel P ja Stam, Martijn. Hash-pohjaiset digitaaliset allekirjoitusjärjestelmät // IMA International Conference on Cryptography and Coding. - Springer Berlin Heidelberg, 2005. - S. 96-115 . - doi : 10.1007/11586821_8 .

Szydlo, Michael. Merkle-puun läpikulku lokitilassa ja ajassa // Kansainvälinen konferenssi kryptografisten tekniikoiden teoriasta ja sovelluksista. - Springer Berlin Heidelberg, 2004. - S. 541-554 . - doi : 10.1007/978-3-540-24676-3_32 .

Rohde, Sebastian ja Eisenbarth, Thomas ja Dahmen, Erik ja Buchmann, Johannes ja Paar, Christof. Nopeat hash-pohjaiset allekirjoitukset rajoitetuilla laitteilla // Kansainvälinen älykorttitutkimuksen ja edistyneiden sovellusten konferenssi. - Springer Berlin Heidelberg, 2008. - S. 104-117 . - doi : 10.1007/978-3-540-85893-5_8 .

Hash-funktiot
yleinen tarkoitus	Adler-32 CRC Fletcherin tarkistussumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash summa
Kryptografinen	Stribog GOST R 34.11-94 Vyö BLAKE BMW CubeHash KAIKU edonkey2k FSB Fuuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Iho Snefru Tiikeri Whirlpool
Avainten luontitoiminnot	bcrypt PBKDF2 scrypt Argon 2 Lyra 2
Tarkista numero ( vertailu )	Tarkista summa Verhouffin algoritmi Kuun algoritmi Damm-algoritmi Viivakoodi pankkitilit pankkikortit ISIN SNILS OKPO TINA OKATO ISBN OGRN ja OGRNIP VIN
Hashes	Sekkinumeroiden vertailu Todennusprotokollat Viivakoodin vertailu Kryptografia Magneettilinkki Merklen allekirjoitus ed2k UURNA