Lamport signatur

Inom kryptografi är en Lamport-signatur eller Lamport-engångssignaturschema en metod för att konstruera en digital signatur . Lamport-signaturer kan byggas från vilken kryptografiskt säker envägsfunktion som helst ; vanligtvis används en kryptografisk hashfunktion .

Även om den potentiella utvecklingen av kvantdatorer hotar säkerheten för många vanliga former av kryptografi såsom RSA , tror man att Lamport-signaturer med stora hashfunktioner fortfarande skulle vara säkra i så fall. Varje Lamport-nyckel kan endast användas för att signera ett enda meddelande. Men i kombination med ett hashträd kan en enda nyckel användas för många meddelanden, vilket gör detta till ett ganska effektivt digitalt signaturschema.

Lamports signaturkryptosystem uppfanns 1979 och uppkallat efter dess uppfinnare, Leslie Lamport .

Exempel

Alice har en 256-bitars kryptografisk hashfunktion och någon form av säker slumptalsgenerator . Hon vill skapa och använda ett Lamport-nyckelpar, det vill säga en privat nyckel och en motsvarande offentlig nyckel.

Gör nyckelparet

För att skapa den privata nyckeln använder Alice slumptalsgeneratorn för att producera 256 par slumptal (totalt 2×256 nummer), varje nummer är 256 bitar stort, det vill säga totalt 2×256×256 bitar = 128 Kibit totalt. Detta är hennes privata nyckel och hon kommer att förvara den på en säker plats för senare användning.

För att skapa den publika nyckeln hashar hon vart och ett av de 512 slumpmässiga siffrorna i den privata nyckeln, vilket skapar 512 hash, var och en med en storlek på 256 bitar. (Också 128 Kbits totalt.) Dessa 512 hashen bildar hennes publika nyckel, som hon kommer att dela med världen.

Undertecknar meddelandet

Senare vill Alice skriva under ett meddelande. Först hashar hon meddelandet till en 256-bitars hashsumma. Sedan, för varje bit i hashen, baserat på värdet på biten, plockar hon ett nummer från motsvarande par av nummer som utgör hennes privata nyckel (dvs. om biten är 0, väljs det första numret, och om biten är 1, den andra är vald). Detta ger en sekvens av 256 nummer. Eftersom varje nummer i sig är 256 bitar långt blir den totala storleken på hennes signatur 256×256 bitar = 65536 bitar = 64 Kibit. Dessa (ursprungligen slumpmässigt utvalda) nummer är hennes signatur och hon publicerar dem tillsammans med meddelandet.

Observera att nu när Alices privata nyckel används ska den aldrig användas igen. Hon måste förstöra de andra 256 numren som hon inte använde för signaturen. Annars minskar varje ytterligare signatur som återanvänder den privata nyckeln säkerhetsnivån mot motståndare som senare kan skapa falska signaturer från dem.

Verifierar signaturen

Sedan vill Bob verifiera Alices signatur av meddelandet. Han hashar också meddelandet för att få en 256-bitars hashsumma. Sedan använder han bitarna i hashsumman för att plocka ut 256 av hasharna i Alices publika nyckel. Han väljer hasharna på samma sätt som Alice valde de slumpmässiga siffrorna för signaturen. Det vill säga, om den första biten i meddelandehashen är en nolla, väljer han den första hashen i det första paret, och så vidare.

Sedan hashar Bob vart och ett av de 256 slumpmässiga siffrorna i Alices signatur. Detta ger honom 256 hash. Om dessa 256 hash exakt matchar de 256 hasharna han just valde från Alices publika nyckel så är signaturen ok. Om inte, är signaturen fel.

Observera att innan Alice publicerar signaturen för meddelandet, känner ingen annan till de 2×256 slumpmässiga siffrorna i den privata nyckeln. Således kan ingen annan skapa den rätta listan med 256 slumpmässiga nummer för signaturen. Och efter att Alice har publicerat signaturen känner andra fortfarande inte till de andra 256 slumptalen och kan därmed inte skapa signaturer som passar andra meddelandehaschar.

Formell beskrivning

Nedan finns en kort beskrivning av hur Lamport-signaturer fungerar, skrivna i matematisk notation . Observera att "meddelandet" i den här beskrivningen är ett block av rimlig storlek med fast storlek, möjligen (men inte nödvändigtvis) hashresultatet av att ett godtyckligt långt meddelande signeras.

Nycklar

Låt $k$ vara ett positivt heltal och låt $P=\{0,1\}^{k}$ vara mängden meddelanden. Låt $f:\,Y\rightarrow Z$ vara en enkelriktad funktion .

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

Den privata nyckeln, $K$ , består av $2k$ värden $y_{i,j}$ . Den publika nyckeln består av de $2k$ värdena $z_{i,j}$ .

Undertecknar ett meddelande

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

Meddelandets signatur är

{\displaystyle \operatorname {sig} (m_{1}\

.

Verifierar en signatur

Verifieraren validerar en signatur genom att kontrollera att $f(s_{i})=z_{i,m_{i}}$ för alla $1\leq i\leq k$ .

För att förfalska ett meddelande måste Eva invertera envägsfunktionen $f$ . Detta antas vara svårlöst för in- och utgångar av lämplig storlek.

Säkerhetsparametrar

Säkerheten för Lamport-signaturer är baserad på säkerheten för envägs-hashfunktionen och längden på dess utdata.

För en hashfunktion som genererar ett n-bitars meddelandesammandrag, innebär den ideala förbilden och 2:a förbildsresistansen på en enda hashfunktionsanrop i storleksordningen 2 ⁿ operationer för att hitta en kollision under en klassisk datormodell. Enligt Grovers algoritm är det övre gränsen för O( ^{2n /2 )-operationer} att hitta en preimage-kollision på en enda anrop av en ideal hashfunktion under en kvantberäkningsmodell. I Lamport-signaturer är varje bit av den publika nyckeln och signaturen baserad på korta meddelanden som endast kräver en enda anrop till en hashfunktion.

För varje privat nyckel y _i,j och dess motsvarande offentliga z _i,j- nyckelpar måste den privata nyckellängden väljas så att utföra en förbildsattack på längden av ingången inte är snabbare än att utföra en förbildsattack på längden av produktion. Till exempel, i ett degenererat fall, om varje privat nyckel y _i,j element endast var 16 bitar långt, är det trivialt att uttömmande söka igenom alla 2 ¹⁶ möjliga privata nyckelkombinationer i 2 ¹⁶ operationer för att hitta en matchning med utdata, oavsett av meddelandesammandragets längd. Därför säkerställer en balanserad systemdesign att båda längderna är ungefär lika.

Baserat på Grovers algoritm, ett kvantsäkrat system, måste längden på de publika nyckelelementen z _i,j , de privata nyckelelementen y _i,j och signaturelementen si _,j vara minst 2 gånger större än säkerhetsklassificeringen av systemet. Det är:

Ett 80-bitars säkert system använder elementlängder på inte mindre än 160 bitar;
Ett 128-bitars säkert system använder elementlängder på inte mindre än 256 bitar;

Försiktighet bör dock iakttas eftersom de idealistiska arbetsuppskattningarna ovan antar en idealisk (perfekt) hashfunktion och är begränsade till attacker som bara är inriktade på en enda förbild åt gången. ^{Det / 5} är känt under en konventionell datormodell att om 23n ^{/ / 5} förbilder söks, minskar den fulla kostnaden per förbild från 2n ^{2 till} 22n . Att välja den optimala elementstorleken med hänsyn till samlingen av flera meddelandesammandrag är ett öppet problem. Val av större elementstorlekar och starkare hashfunktioner, såsom 512-bitars element och SHA-512, säkerställer större säkerhetsmarginaler för att hantera dessa okända saker.

Optimering och varianter

Kort privat nyckel

Istället för att skapa och lagra alla slumpmässiga nummer för den privata nyckeln, kan en enda nyckel av tillräcklig storlek lagras. (Vanligtvis samma storlek som ett av slumptalen i den privata nyckeln.) Den enskilda nyckeln kan sedan användas som frö till en kryptografiskt säker pseudoslumptalsgenerator (CSPRNG) för att skapa alla slumptal i den privata nyckeln vid behov. Notera att en kryptografiskt säker hash (eller åtminstone vars utdata inte är XORed med fröet) inte kan användas istället för CSPRNG eftersom signering av ett meddelande skulle avslöja ytterligare slumpmässiga värden från den privata nyckeln. Om motståndaren kan komma åt signaturen innan de avsedda mottagarna kan, då kan han förfalska en signatur med en halvering av säkerhetsnivån för varje dubblering av de avslöjade slumpmässiga värdena från den privata nyckeln.

På samma sätt kan en enda nyckel användas tillsammans med en CSPRNG för att skapa många Lamport-nycklar. Helst bör då någon form av slumpmässig åtkomst CSPRNG användas, såsom BBS .

Kort offentlig nyckel

En Lamport-signatur kan kombineras med en hash-lista , vilket gör det möjligt att endast publicera den enstaka topphashen istället för alla hasharna i den publika nyckeln. Det vill säga istället för de $2k$ värdena $z_{ij}$ . För att verifiera mot den enda översta hashen måste signaturen inkludera de slumpmässiga siffrorna och de oanvända hashen från hashlistan för den publika nyckeln, vilket resulterar i signaturer som är ungefär dubbelt så stora. Det vill säga att värdena $(z_{ij})$ för alla $j\neq m_{i}$ måste inkluderas.

De oanvända hasharna behöver inte inkluderas i signaturen om en kryptografisk ackumulator används istället för en hashlista.

Korta nycklar och signatur

Winternitz signaturkomprimering minskar storleken på den privata nyckeln och den offentliga nyckeln med något mindre än en faktor av ${\displaystyle 2\langle {\text{chunk size in bits}}\rangle } ,$ och hälften den faktorn för signaturen. Beräkningen ökar med något mer än en faktor $2^{\langle {\text{chunk size i bitar}}\rangle }/\langle {\ text{klumpstorlek i bitar}}\rangle$ . En kryptografiskt säker hash räcker istället för kravet på en CSPRNG.

En hash-lista skulle också kunna användas för att förkorta den publika nyckeln till ett enda värde på bekostnad av att fördubbla storleken på signaturen, såsom förklarats i föregående avsnitt.

Offentlig nyckel för flera meddelanden

Varje offentlig nyckel från Lamport kan endast användas för att signera ett enda meddelande, vilket innebär att många nycklar måste publiceras om många meddelanden ska signeras. Men ett hashträd kan användas på dessa publika nycklar, och publicerar hashträdets översta hash istället. Detta ökar storleken på den resulterande signaturen, eftersom delar av hashträdet måste inkluderas i signaturen, men det gör det möjligt att publicera en enda hash som sedan kan användas för att verifiera valfritt antal framtida signaturer.

Se även

S/KEY

Vidare läsning

L. Lamport , Konstruera digitala signaturer från en envägsfunktion , Teknisk rapport SRI-CSL-98, SRI International Computer Science Laboratory, okt. 1979.
Effektiv användning av Merkle-träd - RSA-laboratoriets förklaring av det ursprungliga syftet med Merkle-träd + Lamport-signaturer, som ett effektivt engångssignaturschema.
En introduktion till hash-baserade signaturer och Merkle-signaturer av Adam Langley.
Referensimplementering av Lamport-schema ovanpå BLAKE2b (C++)
Referensimplementering av Lamport-signaturer ovanpå SHA256, SHA512 eller Blake2b (Rust)