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 . Saugumas remiasi skaičiaus  skaidymo į du pirminius , kad  problemos sudėtingumu.

Raktų parinkimo algoritmas 
 pasirenka du didelius pirminius skaičius  ir
sudaugina juos .  viešas raktas
 ,
o privatus:

Šifravimas/dešifravimas 
Tarkime, kad  nori perduoti  pranešimą , .  turi  viešą raktą – .

 užšifruoja , tiesiog pakėlus jį kvadratu moduliu :

 

 dešifruoja pranešimą, suradus  šaknys  moduliu .  nusprendžia, kuris iš  yra pranešimas.

Kvadratinė šaknis moduliu 

Apibrėžimas. Simboliu  žymėsime aibę skaičių .

Apibrėžimas. Simboliu  žymėsime aibę skaičių . Jeigu  – pirminis, tai  

Apibrėžimas. Tegu  – skaičius, o  – pirminis skaičius. Legendre simbolis  apibrėžiamas taip:

 

Čia  ir  apibrėžtos taip:

 
 

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 , 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:  ir  moduliu n.

Jeigu  – pirminis, tai skaičiaus  moduliu  š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  iš 
  3. 
  4. Rezultatas: 

 – Polinomų žiedas

Rabin kriptosistemos atveju algoritmas SQR3 panaudojamas taip:

 ALGORITMAS SQR4
 ĮVESTIS:  - skaičius, ,  ir  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

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

Kriptografija