Lamports signatur

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 31 december 2014; kontroller kräver 16 redigeringar .

Lamport signatur är ett digitalt signaturkryptosystem med en publik nyckel. Kan byggas på valfri enkelriktad funktion . Den föreslogs 1979 och uppkallades efter dess författare, en amerikansk vetenskapsman, Leslie Lamport [1] .

Beskrivning

Låt Alice ha en 256-bitars kryptografisk hashfunktion och en kryptografiskt stark pseudo-slumptalsgenerator . Hon vill skapa och använda Lamports nyckelpar, en privat nyckel och dess motsvarande offentliga nyckel .

Skapa ett nyckelpar

För att generera en hemlig nyckel använder Alice en slumptalsgenerator för att generera 256 par slumptal (totalt 2x256 tal). Varje nummer består av 256 bitar, så den totala storleken är 2x256x256 bitar = 16 KiB . Dessa nummer kommer att vara Alices hemliga nyckel, och hon kommer att förvara dem på en hemlig plats för senare användning.

För att skapa den publika nyckeln hashar Alice vart och ett av de 512 privata nyckelnumren, vilket gör 512 hash om 256 bitar vardera. Dessa 512 hashen utgör Alices publika nyckel, som hon publicerar.

Meddelandesignatur

Nu vill Alice skriva under meddelandet. Först hashar den meddelandet och får en 256-bitars hash. Sedan, för varje bit i den hashen, tar den motsvarande nummer från den hemliga nyckeln. Om till exempel den första biten i meddelandets hash är noll, tar den den första siffran från det första hemliga nyckelparet. Om den första biten är lika med ett, använder den det andra talet från det första paret. Och så vidare. Som ett resultat erhålls 256 slumptal, vars storlek är 256 × 256 bitar = 8 KiB. Dessa nummer utgör signaturen som Alice skickar tillsammans med meddelandet.

Observera att när Alice har använt sin privata nyckel får den aldrig användas igen. De återstående 256 numren, som hon inte använde i signaturen, får Alice aldrig publicera eller använda. Det är att föredra att hon tar bort dem, annars kan någon komma åt dem och generera en falsk signatur med dem.

Signaturverifiering

Bob vill verifiera signaturen som Alice skrev under meddelandet med. Den hashar också meddelandet och får en 256-bitars hash. Sedan, för varje bit i den hashen, väljer han ett nummer från Alices publika nyckel. Dessa siffror är valda på samma sätt som Alice valde siffrorna för sin signatur. Det vill säga, om den första biten i meddelandehashen är noll, väljer Bob det första numret från det första paret i den publika nyckeln. Och så vidare.

Bob hashar sedan vart och ett av de 256 numren från Alices signatur och får 256 hash. Om dessa 256 hash exakt matchar de 256 hasharna han just fick från Alices publika nyckel, tror Bob att signaturen är äkta. Om de inte matchar, då är det falskt.

Det är värt att notera att innan Alice publicerar signaturen till meddelandet, känner ingen till 2x256 slumptal i den hemliga nyckeln. Således kan ingen skapa den korrekta uppsättningen av 256 nummer att signera. Efter att Alice publicerat signaturen känner ingen fortfarande till de andra 256 numren, och kan därför inte skapa en signatur för meddelanden som har en annan hash [2] .

Exempel

Låt Alice skicka ett meddelande M = "Lamport" till Bob, signera det med Lamports signatur och använda en 8-bitars hashfunktion. Det vill säga det ursprungliga meddelandet kommer att konverteras till en 8-bitars hash.

Nyckelgenerering

Med hjälp av en slumptalsgenerator får Alice åtta par slumptal. Dessa 16 nummer är Alices privata nyckel.

Privat nyckel: $(13,$ $134)$ $(128,$ $67)$ $(25,$ $90 ) (78,$ $156)$ $(89,$ $37)$ $(234,$ $29)$ $(199,$ $74)$ $(12,$ $3)$

För att få den publika nyckeln, beräknar Alice ett hashvärde för varje nummer från den privata nyckeln.

Offentlig nyckel:

$(00101010,$ $10010101)$

$(01100111,$ $11010101)$

$(00101110,$ $11110111)$

$(00100101,$ $11011101)$

$(11100001,$ $00011000)$

$(11000110,$ $11001110)$

$(11001101,$ $11001001)$

$(11100011,$ $11111101)$

Alice publicerar den resulterande publika nyckeln till allmänheten.

Meddelandesignatur

Alice vill skriva under meddelandet M = "Lamport". För att göra detta beräknar den hashvärdet för detta meddelande och associerar varje bit av hashen med ett av värdena i de privata nyckelparen och bildar därigenom en signatur. $H(M)=01011010$

Meddelandesignatur "Lamport": $(13,$ $67,$ $25,$ $156,$ $37,$ $234,$ $74,$ $12)$

Signaturverifiering

Bob får ett undertecknat meddelande "Lamport" och vill kontrollera om Alice verkligen har skickat det. För att göra detta använder han den publika nyckeln som Alice publicerade. Den omvandlar det mottagna meddelandet till en hash och mappar varje bit i den resulterande hashen till ett nummer från ett par i den publika nyckeln. Den hashas sedan meddelandesignaturen och jämför de resulterande två uppsättningarna siffror. Om de är lika, då är signaturen verklig, och meddelandena skickades verkligen av Alice.

En uppsättning nummer erhållna från den offentliga nyckeln:

$00101010,$

$11010101,$

$00101110,$

$11011101,$

$00011000,$

$11000110,$

$11001001,$

$11100011$

Signaturhash:

$00101010,$

$11010101,$

$00101110,$

$11011101,$

$00011000,$

$11000110,$

$11001001,$

$11100011$

Eftersom dessa uppsättningar är lika, är signaturen verklig.

Matematisk beskrivning

Nycklar

Låt vara ett positivt tal, låt vara en uppsättning meddelanden och låt vara en enkelriktad funktion . $k$ $P=\{0,1\}^k$ $f:\,Y\högerpil Z$

För varje och väljer och beräknar den part som signerar meddelandet slumpmässigt . $1\leq i\leq k$ $j\in\{0,1\}$ $y_{i,j}\in Y$ $z_{i,j}=f(y_{i,j})$

Den hemliga nyckeln består av . Den publika nyckeln består av värden . [3] $K$ $2k$ $y_{i,j}$ $2k$ $z_{i,j}$

Meddelandesignatur

Låt vara ett meddelande. $m = m_1\ldots m_k \in\{0,1\}^k$

Meddelandesignaturen är . $tecken(m_1\ldots m_k)=(y_{1,m_1},\ldots, y_{k,m_k})=(s_1,\ldots,s_k)$

Signaturverifiering

Parten som validerar signaturen verifierar för alla . $f(s_i) = z_{i,m_i}$ $1\leq i\leq k$

För att förfalska en meddelandesignatur måste kryptoanalytikern invertera envägsfunktionen , vilket antas vara beräkningsmässigt omöjligt. $f$

Säkerhet

Den kryptografiska styrkan hos Lamport-signaturer baseras på den kryptografiska styrkan hos hashfunktionen .

För varje hashfunktion som genererar ett n-bitars sammandrag, innebär det ideala motståndet mot preimage-återställning och andra preimage-återställning 2 n operationer och 2 n bitar av minne i den klassiska beräkningsmodellen för varje exekvering av hash-funktionen . Med hjälp av Grovers algoritm begränsas förbildsåterställning av en ideal hashfunktion ovan av O( 2n /2 ) operationer i en kvantberäkningsmodell [4] .

Flera meddelandesignaturer

Endast ett enda meddelande kan signeras med en privat nyckel från Lamport. Det betyder att om ett visst antal meddelanden signeras måste samma antal publika nycklar publiceras. Men om du använder ett Merkle-träd som består av publika nycklar, kan du istället för att publicera alla publika nycklar bara publicera toppen av trädet. Detta ökar storleken på signaturen eftersom en del av hashträdet måste inkluderas i signaturen, men det gör det möjligt att använda en enda hash för att verifiera flera signaturer. Enligt detta schema kan du signera meddelanden, var är djupet på Merkle-trädet. Det vill säga, teoretiskt sett kan vi använda en publik nyckel för valfritt antal meddelanden [5] . $N=2^n$ $n$

Nyckelgenerering

Först måste du generera Lamports privata engångsnycklar och Lamports offentliga engångsnycklar . Vidare, för varje publik nyckel , där , beräknas dess hash . Och utifrån dessa värden byggs ett Merkleträd . $2^{n}$ $X_{i}$ $Y_{i}$ $Y_{i}$ $1 \leq i \leq 2^n$ $h_{i}=H(Y_{i})$ $Hej}$

Vi numrerar trädets noder på ett sådant sätt att indexet anger avståndet från denna nod till bladelementet, och indexet anger nodens ordningsnummer från vänster till höger på samma nivå . $a_{i,j}$ $i$ $j$ $i$

I vårt träd är hashvärden bladelement , det vill säga . Varje icke-bladsnod i trädet är ett hashvärde från att sammanfoga två barn, d.v.s. och så vidare. $Hej}$ $h_i=a_{0,i}$ $a_{1,0}=H(a_{0,0}||a_{0,1})$ $a_{2,0}=H(a_{1,0}||a_{1,1})$

Således har vi ett träd vars rotelement är vår publika nyckel . $pub$

Meddelandesignering och validering

För att signera ett meddelande enligt vårt schema måste du först signera det med en engångssignatur från Lamport . Detta görs med ett av de offentliga/privata nyckelparen . $sig'$ $(X_i, Y_i,)$

$a_{0,i}=H(X_i)$ är bladelementet i trädet som motsvarar den publika nyckeln . Vägen från trädets lövelement till dess topp består av elementen , där är lövelementet och är trädets topp. För att beräkna denna väg behöver vi alla barn till noder . Vi vet att noden är ett barn till noden . För att beräkna nästa nod på vägen till toppen behöver vi båda barnen till nod . Därför måste vi känna till nodens "bror" . Låt oss ringa honom . Så, . Därför behöver vi noder för att beräkna toppen av trädet. Vi beräknar dem och sparar dem. $X_{i}$ $a_{0,i}$ $A_0, ... A_n$ $A_0=a_{0,i}$ $A_n=a_{n,0}=pub$ $A_{1}, ..., A_{n}$ $A_{i}$ $A_{{i+1}}$ $A_{{i+1}}$ $A_{i}$ $auth_i$ $A_{i+1}=H(A_i||auth_i)$ $n$ $auth_0,...,auth_{n-1}$

Dessa noder, tillsammans med engångssignaturen för meddelandet, utgör den slutliga signaturen . $sig'$ $M$ $sig=(sig'||X_i||auth_0||auth_1||...||auth_{n-1})$

Mottagaren av meddelandet har den offentliga nyckeln , meddelandet och signaturen till sitt förfogande . Den kontrollerar först meddelandets engångssignatur . Om det är äkta, beräknar mottagaren . Och sedan för beräknar . Om det är lika med , anses signaturen vara äkta. $pub$ $M$ $sig=(sig'||X_i||auth_0||auth_1||...||auth_{n-1})$ $sig'$ $M$ $A_0=H(X_i)$ $j=1,...,n-1$ $A_j=H(A_{j-1}||auth_{j-1})$ $En}$ $pub$

Olika optimeringar och implementeringar

Kort hemlig nyckel

Istället för att generera och lagra alla slumptal för den hemliga nyckeln, kan man lagra ett enda nummer av lämplig storlek. Normalt väljs storleken att vara densamma som storleken på ett slumptal i den privata nyckeln. Denna nyckel kan användas som frö till en slumptalsgenerator (CSPRNG) så att hela den hemliga nyckelsekvensen av slumptal kan återskapas när det behövs.

På samma sätt kan en nyckel användas tillsammans med en CSPRNG för att generera flera Lamport-nycklar. Föredragna är CSPRNGs som har hög kryptografisk styrka, såsom BBS .

Kort offentlig nyckel

En Lamport-signatur kan användas tillsammans med en lista med hash, vilket gör det möjligt att endast inkludera en hash i en publik nyckel. Det vill säga istället för värden - . För att kunna jämföra de slumpmässiga talen i signaturen med hashen i den publika nyckeln måste alla hash som inte används i den publika nyckeln, det vill säga värden för någon , inkluderas i signaturen. Som ett resultat blir den publika nyckeln betydligt kortare och signaturstorleken ungefär fördubblas. $2k$ $z_{{ij}}$ $(z_{ij})$ $j\neq m_i$

Meddelandehashning

Lamports digitala signatursystem kräver inte att meddelandet m hashas innan det signeras. Hashing kan till exempel användas för att signera långa meddelanden, där hashen av meddelandet kommer att signeras, och inte själva meddelandet [6] .

Jämförelse med andra kryptosystem

De främsta fördelarna med Lamports engångssignaturschema är att det kan byggas på vilken envägsfunktion som helst och att dess signatur- och meddelandeverifieringsalgoritm är betydligt snabbare än algoritmerna för återanvändbara signatursystem. Samtidigt har systemet ett antal nackdelar. För det första är nackdelen nycklarnas disponibilitet. Det vill säga, när du signerar varje nytt meddelande måste du generera ett nytt par, vilket leder till komplikationen av systemet. För det andra har systemet nackdelen med en stor signaturstorlek och ett par offentliga och privata nycklar [7] .

Detta system har potential i ljuset av att den potentiella utvecklingen av en kvantdator hotar säkerheten för många allmänt använda algoritmer, såsom RSA , medan Lamport-signaturen kommer att förbli säker även i detta fall [8] . Tillsammans med Merkle trees kan Lamports kryptosystem användas för att autentisera flera meddelanden, vilket fungerar som ett ganska effektivt digitalt signaturschema [9] .

Anteckningar

↑ Lamport, 1979 , sid. 2.
↑ Lamport, 1979 , sid. 3-5.
↑ Katz , sid. 2.
↑ M. I. Anokhin, N. P. Varnovsky, V. M. Sidelnikov, V. V. Yashchenko, Lamport och Naor-Jung . Datum för åtkomst: 17 december 2013. Arkiverad från originalet 17 december 2013. (obestämd)
↑ Michael Szydlo, EFFEKTIV ANVÄNDNING AV MERKLE TREES . Hämtad 24 november 2013. Arkiverad från originalet 17 april 2017. (obestämd)
↑ Lamport, 1979 , sid. 6.
↑ Zaverucha, 2010 , sid. ett.
↑ Garcia , sid. tio.
↑ Vadim Malykh, "Långtidslagring av elektroniska dokument" . Datum för åtkomst: 13 december 2013. Arkiverad från originalet 13 december 2013. (obestämd)

Litteratur

Lamport L. Konstruera digitala signaturer från en envägsfunktion . - SRI International Computer Science Laboratory, 1979.
Peikert K. Teoretiska grunder för kryptografi . - Georgia Tech, 2010. Arkiverad19 december 2013 påWayback Machine
Katz J. Introduktion till kryptografi . — University of Maryland.
Zaverucha G. Stinson R. Cheriton R. Korta engångssignaturer . — University of Waterloo, 2010.
Garcia L. Om säkerheten och effektiviteten av Merkles signaturschema . — Darmstadt.

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort