Merkle signatur

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. november 2016; checks kræver 46 redigeringer .

Merkle-signatur er en post-kvante og genanvendelig digital signaturalgoritme baseret på brugen af et Merkle-træ og en form for digital engangssignatur. [en]

Historie

Signaturen blev første gang udgivet af Ralph Merkle i 1979 i hans artikel "Secrecy, authentication, and public key systems" [2] som en genanvendelig digital signatur ved hjælp af Lamports engangssignatur . [3]

Beskrivelse af algoritmen

Forberedelse

Merkle-signaturen er baseret på en allerede eksisterende digital engangssignatur, hvis kryptografiske styrke skal være baseret på en kryptografisk sikker hashfunktion . Eksempler på sådanne underskrifter vil være Winternitz One-time Signature Scheme eller Lamports underskrift . [4] En digital engangssignatur bør bestå af tre hovedoperationer: [5]

Generering af en hemmelig nøgle og en offentlig nøgle . $x$ $Y$
Generering af en signatur fra en besked ved hjælp af en hemmelig nøgle . $b$ $d$ $x$
Signaturbekræftelse med offentlig nøgle . $b$ $Y$

Det er også nødvendigt at beslutte sig for en krypto-resistent hash-funktion , som senere vil blive brugt til at beregne den offentlige nøgle. [fire] ${\displaystyle H:\{0,1\}^{*}\højrepil \{0,1\}^{s))$

Nøglegenerering

Arrays af nøgler og længder genereres . Længden er valgt til at være en potens af to, da det er nødvendigt at konstruere et Merkle-træ. Hvert par bruges som et privat-offentlig nøglepar til en grundlæggende engangssignatur. Array - er den private nøgle til Merkle-signaturen, et Merkle-træ er bygget til at generere den offentlige nøgle: $x$ $Y$ $N=2^{n}$ $(X_{i},Y_{i})$ $x$

For hver , beregner vi hashværdien - dette vil være træets nullag, det vil sige dets blade. Lad os kalde dette lag . I alt indeholder elementer. Derefter beregner vi det næste lag, som har en størrelse : hvert -te element i laget beregnes gennem to elementer fra det forrige lag , hvor er sammenkædningsoperationen. Hvert næste i -te lag har således en længde og beregnes gennem det i -te lag. Som et resultat kommer vi til det sidste lag af træet , som har en længde og er roden af træet. $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})$ $||$ $jeg$ ${\displaystyle l_{i}=2^{ni))$ $i-1$ $a_n$ $l_{n}=1$

Roden af det konstruerede Merkle-træ tages som den offentlige nøgle: . [6] ${\displaystyle pub\_key=a_{n))$

Signaturgenerering

For at generere en signatur fra arrays og , vælges det 1. par nøgler En digital engangssignatur beregnes for beskeden ved hjælp af den private nøgle . Overvej derefter stien fra roden af Merkle-træet til bladet, der svarer til nøglen . Lad os betegne de hjørner, som denne sti passerer igennem, som en række af længde , hvor er træets rod, og er . Værdien af hvert toppunkt undtagen , beregnes som , hvor og er umiddelbare børn af . For at beregne stien fra træets rod er det således nok at kende rækken af hjørner , som vi vil kalde godkendelsesstien. Meddelelsessignaturen inkluderer således: en verifikationsnøgle , en engangssignatur og en godkendelsessti til at beregne stien til træets rod. [7] $x$ $Y$ $jeg$ $(X_{i},Y_{i})$ $d$ $b_{i}$ $X_{i}$ ${\displaystyle a_{0,n))$ $a_{0,i}$ $Y_{i}$ $EN$ $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}$

Signaturbekræftelse

Først kontrollerer modtageren engangssignaturen i forhold til beskeden . Hvis kontrollen var vellykket, begynder den at bygge stien fra til roden af træet. Først, så og så videre. Hvis , var signaturbekræftelsen vellykket. [otte] $b_{i}$ $d$ $H(Y_{i})$ $A_{0}=H(Y_{i})$ $A_{1}=H(A_{0}||auth_{0})$ $A_{n}=pub\_key$

Fordele

Post-kvante

Almindeligt anvendte digitale signaturalgoritmer, såsom RSA og DSA , drager fordel af kompleksiteten ved talfaktorisering og kompleksiteten ved at beregne den diskrete logaritme . Men ved at bruge Shor 's algoritme og en kvantecomputer kan disse signaturer brydes i polynomiel tid. I modsætning hertil er Merkle-signaturen post-kvante, da dens kryptografiske styrke er baseret på styrken af den kryptografiske hash-funktion og styrken af den digitale engangssignatur. [en]

Genanvendelighed

Et af hovedproblemerne med digitale signaturer baseret på stærke hash-funktioner er, at de typisk bruges i sammenhæng med digitale engangssignaturer, det vil sige signaturer, hvor ét nøglepar bruges til kun at signere én besked. Der er dog måder at udvide sådanne signaturer på, så de kan genbruges. En sådan metode er at bygge et Merkle-træ, som bruges til at autentificere forskellige engangssignaturer. [9]

Ulemper

Trægennemløbsproblemet

Dette problem er relateret til at finde en effektiv algoritme til beregning af godkendelsesdata. Den trivielle løsning - at opbevare alle data i hukommelsen - kræver for meget hukommelse. På den anden side vil metoden med at beregne autentificeringsstien i det område, hvor den er nødvendig, være for dyr for nogle træknuder. [10] Hvis længden af X- og Y-arrays er større end 2^25, bliver brugen af Merkle-signaturen upraktisk. [otte]

Krypteringsanalyse

Det er bevist, at Merkles digitale signaturalgoritme er kryptografisk stærk mod et adaptivt meddelelsesangreb, hvis den bruger en hash-funktion, der er modstandsdygtig over for type 2- kollisioner . [11] [12] Men for at knække Merkle-signaturen skal kryptanalytikeren enten rekonstruere præ-billedet af hash-funktionen eller beregne en Type I-kollision. Det betyder, at fra et praktisk synspunkt er den kryptografiske styrke af en Merkle-signatur baseret på irreversibiliteten af den anvendte hash-funktion og på dens modstand mod førsteklasses kollisioner. [12]

Noter

↑ 12 CMSS , 2006 , s. 349-350.
↑ Merkle, 1979 .
↑ Sikkerhed, 2005 , s. en.
↑ 12 CMSS , 2006 , s. 352.
↑ CMSS, 2006 , s. 351.
↑ Sikkerhed, 2005 , s. 3.
↑ CMSS, 2006 , s. 352-353.
↑ 12 CMSS , 2006 , s. 353.
↑ dods2005hash, 2005 , s. 96.
↑ szydlo2004merkle, 2004 , s. 541.
↑ Sikkerhed, 2005 , s. fire.
↑ 1 2 rohde2008fast, 2008 , s. 109.

Litteratur

Merkle, Ralph Charles. Hemmeligholdelse, autentificering og offentlige nøglesystemer : Teknisk rapport nr. 1979-1. - Citeseer, 1979. - doi : 10.1.1.637.3952 .

Garcia, LC Coronado. Om sikkerheden og effektiviteten af Merkle-signaturordningen : Teknisk rapport 2005/192. — Cryptology ePrint Archive, 2005.

Buchmann, Johannes. CMSS – en forbedret Merkle-signaturordning // International konference om kryptologi i Indien. - Springer Berlin Heidelberg, 2006. - S. 349-363 . - doi : 10.1007/11941378_25 . (utilgængeligt link)

Dods, Chris og Smart, Nigel P og Stam, Martijn. Hash-baserede digitale signaturordninger // IMA International Conference on Cryptography and Coding. - Springer Berlin Heidelberg, 2005. - S. 96-115 . - doi : 10.1007/11586821_8 .

Szydlo, Michael. Merkle trægennemgang i logrum og tid // International konference om teorien og anvendelsen af kryptografiske teknikker. - Springer Berlin Heidelberg, 2004. - S. 541-554 . - doi : 10.1007/978-3-540-24676-3_32 .

Rohde, Sebastian, Eisenbarth, Thomas, Dahmen, Erik, Buchmann, Johannes og Paar, Christof. Hurtige hash-baserede signaturer på begrænsede enheder // International konference om smartkortforskning og avancerede applikationer. - Springer Berlin Heidelberg, 2008. - S. 104-117 . - doi : 10.1007/978-3-540-85893-5_8 .

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge 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 Hud Snefru Tiger Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE