Rabin kriptosistema

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

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.

Turinys

1 Raktų parinkimo algoritmas
2 Šifravimas/dešifravimas
- 2.1 Kvadratinė šaknis moduliu
3 Literatūra
4 Kitos viešo rakto kriptosistemos

[taisyti] 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> \,$

[taisyti] Š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.

[taisyti] 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:  - skaičius,  - pirminis skaičius, 
IŠVESTIS: dvi šaknis skaičiaus  moduliu , jeigu jos egzistuoja
 1. Jeigu  – šaknų nėra.
 2. Parinkti , , kad 
 3. Užrašyti skaičių ,  – nelyginis.
 4. Apskaičiuoti 
 5. 
 6. Visiem  nuo  iki :
   6.1. 
   6.2. Jeigu, , tada 
   6.3. 
 7. Sprendimas:

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

ALGORITMAS SQR2
ĮVESTIS:  - skaičius,  - pirminis skaičius, 
IŠVESTIS: dvi šaknys skaičiaus  moduliu , jeigu jos egzistuoja
 1. 
 2.

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

Jeigu  ir Jeigu , tada
 1. Surasti  ir , kad .
 2. 
 3.  
 4. 
 5. 
 6. Rezultatas:

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

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

ALGORITMAS SQR3
ĮVESTIS:  - skaičius,  - pirminis skaičius, 
IŠVESTIS: dvi šaknys skaičiaus  moduliu , jeigu jos egzistuoja
 1. Pasirenkame , kad 
 2. Tegu  yra polinomas  $x 2 - b x + a$  iš  $Z p [x]$ 
 3. 
 4. Rezultatas:

$Z_p[x]\,$ – Polinomų žiedas

Rabin kriptosistemos atveju algoritmas SQR3 panaudojamas taip:

ALGORITMAS SQR4
ĮVESTIS:  - skaičius, ,  $p$  ir  $q$  pirminiai
IŠVESTIS: keturios šaknys skaičiaus  moduliu , jeigu jos egzistuoja
 1. Naudojant SQR3, surandame skaičiaus  šaknys  moduliu 
 2. Naudojant SQR3, surandame skaičiaus  šaknys  moduliu 
 3. Surandame  ir , kad 
 4. , 
 5. Rezultatas: , visi moduliu