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.
Livio Galla, a parte fare l’avvocato, è uno scrittore molto eclettico: in questa sua opera si è cimentato nel romanzo storico, partendo dalla storia di Alessandro Rossi che prese l’azienda laniera paterna e la fece diventare la più grande d’Italia (avete presente la Lanerossi?) pensando contemporaneamente al benessere degli operai, perché potessero lavorare più tranquilli. La storia intreccia fatti reali, anche se modificati (l’incontro tra Rossi e Garibaldi, o il soprano Teresita Stolzi la cui nascita è stata anticipata) con altri inventati, come la famiglia Sella e la loro sartoria le cui storie si intrecciano con quella dei Rossi. Sullo sfondo troviamo anche l’occupazione austriaca del Veneto: il lanificio Rossi si trova infatti a Schio. Il racconto è avvincente: unica pecca che ho trovato sono le note sui pensieri e comportamenti dei protagonisti, che sono un po’ troppo di maniera. 
Vi ricordate di 2048, il gioco dove dovevate ottenere la maggior potenza di due possibile? Anche