Lamports underskrift
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 31. december 2014; checks kræver 16 redigeringer .Lamport - signatur er et digitalt signaturkryptosystem med en offentlig nøgle. Kan bygges på enhver envejsfunktion . Det blev foreslået i 1979 og opkaldt efter dets forfatter, en amerikansk videnskabsmand, Leslie Lamport [1] .
Beskrivelse
Lad Alice have en 256-bit kryptografisk hashfunktion og en kryptografisk stærk pseudo-tilfældig talgenerator . Hun ønsker at oprette og bruge Lamports nøglepar, en privat nøgle og dens tilsvarende offentlige nøgle .
Oprettelse af et nøglepar
For at generere en hemmelig nøgle bruger Alice en tilfældig talgenerator til at generere 256 par tilfældige tal (2x256 tal i alt). Hvert tal består af 256 bit, så den samlede størrelse er 2x256x256 bit = 16 KiB . Disse numre vil være Alices hemmelige nøgle, og hun vil opbevare dem et hemmeligt sted til senere brug.
For at oprette den offentlige nøgle hasheser Alice hvert af de 512 private nøglenumre og laver således 512 hashes på hver 256 bit. Disse 512 hashes udgør Alices offentlige nøgle, som hun udgiver.
Meddelelsessignatur
Nu vil Alice underskrive beskeden. Først hashsender den beskeden og får en 256-bit hash. Derefter, for hver bit i den hash, tager den det tilsvarende tal fra den hemmelige nøgle. Hvis f.eks. den første bit i meddelelsens hash er nul, tager den det første tal fra det første hemmelige nøglepar. Hvis den første bit er lig med én, bruger den det andet tal fra det første par. Og så videre. Som et resultat opnås 256 tilfældige tal, hvis størrelse er 256 × 256 bit = 8 KiB. Disse tal udgør signaturen, som Alice sender sammen med beskeden.
Bemærk, at når Alice har brugt sin private nøgle, må den aldrig bruges igen. De resterende 256 numre, som hun ikke brugte i signaturen, må Alice aldrig offentliggøre eller bruge. Det er at foretrække, at hun sletter dem, ellers kan nogen få adgang til dem og generere en falsk signatur med dem.
Signaturbekræftelse
Bob vil bekræfte signaturen, som Alice underskrev beskeden med. Det hashes også beskeden og får en 256-bit hash. Derefter vælger han for hver bit i den hash et tal fra Alices offentlige nøgle. Disse numre er valgt på samme måde, som Alice valgte numrene til sin signatur. Det vil sige, at hvis den første bit af meddelelsens hash er nul, vælger Bob det første tal fra det første par i den offentlige nøgle. Og så videre.
Bob hashes derefter hvert af de 256 numre fra Alice's signatur og får 256 hashes. Hvis disse 256 hashes nøjagtigt matcher de 256 hashes, han lige har fået fra Alices offentlige nøgle, mener Bob, at signaturen er ægte. Hvis de ikke matcher, så er det falsk.
Det er værd at bemærke, at før Alice offentliggør signaturen til beskeden, kender ingen 2x256 tilfældige tal i den hemmelige nøgle. Således kan ingen oprette det korrekte sæt af 256 numre til at underskrive. Efter at Alice har udgivet signaturen, kender ingen stadig de andre 256 numre, og kan derfor ikke oprette en signatur for beskeder, der har en anden hash [2] .
Eksempel
Lad Alice sende en besked M = "Lamport" til Bob, underskrive den med Lamports signatur og bruge en 8-bit hash-funktion. Det vil sige, at den oprindelige besked vil blive konverteret til en 8-bit hash.
Nøglegenerering
Ved hjælp af en tilfældig talgenerator får Alice otte par tilfældige tal. Disse 16 numre er Alices private nøgle.
Privat nøgle:
For at få den offentlige nøgle beregner Alice en hashværdi for hvert tal fra den private nøgle.
Offentlig nøgle:
Alice udgiver den resulterende offentlige nøgle til offentligheden.
Meddelelsessignatur
Alice vil underskrive beskeden M = "Lamport". For at gøre dette beregner den hash-værdien af denne besked og forbinder hver bit af hashen med en af værdierne i de private nøglepar og danner derved en signatur.
Meddelelsessignatur "Lamport":
Signaturbekræftelse
Bob modtager en underskrevet besked "Lamport" og vil tjekke, om Alice virkelig har sendt den. For at gøre dette bruger han den offentlige nøgle, som Alice udgav. Den konverterer den modtagne besked til en hash og kortlægger hver bit i den resulterende hash til et tal fra et par i den offentlige nøgle. Den hashes derefter beskedsignaturen og sammenligner de resulterende to sæt tal. Hvis de er ens, så er signaturen ægte, og beskederne blev faktisk sendt af Alice.
Et sæt tal hentet fra den offentlige nøgle:
Signaturhash:
Da disse sæt er ens, er signaturen ægte.
Matematisk beskrivelse
Taster
Lad være et positivt tal, lad være et sæt meddelelser, og lad være en envejsfunktion .
For hver og , den part, der underskriver beskeden, vælger og beregner tilfældigt .
Den hemmelige nøgle består af . Den offentlige nøgle består af værdier . [3]
Meddelelsessignatur
Lad være en besked.
Meddelelsessignaturen er .
Signaturbekræftelse
Den part, der validerer signaturen, verificerer for alle .
For at forfalske en meddelelsessignatur skal kryptanalytikeren invertere envejsfunktionen , hvilket antages at være beregningsmæssigt umuligt.
Sikkerhed
Den kryptografiske styrke af Lamport-signaturer er baseret på den kryptografiske styrke af hash-funktionen .
For hver hash-funktion, der genererer en n-bit digest, indebærer den ideelle modstand mod preimage-gendannelse og anden preimage-gendannelse 2 n operationer og 2 n bits hukommelse i den klassiske beregningsmodel for hver udførelse af hash-funktionen . Ved at bruge Grovers algoritme er præ-billedgendannelse af en ideel hashfunktion afgrænset ovenfor af O( 2n /2 ) operationer i en kvanteberegningsmodel [4] .
Flere meddelelsessignaturer
Kun én enkelt besked kan signeres med én privat Lamport-nøgle. Det betyder, at hvis et vist antal meddelelser er signeret, skal det samme antal offentlige nøgler offentliggøres. Men hvis du bruger et Merkle-træ sammensat af offentlige nøgler, kan du i stedet for at udgive alle offentlige nøgler kun udgive toppen af træet. Dette øger størrelsen af signaturen, fordi en del af hash-træet skal inkluderes i signaturen, men det gør det muligt at bruge en enkelt hash til at verificere flere signaturer. Ifølge denne ordning kan du underskrive beskeder, hvor er dybden af Merkle-træet. Det vil sige, at vi teoretisk set kan bruge én offentlig nøgle til et hvilket som helst antal meddelelser [5] .
Nøglegenerering
Først skal du generere Lamports private engangsnøgler og Lamports offentlige engangsnøgler . Yderligere, for hver offentlig nøgle , hvor , beregnes dens hash . Og ud fra disse værdier bygges et Merkle-træ .
Vi nummererer træets noder på en sådan måde, at indekset angiver afstanden fra denne node til bladelementet, og indekset angiver nodens ordensnummer fra venstre mod højre på samme niveau .
I vores træ er hashværdier bladelementer , det vil sige . Hver ikke-bladsknude i træet er en hashværdi fra sammenføjning af to børn, dvs. og så videre.
Således har vi et træ, hvis rodelement er vores offentlige nøgle .
Beskedsignering og validering
For at underskrive en besked i henhold til vores skema, skal du først underskrive den med en engangs-Lamport-signatur . Dette gøres ved hjælp af et af de offentlige/private nøglepar .
er bladelementet i træet, der svarer til den offentlige nøgle . Stien fra træets bladelement til dets top består af elementerne , hvor er bladelementet og er toppen af træet. For at beregne denne vej har vi brug for alle børn af noder . Vi ved, at node er et barn af node . For at beregne den næste node på stien til toppen skal vi bruge begge børn af node . Derfor skal vi kende nodens "bror" . Lad os ringe til ham . Så, . Derfor har vi brug for noder til at beregne toppen af træet. Vi beregner dem og gemmer dem.
Disse noder udgør sammen med meddelelsens engangssignatur den endelige signatur .
Modtageren af beskeden har den offentlige nøgle , beskeden og signaturen til sin rådighed . Den kontrollerer først beskedens engangssignatur . Hvis det er ægte, beregner modtageren . Og så for beregner . Hvis den er lig med , anses signaturen for autentisk.
Forskellige optimeringer og implementeringer
Kort hemmelig nøgle
I stedet for at generere og gemme alle de tilfældige numre på den hemmelige nøgle, kan man gemme et enkelt tal af den passende størrelse. Typisk er størrelsen valgt til at være den samme som størrelsen af et tilfældigt tal i den private nøgle. Denne nøgle kan bruges som basis for en tilfældig talgenerator (CSPRNG), så hele den hemmelige nøglesekvens af tilfældige tal kan genskabes, når det er nødvendigt.
På samme måde kan en nøgle bruges sammen med en CSPRNG til at generere flere Lamport-nøgler. Foretrukne er CSPRNG'er, der har høj kryptografisk styrke, såsom BBS .
Kort offentlig nøgle
En Lamport-signatur kan bruges sammen med en liste over hashes, hvilket gør det muligt kun at inkludere én hash i en offentlig nøgle. Det vil sige i stedet for værdier - . For at kunne sammenligne de tilfældige tal i signaturen med hashen i den offentlige nøgle, skal alle hashes, der ikke bruges i den offentlige nøgle, det vil sige værdier for nogen , inkluderes i signaturen. Som et resultat bliver den offentlige nøgle væsentligt kortere, og signaturstørrelsen fordobles cirka.
Besked hashing
Lamports digitale signaturordning kræver ikke, at meddelelsen m hashes, før den underskrives. Hashing kan f.eks. bruges til at signere lange beskeder, hvor hashen af beskeden bliver signeret, og ikke selve beskeden [6] .
Sammenligning med andre kryptosystemer
De vigtigste fordele ved Lamports engangssignaturordning er, at den kan bygges på enhver envejsfunktion , og at dens signatur- og meddelelsesverifikationsalgoritme er betydeligt hurtigere end algoritmerne for genanvendelige signatursystemer. Samtidig har ordningen en række ulemper. For det første er ulempen nøglernes disponibilitet. Det vil sige, at når du underskriver hver ny besked, skal du generere et nyt par, hvilket fører til komplikationen af systemet. For det andet har ordningen den ulempe, at den har en stor signaturstørrelse og et par offentlige og private nøgler [7] .
Dette system har potentiale i lyset af, at den potentielle udvikling af en kvantecomputer truer sikkerheden for mange udbredte algoritmer, såsom RSA , mens Lamport-signaturen også vil forblive sikker i dette tilfælde [8] . Sammen med Merkle-træer kan Lamport-kryptosystemet bruges til at autentificere flere meddelelser, der fungerer som et ret effektivt digitalt signaturskema [9] .
Noter
- ↑ Lamport, 1979 , s. 2.
- ↑ Lamport, 1979 , s. 3-5.
- ↑ Katz , s. 2.
- ↑ M. I. Anokhin, N. P. Varnovsky, V. M. Sidelnikov, V. V. Yashchenko, Lamport og Naor-Jung . Dato for adgang: 17. december 2013. Arkiveret fra originalen 17. december 2013.
- ↑ Michael Szydlo, EFFEKTIV BRUG AF MERKLE TRÆER . Hentet 24. november 2013. Arkiveret fra originalen 17. april 2017.
- ↑ Lamport, 1979 , s. 6.
- ↑ Zaverucha, 2010 , s. en.
- ↑ Garcia , s. ti.
- ↑ Vadim Malykh, "Langtidsopbevaring af elektroniske dokumenter" . Dato for adgang: 13. december 2013. Arkiveret fra originalen 13. december 2013.
Litteratur
- Lamport L. Konstruktion af digitale signaturer fra en envejsfunktion . - SRI International Computer Science Laboratory, 1979.
- Peikert K. Kryptografiens teoretiske grundlag . - Georgia Tech, 2010. Arkiveret19. december 2013 påWayback Machine
- Katz J. Introduktion til kryptografi . - University of Maryland.
- Zaverucha G. Stinson R. Cheriton R. Korte engangssignaturer . - University of Waterloo, 2010.
- Garcia L. Om sikkerheden og effektiviteten af Merkle-signaturordningen . — Darmstadt.