La scorsa settimana ho scritto che anche se la struttura logica dell’algoritmo RSA ha cinque parametri, ma la chiave di cifratura e è quasi sempre settata a 65537, per ragioni di efficienza computazionale e perché non dovrebbe dare problemi di sicurezza (almeno nei casi normali). Ma c’è anche un’altra modifica che è stata fatta negli anni, sempre per ridurre il costo computazionale (che nel caso della crittografia a chiave pubblica è molto più alto che nei sistemi di crittografia simmetrici).
Ricordo che nell’algoritmo RSA viene calcolato φ(n) = (p−1)(q−1), dove p e q sono i numeri primi di partenza, il cui prodotto è n, e φ(n) è la funzione φ di Eulero, cioè quanti sono i numeri minori di n e che non hanno fattori primi in comune con n. Nel nostro caso è facile calcolare il “toziente” (altro nome con cui è nota la funzione φ di Eulero), proprio perché p e q sono primi.
Non è però necessario usare φ(n) per scegliere un d tale che ed = 1 (mod φ(n)). È infatti sufficiente usare la funzione di Carmichael λ(n), definita come il più piccolo intero positivo m tale che am ≡ 1 (mod n) per ogni a coprimo con n. Si può dimostrare che λ(n) è un divisore di φ(n), e quindi è un numero più piccolo e pertanto le operazioni di computazione sono più brevi. Ma di quanto lo sono? Di un fattore MCD(p−1, q−1). Chiaramente entrambi i numeri sono pari e quindi c’è un fattore 2, ma si potrebbe sperare che ci sia qualcosa in più. John Cook ha fatto qualche prova, e ha trovato che su 100 coppie di numeri generati casualmente, la mediana del MCM è 2 (quindi in almeno metà dei casi il fattore è effettivamente 2); c’è stato un caso in cui si è arrivati a 2370, mentre il valore medio (poco utile in questo caso, perché a noi serve una sola coppia) è stato 35,44. In pratica, insomma, abbiamo quasi sempre 2 o 4 come fattore comune, In altri termini, se dobbiamo usare spesso una chiave può valer la pena di cercare una coppia di primi per cui λ(n) è effettivamente molto minore di φ(n), altrimenti possiamo far finta di niente.