Semnătură digitală rapidă

Semnătura digitală rapidă este o variantă de semnătură digitală care utilizează un algoritm cu un număr mult mai mic (de zeci de ori) de calcule aritmetice modulare în comparație cu schemele EDS tradiționale . Schema rapidă de semnătură electronică , ca cea obișnuită, include un algoritm pentru generarea perechilor de chei utilizator , o funcție de calcul a semnăturii și o funcție de verificare a semnăturii.

Probleme EDS

De la inventarea EDS în 1976, acesta a fost cel mai promițător domeniu de cercetare în criptosistemele cu cheie publică . Una dintre soluțiile matematice standard pentru construirea algoritmilor criptografici este problema logaritmului discret , pe baza căreia au fost dezvoltați mulți algoritmi pentru obținerea semnăturilor digitale . Principalul dezavantaj al algoritmilor EDS tradiționali , cum ar fi schema ElGamal și RSA , este complexitatea lor de calcul. Calcularea exponențialelor în aritmetică modulară este cea mai intensivă din punct de vedere computațional în schemele criptosistemelor cu cheie publică . În prezent, se lucrează mult pentru a îmbunătăți performanța algoritmilor criptografici prin reducerea numărului de calcule ale exponenților. Cea mai scurtă schemă EDS cunoscută este BLS (Boneh–Lynn–Shacham) care utilizează curbe eliptice , dar este limitată la grupuri care au o funcție de împerechere . Dezvoltatorii de algoritmi lucrează atât pentru a îmbunătăți schemele tradiționale de logaritmi discrete prin utilizarea calculului paralel al exponenților, cât și pentru a explora abordări fundamental diferite bazate, de exemplu, pe teoria grafurilor în loc de aritmetica modulară .

Unii algoritmi rapidi de semnătură digitală

Schema EDS rapidă bazată pe algoritmul Diffie-Hellman

Fie un grup abelian , fie subgrupul său ciclic cu generator de ordine , unde este un număr prim mare . Fie și să fie parametrii de securitate, și . Fie și fie funcții hash . Schema de semnătură este următoarea: $\G$ $\G_{g,q}$ $\g$ $\ q$ $\ q$ $\ l_q$ $\ l_p$ $\ l_q = |q|$ $H: { \{0, 1\}^* } \rightarrow\ G_{g,q}$ $L: { \{ 0, 1 \}^*}\rightarrow\ Z_q^*$ $G: { \{0, 1 \}^*}\rightarrow\ Z_q^*$

Generarea cheilor

Utilizatorul alege o cheie secretă aleatorie și calculează cheia publică . $x \in\ Z_q^*$ $y = g^x$

Creați o semnătură

Intrările sunt o cheie secretă și un mesaj . $x \in\ Z_q^*$ $m \in \{ 0, 1 \}^*$

În continuare, partea care creează semnătura:

1. selectează un număr aleator și un bit aleatoriu ; $k \in \Z_q^*$ $b_m \in \{ 0, 1 \}$

2. calculează ; $\h=H(m,b_m)$

3. calculează ; $\ u = h^x$

4. calculează , unde ; $\ v = ( g^n*h)^k$ $\ n = L(m, g, h, y, u)$

5. calculează ; $\r = G(m, g, h, y, u, v)$

6. calculează . $s = k - xr\mod\q$

Semnătura mesajului este . $\m$ $\sigma\ = (u,r,s,b_m)$

Verificarea semnăturii

Pentru a verifica semnătura mesajului m, procedați în felul următor: $\ \sigma$

1. reprezentat ca ; $\ \sigma$ $\ (u,r,s,b_m)$

2. si se calculeaza ; $\h = H(m,b_m)$ $\ n = L(m,g,h,y,u)$

3. calculat ; $v \prime \ = (g^n*h)^s* (y^n*u)^r$

4. se verifică dacă . $\ r = G(m,g,h,y,u,v\prim)$

Dacă egalitatea din pasul 4 este adevărată, semnătura trece verificarea.

Schema EDS rapidă bazată pe algoritmul Fiat-Shamir

ZN denotă inelul de numere întregi modulo și sunt parametrii de securitate , de obicei , $\N$ $\t$ $\p$ $\t \leqslant\ 4$ $\p \leqslant\ 20$

Rolul Centrului de autentificare cheie (KAC)

CAC alege:

numere prime aleatoare și astfel încât ; $\p$ $\ q$ $\p,q \geqslant\ 2^{256}$

funcția hash unidirecțională ; $\ h: Z_N\otimes Z \rightarrow\ {\{0,1\))^tk$

propriile lor chei publice și private.

CAC publică și cheia publică . $\ N=p*q$ $\h$

Cheia privată a CAC este folosită pentru a semna cheile publice pe care le generează . Pentru a crea astfel de semnături, CAC poate utiliza orice schemă EDS securizată .

Generarea cheilor utilizatorului.

Fiecare utilizator alege o cheie secretă constând din numere aleatorii , variind de la 1 la , astfel încât GCD pentru toți de la 1 la . Crearea semnăturii poate fi accelerată prin alegerea numerelor întregi mici ca . Securitatea unei astfel de scheme se bazează pe presupunerea că calcularea rădăcinilor este dificilă. În prezent, nu se știe despre existența algoritmilor care calculează rădăcinile , cu condiția ca aceste rădăcini să fie de ordin . $\s = (s_1,\cdots\,s_k)$ $\ s_i$ $\ s_i$ $\N$ $\(si,N)= 1$ $\s$ $\ k$ $\s_1,\cdots\,s_k$ $2^t \mod\ N$ $2^t \mod\ N$ $\N^{2^{-t+1}}$

Înregistrare utilizator.

CAC verifică dacă utilizatorul se potrivește, generează un șir care conține numele, adresa etc. și generează o semnătură pentru perechea formată din și cheia publică a utilizatorului . $\ eu$ $\S$ $\ (I,v)$ $\ eu$ $\v$

Crearea unei semnături.

Mesajul de intrare , cheia secretă și modulul , care este folosit pentru calcule. $\m$ $\s = (s_1,\cdots\,s_k)$ $\N$

1. Un număr aleatoriu este selectat din interval și calculat . $\r$ $\ [1,N]$ $\ x = r^{2^t}$

2. Calculat . $\ e = (e_11,\cdots\, e_tk) = h(x,m)$

3. Calculat . $\ y = r \prod\nolimits_{j=1}^k s_j^{\sum\nolimits_{i=1}^t e_{ij}*2^{i-1}} \mod\ N$

Semnătura de ieșire este pereche . $\ (e,y)$

Generarea unei semnături necesită cel mult înmulțiri modulo și, în medie, aleatorii necesită doar înmulțiri. $\{k*t+t-1}$ $\ e$ $\t(k+2)/2+1$

Verificarea semnăturii.

Date de intrare — semnătură , mesaj , , . $\ (e,y)$ $\m$ $\v = (v_1,\cdots\,v_k)$ $\ I,S,N$

1. Semnătura pentru . $\S$ $\ (I,v)$

2. Calculat . $\ z = y^{2^t}\prod\nolimits_{j=1}^k v_j^{\sum\nolimits_{i=1} e_{ij}*2^{i-1}} \mod\ N$

3. Verificați că . $\e=h(z,m)$

Pentru verificarea semnăturii este necesar, în medie, pentru operațiile de înmulțire aleatorie modulo, maximum . $\ e$ $\t(k+2)/2+1$ $\ {k*t + t}$

Securitatea semnăturii.

Pentru a falsifica o semnătură de mesaj , criptoanalistul trebuie să rezolve o ecuație pentru și . $\m$ $\ e =h (y^{2^t}\prod\nolimits_{j=1}^k v_j^{\sum\nolimits_{i=1}^t e_{i,j}*2^{i-1 }},m) \mod\N$ $\ e$ $\y$

În prezent, nu există algoritmi cunoscuți pentru rezolvarea acestei ecuații.

Aplicarea EDS rapid

Algoritmii rapidi de semnătură digitală sunt cei mai eficienți în cazurile în care viteza de obținere a cheii și dimensiunea mică a semnăturii sunt de importanță primordială. Cerințe similare există în rețelele mobile, de senzori sau personale (a căror rază este limitată la o cameră) atunci când se transmite trafic multimedia. Utilizarea unei semnături digitale în telefoanele mobile GSM permite utilizatorilor să creeze ei înșiși un cod PIN, mai degrabă decât să-l primească de la operator.

Implementarea algoritmilor accelerați de generare a semnăturii digitale pentru dispozitive cu resurse limitate, cum ar fi PDA-uri, carduri inteligente încorporate și telefoane mobile, a căror putere de calcul este mult inferioară capacităților computerelor personale, va permite cheltuirea mai puțină energie pentru a crea și stoca o semnătură. și astfel crește timpul de funcționare al dispozitivului fără reîncărcare.

Literatură

Scheme rapide de semnătură digitală la fel de sigure ca Diffie-Hellman Assumptions, Changshe Ma , Jian Weng și Dong Zheng , 22 ianuarie 2007

Generare de semnături Fasr cu o schemă asemănătoare Fiat Shamir, H.Ong , CPSchnorr

Vezi și

Algoritmul Diffie-Hellman

Schema Shamir

Criptosistem rapid cu cheie publică

Criptosistem cu cheie publică

Schema lui ElGamal

Semnatura digitala

Link -uri

Brevetul SUA 5.263.085