Alice, Bob e Eva — La radice discreta

“Un altro sistema che potrebbe avere Alice per decrittare la codifica RSA senza conoscere φ(n) è quello di calcolare la radice discreta”.

“Cosa sarebbe?”.

“Bob, per codificare m, ha usato la formula c ≡ m^e mod n. Potremmo dire che m è la radice discreta e-esima di c, in analogia a quanto si fa con i numeri reali”.

“Ah”.

“Ad oggi non è noto alcun metodo per calcolare la radice discreta in modo veloce. Come al solito, però, non si sa se in futuro questo metodo verrà trovato oppure no. Tra l'altro, questo problema potrebbe essere anche più semplice del problema della fattorizzazione”.

“Perché?”.

“Perché mediante la fattorizzazione si può calcolare la chiave privata di Alice e, quindi, decrittare ogni messaggio destinato ad Alice. Estraendo la radice discreta del messaggio, invece, si può decrittare solo quel singolo messaggio. E, forse, decrittare un unico messaggio può essere più semplice che decrittare ogni messaggio”.

“Insomma, non si sa niente e si spera che le cose vadano bene”.

“Esattamente. Un'altra cosa carina alla quale bisogna stare attenti, ma che non capita molto spesso, è quella dei messaggi che rimangono fissi”.

“Eh?”.

“Ti faccio un esempio. Ricordi quando abbiamo fatto una prova con RSA utilizzando la chiave pubblica (n,e) = (16637,11)?”.

“Sì”.

“Prova a crittare questo messaggio: m = 2793”.

“Ecco: 2793¹¹ mod 16637 = 2793. Ehi, come è possibile?”.

“Eh, succede. Nei casi reali, con numeri giganteschi, succede rarissimamente, ma bisogna stare comunque attenti. In questo caso, con numeri piccoli, succede 32 volte. Ti lascio come esercizio il calcolo”.

“Mamma mia, mi sembra che questa crittografia sia un sistema sempre meno sicuro”.

“Eh, in genere il sistema è sicuro, ma ci possono essere tanti piccoli casi particolari che lo rendono facilmente attaccabile. Ma, a volte, può essere colpa dell'utente”.

“In che senso?”.

“Supponi che due utenti utilizzino due esponenti diversi, ma lo stesso n. Avrebbero, in pratica, due chiavi di questo tipo: (n,e₁), (n,e₂). Bob invia lo stesso messaggio m ai due utenti: esso verrà crittato in due modi diversi, naturalmente”.

“Sì, si fanno due calcoli diversi: c₁ = m^e₁ mod n, c₂ = m^e₂ mod n”.

“Bene. Eva li intercetta tutti e due, e calcola preventivamente due numeri a e b in modo tale che ae₁ + be₂ = 1”.

“Ah, una equazione diofantea. Queste ho imparato a risolverle”.

“Perfetto. Allora calcola anche c₁^a c₂^b”.

“Vediamo: c₁^a c₂^b = m^ae₁ m^be₂ = m^{ae₁ + be₂} = m¹ = m. Ehi, Eva decritta il messaggio!”.

“Eh, sì. Quindi è imperativo usare n diversi. Ma con 150 cifre a disposizione, c'è abbondanza di numeri primi”.

“Ci sono altri problemi?”.

“Ce ne sono di complicati, casi particolari in cui la fattorizzazione è veloce, e cose del genere. Quelli li lascerei perdere, mentre vorrei raccontarti un'ultima situazione critica che potrebbe compromettere la sicurezza”.

“Quale?”.

“Supponi di essere in guerra, per fare un esempio. Tu devi spedire con regolarità dei messaggi in cui trasmetti le coordinate per una ricognizione, o un bombardamento, o che so io. I tuoi messaggi potrebbero essere creati automaticamente, potrebbero avere una struttura standard ed essere diversi solo nel punto in cui scrivi le coordinate”.

“Sì, giusto”.

“Allora Eva potrebbe semplicemente creare tutti i possibili messaggi che tu puoi spedire, crittarli tutti quanti con la chiave pubblica di Alice, e confrontare il suo dizionario di messaggi con il messaggio che ha appena intercettato”.

“Oh cavolo, così riuscirebbe a decrittare quello che scrive Bob senza rompere RSA”.

“Esatto. Per evitare questi problemi si usa una tecnica chiamata padding”.

“In cosa consiste?”.

“Consiste nell'inserire dei caratteri casuali qua e là all'interno del messaggio, in modo da non avere mai due messaggi che sono diversi per pochi caratteri”.

“Caratteri casuali?”.


“Sì, se io volessi spedirti il messaggio Ci vediamo domani potrei, prima di crittarlo, modificarlo in Topolino Ci Pippo vediamo Pluto domani. Noi siamo già d'accordo che i personaggi dei fumetti devono essere cancellati dal messaggio, naturalmente”.

“Ah. E se Eva intercetta questo nostro accordo?”.

“Nessun problema: anche se lei è a conoscenza di questa modifica, non sa quali siano i nomi dei personaggi che io voglio usare, e non sa dove li inserisco. Quindi il suo attacco basato sullo schema fisso dei messaggi non funziona più. Il sistema usato nella realtà si chiama Optimal Asymmetric Encryption Padding”.

“Peccato, mi sarebbe piaciuto un Comics and Cartoons Encryption Padding”.

“Eh, vabbé, non si può avere tutto. Ti lascio un esempio reale di codice crittato con RSA. Il messaggio è un testo codificato in questo modo: A = 01, B = 02, …, Z = 26, e lo spazio è uguale a 00”.

“Ok”.

“Vado a capo perché non ci sto:”.

n = 11438162575788886766923577997614661201021829672124236256256184293
    5706935245733897830597123563958705058989075147599290026879543541

e = 9007

c = 9686961375462206147714092225435588290575999112457431987469512093
    0816298225145708356931476622883989628013391990551829945157815154

⇐ · ⇒