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

[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: 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 x2bx + aZp[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\,

[taisyti] Literatūra

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

[taisyti] Kitos viešo rakto kriptosistemos