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.
In questo libro Briggs presenta un gran numero di esercizi, che probabilmente almeno in Italia possono essere anche dati agli studenti degli ultimi due anni delle superiori. Ma la parte degli esercizì è forse la meno interessante (tra l’altro non tutti gli esercizi hanno una soluzione, anche se c’è la risposta e un “aiuto” che però a volte è inutile). Poi c’è una parte curiosa, i commenti a margine del testo. Ma ciò che è davvero interessante è la parte introduttiva dei capitoli, dove Briggs spiega come approcciare le varie di problemi. Uno studente brillante può sfruttare queste spiegazioni per imparare a risolvere i problemi: d’altra parte, i professori hanno invece un certo numero di problemi se vogliono fare delle verifiche.