Crittografia

La soluzione di Shannon dei cifrari classici

L'articolo è tratto dalla tesi di laurea in "Applicazione delle tecniche di crittografia nella trasmissione ed elaborazione dati" redatta dall'ingegnere Federico Gennari nell'anno accademico 2000/2001.

5.5 – metodi proposti da Shannon per la soluzione di cifrari classici

Ed ora rivolgiamo l’attenzione alle generalità sulla soluzione dei crittogrammi prodotti dai cifrari classici (quelli moderni si basano sulla elaborazione di grosse masse di numeri piuttosto che sullo studio del testo). Pur non essendo tanto rigoroso da  costruirci sopra dei teoremi, le conclusioni esposte sono sostanzialmente corrette e fondate.

Innanzi tutto si suppone di conoscere la famiglia di trasformazioni T_i e le relative probabilità delle chiavi. Per quanto possa sembrare improbabile ci sono due risposte a ciò:

-   L’indecisione tra più tipi di cifratura è risolta con una somma pesata dalle loro probabilità, in accordo alla migliore stima della loro probabilità a priori. Es. T=pR+qS  (dove p+q=1, prob. a priori. Scelta aleatoria tra due sistemi R e S diversi, ognuno con prob. p e q di essere scelto)

- Nei panni di un progettista, questo risulta essere il caso peggiore, una situazione di sicurezza in cui mettersi, e alla lunga bisogna aspettarsi che si verifichi sul serio.

1) Forza bruta, ovvero tentare sistematicamente tutte le chiavi fino a trovare la soluzione, detta anche ricerca esaustiva della chiave. Questo risulta assai poco pratico, e lo si può vedere con un esempio: un semplice cifratore a sostituzione cambia ogni lettera dell’alfabeto corrente con un rimpiazzo fisso, un'altra lettera in genere. Ne deriva un nuovo alfabeto, permutazione di quello corrente. Con 21 lettere (26 in Inglese), ci sono 21! modi diversi di disporre le lettere e quindi generare un nuovo alfabeto, provarli tutti risulta molto difficile (anche se non è più impossibile con l’hardware moderno a basso costo. Il cifrario DES, di cui parleremo più avanti, è stato scardinato esattamente in questo modo). In realtà si tenta sempre un metodo esaustivo, ma con un accorgimento. Si divide lo spazio delle chiavi in S sottoinsiemi equiprobabili (S=2 minimizza i passaggi, ma non sempre la probabilità delle chiavi lo permette) e si cerca se possibile un test di consistenza per l’intero gruppo. Trovato il gruppo che contiene la chiave giusta, si riapplica la suddivisione in sottogruppi, e per ognuno si applica il test, e così via fino a trovare la chiave. Mentre la ricerca esaustiva richiede un   numero di tentativi dell’ordine del numero di chiavi, adesso l’ordine è della grandezza della chiave in bit; esattamente il numero di tentativi è _. Questo perché dividere in S sottoinsiemi massimizza l’informazione ottenuta ad ogni prova fino a log S, ed il numero aspettato di prove è l’informazione totale da ottenere, che è H(K) diviso per questa quantità.

A volte non si ha bisogno di supporre la chiave intera per applicare un test di consistenza, si può testare anche una supposizione di parte della chiave. In altre parole è possibile risolvere la chiave bit a bit facendo test su parte della chiave (*). Lo stesso effetto si può vedere in tutti i cifrari elementari come nel Vigenère, dove la supposizione di due o tre lettere della chiave è facilmente testata decifrando in altri punti con questo frammento e notando se emerge qualcosa di chiaro. Una prima conclusione è che un ammontare considerevole di chiave deve essere usato per cifrare ogni piccolo elemento del messaggio.

2)     Metodi statistici. In genere in metodi statistici funzionano così:si misura una certa statistica S sul crittogramma E, esempio la frequenza delle lettere nei cifrari a sostituzione che è la statistica principe per molti cifrari classici, identica in valore per tutti i messaggi ragionevoli M (per cui indipendente da M) [2] Il valore ottenuto serve per limitare le possibili chiavi a solo quelle che danno valori di S vicini a quello osservato (notare che se la statistica S non dipende dalla chiave K o varia oltre che con K anche con M in maniera assai determinante, essa non è limitante per K. La frequenza delle lettere varia molto marginalmente col messaggio). 

Si può dunque assegnare un certo potere risolvente a S, e per ogni suo valore ci sarà un’equivocazione condizionata della chiave H(K|S); questo è tutto quello che si sa della chiave. La media pesata di questi valori   da un’equivocazione media della chiave quando S è noto. La grandezza della chiave H(K) meno questa equivocazione media da il potere risolvente di S. Nei sistemi fortemente ideali, tutte le statistiche sono indipendenti dalla chiave.

Ci sono due metodi per vanificare lo studio statistico: i metodi di diffusione e di confusione.

Nella diffusione, la struttura statistica di M che porta alla ridondanza è dissipata in una struttura che coinvolge lunghe combinazioni di lettere nel crittogramma. L’effetto è che il nemico deve acquisire un ammontare di materiale enorme per fissare questa struttura; inoltre anche se il materiale è sufficiente, il lavoro analitico aumenta a dismisura visto che la ridondanza è stata diffusa su un gran numero di statistiche individuali. Un esempio può essere un’operazione di media su un messaggio M composto da m₁,m₂,m₃,… lettere: aggiungendo cioè s lettere successive del messaggio per ottenere una singola lettera del crittogramma y_n. Si può dimostrare che la ridondanza della sequenza y è identica alla sequenza m (stessa frequenza di lettere e di coppie, ecc.), ma la sua struttura è stata dissipata. Senza dispositivi a memoria infinita non si possono cancellare le statistiche, ma almeno si possono sparpagliare.

Il metodo della confusione si basa sul relazionare le semplici statistiche di E e la semplice descrizione di K in maniera molto complicata. In questo modo è ancora possibile calcolare un S_i, ma la sua dipendenza da K coinvolge tutti gli elementi della chiave (o almeno un grosso gruppo anziché una o poche) e in maniera complicata. Cosicché per trovare una limitazione su K dagli S_i, bisogna risolvere un intero sistema d’equazioni di molti S_i su molti elementi incogniti k_p.

f₁(k₁, k₂, …, k_p)= s₁                                     sistema di difficile soluz. perché f molto complesse e

f₂(k₁, k₂, …, k_p)= s₂                                     coinvolgono molti k_i, nonostante che s₁,s₂, …, s_n siano

_{…            …            …}                                            sufficienti a calcolare k_i

f_n(k₁, k₂, …, k_p)= s_n

3) Metodo della parola probabile, è uno degli strumenti più efficaci. Se si scovano parole o frasi che ci si aspetta siano presenti nel messaggio, o per la sua natura (ad esempio “Mein Fuhrer” come incipit dei messaggi tedeschi nella seconda guerra mondiale) o d’uso comune (ad esempio congiunzioni, articoli, avverbi ed altro), si può recuperare parte della chiave da invertire sul resto del crittogramma. Se escono altre parti in chiaro, la supposizione era giusta.

Un test sulla bontà di un codice segreto può essere: Quanto è difficile ricavare la chiave conoscendo il messaggio M e il crittogramma E? Ovvero quanto è difficile trovare la soluzione di questo sistema:

e₁ = f₁ (m₁, m₂, …m_s, k₁, k₂, …k_r)

e₂ = f₂ (m₁, m₂, …m_s, k₁, k₂, …k_r)

...                     ...

...                     ...

e_s = f_s (m₁, m₂, …m_s, k₁, k₂, …k_r)

supponendo di conoscere tutto eccetto i k_i. Dal punto di vista della confusione è preferibile coinvolgere più m_i possibili, specialmente non adiacenti perché meno correlati, introducendo però un’indesiderata propagazione dell’errore (ogni e_i errato trasmette l’errore agli m_i coinvolti nella cifratura)

• » Invia tramite EMAIL
• » Versione per la STAMPA
• » Le vostre opinioni

I link correlati all'argomento

• La tesi in formato pdf
• L'indice della tesi