Hash de domeniu complet

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 24 ianuarie 2019; verificările necesită 30 de modificări .

În criptografie , Full Domaine Hash ( FDH sau Full Domain Hash ) este o schemă de semnătură bazată pe RSA care urmează paradigma hash și semnătură . Este dovedit sigur (adică neafectat de atacurile adaptive cu mesaje alese) în modelul de oracol aleatoriu . FDH implică hashingul mesajului folosind o funcție a cărei dimensiune a imaginii este dimensiunea modulului RSA și apoi ridicarea rezultatului la puterea exponentului RSA secret .

Introducere

De la descoperirea criptografiei cu cheie publică de către Whitfield Diffie și Martin Hellman [ 1 ] , unul dintre cele mai importante subiecte de cercetare a fost dezvoltarea unor criptosisteme practice și sigure (în înțelegere practică). Dovada securității practice este de obicei complexitatea computațională de la rezolvarea unei probleme binecunoscute până la spargerea unui criptosistem. Problemele binecunoscute includ factorizarea numerelor întregi mari , calcularea logaritmului discret modulo un număr prim p sau extragerea unei rădăcini modulo un număr întreg compus, pe care se bazează criptosistemul RSA [2] .

O practică foarte obișnuită pentru semnarea cu RSA este de a mai întâi hash mesajul, adăugați o sare la mesaj și apoi ridicați-l la puterea cheii publice. Această paradigmă „hash and decrypt” este baza a numeroase standarde, cum ar fi PKCS # 1 v2.0 [3] . Schema este de a lua o funcție hash a cărei dimensiune de ieșire este exact dimensiunea modulului: aceasta este schema completă de hashing a domeniului (FDH) introdusă de Bellard și Rogaway în articolul „Oracolele aleatorii sunt practice: a paradigmă pentru proiectarea protocoalelor eficiente” [4] . Schema FDH se dovedește sigură în modelul de oracol aleatoriu, presupunând că este greu să inversați RSA , adică să luați o rădăcină modulo un număr întreg compus. Metodologia oracolului aleatoriu a fost introdusă de Bellard și Rogaway în „Oracolele aleatoare sunt practice: o paradigmă pentru proiectarea protocoalelor eficiente” [4] , unde arată cum să dezvolte scheme de semnătură extrem de sigure din orice funcție cu o intrare secretă . În modelul de oracol aleatoriu , o funcție hash este tratată ca un oracol care produce o valoare aleatorie pentru fiecare cerere nouă. În lucrarea originală, un oracol aleatoriu convertește o secvență de lungime fixă de 0 și 1 într-o secvență de lungime infinită și selectează aleatoriu o secvență cu lungimea necesară din secvența . Lucrarea fundamentală a lui Bellard și Rogaway subliniază că, pentru aplicarea practică a securității dovedibile, este important să se ia în considerare reducerile de securitate „dure”. O degradare a securității este „grea” atunci când orice acțiune a criptoanalistului de a rupe schema de semnătură are ca rezultat rezolvarea unei probleme bine stabilite cu o probabilitate suficientă, în mod ideal cu o probabilitate de 1. În acest caz, schema de semnătură este aproape la fel de sigură ca problema bine stabilită. În schimb, dacă contracția este „slabă”, adică probabilitatea menționată mai sus este prea mică, garanția pentru schema de semnătură poate fi destul de slabă. ${\{0,1\}}^{*}\longrightarrow {\{0,1\}}^{\infty }$

Definiție

Schema completă de semnătură hash de domeniu (Gen, Sign, Verify) este definită după cum urmează. Algoritmul de generare a cheilor rulează RSA pentru a obține . Iese unde și . Algoritmul de semnătură și verificare are acces la un oracol cu funcție hash $(N,e,d)$ $(pk,sk)$ $pk=(N,e)$ $sk=(N,d)$ $H_{FDH}:{\{0,1\}}\la {\mathbb {Z} _{N}}$

Semnarea și verificarea se face după cum urmează:

{\textstyle {\begin{aligned}SignFDH_{N,d}(M)\\y\leftarrow H_{FDH}(M)\\return:y^{d}modN\\\\VerifyFDH_{N,e} (M,x)\\y\leftarrow x^{e}modN;\\y'\leftarrow H_{FDH}(M)\\if(y=y')then\\return:1\\else\\ return:0\end{aliniat}}}

Analiza de securitate a schemei FDH

Abordarea Bellard și Rogway

Teorema 1 Să presupunem că RSA este -secure (cu probabilitatea ɛ′ durează t′ timp pentru a se rupe) Atunci schema de semnătură FDH este -secure, unde $(t',\varepsilon ')$ $(t,\varepsilon)$

{\begin{aligned}t&=t'-(q_{\text{hash}}+q_{\text{sig}}+1)\\\varepsilon &=(q_{\text{hash}} +q_{\text{sig)))*\varepsilon '\end{aligned}}

Dezavantajul acestui rezultat este că poate fi mult mai mic decât . De exemplu, dacă presupunem că un criptoanalist poate interoga numărul de semnături și poate calcula hash-uri pe mesaje chiar dacă probabilitatea inversării RSA este doar , atunci tot ceea ce obținem este că probabilitatea este aproape , ceea ce nu este satisfăcător. Pentru a obține un nivel acceptabil de securitate, trebuie să folosim o dimensiune mai mare a modulului, care va afecta pozitiv eficiența circuitului. $\varepsilon '$ $\varepsilon$ $q_{\text{sig}}=2^{30}$ $q_{\text{hash}}=2^{60}$ $2^{-61}$ $1/2$

Pentru a obține cea mai adecvată marjă de securitate, Bellar și Rogaway au dezvoltat o nouă schemă, schema de semnătură probabilistică , care oferă o reducere strictă de securitate: probabilitatea de falsificare a semnăturii este aproape la fel de mică ca și în cazul inversării . În schimb, există o abordare alternativă care poate fi aplicată schemei FDH pentru a obține o legătură mai bună. [5] $(PSS)$ $RSA(\varepsilon =\varepsilon ')$

Abordare alternativă

O altă reducere care oferă o estimare de securitate mai bună pentru FDH se bazează pe demonstrarea teoremei

Teorema 2 Fie RSA în siguranță. Atunci schema de semnătură FDH este -secure, unde $(t',\epsilon ')$ $(t,\epsilon )$

{\begin{aligned}t&=t'-(q_{\text{hash}}+q_{\text{sig}}+1)\\\epsilon &={\frac {1}{\left (1-{\frac {1}{q_{\text{sig}}}}\right)^{q_{\text{sig}}+1}}}\cdot q_{\text{sig}}\cdot \epsilon '\end{aliniat}}

Pentru mari , . $q_{\text{sig}}$ $\epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '$

Definiția 1

Vom numi un invertor un algoritm care rupe RSA , a cărui probabilitate de succes după ce nu a trecut mai mult de t timp de procesare este de cel puțin ɛ . $eu$ $(t,\epsilon )$

Definiția 2

Un falsificator este un algoritm care încalcă schema de semnătură (Gen, Sign, Verify) dacă, după nu mai mult de solicitări către oracolul hash, solicitări semnate și timp de procesare, emite un fals de semnătură cu o probabilitate de cel puțin ɛ . $F$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ $q_{\text{hash}}$ $q_{\text{sig}}$ $t$

Dovada Să fie un falsificator care încalcă FDH-ul. Presupunem că nu repetă niciodată aceeași cerere de oracol hash sau cerere de semnătură. Construirea unui invertor care sparge RSA. Invertorul primește ca intrare , unde este cheia publică și este ales aleatoriu în (un subset al tuturor mesajelor hashing) . Invertorul încearcă să găsească de unde este definită funcția RSA . Invertorul pornește pentru această cheie publică. Falsificatorul face cereri de oracol hash și solicitări de semnătură. primind un răspuns de la oracolul hash, îi semnează independent. $F$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ $F$ $eu$ $(t',\epsilon ')$ $eu$ $(N,e,y)$ $(N,e)$ $y$ $\mathbb {Z} _{N}$ $eu$ $x=f^{-1}(y)$ $f$ $N,e$ $eu$ $F$ $F$ $eu$

Pentru simplitate, presupunem că atunci când face o cerere de semnare a unui mesaj , a făcut deja o solicitare corespunzătoare oracolului hash pentru . Dacă nu, continuăm și creăm independent o solicitare hash-oracle pentru mesajul .Invertorul folosește un contor care este inițial setat la zero. Când interogând oracolul hash pentru un mesaj , invertorul crește , potrivește mesajul hash cu mesajul original și alege un număr aleatoriu în . apoi revine cu probabilitate și cu probabilitate . Iată o probabilitate fixă, care va fi determinată mai târziu. Când faceți o cerere de semnătură pentru , acesta a solicitat deja un hash , deci pentru unii .If , atunci revine ca semnătură. În caz contrar, procesul se oprește și invertorul eșuează. $F$ $M$ $M$ $M$ $eu$ $i$ $F$ $M$ $eu$ $i$ $M_{i}=M$ $r_{i}$ $\mathbb {Z} _{N}$ $eu$ $h_{i}=r_{i}^{e}modN$ $p$ $h_{i}=y*r_{i}^{e}modN$ $1-p$ $p$ $F$ $M$ $M$ $M=M_{i)$ $i$ $h_{i}={r_{i}}^{e}modN$ $eu$ $r_{i)$

În cele din urmă, termină treaba și afișează un fals . Presupunem că hash-ul a fost solicitat mai devreme. Dacă nu, face o cerere către oracolul hash în sine, deci, în orice caz, pentru unii . Atunci, dacă , obținem și iese ca reciprocă a lui . În caz contrar, procesul se oprește și invertorul eșuează. $F$ $(M,x)$ $F$ $M$ $eu$ $M=M_{i)$ $i$ $h_{i}=y*{r_{i}}^{e}modN$ $x={h_{i}}^{d}=y^{d}*r_{i}modN$ $eu$ $y^{d}={\frac {x}{r_{i)}}modN$ $y$

Probabilitatea ca vom răspunde la toate solicitările de semnătură este de cel puțin . Apoi tipărește inversul pentru cu probabilitate . Astfel, cu cel puțin probabilitate , deduce contrariul pentru . Funcția este maximă pentru și $p^{q_{\text{sig}})$ $eu$ $y$ $f$ $1-p$ $\alpha (p)=p^{q_{\text{sig)}}*(1-p)$ $eu$ $y$ $f$ $\alpha (p)$ $p_{\text{max}}=1-1/(q_{\text{sig}}+1)$

{\displaystyle \alpha (p_{\text{max)})={\frac {1}{q_{\text{sig}}))(1-{\frac {1}{1+q_{\text{ sig))))^{1+q_{\text{sig))))

Prin urmare obținem:

{\begin{aliniat}\epsilon (k)&={\frac {1}{\left(1-{\frac {1}{q_{\text{sig}}+1}}\right) ^{q_{\text{sig}}+1}}}\cdot q_{\text{sig}}\cdot \epsilon '\end{aligned}}

Pentru cei mari $q_{\text{sig}}$

$\epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '$ .

Timpul de funcționare este timpul de funcționare adăugat la timpul necesar pentru calcularea valorilor . Este în esență un singur calcul RSA, care este timpul cub (sau mai bine). Aceasta dă formula pentru . $eu$ $F$ $Bună}$ $t$

Abrevierea finală

Calitatea noii reduceri nu depinde de numărul de apeluri hash efectuate de fals, ci depinde doar de numărul de cereri de semnătură. Acest lucru este de importanță practică, deoarece în aplicațiile reale numărul de apeluri de funcție hash este limitat doar de puterea de procesare a falsificatorului, în timp ce numărul de solicitări de semnătură poate fi limitat: semnatarul poate refuza să semneze mai mult decât sau mesaje. Cu toate acestea, reducerea nu este încă rigidă și rămâne un decalaj semnificativ între securitatea precisă a FDH și securitatea precisă a PSS . $2^{20}$ $2^{30}$

În multe dovezi de securitate din modelul de oracol aleatoriu, invertorul trebuie să „ghicească” ce interogare hash va fi folosită de adversar pentru a falsifica, rezultând un factor în probabilitatea de succes. S-a dovedit că cea mai bună metodă este de a include o interogare ca răspuns la multe interogări hash, astfel încât falsificarea este mai probabil să fie utilă invertorului. Această observație se aplică și schemei de semnătură Rabin [6] , schema de semnătură a lui Peye [7] , precum și schemei de semnătură Gennaro-Halevi-Rabin [8] , pentru care coeficientul din dovada de securitate aleatoare a oracolului poate fi de asemenea redus la . $q_{\text{hash}}$ $y$ $q_{\text{hash}}$ $q_{sig)$

Note

↑ Direcții noi în criptografie . Consultat la 25 decembrie 2018. Arhivat din original la 12 octombrie 2019. (nedefinit)
↑ O metodă de obținere a semnăturilor digitale și a criptosistemelor cu cheie publică . Preluat la 25 decembrie 2018. Arhivat din original la 26 decembrie 2018. (nedefinit)
↑ Specificații de criptare RSA . Preluat la 25 decembrie 2018. Arhivat din original la 12 decembrie 2018. (nedefinit)
↑ 1 2 Oracolele aleatorii sunt practice: o paradigmă pentru proiectarea protocoalelor eficiente . Preluat la 25 decembrie 2018. Arhivat din original la 24 decembrie 2018. (nedefinit)
↑ Securitatea exactă a semnăturilor digitale - Cum să semnezi cu RSA și Rabin . Preluat la 25 decembrie 2018. Arhivat din original la 23 decembrie 2018. (nedefinit)
↑ Semnăturile digitalizate și funcțiile cu cheie publică la fel de insolubile precum factorizarea . Preluat la 25 decembrie 2018. Arhivat din original la 3 noiembrie 2018. (nedefinit)
↑ Sisteme criptografice cu cheie publică bazate pe clase de reziduuri de grad compus. Proceedings of Eurocrypt'99 . Consultat la 25 decembrie 2018. Arhivat din original la 6 mai 2021. (nedefinit)
↑ Securizarea semnăturilor hash-and-sign fără oracolul aleatoriu, procedurile Eurocrypt'99 . Consultat la 25 decembrie 2018. Arhivat din original la 14 iulie 2012. (nedefinit)