PROTEZIONE LOGICA DEI DATI NEI SISTEMI DI COMUNICAZIONE a cura di Gianluca Di Tomassi

Cap 2

ALGORITMI SIMMETRICI

Introduzione
Sistemi a repertorio
Algoritmi di sostituzione
Algoritmi di sostituzione semplice
Algoritmi di sostituzione con alfabeto misto
Sostituzione omofonica
Codifica omofonica di ordine superiore
Sostituzione polialfabetica
Cifrario Vigenere
Cifrario Beaufort
Algoritmi di Trasposizione
Algoritmi di sovrapposizione
Cifrario Vernam
Sistemi algebrici

 

Introduzione

Come già accennato nel 1.2.1, per algoritmi simmetrici si intende quella classe che utilizza algoritmi noti o segreti e chiavi segrete. Essi forniscono una cifratura dei dati la cui segretezza si basa sulla non conoscenza delle chiavi utilizzate.

Come già visto la funzione matematica EK(M) indica un algoritmo di cifratura convenzionale dove :

M : indica il testo chiaro;

K : indica la chiave usata;

E : indica la funzione di cifratura.

D rappresenta la funzione inversa di E ed è l' algoritmo di decifratura e si indica con DK(C) dove con C si intende il testo cifrato. Se si usa la stessa chiave utilizzata nella funzione E allora D consente di recuperare il corretto valore del messaggio chiaro.

La robustezza di questi algoritmi viene misurata dal rapporto

al crescere di tale rapporto si ottengono algoritmi più forti (si possono comunque utilizzare chiavi corte con algoritmi già esistenti come nel caso del D.E.S.)

Di seguito sono riportati i più noti algoritmi simmetrici

[Torna inizio pagina]

2.1 Sistemi a repertorio

Con i sistemi a repertorio grazie ad un Codice (o Repertorio) si trasformano i messaggi in chiaro in un equivalente testo cifrato, e solo chi dispone del codice corretto è in grado di decifrare il messaggio. Per esempio una intera frase può essere rappresentata con una parola o con poche lettere e, in modo analogo a pochi caratteri possono essere associate intere frasi.

Lo svantaggio di questi sistemi risiede nel dizionario utilizzato il cui numero di voci è limitato, tanto che un analista con il tempo potrebbe riuscire a ricostruire e scoprire così il testo chiaro.

[Torna inizio pagina]

 

2.2 Algoritmi di sostituzione

Questi tipi di algoritmi associano ad ogni carattere del testo cifrato, un altro carattere opportunamente determinato. Tale processo si può rappresentare attraverso una funzione f che ha come dominio A (l' alfabeto dei caratteri in chiaro) e come codominio C (l' alfabeto dei caratteri cifrati), cioè :

con A=a1,.... ...,an e C=f (a1),.... ....,f (an)

Cioè f determina una corrispondenza biunivoca fra gli elementi di A e quelli di C e la chiave usata è la funzione stessa.

Quando avviene ciò, ossia tra i due alfabeti c' è una biiezione allora si parla di Codice Monoalfabetico.

Tra i più noti algoritmi di sostituzione ci sono:

[Torna inizio pagina]

 

2.2.1 Algoritmi di sostituzione semplice

Con questo tipo di algoritmo, per ogni lettera di testo chiaro si eseguono le seguenti operazioni:

m si associa ad ogni lettera la sua posizione nell' alfabeto in chiaro

m traslazione di k posizioni modulo il numero delle lettere dell' alfabeto usato

m associazione della posizione così ottenuta alla lettera corrispondente

Se xi è il carattere che sostituisce yi nella i-esima posizione del testo chiaro, allora xi=[yi+k] mod n

Questa sostituzione si può realizzare in 25*(26!) 9.7*1027 modi diversi (26! è il numero di modi in cui si può riscrivere un alfabeto di 26 caratteri e 25 sono i diversi valori che può assumere la costante k).

Un crittoanalista che volesse decifrare un testo codificato in modo esaustivo, disponendo di un calcolatore in grado di fare un tentativo ogni , impiegherebbe

t =

Il risultato ottenuto però non garantisce alcuna sicurezza su tale metodo, in quanto il crittoanalista dispone di dati statistici sulla frequenza media con cui i caratteri compaiono mediamente in un testo scritto in una medesima lingua, e in base a queste informazioni egli può ricostruire in poco tempo il messaggio originale. Un esempio di algoritmo di sostituzione semplice è il codice di Cesare del quale qui di seguito vediamo un' applicazione:

Messaggio da cifrare : OGGIEUNABELLAGIORNATA

Messaggio cifrato : rllnhaqdehoodlnruqdzd

In questo caso la traslazione dell' alfabeto chiaro è stata di 3 posizioni, e il crittoanalista deve fare al massimo 21 (quante sono le lettere dell' alfabeto chiaro) tentativi per decifrare il messaggio.

Anche prendendo come alfabeto cifrato una permutazione di quella in chiaro la rottura del codice è relativamente facile,infatti se un messaggio è abbastanza lungo (è sufficiente una pagina) e viene cifrato con un codice monoalfabetico, si conserva la frequenza della lingua, così da risultare un metodo poco affidabile.

[Torna inizio pagina]

 

2.2.2 Algoritmi di sostituzione con alfabeto misto

In questo tipo di algoritmo di sostituzione si utilizza un alfabeto misto con chiave. Quest' ultima è una parola priva di ripetizioni di lettere e volendo schematizzare i passi che tale algoritmo esegue si individuano due fasi:

« si prendono le K (con K variabile) lettere della parola chiave e si tolgono dall' alfabeto chiaro

« si elenca la parola chiave e di seguito si associano le restanti lettere dell' alfabeto nell' ordine con cui si presentano

ES.

parola chiave = CANE

Messaggio da cifrare : OGGIEUNABELLAGIORNATA

Messaggio cifrato : offhbumcabiicfhormctc

Questo tipo di algoritmo prevede quindi una sorta di permutazione che si fa sull' alfabeto chiaro ma purtroppo presenta gli stessi inconvenienti e limiti degli algoritmi a sostituzione semplice, in quanto attraverso dati statistici sulla frequenza delle lettere è possibile risalire a buona parte del testo chiaro.

[Torna inizio pagina]

 

2.3 Sostituzione omofonica

Per ogni lingua è possibile definire una distribuzione di frequenza di ogni lettera dell' alfabeto, cioè trovare quanto spesso ogni lettera compare nella lingua presa in considerazione.

Per ottenere un risultato plausibile occorre utilizzare un testo abbastanza lungo del quale si conosce il numero totale di lettere, in modo da osservare il peso che una lettera ha all' interno dell' intero testo.

In questa pagina è riportata la frequenza delle lettere rispetto alle principali lingue europee.

La distribuzione di frequenza delle lettere dell' alfabeto italiano, calcolato su un testo di 10000 lettere è:

Dopo aver eseguito una sostituzione, la frequenza delle lettere che compaiono maggiormente non saranno più le stesse.

Un intruso calcolando la frequenza delle nuove lettere e confrontandola con quella delle lettere in chiaro, individua ugualmente la corrispondenza esistente tra quelle cifrate e quelle in chiaro appunto.

Per ovviare a questo inconveniente si può utilizzare il metodo della Sostituzione omofonica (chiamata anche Sostituzione con varianti o multipla) che lavora associando ad ogni carattere chiaro uno o più caratteri equivalenti fra di loro, in modo da appiattire il più possibile la curva di distribuzione delle singole lettere. L' unica operazione da fare consiste nello scegliere i caratteri di cifratura in modo del tutto casuale. L' operazione di decifratura opera in modo inverso.

ES.

La sostituzione può avvenire in base alla posizione della lettera nel messaggio, cioè per la prima occorrenza si sostituisce la prima lettera, per la seconda occorrenza la seconda e così via (in rotazione).

Per cui se il messaggio da cifrare è : CASSA

Il messaggio cifrato è : mn40o

La distribuzione delle frequenze dopo la codifica omofonica è:

Se prendiamo il messaggio : LE QUATTRO STAGIONI esso può essere cifrato in

3*3*1*1*2*2*2*1*2*2*2*2*1*2*2*2*2=18432 modi differenti.

Una codifica omofonica gode quindi di alcune caratteristiche che la rendono competitiva nei confronti degli altri sistemi:

 Codifica e decodifica sono molto semplici in quanto si tratta di facili sostituzioni;

E' un sistema molto sicuro e anche se scoperto è facilmente modificabile;

ƒ Errori nella trasmissione (dovuti ad esempio a rumori di linea) provocano piccole perdite di informazione poichè la decodifica della parte successiva del testo non dipende dai caratteri che la precedono;

La modifica dei dati codificati e registrati non richiede una decodifica e successiva codifica di tutto il testo, ma solo della parte interessata.

[Torna inizio pagina]

 

 

2.4 Codifica omofonica di ordine superiore

E' possibile cifrare i messaggi in modo tale che essi si possano decifrare in testi diversi, utilizzando chiavi differenti.

Per esempio per costruire un messaggio omofonico del secondo ordine (cioè tale che un testo cifrato si possa decifrare in due testi chiari) si inseriscono casualmente i numeri compresi tra 1 ed N2 (dove N è il numero di caratteri usati) in una matrice quadrata K di ordine N.

Tale matrice ha sia le righe che le colonne in corrispondenza con i caratteri dell' alfabeto A del testo chiaro.

La riga A di K definisce f1(a) mentre la colonna A di K definisce f2(a), con a elemento dell'alfabeto.

In questo modo l' insieme delle righe corrisponde ad una chiave f1 e l' insieme delle colonne corrisponde ad una chiave f2.

Il messaggio in chiaro M viene cifrato nel seguente modo:

r M viene anagrammato in un messaggio X

r si cifrano M e X ottenendo C dove ogni ci = K [M,X] con i=1..N.

Ogni elemento c quindi è dato dall' intersezione degli insiemi f1(m) e f2(x).

  • ES. A= a, m, o, r N=4 per cui K è una matrice 4*4

    a m o r

    a 10 4 15 13 M = r o m a

    m 9 1 14 7 X =m o r a

    o 6 16 3 11 C = 12 3 7 10

    r 2 12 5 8

    [Torna inizio pagina]

  •  

     

    2.5 Sostituzione polialfabetica

    I cifrari polialfabetici utilizzano sequenze di N alfabeti di sostituzione, variando così notevolmente la curva di distribuzione delle lettere dell' alfabeto. Esistono due tipi di sostituzione polialfabetica:

     

  • CIFRARIO VIGENERE
  • Il cifrario di Vigenere utilizza come chiave una sequenza periodica di sostituzione. La chiave che viene usata è una parola o una frase di senso compiuto in maniera tale da memorizzarla facilmente.

    Quando la lunghezza della chiave è uguale a quella del messaggio, si ottiene il massimo grado di sicurezza.

    Le chiavi K=k1,.....,kn (costituito da sequenze di lettere) contiene ki che indica il numero degli spostamenti da fare nell' i-esimo alfabeto per cifrare ogni lettera in chiaro cioè:

    f(ai) = (ai + ki) mod n

    ES.

    Messaggio da cifrare: OGGI E UNA BELLA GIORNATA

    La codifica viene fatta con l' uso della chiave "SOLE" di quattro lettere che determina quali righe della tavola di Vigenere bisogna utilizzare.

    Per cui

    Messaggio da cifrare : OGGIEUNABELLAGIORNATA

    chiave : SOLESOLESOLESOLESOLES

    Messaggio cifrato : gurmwiyetswvsvtyjblxs

    Questo sistema di sostituzione polialfabetica non dà però alcun affidamento, infatti se un crittoanalista spezza il testo codificato in gruppi di quattro lettere ciascuno e li sovrappone, le quattro colonne così ottenute derivano rispettivamente da alfabeti diversi e quindi la frequenza di ciascuna lettera in ciascuna colonna permette di ricostruire immetiatamente il testo originale (sempre se il testo cifrato è tale da permettere una analisi delle frequenze).

     

    L' analisi di un testo codificato secondo il cifrario Vigenere consiste quindi nell' individuare la lunghezza della chiave.

    Il problema che si sviluppa con l' uso di questo cifrario si può risolvere facendo in modo che le curve di distribuzione ricavate dal testo codificato siano le meno significative possibile.

    Una soluzione risiede quindi nella codifica omofonica come già spiegato nel par. 2.2.3 .

    Quì di seguito è riportata la tavola di Vigenere come formulata originalmente.

    Tavola di Vigenere

     

     

  • CIFRARIO BEAUFORT
  • Il cifrario Beaufort fu proposto per la prima volta dall' italiano Giovanni Sestri nel 1710 anche se poi ha preso il nome dell' ammiraglio francese Francis Beaufort.

    La sostituzione che si effettua sui caratteri in chiaro è del tipo :

    fi(a) = ( ki - a) mod n

    Questo metodo prevede di ribaltare le lettere dell' alfabeto che vengono spostate verso destra di ki+1 posizioni.

  • Il cifrario Beaufort si può variare utilizzando una sostituzione del tipo

    fi(a) =(a-ki ) mod n e dato che (a-ki ) mod n=(a+(n-ki )) mod n

  • si può vedere f nel seguente modo:

    fi(a) = [(n-1)-a+( C +1)] mod n

    Il cifrario è equivalente a quello di Vigenere con carattere chiave (n-ki ). Quindi esso è l' inverso di Vigenere, così se uno viene utilizzato per la codifica, l' altro viene usato per la decodifica.

    ES.

    Sia ki =D allora la corrispondenza fra testo chiaro e testo cifrato è data da:

    fi(a) = ( D - ai) mod 21

    e allora

    [Torna inizio pagina]

     

    2.6 Algoritmi di Trasposizione

    Se si effettua la trasposizione di un messaggio, i caratteri del testo possono essere riordinati in due modi:

    þ mediante figure geometriche;

    þ mediante uno schema logico;

    Se si usano figure geometriche, la cifratura si può schematizzare nel seguente modo:

    m il testo chiaro viene scritto nella figura seguendo un certo cammino di inserimento

    m il testo cifrato è recuperato dalla figura secondo un cammino di uscita

    La chiave è così costituita dalla figura e dai cammini di entrata e di uscita. Una trasposizione molto utilizzata è quella di Ipercubo di dimensione n. Se n=3 i passi dell' algoritmo sono:

    Œ considerato un cubo, i suoi vertici sono contrassegnati con 8 possibili configurazioni assunte da gruppi di 3 bit (000,001,010.....,111) e in modo che vertici adiacenti abbiano configurazioni adiacenti, cioè differiscano di un solo bit l' una dall' altra.

    Configurazione di bit adiacenti

     si schiaccia il cubo in modo da poter essere rappresentato nel piano come un grafo

    Grafo di configurazione di bit adiacenti

    Ž il testo da cifrare si suddivide in blocchi di 8 caratteri e ogni gruppo si dispone sui nodi del grafo da sinistra verso destra e dall' alto verso il basso

     scelto un nodo di partenza, muovendoci lungo i lati del grafo in modo da toccare tutti i vertici (cammino Hamiltoniano se il vertice di arrivo è adiacente a quello precedente), si esegue la rilettura degli 8 caratteri ottenendo così il testo codificato

    Cammino Hamiltoniano

    ES.

    Messaggio da codificare : LASCIATE OGNI SPERANZA VOI CHE ENTRATE

    Messaggio cifrato: lacaetis onipserg nazvocia hetrneta

    L' affidabilità di questo sistema è direttamente proporzionale alla dimensione dell' ipercubo.

    I motivi per ritenere che un sistema di trasposizione polidimensionale sia un ottimo sistema crittogafico sono molti:

    J come già detto, in un grafo , vertici adiacenti hanno configurazioni adiacenti, per cui muovendosi su un cammino Hamiltoniano si genera un codice di Gray, un codice cioè in cui due configurazioni consecutive differiscono per un solo bit (000,001,011....).

    Questo rende più facile la generazione pseudo-casuale di tali sequenze.

    J se la generazione pseudo-casuale delle sequenze è realizzata via software, la procedura è molto semplice e richiede bassissima occupazione di memoria ad alta velocità

    J se il crittoanalista decodifica un blocco di testo che è cifrato su un certo cammino, non può applicare la stessa decodifica al successivo blocco perchè il cammino sarà diverso.

    Se si utilizzano tecniche di trasposizione che non usano figure geometriche allora il testo si divide in sequenze di caratteri della stessa lunghezza della chiave.

    Questi gruppi vengono scritti in modo ordinato sotto la chiave. Si ottengono così n colonne (con n = lunghezza chiave).

    Ogni colonna corrisponde ad un carattere della chiave, se ora le colonne vengono lette dall' alto verso il basso a partire dalla quella a cui corrisponde il carattere della chiave che viene primo (poi secondo, terzo...) nell' alfabeto si ottiene una trasposizione del testo in chiaro.

    Se questo procedimento si itera più volte con chiavi differenti, si ottiene un testo cifrato molto resistente ad un eventuale attacco.

    Es.

    Messaggio da cifrare : LE QUATTRO STAGIONI DI VIVALDI

    chiave : LIBRO

    L I B R O

    3 2 1 5 4

    L E Q U A

    T T R O S

    T A G I O

    N I D I V

    I V A L D

    I

    Messaggio cifrato: qrgda etaiv lttni iasov duoiil

    Effettuando una seconda trasposizione con chiave diversa

    chiave : MEDIO

    M E D I O

    2 3 4 1 5 Messaggio cifrato: dinoi qelid

    Q R G D A lrtta vgats oavivi

    E T A I V

    L T T N I

    I A S O V

    D V O I I

    L

    [Torna inizio pagina]

     

    2.7 Algoritmi di sovrapposizione

    Il cifrario di Vernam viene anche più propriamente chiamato come algoritmo di sovrapposizione, in quanto Vernam è stato il primo a riconoscere l' efficacia di un metodo di sovrapposizione, che permette di cifrare il testo chiaro combinandolo, attraverso la somma modulo 2, con una stringa di K bit casuali. La sequenza che si deve sommare al testo chiaro viene generata utilizzando la tecnica dei registri a scorrimento (shift register). Per garantire resistenza agli attacchi è necessario che la stringa che viene trasmessa goda delle seguenti proprietà :

    r la sequenza di output deve avere un periodo di lunghezza pari almeno ad un certo valore k

    r il testo cifrato deve essere casuale

    Poichè si lavora su un campo di Galois GF(2) attraverso le operazioni di somma e moltiplicazione si può costruire un qualsiasi sistema logico, tra cui un generatore casuale (vedi cap. 6.1.1).

    Il circuito logico che costituisce il generatore di stringhe pseudo-casuali è composto da :

    « elementi di memoria detti registri

    « circuiti porta chaimati gate, collegati in modo variabile

    Un registro a scorrimento lineare si può rappresentare come

    dove ogni quadratino S1..Sn rappresenta un registro che può assumere valori binari. Gli Si sono anche noti come stadi del registro a scorrimento e la loro configurazione determina lo stato del registro stesso. Se i registri hanno capacità di memoria di n bit allora il generatore, in un certo istante può stare in uno qualsiasi degli stadi possibili, che sono 2n-1 (la n-pla nulla è esclusa). Una volta che il sistema assume uno stato di memoria già assunto esso ripercorrerà tutti gli stati già passati, producendo in questo modo una uscita periodica. Il periodo T con cui il generatore si ripete è 2n. Un registro a scorrimento è un registro che ad ogni segnale di sincronizzazione perde il valore dell' ultima cella, modifica quello delle restanti tramite uno shift e determina quello della prima attraverso segnali esterni.

    In particolare nei registri a scorrimento lineare il contenuto della prima cella è dato dalla somma modulo 2 di alcune celle successive, utilizzando la funzione di feedback

    f(S0,S1,..,Sn ) = C0S0+C1S1+....+CnSn

    I coefficienti C1,..,Cn sono chamati coefficienti di feedback e assumono valori binari. Per ogni registro con coefficienti di feedback C1,..,Cn il polinomio caratteristico f(x) è :

    f(x) = C0+C1X1+....+Cn-1Xn-1+Xn

    Per ogni polinomio caratteristico esistono 2n possibili inizializzazioni, quindi i polinomi possono essere usati per generare altrettante sequenze diverse, delle quali una sarà quella nulla. Essendo la somma modulo 2 la unica operazione che si effettua si origina un sistema lineare. La sequenza che si genera ha una certa periodicità P che varia a seconda della lunghezza n del registro, del contenuto iniziale e del collegamento di retroazione.

    Esempio:

    Gli shift register esistenti sul mercato hanno il polinomio caratteristico già inserito mentre le n-ple sono lunghe abbastanza da essere trasmesse velocemente.

    [Torna inizio pagina]

     

    2.7.1 Cifrario Vernam

    Il testo chiaro M dopo essere stato codificato in bit, viene sommato modulo 2 ad una sequenza pseudo-casuale k e quindi trasmesso.

    L' ente A codifica quindi in bit il testo chiaro M e somma (modulo 2) ad esso una sequenza pseudo-casuale K (nota sia ad A che a B) ottenendo il valore C che viene inviato da A a B.

    Una volta che all' ente B perviene il valore C non resta altro che risommare ad esso la sequenza K per ottenere di nuovo il messaggio in chiaro. Cioè

    M+k=C C+K=M+K=M

    Il cifrario Vernam ha le seguenti caratteristiche:

     un eventuale errore della linea altererebbe un solo bit dopo la cifratura evitando così la propagazione di errori.

    le frequenze di lettere nel testo cifrato dipendono dalle frequnze del messaggio m e dalla sequenza k. Maggiore è la casualità di k, migliore è il grado di disordine e casualità del testo codificato

    ƒ chi conosce il testo in chiaro ed il suo corrispondente testo cifrato risale immediatamente alla sequnza di mascheramento k.

    [Torna inizio pagina]

     

    2.8 Sistemi algebrici

    Nei sistemi algebrici, per mezzo di una tabella viene associato ad ogni lettera dell' alfabeto un numero con la regola che a lettere diverse corrispondano numeri diversi. Definiamo una matrice quadrata A di ordine n i cui elementi sono numerici. La cifratura di una parola di lunghezza n si ottiene facendo:

    Y = A * X

    dove X è un vettore colonna di dimensione n. Ogni xi è un numero associato ad un carattere della parola da cifrare. Infine si trasformano i numeri in lettera per ogni yi e il testo che si ottiene è quello cifrato.

    Per decifrare si calcola

    A-1 *Y = X

    dove A-1 è la matrice inversa di A.

    Esempio :

    Messaggio : bar n=3

    bar = 65 67 27

    ber = 109 95 43

    Il vantaggio nell' utilizzare sistemi algebrici, come si vede dall' esempio, sta nel fatto che la modifica di un singolo carattere implica la variazione di tutti gli elementi del vettore Y. In questo modo è eliminata la corrispondenza uno a uno tra carattere chiaro e carattere codificato. Di conseguenza gli attacchi del crittoanalista basati sull' analisi delle frequenze sono molto più complessi. L' unico svantaggio di questo sistema di codifica è la relativa complessità delle operazioni da effettuare, sia in fase di codifica sia in quella di decodifica.

     

    INDICE