Algoritmul de criptare a datelor
cu cheie publică RSA
Algoritmul de criptare a cheilor publice este cel mai curent (RSA - Rivest, Shamir și Aldeman - inventatorii săi).
Un număr prime se împarte numai cu 1 și în sine;
În mod simplu, nu au divizor comun decât 1;
Rezultatul operației i mod j este restul diviziunii întregi a lui i de către j.
Pentru a utiliza algoritmul RSA, trebuie mai întâi să generați cheile publice și private, parcurgând pașii următori:
1) Alegem două numere prime foarte mari p și q.
2) Definiți n ca rezultat al înmulțirii p pe q (n = p * q).
3) Alegem un număr aleatoriu mare, pe care îl numim d. Acest număr trebuie să fie relativ prime cu rezultatul de multiplicare (p-1) * (q-1).
4) Definiți un număr e pentru care relația următoare (e * d) mod ((p-1) * (q-1)) = 1 este adevărată.
5) Apelam cheia publică e și n, iar cheia secretă este numerele d și n.
Acum, pentru a cripta datele de pe o cheie cunoscută, trebuie să faceți următoarele:
- spargeți textul criptat în blocuri, fiecare dintre acestea reprezentând un număr M (i) = 0,1,2. n-1 (adică numai până la n-1).
- criptează textul, considerat ca o secvență de numere M (i) cu formula C (i) = (M (I) ^ e) mod n.
Pentru a decripta aceste date folosind o cheie secretă, este necesar să efectuăm următoarele calcule: M (i) = (C (i) ^ d) mod n. Ca urmare, se va obține un set de numere M (i) care reprezintă textul sursă.
Pentru a prezenta mai clar algoritmul RSA, voi da următorul exemplu:
Noi criptăm și descifrăm mesajul "SAV" prin algoritmul RSA. Pentru simplitate, voi folosi numere mici (în practică - trebuie să luați mai multe).
1) Alegeți p = 3 și q = 11.
2) Definiți n = 3 * 11 = 33.
3) Gasim (p-1) * (q-1) = 20. Prin urmare, d va fi, de exemplu, 3: (d = 3).
4) Alegem numărul e prin următoarea formulă: (e * 3) mod 20 = 1. Aceasta înseamnă că e va fi, de exemplu, 7: (e = 7).
5) Imaginați mesajul criptat ca o secvență de numere în intervalul de la 0 la 32 (nu uitați că se termină în n-1). Scrisoarea A = 1, B = 2, C = 3.
Acum criptăm mesajul folosind cheia publică
C1 = (3 ^ 7) mod 33 = 2187 mod 33 = 9;
C2 = (1 ^ 7) mod 33 = 1 mod 33 = 1;
C3 = (2 ^ 7) mod 33 = 128 mod 33 = 29;
Acum decodificăm aceste date utilizând cheia privată.
M1 = (9 ^ 3) mod 33 = 729 mod 33 = 3 (C);
M2 = (1 ^ 3) mod 33 = 1 mod 33 = 1 (A);
M3 = (293) mod 33 = 24389 mod 33 = 2 (B);
Totul, datele sunt descifrate.
Rezistența criptografică a algoritmului RSA se bazează pe presupunerea că este extrem de dificil să se determine cheia secretă de către cea cunoscută, deoarece pentru aceasta este necesară rezolvarea problemei existenței divizoarelor întregi. Această problemă este NP-completă și, ca o consecință a acestui fapt, nu permite o soluție eficientă (polinomică). Mai mult decât atât, însăși problema existenței unor algoritmi eficienți pentru rezolvarea problemelor NP-complete este până în prezent deschisă. Dacă utilizați numere formate din 200 de cifre (pe care ar trebui să le utilizați atunci când criptați date), va trebui să generați un număr mare de operații (aproximativ 10 ^ 23) pentru decriptare neautorizată.
P.S / Datele de mai sus nu ar trebui utilizate în scopuri ilegale!
[a apărut o eroare în timpul procesării acestei directive]