cerca
Crittografia: lezioni del 27 e del 28 febbraio 2008
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Crittografia: lezioni del 27 e del 28 febbraio 2008

 :: Crittografia: lezioni del 27 e 28 febbraio 2008 ::

Torna alla pagina di Crittografia

Protocollo Crittografico

Un protocollo crittografico definisce come le parti, ovveri le entità coinvolte nella trasmissione del messaggio criptato, devono comportarsi per ottenere le proprietà di sicurezza desiderate. Vedremo più in là che cosa voglia dire "proprietà di sicurezza".

Il protocollo si attua in uno scenario. Nel mondo ideale di Umpalandia, tutte le persone sono oneste, e non c'è nessun problema nel trasmettere messaggi privati. Negli scenari reali, invece, capita spesso che tra le due parti oneste cerchi di inserirsi qualche disonesto. Oppure, sono direttamente due disonesti che cercano di comunicare, con altri disonesti che cercano di spiare.

I protocolli sono pensati per certi scenari, ma occorre tener presente che gli scenari cambiano.

Principio di Kerckhoff

La sicurezza di un cifrario deve dipendere solo dalla segretezza della chiave, e non dalla segretezza dell'algoritmo usato.

Crittografia Classica

Storicamente, la crittografia è servita per scopi militari e diplomatici. Dobbiamo distinguere due modi per rendere una conversazione segreta: la steganografia e la crittografia.

La parola steganografia significa "scrittura occultata", e si riferisce a tutte le tecniche che si possono adottare per nascondere il messaggio a occhi indiscreti. Non si modifica il messaggio, ma si cerca di far sì che altri non lo vedano. Ad esempio, passarsi pizzini con strette di mano è un sistema steganografico, perché la gente non vede il biglietto.

La crittografia invece cerca di nascondere il contenuto del messaggio, così che anche se capita in mano ad un malintenzionato, questi non possa capirlo.

Esempi di steganografia possono essere l'inchiostro invisibile o l'annuncio sul giornale della vendita di un immobile, che gli eletti invece sanno voler dire qualcos'altro o così via. Il vantaggio della steganografia è che le parti possono nascondere il fatto stesso di essere in comunicazione. Lo svantaggio evidente è che cercando bene, il messaggio prima o poi salta fuori: quando il sistema viene scoperto, la segretezza è perduta.

Ciò non accade con un crittosistema: anche se scopro il sistema, senza opportuna chiave non so che farmene (dovrei analizzare il sistema e trovarne punti di debolezza etc. ma questa è un'altra storia).

Cifrario di Polibio

1 2 3 4 5
1 A B C D E
2 F G H IJ K
3 L M N O P
4 Q R S T U
5 V W X Y Z

Si tratta di una tabella, in cui le lettere sono identificate dalle coordinate con cui compaiono in suddetta tabella. Qui la chiave consiste nella tabella stessa.

Con questo sistema, la parola CASA viene crittata in 13 11 43 11.


Cifrario di Cesare

Si prende l'alfabeto, e si stabilisce che ogni lettera corrisponda alla k-esima lettera che la segue. Se scelgo di spostrare l'alfabeto di 3 posti, avrei:

 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
 D E F G H I J K L M N O P Q E S T U V W X Y Z A B C

In questo modo, la frase LA VERITA' E' LA' FUORI diventerebbe OD YHULWD' H' OD' IXEUL.

Se l'alfabeto è di 26 lettere, ho 25 possibili chiavi diverse. Posso infatti spostare di 1, 2... 25. 26 sarebbe come spostare di 0, quindi non critterei un bel niente.

In termini matematici, ho la funzione di crittazione Ek = (x + K), dove x è la lettera da cifrare e K è la chiave.

Si capisce subito che è un sistema piuttosto semplice da decrittare. Per provare tutte le 25 possibili chiavi, anche lavorando a mano non ci si metterebbe troppo tempo.

Cifrario simmetrico

Possiamo già da questi 2 esempi astrarre il concetto di cifrario simmetrico. Le 2 parti che interagiscono conoscono la stessa chiave K. La funzione Ek di crittazione è l'inversa della funzione Dk di decrittazione. Per questo si dice simmetrico.

Ci sono 2 tipi di cifrari simmetrici:

  • BLOCK CIPHER, o cifrario a blocco, in qui suddivido il messaggio in blocchi di fissata lunghezza e ciascuno di essi viene crittato
  • STREAM CIPHER, o cifrario a flusso, in cui si cifra bit ber bit (o byte per byte). Al flusso di dati in input corrisponde un flusso di chiavi. Un esempio è la cifratura di Sky, in cui arriva un flusso crittato e il decoder decritta man mano.

Completiamo la notazione matematica introdotta prima:

 Testo in chiaro: X =  [X1, X2, ... ,Xn]
 Chiave: K = [K1, K2, ... , Kn]
 Messaggio cifrato: Y = Ek(X) = [Y1, Y2, ... , Yn]

Posso quindi dire che, se Ek è la funzione di crittazione, e Dk è quella di decrittazione, allora ho che

 X = Dk (Ek(X))

Come dicevamo sopra, Dk è l'inverso di Ek.

Il requisito fondamentale è che non si debbano perdere informazioni durante l'applicazione delle funzioni di crittazione e decrittazione.

Le possibili funzioni di trasformazione, poi, ricadono in 2 tipi principali:

  • Sostituzione: ad ogni elemento si sostituisce un altro elemento.
  • Trasposizione: gli elementi vengono scambiati di posto

Le tecniche moderne cercano di mettere insieme questi due principi di trasformazione.

Cifrari con shift

Sono quelli di Cesare, per intenderci. Approfondendo il discorso sul numero possibile di chiavi, che sono 25, si scopre che le funzioni sono:

 Ek(X) = (x + K) mod 26
 Dk(Y) = (y - K) mod 26

Il modulo 26 serve perché lo spazio dell'alfabeto è di 26 posizioni. In questo caso, lo spazio dell'alfabeto coincide con lo spazio delle chiavi.

Un attacco a forza bruta, conoscendo Dk, prova tutte le chiavi fino a che non trova quella giusta. In media occorre provare metà dello spazio delle chiavi. Si capisce che un attacco a forza bruta su di un cifrario con shift rende evidente la sua intrinseca debolezza: questo perché lo spazo delle chiavi è molto piccolo.

Cifrari monoalfabetici

Si usa il principio di sostituzione. Ad una lettera dell'alfabeto, si decide di farne corrispondere un'altra in modo arbitrario. Ovviamente questa sostituzione deve essere univoca, affinché la tecnica sia buona (ovvero univoca e funzionante).

Siccome lo spazio della chiava è composto da tutte le possibili combinazioni delle 26 lettere dell'alfabeto, posso ottenere 26! chiavi diverse, in altre parole 288. Tantine... In questo caso, un tentativo di decrittazione a forza bruta non renderebbe.

Cifrari a sostituzione

È una variante del cifrario monoalfabetico. Si sceglie una certa frase e la si usa, togliendo le lettere ripetute, per sostituire le prime lettere dell'alfabeto. Per le restanti, si usa l'alfabeto normale (sempre togliendo le lettere ripetute). Siccome questa spiegazione non è chiara, faccio un esempio con la chiave DARIO ANDREA (che non è nemmeno molto buona perché usa poche lettere, e in pratica esce... DARIONE!):

 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
 D A R I O N E B C F G H J K L M P Q S T U V W X Y Z

In questo caso, alcune lettere coincidono, purtroppo, mentre altre no.

Comunicare con questo sistema è un po' più semplice rispetto al cifrario monoalfabetico, perché basta conoscere la frase ed il resto vien da sé. Le chiavi possibili in questo caso sono più di 26, ma meno di 26! perché non tutte le combinazioni di lettere sono frasi compiute.

Definizioni di sicurezza

In questi cifrari che abbiamo visto finora, la dimensione dello spazio della chiava mi dà 1 stima del tempo che impiegherei per decrittarli usando la forza bruta. Ma dobbiamo introdurre un paio di concetti nuovi, riguardanti un algoritmo di crittazione. Esso può infatti essere:

  • COMPUTATIONALLY SECURE = il tempo per decrittare è grande e cmq superiore alla vita utile dell'informazione crittata;
  • UNCONDITIONALLY SECURE = indipendentemente dal tempo e dalle risorse, il sistema è impossibile da decrittare.

Di algoritmi incondizionatamente sicuri se ne conosce solamente uno, ed è anche poco pratico da usare. Stelvio non ci ha ancora detto qual'è, ma lo scopriremo. Per quanto riguarda gli altri algoritmi, quelli computazionalmente sicuri, bisogna considerare proprio la parola "computazionalmente". Infatti, un algoritmo con chiave a 56 bit come il DES fino a 10 anni fa era piuttosto buono, perché la potenza dei calcolatori dell'epoca rendeva molto lungo il processo di decrittazione. Ma oggigiorno ci vorrebbero una decina di ore per scoprire una chiave a 56 bit. Allo stato attuale delle cose, una chiave a 80 bit costituisce una bella difficoltà.

Crittoanalisi

Però finora stiamo considerando solamente il caso della forza bruta. È sempre il migliore, il più conveniente? Prendiamo ad esempio il cifrario monoalfabetico. Lo spazio delle chiavi è bello ciccione, 288, ma in realtà decrittare un messaggio crittato con questo sistema impiega un tempo di 10 minuti, più o meno...

Infatti, non si usa la forza bruta, ma l'analisi crittografica. Vuol dire che si analizza l'algoritmo, studiando come è fatto e cercandone possibili falle e debolezze per poterlo attaccare. Nel caso del cifrario monoalfabetico, conoscendo la lingua in cui è scritto, ci si può basare sul sistema della frequenza delle lettere. Se so che eg in italiano la lettera E compare un numero x% di volte, allora il simbolo che nel testo crittato comparirà con una percentuale vicina sarà probabilmente il simbolo che nasconde la lettera E. E così via.

Per ovviare a ciò, si può fare in modo di sballare le frequenze, inserendo ad esempio qua e là i simboli corrispondenti a lettere poco frequenti, così da alzarne la frequenza percentuale. Oppure usare più simboli per la stessa lettera, per abbassare la frequenza percentuale di una lettera frequente. O ancora, usare parole in codice tramite un nomenclatore. Per esempio, stabilisco che la frase "La mia mano è sopra il caffé" voglia dire che l'edificio davanti a cui mi trovo è quello designato per la riunione dei capi di Mohammed Farrah Aidid. Ma se il mio nomenclatore finisce in mani nemiche, non è più utilizzabile. La macchina Enigma dei tedeschi è caduta in parte anche per questo motivo: era stato trovato il nomenclatore.

Torna alla pagina di Crittografia