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 =  \,,
o privatus:
: K_p =  \,

## Š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 \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) = \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 \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^st\,, 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^2a^{-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 \le a \le 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 \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}\ 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