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\ne 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,\dots ,n-1\}$. $B$ turi $A$ viešą raktą – $n$.

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

$c\equiv m^2(\mathrm{mod}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,\dots ,4$ yra pranešimas.

Kvadratinė šaknis moduliu

Apibrėžimas. Simboliu $Z_n$ žymėsime aibę skaičių $\{0,1,\dots ,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\le n\le 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)=\{\begin{array}{ccc}0& :& p|a\\ 1& :& a\in Q_p\\ -1& :& a\in \overline{Q_p}\end{array}$

Čia $Q_p$ ir $\overline{Q_p}$ apibrėžtos taip:

$Q_p=\{a|\mathrm{\exists }x\in Z_p^{*},kad{x}^2\equiv a(\mathrm{mod}p),a\in Z_p^{*}\}$

$\overline{Q_p}=\{a|neegzistuojax\in Z_p^{*},kad{x}^2\equiv a(\mathrm{mod}p),a\in Z_p^{*}\}$

Bendras algoritmas kvadratinėm šaknims surasti:

ALGORITMAS SQR1
ĮVESTIS: $a$ - skaičius, $p$ - pirminis skaičius, $1\le a\le 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\le b\le 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}(\mathrm{mod}p)$
 5. $c\leftarrow b^t(\mathrm{mod}p),r\leftarrow a^{(t+1)/2}(\mathrm{mod}p)$
 6. Visiem $i$ nuo $1$ iki $s-1$:
   6.1. $d=(r^2{a}^{-1}{)}^{2^{s-i-1}}(\mathrm{mod}p)$
   6.2. Jeigu, $d\equiv -1(\mathrm{mod}p)$, tada $r\leftarrow rc(\mathrm{mod}p)$
   6.3. $c\leftarrow c^2(\mathrm{mod}p)$
 7. Sprendimas: $(r,-r)$

Jeigu $p\equiv 3(\mathrm{mod}4)$, tai naudojamas sekantis algoritmas:

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

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

Jeigu $p\equiv 3(\mathrm{mod}4)$ ir Jeigu $q\equiv 3(\mathrm{mod}4)$, tada
 1. Surasti $a$ ir $b$, kad $ap+bq=1$.
 2. $r=a^{(p+1)/4}(\mathrm{mod}p)$
 3. $s=a^{(q+1)/4}(\mathrm{mod}q)$ 
 4. $x=(aps+bqr)(\mathrm{mod}n)$
 5. $y=(aps-bqr)(\mathrm{mod}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\le a\le 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}modf$
 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)modn$, $y\leftarrow (rdq-scp)modn$
 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