Criptosistemul Rabin
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 17 august 2021; verificarea necesită 1 editare .Criptosistemul Rabin este un sistem criptografic cu cheie publică a cărui securitate este asigurată de dificultatea de a găsi rădăcini pătrate în inelul de reziduuri modulo un număr compus . Securitatea sistemului, ca și securitatea metodei RSA , se datorează dificultății de factorizare a numerelor mari. Un mesaj criptat poate fi decriptat în 4 moduri. Dezavantajul sistemului este necesitatea de a selecta un mesaj adevarat din 4 posibile.
Istorie
În ianuarie 1979, Michael O. Rabin a publicat o descriere a sistemului său. S-a dovedit că restaurarea textului simplu din text cifrat este la fel de dificilă precum factorizarea numerelor mari. Sistemul lui Rabin a devenit primul criptosistem asimetric pentru care a fost efectuată o astfel de dovadă. Complexitatea recuperării este legată de dificultatea extragerii rădăcinii pătrate modulo un număr compus N = p · q . Problema factorizării și problema rădăcinii pătrate sunt echivalente, adică:
- cunoscând divizorii primi ai numărului N , se pot extrage rădăcinile pătrate modulo N ;
- știind cum să extragem rădăcini pătrate modulo N , se poate factoriza N în factori primi.
Generare cheie
Sistemul Rabin, ca orice criptosistem asimetric , folosește o cheie publică și una privată. Cheia publică este folosită pentru a cripta mesajele și poate fi eliberată publicului. Cheia privată este necesară pentru decriptare și ar trebui să fie cunoscută numai de destinatarii mesajelor criptate.
Procesul de generare a cheilor este următorul:
- două numere aleatoare p și q sunt alese ținând cont de următoarele cerințe:
- numerele trebuie să fie mari (vezi adâncimea de biți );
- numerele trebuie să fie prime ;
- trebuie îndeplinită următoarea condiţie: p ≡ q ≡ 3 mod 4 .
- se calculează numărul n = p · q ;
- numărul n este cheia publică; numerele p și q sunt închise.
Exemplu. Fie p = 7 și q = 11 . Atunci n = p · q = 7 · 11 = 77 . Numărul n = 77 este cheia publică, iar numerele p = 7 și q = 11 sunt cheia privată. Destinatarul le spune expeditorilor numărul 77. Expeditorii criptează mesajul folosind numărul 77 și îl trimit destinatarului. Destinatarul decriptează mesajul folosind numerele 7 și 11. Cheile date sunt proaste pentru utilizare practică, deoarece numărul 77 este ușor de descompus în factori primi (7 și 11).
Criptare
Mesajul original m (text) este criptat folosind cheia publică - numărul n conform următoarei formule:
c = m² mod n .Datorită utilizării înmulțirii modulo, viteza de criptare a sistemului Rabin este mai mare decât viteza de criptare a metodei RSA , chiar dacă în acest din urmă caz se alege o valoare mică a exponentului.
Exemplu (continuare). Fie textul sursă m = 20 . Atunci textul cifrat ar fi: c = m² mod n = 20² mod 77 = 400 mod 77 = 15 .
Decriptare
Pentru a decripta mesajul, aveți nevoie de o cheie privată - numerele p și q . Procesul de decriptare este următorul:
- mai întâi, folosind algoritmul Euclid , numerele și se găsesc din ecuația ;
- apoi, folosind teorema chineză a restului , se calculează patru numere:
Exemplu (sfârșit). Ca rezultat al decodării obținem: . Vedem că una dintre rădăcini este textul original m .
Evaluarea algoritmului
Eficiență
Descifrarea textului, pe lângă cel corect, duce la încă trei rezultate false. Acesta este principalul dezavantaj al criptosistemului Rabin și unul dintre factorii care l-au împiedicat să găsească o utilizare practică largă.
Dacă textul sursă este un mesaj text, atunci determinarea textului corect nu este dificilă. Cu toate acestea, dacă mesajul este un flux de biți aleatori (de exemplu, pentru a genera chei sau o semnătură digitală ), atunci determinarea textului corect devine o problemă reală. O modalitate de a rezolva această problemă este să adăugați un antet cunoscut sau un fel de etichetă la mesaj înainte de criptare.
Viteza de calcul
Algoritmul Rabin este similar cu codificarea RSA, dar în loc să ridice mesajul la puterea e , criptarea folosește operația de pătrare a blocului de mesaje, care afectează favorabil viteza algoritmului fără a sacrifica puterea criptografică.
Pentru decodare, se aplică teorema chineză a restului împreună cu două exponențiații modulo. Aici eficiența este comparabilă cu RSA.
Selectarea textului dorit dintre cele patru duce la costuri de calcul suplimentare. Și acest lucru a servit pentru a se asigura că criptosistemul Rabin nu a primit o utilizare practică largă.
Securitate
Marele avantaj al criptosistemului Rabin este că textul aleatoriu poate fi recuperat în întregime din textul cifrat numai dacă decriptorul este capabil să factorizeze eficient cheia publică n.
Un criptosistem Rabin este rezistent la un atac cu totul sau nimic bazat pe un atac cu text cifrat simplu, dacă și numai dacă problema factorizării unui număr întreg în factori primi este insolubilă.
Securitatea all-or-nothing înseamnă că, având un text criptat cu un anumit algoritm, un atacator trebuie să recupereze un bloc din textul original, a cărui dimensiune este de obicei determinată de parametrul de securitate al criptosistemului. Având în vedere originalul și textul cifrat, atacatorul trebuie să recupereze întregul bloc de cheie privată . În acest caz, atacatorul fie obține un succes complet, fie nu primește nimic. Cuvântul „nimic” înseamnă că atacatorul nu are nicio informație secretă nici înainte, nici după un atac nereușit.
Criptosistemul lui Rabin este complet lipsit de apărare împotriva atacurilor bazate pe textul cifrat ales . De regulă, atacatorul folosește toate posibilitățile pe care le are. El ia contact cu utilizatorul atacat, îi trimite textul cifrat pentru decriptare ulterioară și cere returnarea textului original.
De exemplu, adăugarea redundanței, cum ar fi repetarea ultimilor 64 de biți, poate face rădăcina unică. Algoritmul de decriptare în acest caz produce o singură rădăcină, care este deja cunoscută atacatorului.
Procesul este vulnerabil în plus, deoarece numai reziduurile pătrate sunt utilizate în codificare. În exemplul cu n = 77, sunt folosite doar 23 din 76 de stări posibile.
Vezi și
Literatură
- Mao V. Criptarea - metode asimetrice // Criptografia modernă : Teorie și practică / transl. D. A. Klyushina - M . : Williams , 2005. - 768 p. — ISBN 978-5-8459-0847-6
- Schneier B. Criptografia aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .