Come probabilmente sapete, l’algoritmo RSA è uno dei più famosi algoritmi di crittografia a chiave pubblica: questo significa che chiunque può mandarci un messaggio cifrato, usando appunto la chiave pubblica, ma solo noi possiamo decodificarlo. L’algoritmo è tendenzialmente questo:

(a) Scegliamo due numeri primi molto grandi p e q.
(b) Calcoliamo n = pq e φ(n) = (p−1)(q−1).
(c) Scegliamo una chiave di crittazione e che sia un numero relativamente primo rispetto a φ(n). (La lettera “e” sta per “encryption”, se ve lo foste chiesti.)
(d) Calcoliamo la chiave di decrittazione d tale che ed = 1 (mod φ(n)).
(e) Pubblichiamo e e n, mantenendo segreti d, p e q.

La logica della crittografia RSA è che se conosciamo p e q possiamo calcolare “facilmente” n, φ(n) e d, ma non è possibile trovare d senza fattorizzare n, e almeno per il momento la fattorizzazione non è facile da fare, checché si dica delle meraviglie dei computer quantistici.

La cosa buffa è che di solito (pare nel 99,5% dei casi in un sondaggio compiuto da due ricercatori) i punti (b) e (c) si invertono: si sceglie prima e e poi si prendono i due primi, verificando che φ(n) sia primo rispetto a e. E soprattutto non si sceglie e a caso, ma si usa 65537. Come mai? John D. Cook lo spiega esaurientemente: è abbastanza grande perché φ(n) sia relativamente primo (se non lo è, bisogna trovare altri p e q) ed essendo uno più una potenza di 2 si risparmia sui calcoli. C’è addirittura chi ha usato e = 3, ma li si esagera. In realtà, continua Cook, usare un e troppo piccolo può far correre il rischio che qualcuno che ha accesso al computer dove sono stati fatti i conti riesce a trovare alcuni dei bit del numero, e in questo caso ci sono algoritmi più rapidi per decrittare a forza bruta. E scegliere un altro primo? Il punto è che e non è semplicemente una potenza di due più uno, ma un numero primo di Fermat: ne conosciamo solo 5 (3, 7, 17, 257, 65537), e anche se ce ne fosse un altro sarebbe così grande da risultare impraticabile…

Insomma, all’atto pratico abbiamo una semplificazione dell’algoritmo, visto che non scegliamo più e; ma la prossima volta vedremo che ce n’è un’altra.