Questo sito contribuisce alla audience di

L'algoritmo RSA

Ecco come si realizza l'algoritmo a chiave pubblica RSA. L'articolo è tratto dalla tesi di laurea in "Applicazione delle tecniche di crittografia nella trasmissione ed elaborazione dati" redatta dall'ingegnere Federico Gennari nell'anno accademico 2000/2001.

RSA
Chiave Pubblica = (n,e) (cifratura)

n = (p*q)                    (prodotto di due numeri primi arbitrari di circa 100 cifre)

e                                  (numero scelto casualmente tale che sia primo a (p-1)*(q-1). Per poche cifre di p e q, si può stabilire come )

Chiave Privata = (n,d)  (decifratura)

d = (e-1) mod[(p-1)(q-1)]                   (notare che d*e = mod[(p-1)(q-1)]

                                                                                   =[A*(p-1)(q-1)+1] mod[(p-1)(q-1)]

                                                           ovvero 1 più un numero intero A di (p-1)(q-1)

                                                           Inoltre la funzione Eulero phi (n) = (p-1)(q-1) )

Cifratura

c = (te) mod n             (dove c è il testo cifrato e t il testo in chiaro)

Decifratura

t = (cd) mod n             (notare che [t4 mod n] = [t * [(t3) mod n] mod n]

      [t5 mod n] = [t * [(t4) mod n] mod n]

in modo che i calcoli intermedi non superino mai n2 in quantità)

Un generico ricevente genera p e q numeri primi e quindi si calcola n, sceglie e, calcola d ed infine distrugge p e q. Il ricevente distribuisce pubblicamente la coppia (n,e). tenendo per sé il numero d segreto. Una persona che gli voglia mandare un messaggio cifrato usa la coppia (n,e) del ricevente, questi per le leggerlo usa la sua coppia (n,d). Notare che dopo l’uso della coppia pubblica neppure il mittente può decifrare il messaggio base t dopo la sua conversione nel testo cifrato c.

Esempio

Codifica con RSA del messaggio “MY MISTRESS’ EYES ARE NOTHING LIKE THE SUN. ” per mezzo dell’alfabeto “ABCDEFGHIJKLMNOPQRSTUVWXYZ,.’ ” Il testo viene convertito in un equivalente numerico M: la stringa “ABCD” viene interpretata come il numero in base 30 dato da A ·303+B ·302+C ·30+D, e poi ad A viene assegnato il valore 0, a B il valore 1, e cos´ı via, dove sta per lo spazio ed ha equivalente numerico 29. Inoltre sono stati scelti i seguenti valori dei parametri: p = 1069, q = 1973, n = pq = 2109137, (n) = 2106096, e = 10001, dº  e−1 mod (n) = 40433.

|Testo                           |M                    |C = Me mod n

M    Y    _    M            346482            888745

 I     S     T    R            232787            1201313

E     S     S     ’            124768            1174612

_     E     Y    E            787324            636449

S     _     A    R            512117            227442

E     _     N    O           134504            1999438

T     H     I     N           519553            483208

G     _     L     I            188438            983073

K    E      _    T            274489            1326351

H    E      _    S            193488            151797

U    N      .     _            552539            1507154

I criteri di scelta dei parametri sono: p e q grandi e di lunghezza circa uguale, mentre e piccolo e primo rispetto (n) (tipicamente è identico per tutti gli utenti). All’inizio il valore suggerito di e era di 3, mentre adesso si usa o 17 o  216-1 = 65535 ( questo per evitare un tipo di attacco basato sul CRT, mandando lo stesso messaggio a tre persone diverse che hanno tutti e=3 ma moduli diversi, nella bibliografia si trovano i testi dove tale attacco è ben discusso). A questo punto d verrà molto grande. Per il calcolo di d si usa l’algoritmo esteso di Euclide oppure il calcolo del MCD binario.

Se si sceglie una chiave a 768 bit, poco indicata se non per messaggi di poco valore, i numeri primi devono avere lunghezza approssimativamente di 384 bit; in genere però la lunghezza consigliata della chiave è 1024 bit, fino a 2048 bit per messaggi ad alto rischio o valore.

Raddoppiare la lunghezza della chiave o del modulo n, aumenta di un fattore quattro il tempo necessario per le operazioni pubbliche (cifratura e verifica delle firme) e di un fattore otto il tempo per le operazioni private (decifratura e firma), mentre il tempo di generazione di una chiave lunga il doppia aumenta di un fattore 16, ma questa è un’occasione alquanto rara per la grande maggioranza degli utenti.

Per velocizzare le operazioni attuate dall’algoritmo esistono vari metodi, alcuni dei quali citati nell’appendice 5.

Ecco alcuni algoritmi usati per la fattorizzazione di n = p q, da cui ricavare d:

- Divisione semplice (Trial division): il più vecchio e meno efficiente. Tempo di lavoro esponenziale. Prova tutti i numeri primi minori della radice quadrata di n (sqrt(n) ).

- Setaccio quadratico (Quadratic Sieve (QS)): l’algoritmo più veloce per numeri minori di 110 cifre.

- Setaccio quadratico a polinomi multipli (Multiple Polynomial Quadratic Sieve (MPQS)): versione più veloce del QS.

- Variazione di numeri primi doppiamente lunghi del MPQS: ancora più veloce.

- Setaccio del campo numerico (Number Field Sieve (NFS)): correntemente l’algoritmo conosciuto come più veloce per i numeri superiori a 110 cifre). Fu usato per fattorizzare il nono numero di Fermat.

I migliori algoritmi hanno tempo sub esponenziale, mentre il NFS ha tempo asintotico stimato come il più vicino al comportamento polinomiale (*)

(*) 

Gli algoritmi di fattorizzazione si dividono in due classi, quelli di proposito generale (general purpose) che ci interessano maggiormente, e quelli di proposito specifico (special purpose), che si riferiscono alla fattorizzazione di piccoli numeri e non è il nostro caso.

Gli algoritmi a proposito speciale includono il metodo rho Pollard, con tempo medio , ed il metodo Pollard p-1, con tempo di lavoro O(p’) dove p’ è il più grande fattore primo di p-1 (esiste anche una variante con p+1). Tutti questi usano una quantità di tempo che è esponenziale con la grandezza (lunghezza in bit) di p, il fattore primo che cercano, e sono troppo lenti per la maggior parte degli impieghi. Il metodo della curva ellittica (ECM) è superiore, con tempo asintotico di ; l’ECM in genere è usato per cercare fattori di numeri generati casualmente ma non è abbastanza veloce per i moduli grandi come quelli usati nell’RSA.

Il migliore algoritmo di fattorizzazione di  proposito generale è il setaccio del  campo di numeri (Number Field Sieve, NFS), che lavora per un tempo che è approssimativamente , mentre prima il primato era detenuto dal setaccio quadratico multi polinomiale (Multiple Polinomial Quadratic Sieve, MPQS) con tempo di lavoro .