ESIGN

ESIGN ( în engleză Efficient digital SIGNature - semnătură digitală efectivă) este o schemă de semnătură digitală cu cheie publică bazată pe problema factorizării numerelor . O caracteristică distinctivă a acestei scheme este capacitatea de a genera rapid o semnătură. [unu]

Istorie

Semnătura digitală a fost dezvoltată de compania japoneză NTT în 1985. [2] Schema sa dovedit a fi eficientă în ceea ce privește viteza de generare a semnăturii digitale. Cu toate acestea, primele versiuni au fost sparte de Ernie Btickel și John DeLaurentis , după care parametrii algoritmului recomandați au fost modificați . [3] Încercările ulterioare de hacking nu au avut succes. Autorii susțin că complexitatea spargerii celei mai recente versiuni de ESIGN este comparabilă cu complexitatea problemei de factorizare pentru un număr de formă , unde și sunt numere prime . [patru] $n$ $p^{2}q$ $p$ $q$

Descrierea protocolului

Introducere

Există două entități implicate în protocol: entitatea , al cărei scop este de a dovedi că autorul mesajului este , și subiectul , al cărui scop este să verifice calitatea de autor. În ESIGN pentru implementarea obiectivelor stabilite și trebuie să efectueze următoarele acțiuni [5] . $A$ $m$ $B$ $A$ $B$

Anterior, generează chei : publice, cunoscute de toată lumea și private , cunoscute doar de subiect . $A$ $A$
Subiectul generează o semnătură digitală pentru mesaj pe baza cheii private. $A$ $s$ $m$
$A$ trimite subiectului un mesaj împreună cu o semnătură . $m$ $s$ $b$
Subiectul validează semnătura pe baza cheii publice. $B$

Generarea de chei publice și private

Cheile ESIGN sunt generate după cum urmează [6] .

Două numere prime de aceeași lungime de biți sunt selectate aleatoriu. $p$ $q$
Se calculează numărul . $n=p^{2}q$
Se alege un număr întreg pozitiv . $k\geqslant 4$
Perechea de numere este cheia publică. $(n,k)$
O pereche de numere este o cheie privată. $(p,q)$

Generarea semnăturii

Pentru a semna un mesaj , unde este un număr binar de lungime arbitrară, se fac următorii pași [6] . $m$ $m$

, unde este o funcție hash preselectată , care ia valori de la până la . $\mu=h(m)$ $h$ $0$ $n-1$
Un număr aleatoriu este selectat din interval . $X$ $[0,pq)$
Și se calculează , unde este funcția de rotunjire la cel mai mic număr întreg, argumentul mai mare. $\chi =\left\lceil {\frac {\mu -(x^{k}{\bmod {n})}}{pq))\right\rceil$ $\varkappa =\left({\frac {\chi {k*x^{k-1}}}\right){\bmod {p}}$ $\lceil \cdot \rceil \colon \mathbb {R} \to \mathbb {Z}$
Semnătura este calculată . $s=x+\varkappa pq$

Verificarea semnăturii

Pentru a verifica dacă semnătura semnează într-adevăr mesajul , se parcurg următorii pași [6] . $s$ $m$

, unde este aceeași funcție hash care a fost folosită pentru a genera semnătura. $\mu=h(m)$ $h$
Calculat . $\xi =\left\lceil {\frac {2}{3}}\log _{2}{n}\right\rceil$
Se efectuează un test de inegalitate . $\mu \leqslant s^{k}{\bmod {n}}\leqslant \mu +2^{\xi }$
Semnătura este considerată validă dacă inegalitatea este satisfăcută.

Versiunile anterioare

În versiunea propusă inițial de ESIGN, parametrul era egal cu doi. [5] Cu toate acestea, după atacul de succes al lui Ernie Brickell și John DeLaurentis, care s-a extins și la varianta de circuit cu , autorii au schimbat cerința pentru acest parametru la cea existentă . [7] $k$ $k = 3$ $k\geqslant 4$

Criptanaliză

Atacul asupra funcției hash

Atacurile asupra unei funcții hash cu scopul de a falsifica o semnătură se bazează pe imperfecțiunea acesteia, adică pe nepotrivirea funcției hash cu unul sau mai multe criterii de putere criptografică, cu condiția ca, în cazul ESIGN, egalitatea în criterii. ar trebui înțeles până la cele mai semnificative biți. Această relaxare se datorează condiției de verificare a semnăturii, care este satisfăcută nu numai pentru valoarea hash inițială, ci și pentru altele care se potrivesc în primii biți înalți. $h$ $(\log _{2}{n})/3$ $(\log _{2}{n})/3$

Să presupunem că funcția este instabilă la căutarea coliziunilor, adică puteți găsi astfel de diferite și că și potriviți în primii biți înalți. Apoi, semnând mesajul , autorul , nebănuind nimic, semnează automat mesajul , deoarece inegalitatea $h$ $m$ $m'$ $h(m)$ $h(m')$ $(\log _{2}{n})/3$ $m$ $A$ $m'$ $h(m')\leqslant s^{k}{\bmod {n}}\leqslant h(m')+2^{\left\lceil {\frac {2}{3}}\log _ {2}{n}\right\rceil}$

Dacă funcția de hash aleasă este sigură criptografic, atunci atacul de coliziune va lua operațiunile de calcul al funcției de hash, atacul care utilizează cea de-a doua preimagine va lua operațiuni, ceea ce este considerat nerealizabil, pentru mari . [8] [9] $2^{(\log _{2}{n})/3}$ $2^{(\log _{2}{n})/6}$ $n$

Atacul cu cheia publică

Un atac asupra unei chei publice este o încercare de a obține o cheie privată din aceasta . Acest lucru se poate face prin rezolvarea ecuației , adică prin factorizarea numărului . Puteți vedea că în RSA un număr este generat într-un mod similar, acolo , dar astăzi întrebarea în care dintre cazuri factorizarea devine mai simplă sau mai dificilă rămâne deschisă, deoarece încă nu există algoritmi de factorizare eficienți. În prezent, cea mai rapidă modalitate de a factoriza un număr , fie pentru ESIGN, fie pentru RSA, este metoda sită a câmpului numeric , care face acest lucru la o rată dependentă de lungimea biților . Cu toate acestea, cu o lungime mare de biți a numărului , sarcina de factorizare devine imposibilă. [10] [9] $(n,k)$ $(p,q)$ $n=p^{2}q$ $n$ $n$ $n=pq$ $n$ $n$ $n$

Setări recomandate

Pe lângă restricțiile deja introduse în descrierea ESIGN, pentru o mai mare securitate, se recomandă să alegeți dimensiunea și egală sau mai mare decât biții, dimensiunea egală sau mai mare , respectiv, și parametrul mai mare sau egal cu 8 [ 11] : $p$ $q$ $320$ $n$ $960$ $k$

$\log _{2}{p}\geqslant 320$ ;
$k\geqslant 8$ ;

Nivelul de securitate față de alte scheme de semnătură digitală

Mai jos este un tabel de corespondență între nivelul de securitate ESIGN și nivelurile de securitate RSA și ECDSA pentru diferite dimensiuni de parametri în biți. Puteți vedea că, cu aceleași dimensiuni , RSA și ESIGN sunt comparabile în ceea ce privește securitatea. [12] $n$ $n$

Dimensiune în ESIGN, biți $n$	Dimensiune în RSA, biți $n$	Dimensiune în ECDSA, biți $n$
960	960	152
1024	1024	160
2048	2048	224
3072	3072	256
7680	7680	384

Beneficii

Schema ESIGN vă permite să generați rapid o semnătură. Deoarece operațiunile complexe din punct de vedere computațional, cum ar fi exponențiarea și găsirea elementului invers , nu depind de mesajul care este semnat , ele pot fi efectuate în avans și stocate în memorie. Astfel, pentru a semna un mesaj, este suficient să efectuați operațiunile rămase de adunare, înmulțire și împărțire, a căror pondere în complexitatea de calcul a algoritmului de creare a semnăturii este mică. În cazul în care , iar lungimea biților este egală cu , viteza de generare a semnăturii în este mai mare decât pentru RSA cu parametrii corespunzători. În ceea ce privește verificarea semnăturii, viteza acesteia este comparabilă cu viteza verificării semnăturii din algoritmul RSA , al cărui exponent deschis este mic. [13] [9] $(x^{k}{\bmod {n)))$ $(k*x^{k-1})^{-1)$ $m$ $k = 4$ $n$ $768$ $10\div 100$

Protocoale de autentificare bazate pe ESIGN

Cu ajutorul ESIGN, puteți implementa protocoale de identificare cu cunoștințe zero care permit subiectului ( English Prover - proving) să-i demonstreze subiectului ( English Verifier - verificare) faptul prezenței informațiilor, păstrând secretul de . Protocoalele de identificare bazate pe ESIGN sunt la fel de eficiente ca protocolul Feig-Fiat-Shamir . Vom lua în considerare două astfel de protocoale: trei runde și două runde. [paisprezece] $P$ $V$ $V$

Schema de identificare în trei runde

$P$ generează chei ESIGN publice și private . $(n,k)$ $(p,q)$
$P$ selectează aleatoriu numerele și , calculează , unde este o funcție unidirecțională , este operația de concatenare și trimite la verificator . $r$ $u$ $x=f(r\|u)$ $f$ $\|$ $X$ $V$
$V$ alege aleatoriu un număr și îl trimite probatorului. $y$
$P$ calculează , generează o semnătură pentru , și trimite un triplu verificatorului. $m=r\oplus y$ $s$ $m$ $(s,r,u)$
$V$ verifică dacă semnătura mesajului este egală și validă . $x=f(r\|u)$ $s$ $m$

Schema de identificare în două runde

$P$ generează chei ESIGN publice și private . $(n,k)$ $(p,q)$
$V$ alege aleatoriu un număr și îl trimite probatorului. $r$
$P$ alege aleatoriu un număr , calculează , generează o semnătură pentru și o trimite verificatorului. $u$ $m=f(r\|u)$ $s$ $m$ $(s,u)$
$V$ verifică dacă semnătura mesajului este egală și validă . $m=f(r\|u)$ $s$ $m$

În protocoalele de mai sus, informațiile secrete sunt cheile , a căror cunoaștere dovedește subiectul . Dacă rezultatele tuturor verificărilor din etapele finale au succes, atunci se consideră că el are cu adevărat un secret. $(p,q)$ $P$ $P$

Note

↑ Menezes, Oorschot, Vanstone, 1996 , §11.7 p.2, pp. 473-474.
↑ Minghua, 2001 , p. unu.
↑ Schneier, 2002 , capitolul 20, p.6.
↑ Atsushi, 1991 , capitolul 2, paragraful 3: „Conjectăm că a sparge versiunea noastră de grad superior (ESIGN) este la fel de greu ca factorizarea N”.
↑ 1 2 Schneier, 2002 , capitolul 2, p.6.
↑ 1 2 3 Menezes, Oorschot, Vanstone, 1996 , §11.7 p.2, p. 473.
↑ Menezes, Oorschot, Vanstone, 1996 , §11.9, pp. 486-487.
↑ Minghua, 2001 , p. 3.
↑ 1 2 3 Menezes, Oorschot, Vanstone, 1996 , §11.7 p.2, p. 474.
↑ Minghua, 2001 , p. patru.
↑ Minghua, 2001 , p. 6.
↑ Minghua, 2001 , p. 7.
↑ Atsushi, 1991 , capitolul 3.
↑ Atsushi, 1991 , capitolul 4.

Literatură

Schneier B. Criptografia aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .
Alfred J. Menezes, Paul C. van Oorschot și Scott A. Vanstone. Capitolul 11. Semnături digitale // Manual de criptografie aplicată . - a 5-a ed. - CRC Press , 1996. - S. 473-474. — 816 p. - ISBN 0-8493-8523-7 .
Atsushi Fujioka, Tatsuaki Okamoto, Shoji Miyaguchi. ESIGN: O implementare eficientă a semnăturii digitale pentru carduri inteligente // Progrese în criptologie - EUROCRYPT '91 : Proceedings of Conf. / Advances in Cryptology - EUROCRYPT '91, Brighton, Marea Britanie, 8-11 aprilie 1991. - Springer Berlin Heidelberg, 1991. - P. 446-457 . — ISBN 978-3-540-54620-7 . (link indisponibil)
Alfred Menezes, Minghua Qu, Doug Stinson, Yongge Wang Evaluarea nivelului de securitate al criptografiei: Schema de semnătură ESIGN : materiale de proiect / Proiect CRYPREC, Japonia. - 2001. - ianuarie. Arhivat din original pe 9 august 2017.