Criptosistem Cramer–Shoup

Sistemul Cramer – Shoup este un  algoritm de criptare cu cheie publică . Primul algoritm care s-a dovedit rezistent la atacuri bazat pe text cifrat ales adaptativ . Proiectat de Ronald Kramer și Victor Shoup în 1998. Securitatea algoritmului se bazează pe ipoteza discriminării Diffie-Hellman . Este o extensie a schemei ElGamal , dar spre deosebire de schema ElGamal, acest algoritm este insolubil(Un hacker nu poate înlocui textul cifrat cu un alt text cifrat care ar fi decriptat într-un text legat de original, adică fiind o funcție a acestuia). Această robustețe este obținută prin utilizarea unei funcții hash universale unidirecționale și calcule suplimentare, rezultând un text cifrat care este de două ori mai mare decât schema ElGamal.

Atacul cu text cifrat ales

Un atac criptografic în care un criptoanalist adună informații despre un cifru ghicind textul cifrat și decriptându-l cu o cheie necunoscută. Criptanalistul poate folosi decriptorul de mai multe ori pentru a obține textul cifrat decriptat. Folosind datele primite, el poate încerca să recupereze cheia secretă pentru decriptare. Un atac cu text cifrat poate fi adaptiv sau neadaptativ.

Era bine cunoscut faptul că multe criptosisteme utilizate pe scară largă erau vulnerabile la un astfel de atac și timp de mulți ani s-a crezut că atacul nu era practic și nu prezenta decât interes teoretic. Lucrurile au început să se schimbe la sfârșitul anilor 1990, mai ales când Daniel Bleichenbacher a demonstrat un atac practic bazat pe text cifrat asupra serverelor SSL folosind o formă de criptare RSA .

Atac neadaptativ

Într-un atac neadaptativ, criptoanalistul nu folosește rezultatele decriptărilor anterioare, adică textele cifrate sunt selectate în avans. Astfel de atacuri sunt numite atacuri la ora prânzului (ora prânzului sau CCA1).

Adaptive Attack

În cazul unui atac adaptiv, criptoanalistul selectează adaptiv un text cifrat care depinde de rezultatele decriptărilor anterioare (CCA2).

Reziliența la atacul adaptiv poate fi văzută pe exemplul jocului:

• Algoritmul de generare a cheii este lansat în schema de criptare cu lungimea cheii corespunzătoare furnizată ca intrare.
• Adversarul face o serie de cereri arbitrare oracolului de decriptare, decriptând astfel textele cifrate alese de el.
• Adversarul selectează două mesaje și le trimite la oracolul de criptare.
• Oracolul de criptare selectează aleatoriu un bit , apoi criptează , care este transmis adversarului (aruncarea monedei pentru a selecta bitul este ascunsă adversarului).
• Adversarul face din nou o serie de cereri arbitrare oracolului de decriptare cu singura restricție că cererea trebuie să fie diferită de mesajul primit de la oracolul de criptare.
• Adversarul dă un bit - valoarea așteptată a bitului ales de oracolul de criptare la pasul 4. Dacă , atunci superioritatea adversarului este considerată egală cu .

Problema discriminării Diffie-Hellman

Există mai multe formulări echivalente ale problemei discriminării Diffie-Hellman. Cel pe care îl vom folosi arată așa.

Fie un grup de ordin , unde este un număr prim mare. De asemenea  - . Și există două distribuții:

• Distribuția cvadruplelor aleatoare .
• Distribuția cvadruplelor , unde - sunt aleatoare și pentru aleatoriu .

Un algoritm care rezolvă problema Diffie-Hellman este un algoritm probabilistic care poate distinge efectiv între cele două distribuții enumerate. Adică, un algoritm care ia una dintre cele două distribuții ca intrare ar trebui să returneze 0 sau 1 și, de asemenea, tinde spre 0.

Problema discriminării Diffie-Hellman este grea dacă nu există un astfel de algoritm probabilistic polinomial.

Schema de bază

Să avem un grup de ordin , unde este un număr prim mare. Mesajele sunt elemente . De asemenea, folosim o familie generică de funcții hash unidirecționale care mapează șiruri lungi de biți la elemente , unde  — .

Generare cheie

Algoritmul de generare a cheilor funcționează după cum urmează:

• Alice generează elemente aleatorii și aleatorii
• calculează Alice .
• O funcție hash este selectată din familia universală de funcții hash unidirecționale. Cheia publică este , cheia privată este .

Criptare

Mesaj dat . Algoritmul de criptare funcționează după cum urmează

• Bob alege la întâmplare .
• Bob calculează următoarele valori:
  • ;
  • ;
  • , unde este o funcție hash universală unidirecțională;
  • ;
• Bob îi trimite textul cifrat Alicei.

Decriptare

După primirea textului cifrat și utilizarea cheii private :

• calculează Alice .
• Alice verifică starea . Dacă condiția nu este îndeplinită, atunci protocolul se încheie cu eșec de decriptare. În caz contrar, este afișat un mesaj .

Corectitudinea protocolului

Să verificăm corectitudinea schemei de criptare (decriptarea mesajului criptat dă același mesaj). Având în vedere că și , avem . De asemenea și . Prin urmare, verificarea decriptării reușește și este afișat mesajul original .

Diagrama simplificată

Diferențele față de schema de bază

Pentru a obține securitatea împotriva atacurilor neadaptative (și numai a acestora), puteți simplifica semnificativ protocolul fără a utiliza . Când criptăm, folosim , iar când decriptăm, verificăm că .

Un exemplu de circuit simplificat

Să presupunem că avem un grup de ordine . În consecință  - .