Rabin kriptosistema

Rabin kriptosistema yra viešo rakto kriptosistema. Ji buvo sukurta Michael O. Rabin.

Tai labai greita kriptosistema, kadangi šifravimui reikalauja vienos operacijos – kėlimo kvadratu moduliu $n\,$. Saugumas remiasi skaičiaus $n\,$ skaidymo į du pirminius $p,q\,$, kad $pq=n\,$ problemos sudėtingumu.

Raktų parinkimo algoritmas

$A\,$ pasirenka du didelius pirminius skaičius $p,q,\ p\neq q\,$ ir sudaugina juos $n=pq\,$. $A\,$ viešas raktas

$K_{v}=<n>\,$,

o privatus:

$K_{p}=<p,q>\,$

Šifravimas/dešifravimas

Tarkime, kad $B\,$ nori perduoti $A\,$ pranešimą $m\,$, $m\in \{0,1,\ldots ,n-1\}\,$. $B\,$ turi $A\,$ viešą raktą – $n\,$.

$B\,$ užšifruoja $m\,$, tiesiog pakėlus jį kvadratu moduliu $n\,$:

$c\equiv m^{2}{\pmod {n}}\,$

$A\,$ dešifruoja pranešimą, suradus $c\,$ šaknys $m_{1},m_{2},m_{3},m_{4}\,$ moduliu $n\,$. $A\,$ nusprendžia, kuris iš $m_{i},\ i=1,\ldots ,4\,$ yra pranešimas.

Kvadratinė šaknis moduliu

Apibrėžimas. Simboliu $Z_{n}\,$ žymėsime aibę skaičių $\{0,1,\ldots ,n-1\}$.

Apibrėžimas. Simboliu $Z_{n}^{*}\,$ žymėsime aibę skaičių $\{a\in Z_{n}|DBD(a,n)=1\}$. Jeigu $n\,$ – pirminis, tai $Z_{n}^{*}=\{a\ |\ 1\leq n\leq n-1\}\,$

Apibrėžimas. Tegu $a\,$ – skaičius, o $p\,$ – pirminis skaičius. Legendre simbolis $\left({\frac {a}{p}}\right)\,$ apibrėžiamas taip:

$\left({\frac {a}{p}}\right)=\left\{{\begin{matrix}0&:&p|a\\1&:&a\in Q_{p}\\-1&:&a\in {\bar {Q_{p}}}\end{matrix}}\right.$

Čia $Q_{p}\,$ ir ${\bar {Q_{p}}}\,$ apibrėžtos taip:

$Q_{p}=\{a\ |\exists x\in Z_{p}^{*},\ kad\ x^{2}\equiv a{\pmod {p}},\ a\in Z_{p}^{*}\}\,$

${\bar {Q_{p}}}=\{a\ |neegzistuoja\ x\in Z_{p}^{*},\ kad\ x^{2}\equiv a{\pmod {p}},\ a\in Z_{p}^{*}\}\,$

Bendras algoritmas kvadratinėm šaknims surasti:

ALGORITMAS SQR1
ĮVESTIS: $a\,$ - skaičius, $p\,$ - pirminis skaičius, $1\leq a\leq p-1\,$
IŠVESTIS: dvi šaknis skaičiaus $a\,$ moduliu $p\,$, jeigu jos egzistuoja
 1. Jeigu $\left({\frac {a}{p}}\right)=-1\,$ – šaknų nėra.
 2. Parinkti $b\,$, $1\leq b\leq p-1\,$, kad $\left({\frac {b}{p}}\right)=-1\,$
 3. Užrašyti skaičių $p-1=2^{s}t\,$, $t\,$ – nelyginis.
 4. Apskaičiuoti $a^{-1}{\pmod {p}}\,$
 5. $c\leftarrow b^{t}{\pmod {p}},\ r\leftarrow a^{(t+1)/2}{\pmod {p}}\,$
 6. Visiem $i\,$ nuo $1\,$ iki $s-1\,$:
   6.1. $d=(r^{2}a^{-1})^{2^{s-i-1}}{\pmod {p}}\,$
   6.2. Jeigu, $d\equiv -1{\pmod {p}}$, tada $r\leftarrow rc{\pmod {p}}$
   6.3. $c\leftarrow c^{2}{\pmod {p}}\,$
 7. Sprendimas: $(r,-r)\,$

Jeigu $p\equiv 3{\pmod {4}}$, tai naudojamas sekantis algoritmas:

ALGORITMAS SQR2
ĮVESTIS: $a\,$ - skaičius, $p\,$ - pirminis skaičius, $1\leq a\leq p-1\,$
IŠVESTIS: dvi šaknys skaičiaus $a\,$ moduliu $p\,$, jeigu jos egzistuoja
 1. $r=a^{(p+1)/4}{\pmod {p}}\,$
 2. $(r,-r)\,$

Taikymas šio algoritmo (SQR2) Rabin kriptosistemos atveju atrodo taip:

Jeigu $p\equiv 3{\pmod {4}}\,$ ir Jeigu $q\equiv 3{\pmod {4}}\,$, tada
 1. Surasti $a\,$ ir $b\,$, kad $ap+bq=1\,$.
 2. $r=a^{(p+1)/4}{\pmod {p}}\,$
 3. $s=a^{(q+1)/4}{\pmod {q}}\,$ 
 4. $x=(aps+bqr){\pmod {n}}\,$
 5. $y=(aps-bqr){\pmod {n}}\,$
 6. Rezultatas: $(x,-x,y,-y)\,$

Pastaba: $-x\,$ ir $-y\,$ moduliu n.

Jeigu $p\,$ – pirminis, tai skaičiaus $a\,$ moduliu $p\,$ šaknys surasime algoritmo SQR3 pagalba:

ALGORITMAS SQR3
ĮVESTIS: $a\,$ - skaičius, $p\,$ - pirminis skaičius, $1\leq a\leq p-1\,$
IŠVESTIS: dvi šaknys skaičiaus $a\,$ moduliu $p\,$, jeigu jos egzistuoja
 1. Pasirenkame $b\in Z_{n}\,$, kad $\left({\frac {b^{2}-4a}{p}}\right)=-1\,$
 2. Tegu $f\,$ yra polinomas $x^{2}-bx+a$ iš $Z_{p}[x]$
 3. $r=x^{(p+1)/2}\ mod\ f\,$
 4. Rezultatas: $(r,-r)\,$

$Z_{p}[x]\,$ – Polinomų žiedas

Rabin kriptosistemos atveju algoritmas SQR3 panaudojamas taip:

ALGORITMAS SQR4
ĮVESTIS: $a\,$ - skaičius, $n=pq\,$, $p$ ir $q$ pirminiai
IŠVESTIS: keturios šaknys skaičiaus $a\,$ moduliu $n\,$, jeigu jos egzistuoja
 1. Naudojant SQR3, surandame skaičiaus $a\,$ šaknys $(r,-r)\,$ moduliu $p\,$
 2. Naudojant SQR3, surandame skaičiaus $a\,$ šaknys $(s,-s)\,$ moduliu $q\,$
 3. Surandame $c\,$ ir $d\,$, kad $cp+dq=1\,$
 4. $x\leftarrow (rdq+scp)\ mod\ n\,$, $y\leftarrow (rdq-scp)\ mod\ n\,$
 5. Rezultatas: $(x,-x,y,-y)\,$, visi moduliu $n\,$

Literatūra

• A. Menezes, P. van Oorschot, S. Vanstone, 1996, Handbook of Applied Cryptography

Kitos viešo rakto kriptosistemos

• Rivest-Shamir-Adleman kriptosistema, RSA
• Merkle-Hellman kriptosistema