Schema probabilistică a semnăturii Rabin

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

Schema de semnătură probabilistică a lui Rabin este o metodă de semnătură digitală propusă inițial de Michael O. Rabin în 1979 [1] . Schema de semnătură a lui Rabin a fost una dintre primele scheme de semnătură digitală propuse și este singura care leagă direct complexitatea falsificării semnăturii cu problema factorizării întregi . Algoritmul de semnătură al lui Rabin este nepotrivit într-un model de calcul aleator aleator care presupune că problema factorizării întregi este indecidabilă. Schema de semnătură Rabin este, de asemenea, strâns legată de criptosistemul Rabin .

Algoritmul original

Generarea cheilor
- Sunt selectate numere prime , fiecare cu dimensiunea unui bit, iar produsul este calculat . $p$ $q$ $k/2$ $n=p\cdot q$
- Apoi, unul aleator este selectat din . $b$ $\{1,\ldots ,n\}$
- Cheia publică este o pereche . $(n,b)$
- cheie privată, respectiv . $(p,q)$
Semnătură
- Pentru a semna un mesaj , este selectat și calculat un număr aleatoriu . $m$ $U$ $m\cdot U\mod n$
- Apoi ecuația este rezolvată . $x(x+b)\mod n=m\cdot U\mod n$
- Dacă nu există o soluție pentru ecuație, se alege o nouă valoare și ecuația este rezolvată din nou. $U$
- Semnătura mesajului va fi un cuplu $m$ $(U,x)$
Examinare
- Având în vedere mesajul și semnătura, verificatorul efectuează calcule și apoi verifică dacă sunt egale. $m$ $(U,x)$ $V$ $x(x+b)modn$ $m\cdot U\mod n$

Algoritmul original nu folosește funcții hash și este considerat nesigur. [2]

Algoritm sigur și simplificat

Algoritmul sigur și securizat [3] se bazează pe o funcție hash rezistentă la coliziuni . $H:\{0,1\}^{*}\rightarrow \{0,1\}^{k)$

În majoritatea vizualizărilor, algoritmul este simplificat prin alegerea . Se presupune că funcția hash cu numărul de biți de ieșire este un oracol aleatoriu și algoritmul funcționează după cum urmează: $b=0$ $H$ $k$

Generarea cheilor

Sunt alese numere prime , fiecare cu dimensiunea unui bit, iar modul 4 este egal cu 3. Apoi, produsul este calculat . $p$ $q$ $k/2$ $p$ $q$ $n=p\cdot q$
Cheia publică în acest caz este . $n$
Cheia privată va fi perechea . $(p,q)$

Semnătură

Pentru a semna un mesaj , este selectat și calculat un număr aleatoriu . $m$ $U$ $H(m,U)$
Dacă nu este un pătrat modulo , se alege o nouă valoare . $H(m,U)$ $n$ $U$
După aceea, se găsește o valoare x, care este soluția ecuației . $x^{2}=H(m,U)\mod n$
Semnătura mesajului va fi un cuplu . $m$ $(U,x)$

Examinare

Având în vedere mesajul și semnătura, verificatorul efectuează calcule și apoi verifică dacă sunt egale. $m$ $(U,x)$ $V$ $x^{2}modn$ $H(m,U)$

Note

În unele implementări ale algoritmului, valoarea nu este utilizată. În schimb, este posibil să înmulțim valoarea hash cu două numere a sau b cu proprietăți și , unde denotă simbolul Legendre . Apoi, pentru orice modulo, doar unul dintre cele patru numere va fi un modulo pătrat , iar acest număr este ales pentru a semna digital mesajul. $U$ $\left({\tfrac {a}{p}}\right)=-\left({\tfrac {a}{q}}\right)=-1$ $\left({\tfrac {b}{q}}\right)=-\left({\tfrac {b}{p}}\right)=-1$ $(\cdot )$ $H$ $n$ $H,aH,bH,abH$ $n$

Pentru a simplifica și mai mult algoritmul, trebuie să schimbați mesajul până când semnătura trece de verificare. $m$

\\ Funcția de schimbare a mesajului pentru verificarea semnăturii def root ( m : str , p , q ): while True : x = h ( m ) sig = pow ( p , q - 2 , q ) * p * pow ( x , ( q ) + 1 ) / 4 , q ) sig = ( pow ( q , p - 2 , p ) * q * pow ( x , ( p + 1 ) / 4 , p ) + sig ) % ( nrabin ) dacă ( sig * sig ) ) % nrabin == x : print ( „Scrieți mesajul extins în fișierul m.txt” ) f = deschis ( 'm.txt' , 'w' ) f . scrie ( m ) f . close () break m = m + ' ' return sig

Securitate

Dacă funcția hash este un oracol aleatoriu, adică ieșirea sa este cu adevărat aleatorie la , atunci falsificarea unei semnături pentru orice mesaj este la fel de dificilă precum calcularea rădăcinii pătrate a unui element aleatoriu din . $H$ $\mathbb {Z} /n\mathbb {Z}$ $m$ $\mathbb {Z} /n\mathbb {Z}$

Pentru a demonstra [4] că obținerea unei rădăcini pătrate aleatoare este la fel de dificilă ca și factorizarea, trebuie remarcat că în majoritatea cazurilor există patru rădăcini pătrate diferite, deoarece are două rădăcini pătrate modulo și două rădăcini pătrate modulo , iar fiecare pereche dă un rădăcină pătrată modulo după teorema chineză a restului . Unele dintre rădăcini pot avea aceeași valoare, dar probabilitatea ca aceasta este extrem de mică. $n$ $p$ $q$ $n$

Dacă este posibil să găsim două rădăcini pătrate diferite astfel încât dar , atunci aceasta duce imediat la o factorizare a lui , deoarece factorii primi sunt divizibili cu , dar nu divizibili. Deci, calculul va avea ca rezultat o factorizare non-trivială . $X$ $y$ $x^{2}=y^{2}\mod n$ $x\neq \pm y\mod n$ $n$ $n$ $x^{2}-y^{2}=(xy)(x+y)$ $\operatorname {gcd} (x\pm y,n)$ $n$

Acum se presupune că există un algoritm eficient pentru găsirea a cel puțin o rădăcină pătrată. Apoi se alege un modulo aleator și se pune la pătrat , după folosirea algoritmului, se ia rădăcina pătrată a modulo și se obține o nouă rădăcină , care cu o probabilitate de 50% . $r$ $n$ $r^{2}=R\mod n$ $R$ $n$ $r^\prim$ $r\neq \pm r^{\prime }\mod n$

Vezi și

Note

↑ Semnături digitalizate și funcții de cheie publică la fel de insolubile ca factorizarea (link nu este disponibil)
↑ | Michele Elia, Davide Schipani, Despre semnătura Rabin c.1-3 . Preluat la 13 decembrie 2019. Arhivat din original la 22 septembrie 2019. (nedefinit)
↑ | Michele Elia, Davide Schipani, Despre semnătura Rabin c.5-9 . Preluat la 13 decembrie 2019. Arhivat din original la 22 septembrie 2019. (nedefinit)
↑ Semnături digitalizate și funcții de cheie publică la fel de insolubile ca factorizarea c.15-19 (link nu este disponibil)

Literatură

Michele Elia, Davide Schipani, Despre semnătura Rabin , 2011 PDF
Buchmann, Johannes. Einführung in die Kryptographie . a doua editie. Berlin: Springer, 2001. ISBN 3-540-41283-2
Menezes, Alfred; van Oorschot, Paul C.; și Vanstone, Scott A. Handbook of Applied Cryptography . CRC Press, octombrie 1996. ISBN 0-8493-8523-7
Rabin, Michael. Semnături digitalizate și funcții cu cheie publică la fel de insolubile precum factorizarea (în PDF). MIT Laboratory for Computer Science, ianuarie 1979.
Scott Lindhurst, O analiză a algoritmului lui Shank pentru calcularea rădăcinilor pătrate în câmpuri finite. în R Gupta și KS Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, vol 19 CRM Proc & Lec Notes, AMS, Aug 1999.
R Kumanduri și C Romero, Teoria numerelor cu aplicații computerizate, Alg 9.2.9, Prentice Hall, 1997. O probabilitate pentru rădăcina pătrată a unui rest patratic modulo un prim.

Link -uri

Sursa

Smart N. Criptografie. - M .: Technosfera, 2005. S. 525.