Criptosistemul lui Rabin

Criptosistemul Rabin este un sistem de criptare cu cheie publică dezvoltat în 1979 de Michael Oser Rabin care, la fel ca sistemul RSA , își bazează securitatea pe faptul că problema factorizării întregi este dificilă din punct de vedere al calculului.

Criptare

Generarea cheie

Fiecare utilizator trebuie

Generați două numere prime p și q astfel încât $p\equiv 3{\pmod {4}}\,$ ${\ displaystyle p \ equiv 3 {\ pmod {4}} \,}$ ${\ displaystyle p \ equiv 3 {\ pmod {4}} \,}$ Și $q\equiv 3{\pmod {4}}\,$ ${\ displaystyle q \ equiv 3 {\ pmod {4}} \,}$ ${\ displaystyle q \ equiv 3 {\ pmod {4}} \,}$
A calcula $n=pq$ ${\ displaystyle n = pq}$ ${\ displaystyle n = pq}$

In acest punct

$(p,q)$ ${\ displaystyle (p, q)}$ ${\ displaystyle (p, q)}$ este cheia privată
$n$ ${\ displaystyle n}$ $n$ este cheia publică

Funcția de criptare

Funcția de criptare este:

f_{A}:\mathbb {Z} _{n}\to \mathbb {Z} _{n},f_{A}(M)=C\equiv M^{2}{\pmod {n}}\,

{\ displaystyle f_ {A}: \ mathbb {Z} _ {n} \ to \ mathbb {Z} _ {n}, f_ {A} (M) = C \ equiv M ^ {2} {\ pmod {n }} \,}

{\ displaystyle f_ {A}: \ mathbb {Z} _ {n} \ to \ mathbb {Z} _ {n}, f_ {A} (M) = C \ equiv M ^ {2} {\ pmod {n }} \,}

Decriptare

Procedura de decriptare a unui mesaj dat criptat $C.$ ${\ displaystyle C}$ $C.$ necesită cunoașterea cheii private $(p,q)$ ${\ displaystyle (p, q)}$ ${\ displaystyle (p, q)}$ și efectuarea următorilor pași:

Sunt calculate
1. $m_{p}\equiv C^{\frac {p+1}{4}}{\pmod {p}}\,$ ${\ displaystyle m_ {p} \ equiv C ^ {\ frac {p + 1} {4}} {\ pmod {p}} \,}$ ${\ displaystyle m_ {p} \ equiv C ^ {\ frac {p + 1} {4}} {\ pmod {p}} \,}$
2. $m_{q}\equiv C^{\frac {q+1}{4}}{\pmod {q}}\,$ ${\ displaystyle m_ {q} \ equiv C ^ {\ frac {q + 1} {4}} {\ pmod {q}} \,}$ ${\ displaystyle m_ {q} \ equiv C ^ {\ frac {q + 1} {4}} {\ pmod {q}} \,}$

Atunci $\pm m_{p}{\pmod {p}}\,$ ${\ displaystyle \ pm m_ {p} {\ pmod {p}} \,}$ ${\ displaystyle \ pm m_ {p} {\ pmod {p}} \,}$ Și $\pm m_{q}{\pmod {q}}\,$ ${\ displaystyle \ pm m_ {q} {\ pmod {q}} \,}$ ${\ displaystyle \ pm m_ {q} {\ pmod {q}} \,}$ sunt rădăcinile pătrate ale $C.$ ${\ displaystyle C}$ $C.$ în $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ Și $\mathbb {Z} _{q}$ ${\ displaystyle \ mathbb {Z} _ {q}}$ ${\ displaystyle \ mathbb {Z} _ {q}}$ respectiv.

Cu algoritmul lui Euclid se calculează două numere întregi $la, b$ ${\ displaystyle a, b}$ $a, b$ astfel încât $ap+bq=1$ ${\ displaystyle ap + bq = 1}$ ${\ displaystyle ap + bq = 1}$
Cu teorema chineză sunt calculați
1. $M_{1}=apm_{q}+bqm_{p}$ ${\ displaystyle M_ {1} = apm_ {q} + bqm_ {p}}$ ${\ displaystyle M_ {1} = apm_ {q} + bqm_ {p}}$
2. $M_{2}=apm_{q}-bqm_{p}$ ${\ displaystyle M_ {2} = apm_ {q} -bqm_ {p}}$ ${\ displaystyle M_ {2} = apm_ {q} -bqm_ {p}}$
3. $M_{3}=-apm_{q}+bqm_{p}$ ${\ displaystyle M_ {3} = - apm_ {q} + bqm_ {p}}$ ${\ displaystyle M_ {3} = - apm_ {q} + bqm_ {p}}$
4. $M_{4}=-apm_{q}-bqm_{p}$ ${\ displaystyle M_ {4} = - apm_ {q} -bqm_ {p}}$ ${\ displaystyle M_ {4} = - apm_ {q} -bqm_ {p}}$
Unul dintre $M_{1}$ ${\ displaystyle M_ {1}}$ ${\ displaystyle M_ {1}}$ , $M_{2}$ ${\ displaystyle M_ {2}}$ ${\ displaystyle M_ {2}}$ , $M_{3}$ ${\ displaystyle M_ {3}}$ ${\ displaystyle M_ {3}}$ , $M_{4}$ ${\ displaystyle M_ {4}}$ ${\ displaystyle M_ {4}}$ Și $M.$ ${\ displaystyle M}$ $M.$

Detalii și cazuri speciale

Pentru a distinge m care codifică mesajul celorlalte rădăcini (celălalt m), va fi necesar să se includă informații suplimentare.

Interesant, în cazul în care numărul prim P este congruent cu 1 modul 4, nu se cunoaște niciun algoritm polinom determinist care să găsească rădăcinile pătrate ale reziduurilor pătratice ale lui P.

Prin urmare, faptul că P = 3 mod 4, eq = 3 mod 4 este fundamental pentru funcționarea corectă a algoritmului descris, deoarece este câmpul de existență al ecuațiilor anterioare.

Un atacator nu ar ști care dintre cele patru rădăcini este corect, dar nu destinatarul. Acest lucru este rezolvat prin acordul asupra unor reguli de redundanță, cunoscute între expeditor și destinatar, care să fie incluse în mesaj pentru a putea distinge care dintre cele patru rădăcini corespunde cu cea a mesajului original.

Securitatea sistemului Rabin

Elemente conexe

Portal de criptografie

Portal de securitate IT