Introduzione
-------------
Ho scritto alcuni tutorial sulla sicurezza e sulla crittografia, ma senza mai specificare nella pratica i tipi di problemi che ci possono essere in alcuni algoritmi fragili; nell'ultimo tutorial sulla crittografia in Java avevo promesso di parlare dell'algoritmo RSA per vedere come funziona un algiritmo robusto, collaudato e potente, ma prima ho pensato di parlare di algoritmi fai date e delle relative debolezze.
In questo articolo verrà analizzato l'algoritmo del CxC.

L'algoritmo
-----------
L'algiritmo è molto semplice, si ottiene il carattere ASCII, si aggiunge 1, si moltiplica per la chiave usata.
Facciamo un esempio pratico:

a    b    c
97 98  99

e come chiave usiamo 1234
Otteniamo questo:

98*1234 = 120932
99*1234 = 122166
100*1234 = 123400

E nel file quindi abbiamo

-120932-122166-123400-

Tenendo conto che il fatto di avere a disposizione un algoritmo non rende più o meno facile una forzatura(pgp ha libero l'algoritmo e al momento nessuno l'ha mai forzato, che si sappia) noi possiamo trovare la chiave o il testo originario, vediamo come trovare la prima.

Trovare la chiave
-----------------
Come avete notato ogni numero viene moltiplicato per lo stesso(la chiave), quindi il risultato sarà sicuramente divisibile da un CM(che non deve per forza essere un l'MCM) e i numero non saranno primi fra loro.
Sapendo questo possiamo ricorrere alla fattorizzazione dei numeri, sirucamente vi ricordere come funziona ma visto che siamo programmatori non faremo certo un lavoro così sporco a mano, ma useremo un programma, io ho usato il mio nella sezione C/C++ che al momento calcola solo 3 numeri, ma ci sono anche programmi simili che calconalo n numeri.
Usando il mio programma inseriamo i tre numeri visti sipra e otteniamo:

-----------
120932:2
60466:2
30233:7
4319:7
617:617

122166:2
61083:3
20361:3
6787:11
617:617

123400:2
61700:2
30850:2
15425:5
3085:5
617:617

mcm(120932, 122166, 123400) = 598613400
MCD(120932, 122166, 123400) = 1234
--------

Questa volta siamo stati più che fortunati, visto che la chiave era proprio l'MCM, ma nel caso non lo fosse si potrebbe semplicemente fattorizzare anche l'MCM per trovare tutte le chiavi possibili, vediamo ad esempio:

c      i      a
99 105   97

otteniamo

100 * 1234 = 123400
106 * 1234 = 130804
98 * 1234 =  120932

Fattorizzando otteniamo:

---------------
123400:2
61700:2
30850:2
15425:5
3085:5
617:617

130804:2
65402:2
32701:53
617:617

120932:2
60466:2
30233:7
4319:7
617:617

mcm(123400, 130804, 120932) = 320469800
MCD(123400, 130804, 120932) = 2468
--------------------

Adesso noi sappiamo che il numero più grande che può dividere i risultati è 2468 e quindi sappiamo che è la chiave più grande possibile, per trovarle tutte come detto prima basta fattorizzare anche lui e otteniamo:

--------
2468:2
1234:2
617:617

mcm(2468, 1, 1) = 2468
MCD(2468, 1, 1) = 1
-------

Ed ecco che fra i possibili divisori c'è anche 1234; se poi il numero scelto come chiave fosse pure primo sarebbe ancora più facile da individuare.
Naturalmente questa strada si complica se avessimo a che fare con numeri molto grandi, ma per nostra sfortuna(o fortuna dipende) c'è un altro problema che ci può aiutare, e questo mi riporta al secondo paragrafo.

Trovare il testo
---------------
Un altro tipico problema degli algoritmi fai da te è l'analisi delle frequenze, questo spesso avviene in algoritmi che si basano sun un ECB quindi ogni blocco, ogni carattere o ogni unità di codifica viene codificata sempre allo stesso modo ed è indipendente dal resto del codice cifrato, ad esempio una parola particolare come:

  r        a      d      a     r
114    97   100   97  144

codificata con una qualsiasi chiave(mettiamo 1989) otteniamo:

115 * 1989 = 228735
98 * 1989 = 194922
101 * 1989 = 200889
98 * 1989 = 194922
115 * 1989 = 228735

oltre che essere palindroma come parola chiara e anche come parola codificata ha delle lettere che si ripetono e potremmo trasrcivere in:

a - b -c - b - a

e a questo punto diventa come giocare all'impiccato visto che alla posizione 1 e 5 c'è la stessa, alla 2 e 4 anche e una unica nelle 3.
Usando poi una tabella delle frequenze(ad esempio in inglese la 'e' è la lettera più frequente) si riduce ancora di più il campo.

Un altro trucchetto è quello di cercare i numeri che finiscono con degli 0(zeri) e quindi provarle togliendone 2 di 0; ad esempio nel primo test abbiamo visto che la 'c' veniva codificata con 123400, togliendo gli 00 avevamo la chiave servita; putrtoppo 100 viene fuori come primo moltiplicatore solo se la lettera è una 'c', fosse stata una vocale era ancora più facile(molto più frequente).

Conclusione
------------
bhè questo era solo un piccolo esempio, per trovare altre vie basta analizzare i numeri e trovare altre coincidenze, altre relazioni fra lettera e risultato(ad esempio le vocali alla base saranno sempre quelle, tutte le lettere sono sempre quelle: ASCII + 1).
Ciao e buon divertimento.

Disponibile su forum o via email.