Algoritmul RSA

Algoritmul RSA

Singura problema este aceea ca avem nevoie de algoritmi care sa satisfaca complet toate cele trei cerinte. Datorita posibilelor avantaje ale criptografiei cu chei publice, multi cercetatori au lucrat din greu la acest subiect si au fost deja publicati cativa algoritmi. O metoda buna a fost descoperita de un grup de la MIT (Rivest s,.a. 1978). Ea este cunoscuta prim initialele numelor celor trei descoperitori (Rivest, Shamir, Adelman): RSA. Metoda 1or este bazata pe cateva principii din teoria numerelor. Vom rezuma mai jos modul in care se foloseste aceasta metoda; pentru detalii, a se consulta articolul.

1. Se aleg doua numere prime, p si q, (de obicei mai mari decat 10¹⁰⁰).

2. Se calcu1eaza n=p*q si z = (p-1)*(q-1).

3. Se alege un numar relativ prim cu z si este notat cu d.

4. Se gaseste e stfel incat e*d =1 mod z.

Cu acesti parametri calculati in avans, suntem gata sa incepem criptarea. Impartim textul clar (privit ca si de biti) in blocuri, astfel incat fiecare mesaj de text clar, P, sa intre in intervalul 0< P< n. Aceasta poate fi facuta grupand textul clar in blocuri de cate k biti, unde k este cel mai mare numar intreg pentru care inegalitatea 2^k<n este adevarata.

Pentru a cripta mesajul P, se calculeaza C = P (mod n). Pentru a decripta C, se calculeaza P = C^d(mod n). Se poate demonstra ca pentru toti P din intervalul specificat, criptarea si decriptarea sunt functii inverse una alteia. Pentru a realiza criptarea este nevoie de e si n. Pentru a realiza decriptarea este nevoie de d si n. De aceea, cheia publica consta din perechea (e, n) iar cheia privata din perechea (d, n)

Securitatea metodei este bazata pe dificultatea factorizarii numerelor mari. Daca un criptanalist factoriza numarul n (public cunoscut), el ar putea gasi p si q, iar din acestea pe z. Cu z si e cunoscuti criptanalistul il poate calcula pe d folosind algoritrnul lui Euclid. Din fericire, matematicienii au incercat sa factorizeze numere mari de cel putin 300 de ani si experienta acumulata sugereaza ca aceasta este o problema mai mult decat dificila.

In conformitate cu Rivest si colegii sai, factorizarea unui numar de 200 de cifre necesita un timp de calcul de patru miliarde de ani; factorizarea unui numar de cifre necesita 10²⁵ de ani. In ambele cazuri ei presupun ca se foloseste cel mai bun algoritm de factorizare si un calculator cu timp de executie unei instructiuni de 1msec. Chiar daca viteza calculatoarelor va continua sa sporeasca cu un ordin de marimea pe deceniu, vor mai trece secole pana cand factorizarea unui numar de cinci sute de cifre va devenii realizabila, moment in care descendentii nostri vor alege pur si simplu p si q mai mari.

Un exemplu didactic banal pentru algoritmul RSA este dat in Figura 2-8. pentru acest exemplu am ales p=3 si q=11, rezultand n=33 si z=20. o valoare potrivita pentru d este d=7, deoarece 7 si 20 nu au factori comuni. Cu aceste alegeri, e poate fi gasit prin rezolvarea ecuatiiei 7e=1(mod 20),care da e=3. Textul cifrat C, pentru textul clar al mesajului, P, este dat de C= P³ (mod 33). Textul cifrat este decriptat de catre receptor dupa regula P = C⁷ (mod 33). Figura prezinta ca exemplu criptarea si decriptarea textului clar "SUZANNE".

Deoarece numerele prime alese pentru acest exemplu sunt prea mici, P poate fi mai mic decat 33, astfel incat blocul de text clar poate contine doar un singur caracter. Rezultatul este un cifru cu substitutie monoalfabetica, nu foarte impresionant. Daca in locul acestora am fi ales p si q=10¹⁰⁰, am fi avut n = 10²⁰⁰ astfel incat fiecare bloc poate fi de pana la 664 biti (2⁶⁶⁴=10²⁰⁰) sau 83 de caractere de 8 biti fata de 8 caractere pentru DES.

Text clar(P) Text cifrat (C) Dupa decriptare

Simbolic Numeric P³ P³ (mod 33) C⁷ C⁷ (mod 33) Simbolic

S 19 6859 28 13492928512 19 S
U 21 9261 21 1801083541 21 U
Z 26 17576 20 1280000000 26 Z
A 01 1 1 1 1 A
N 14 2744 5 78125 14 N
N 14 2744 5 78125 14 N
E 05 125 26 8031810176 5 E

Calcul efectuat de emitator Calcul efectuat de receptor

Fig. 2-8. Un exemplu de algoritm RSA.

Trebuie subliniat ca folosirea RSA in modul descris este similara folosirii DES-ului in ECB - blocuri de intrare identice conduc la blocuri de iesire identice. De aceea este necesara o anumita forma de inlantuire pentru criptarea datelor. Totusi, in practica, multe sisteme bazate pe RSA folosesc criptografia cu cheie publica in principal pentru distribuirea cheilor de sesiune de unica folosinta utilizate pentru DES, IDEA sau alti algoritmi similari. RSA este prea lent pentru a cripta eficient volume mari de date.