Semnătura lui Lampport

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 31 decembrie 2014; verificările necesită 16 modificări .

Semnătura Lamport este un criptosistem de semnătură digitală cu o cheie publică. Poate fi construit pe orice funcție unidirecțională . A fost propus în 1979 și numit după autorul său, un om de știință american, Leslie Lamport [1] .

Descriere

Să fie Alice să aibă o funcție hash criptografică de 256 de biți și un generator de numere pseudoaleatoare puternic criptografic . Ea dorește să creeze și să utilizeze perechea de chei a lui Lamport, o cheie privată și cheia publică corespunzătoare .

Crearea unei perechi de chei

Pentru a genera o cheie secretă, Alice folosește un generator de numere aleatorii pentru a genera 256 de perechi de numere aleatorii (2x256 de numere în total). Fiecare număr este format din 256 de biți, deci dimensiunea totală este de 2x256x256 biți = 16 KiB . Aceste numere vor fi cheia secretă a lui Alice, iar ea le va păstra într-un loc secret pentru utilizare ulterioară.

Pentru a crea cheia publică, Alice hashează fiecare dintre cele 512 numere de cheie privată, făcând astfel 512 hashe-uri de 256 de biți fiecare. Aceste 512 hasheuri formează cheia publică a lui Alice, pe care o publică.

Semnătura mesajului

Acum Alice vrea să semneze mesajul. Mai întâi, trimite mesajul și primește un hash de 256 de biți. Apoi, pentru fiecare bit din acel hash, ia numărul corespunzător din cheia secretă. Dacă, de exemplu, primul bit din hash-ul mesajului este zero, acesta ia primul număr din prima pereche de chei secrete. Dacă primul bit este egal cu unu, se folosește al doilea număr din prima pereche. Si asa mai departe. Ca rezultat, se obțin 256 de numere aleatoare, a căror dimensiune este de 256 × 256 biți = 8 KiB. Aceste numere formează semnătura pe care Alice o trimite împreună cu mesajul.

Rețineți că, odată ce Alice și-a folosit cheia privată, aceasta nu trebuie să fie folosită din nou. Cele 256 de numere rămase, pe care nu le-a folosit în semnătură, Alice nu trebuie să le publice sau să le folosească niciodată. Este de preferat ca ea să le ștergă, altfel cineva le poate accesa și genera o semnătură falsă cu ele.

Verificarea semnăturii

Bob vrea să verifice semnătura cu care Alice a semnat mesajul. De asemenea, trimite mesajul și primește un hash de 256 de biți. Apoi, pentru fiecare bit din acel hash, el alege un număr din cheia publică a lui Alice. Aceste numere sunt alese în același mod în care Alice a ales numerele pentru semnătură. Adică, dacă primul bit al mesajului hash este zero, Bob alege primul număr din prima pereche din cheia publică. Si asa mai departe.

Bob apoi șterge fiecare dintre cele 256 de numere din semnătura lui Alice și primește 256 de hashe-uri. Dacă aceste 256 de hasheuri se potrivesc exact cu cele 256 de hashe-uri pe care tocmai le-a primit de la cheia publică a lui Alice, Bob crede că semnătura este autentică. Dacă nu se potrivesc, atunci este fals.

Este de remarcat faptul că înainte ca Alice să publice semnătura mesajului, nimeni nu știe 2x256 numere aleatorii din cheia secretă. Astfel, nimeni nu poate crea setul corect de 256 de numere de semnat. După ce Alice publică semnătura, nimeni nu mai știe celelalte 256 de numere și, prin urmare, nu poate crea o semnătură pentru mesajele care au un hash diferit [2] .

Exemplu

Lăsați -l pe Alice să trimită un mesaj M = „Lamport” lui Bob, semnându-l cu semnătura lui Lamport și folosind o funcție hash pe 8 biți. Adică, mesajul original va fi convertit într-un hash de 8 biți.

Generare cheie

Folosind un generator de numere aleatoare, Alice obține opt perechi de numere aleatorii. Aceste 16 numere sunt cheia privată a lui Alice.

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

Pentru a obține cheia publică, Alice calculează o valoare hash pentru fiecare număr din cheia privată.

Cheie publică:

$(00101010,$ $10010101)$

$(01100111,$ $11010101)$

$(00101110,$ $11110111)$

$(00100101,$ $11011101)$

$(11100001,$ $00011000)$

$(11000110,$ $11001110)$

$(11001101,$ $11001001)$

$(11100011,$ $11111101)$

Alice publică cheia publică rezultată.

Semnătura mesajului

Alice vrea să semneze mesajul M = „Lamport”. Pentru a face acest lucru, calculează valoarea hash a acestui mesaj și asociază fiecare bit al hash-ului cu una dintre valorile din perechile de chei private, formând astfel o semnătură. $H(M)=01011010$

Semnătura mesajului „Lamport”: $(13,$ $67,$ $25,$ $156,$ $37,$ $234,$ $74,$ $12)$

Verificarea semnăturii

Bob primește un mesaj semnat „Lamport” și vrea să verifice dacă Alice l-a trimis cu adevărat. Pentru a face acest lucru, el folosește cheia publică pe care Alice a publicat-o. Acesta convertește mesajul primit într-un hash și mapează fiecare bit din hashul rezultat la un număr dintr-o pereche din cheia publică. Apoi indexează semnătura mesajului și compară cele două seturi de numere rezultate. Dacă sunt egale, atunci semnătura este reală, iar mesajele au fost într-adevăr trimise de Alice.

Un set de numere obținute din cheia publică:

$00101010,$

$11010101,$

$00101110,$

$11011101,$

$00011000,$

$11000110,$

$11001001,$

$11100011$

Hash de semnătură:

$00101010,$

$11010101,$

$00101110,$

$11011101,$

$00011000,$

$11000110,$

$11001001,$

$11100011$

Deoarece aceste seturi sunt egale, semnătura este reală.

Descriere matematică

Chei

Fie un număr pozitiv, fie un set de mesaje și fie o funcție unidirecțională . $k$ $P=\{0,1\}^k$ $f:\,Y\săgeata la dreapta Z$

Pentru fiecare și , partea care semnează mesajul alege și calculează aleatoriu . $1\leq i\leq k$ $j\in\{0,1\}$ $y_{i,j}\în Y$ $z_{i,j}=f(y_{i,j})$

Cheia secretă constă din . Cheia publică este formată din valori . [3] $K$ $2k$ $y_{i,j}$ $2k$ $z_{i,j}$

Semnătura mesajului

Să fie un mesaj. $m = m_1\ldots m_k \in\{0,1\}^k$

Semnătura mesajului este . $semn(m_1\ldots m_k)=(y_{1,m_1},\ldots, y_{k,m_k})=(s_1,\ldots,s_k)$

Verificarea semnăturii

Partea care validează semnătura verifică pentru toți . $f(s_i) = z_{i,m_i}$ $1\leq i\leq k$

Pentru a falsifica o semnătură de mesaj, criptoanalistul ar trebui să inverseze funcția unidirecțională , care se presupune că este imposibil din punct de vedere computațional. $f$

Securitate

Puterea criptografică a semnăturilor Lamport se bazează pe puterea criptografică a funcției hash .

Pentru fiecare funcție hash care generează un digest de n biți, rezistența ideală la recuperarea preimagine și la recuperarea a doua preimagine implică 2 n operații și 2 n biți de memorie în modelul de calcul clasic pentru fiecare execuție a funcției hash . Folosind algoritmul lui Grover , recuperarea pre-imagine a unei funcții hash ideale este delimitată mai sus de operații O(2 n /2 ) într-un model de calcul cuantic [4] .

Semnături multiple pentru mesaje

Un singur mesaj poate fi semnat cu o cheie privată Lamport. Aceasta înseamnă că dacă un anumit număr de mesaje sunt semnate, trebuie publicat același număr de chei publice. Dar, dacă utilizați un arbore Merkle compus din chei publice, atunci în loc să publicați toate cheile publice, puteți publica doar partea de sus a arborelui. Acest lucru mărește dimensiunea semnăturii, deoarece o parte din arborele hash trebuie inclusă în semnătură, dar face posibilă utilizarea unui singur hash pentru a verifica mai multe semnături. Conform acestei scheme, puteți semna mesaje, unde este adâncimea arborelui Merkle. Adică, teoretic, putem folosi o cheie publică pentru orice număr de mesaje [5] . $N=2^n$ $n$

Generare cheie

Mai întâi trebuie să generați cheile unice private ale Lamport și cheile unice publice ale Lamport . În plus, pentru fiecare cheie publică , unde , se calculează hash-ul său . Și pe baza acestor valori se construiește un arbore Merkle . $2^{n}$ $X_{i}$ $Y_{i}$ $Y_{i}$ $1 \leq i \leq 2^n$ $h_{i}=H(Y_{i})$ $Bună}$

Numerotăm nodurile arborelui în așa fel încât indicele să desemneze distanța de la acest nod la elementul frunză, iar indicele să desemneze numărul ordinal al nodului de la stânga la dreapta la același nivel . $a_{i,j}$ $i$ $j$ $i$

În arborele nostru, valorile hash sunt elemente frunze, adică . Fiecare nod care nu este frunză al arborelui este o valoare hash de la unirea a doi copii împreună, adică , și așa mai departe. $Bună}$ $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})$

Astfel, avem un arbore al cărui element rădăcină este cheia noastră publică . $cârciumă$

Semnarea și validarea mesajelor

Pentru a semna un mesaj conform schemei noastre, mai întâi trebuie să-l semnați cu o semnătură Lamport unică . Acest lucru se face folosind una dintre perechile de chei publice/private . $semn'$ $(X_i, Y_i,)$

$a_{0,i}=H(X_i)$ este elementul frunză al arborelui corespunzător cheii publice . Calea de la elementul frunză al copacului până la vârful acestuia constă din elementele , unde este elementul frunză și este vârful copacului. Pentru a calcula această cale, avem nevoie de toți copiii nodurilor . Știm că nodul este un copil al nodului . Pentru a calcula următorul nod pe calea către vârf, avem nevoie de ambii copii ai nodului . Prin urmare, trebuie să cunoaștem „fratele” nodului . Să-l sunăm . Deci, . Prin urmare, avem nevoie de noduri pentru a calcula partea de sus a arborelui. Le calculăm și le salvăm. $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}$

Aceste noduri, împreună cu semnătura unică a mesajului, constituie semnătura finală . $semn'$ $M$ $sig=(sig'||X_i||auth_0||auth_1||...||auth_{n-1})$

Destinatarul mesajului are la dispoziție cheia publică , mesajul și semnătura . Mai întâi verifică semnătura unică a mesajului . Dacă este autentic, destinatarul calculează . Și apoi pentru calcule . Dacă este egală cu , atunci semnătura este considerată autentică. $cârciumă$ $M$ $sig=(sig'||X_i||auth_0||auth_1||...||auth_{n-1})$ $semn'$ $M$ $A_0=H(X_i)$ $j=1,...,n-1$ $A_j=H(A_{j-1}||auth_{j-1})$ $Un}$ $cârciumă$

Diverse optimizări și implementări

Cheie secretă scurtă

În loc de a genera și stoca toate numerele aleatorii ale cheii secrete, se poate stoca un singur număr de dimensiunea corespunzătoare. De obicei, dimensiunea este aleasă să fie aceeași cu dimensiunea unui număr aleatoriu din cheia privată. Această cheie poate fi folosită ca sămânță pentru un generator de numere aleatoare (CSPRNG), astfel încât întreaga secvență de chei secrete de numere aleatoare să poată fi recreată atunci când este necesar.

În același mod, o cheie poate fi utilizată împreună cu un CSPRNG pentru a genera mai multe chei Lamport. Sunt preferate CSPRNG-urile care au o putere criptografică ridicată, cum ar fi BBS .

Cheie publică scurtă

O semnătură Lamport poate fi utilizată împreună cu o listă de hashuri, făcând posibilă includerea unui singur hash într-o cheie publică. Adică, în loc de valori - . Pentru a putea compara numerele aleatorii din semnătură cu hash-ul din cheia publică, toate hashurile neutilizate în cheia publică, adică valorile pentru oricare , trebuie incluse în semnătură. Ca rezultat, cheia publică devine semnificativ mai scurtă, iar dimensiunea semnăturii se dublează aproximativ. $2k$ $z_{{ij}}$ $(z_{ij})$ $j\neq m_i$

Mesaj hashing

Schema de semnătură digitală Lamport nu necesită ca mesajul m să fie hashing înainte de a fi semnat. Hashingul poate fi folosit, de exemplu, pentru a semna mesaje lungi, unde hash-ul mesajului va fi semnat, și nu mesajul în sine [6] .

Comparație cu alte criptosisteme

Principalele avantaje ale schemei de semnătură unică a Lamport sunt că poate fi construită pe orice funcție unidirecțională și că algoritmul său de verificare a semnăturii și a mesajelor este semnificativ mai rapid decât algoritmii sistemelor de semnătură reutilizabile. În același timp, schema are o serie de dezavantaje. În primul rând, dezavantajul este posibilitatea de unică folosință a cheilor. Adică, la semnarea fiecărui mesaj nou, trebuie să generați o nouă pereche, ceea ce duce la complicarea sistemului. În al doilea rând, schema are dezavantajul unei dimensiuni mari a semnăturii și a unei perechi de chei publice și private [7] .

Acest sistem are potențial în lumina faptului că dezvoltarea potențială a unui computer cuantic amenință securitatea multor algoritmi utilizați pe scară largă, precum RSA , în timp ce semnătura Lamport va rămâne sigură și în acest caz [8] . Împreună cu arborii Merkle , criptosistemul Lamport poate fi folosit pentru autentificarea mai multor mesaje, acționând ca o schemă de semnătură digitală destul de eficientă [9] .

Note

↑ Lampport, 1979 , p. 2.
↑ Lampport, 1979 , p. 3-5.
↑ Katz , p. 2.
↑ M. I. Anokhin, N. P. Varnovsky, V. M. Sidelnikov, V. V. Yashchenko, Scheme Lamport și Naor-Jung . Data accesului: 17 decembrie 2013. Arhivat din original la 17 decembrie 2013. (nedefinit)
↑ Michael Szydlo, UTILIZARE EFICIENTĂ A ARBOCILOR MERKLE . Consultat la 24 noiembrie 2013. Arhivat din original la 17 aprilie 2017. (nedefinit)
↑ Lampport, 1979 , p. 6.
↑ Zaverucha, 2010 , p. unu.
↑ Garcia , p. zece.
↑ Vadim Malykh, „Depozitarea pe termen lung a documentelor electronice” . Data accesului: 13 decembrie 2013. Arhivat din original pe 13 decembrie 2013. (nedefinit)

Literatură

Lampport L. Construirea semnăturilor digitale dintr-o funcție unidirecțională . - SRI International Computer Science Laboratory, 1979.
Peikert K. Fundamentele teoretice ale criptografiei . - Georgia Tech, 2010. Arhivat19 decembrie 2013 laWayback Machine
Katz J. Introducere în Criptografie . — Universitatea din Maryland.
Zaverucha G. Stinson R. Cheriton R. Semnături scurte unice . — Universitatea din Waterloo, 2010.
Garcia L. Despre securitatea și eficiența schemei de semnătură Merkle . — Darmstadt.

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP