Cifrario di Vigenère
Da Wikipedia, l'enciclopedia libera.
Il cifrario di Vigenère è il più semplice dei cifrari polialfabetici; fu pubblicato nel 1553 da Giovan Batista Belaso in "La cifra del. Sig. Giovan Batista Belaso" ma più tardi, nel 1586, fu erroneamente attribuito a Blaise de Vigenère; ritenuto per secoli un cifrario inattaccabile, ha goduto di una fama dovuta soprattutto alla sua semplicità e in buona parte immeritata essendo molto più debole di altri codici polialfabetici precedenti quali il disco dell'Alberti, o altre cifre del Bellaso; una fama che è durata fino alla I guerra mondiale molti anni dopo la scoperta del primo metodo di crittanalisi: il metodo Kasiski del 1863.
Indice |
Il metodo
Il metodo si può considerare una generalizzazione del cifrario di Cesare; invece di spostare sempre dello stesso numero di posti la lettera da cifrare, questa viene spostata di un numero di posti variabile, determinato in base ad una parola chiave, da concordarsi tra mittente e destinatario, e da scriversi sotto il messaggio, carattere per carattere; la chiave era detta anche verme, per il motivo che, essendo in genere molto più corta del messaggio, deve essere ripetuta molte volte sotto questo, come nel seguente esempio:
Testo chiaro - ARRIVANOIRINFORZI Verme - VERMEVERMEVERMEVE Testo cifrato - VVIUZVRFUVDRWAVUM
Il testo cifrato si ottiene spostando la lettera chiara di un numero fisso di caratteri, pari al numero ordinale della lettera corrispondente del verme. Di fatto si esegue una somma aritmetica tra l'ordinale del chiaro (A = 0, B = 1, C = 2 ...) e quello del verme; se si supera l'ultima lettera, la Z, si ricomincia dalla A, secondo la logica delle aritmetiche finite.
Il vantaggio rispetto ai cifrari monoalfabetici è evidente: la singola lettera del testo chiaro non è sempre cifrata con la stessa lettera; e questo rende più difficile la crittanalisi statistica del testo cifrato.
La tavola di Vigenère
Per semplificare la cifratura, il Vigenère propose l'uso della seguente tavola quadrata, composta da alfabeti ordinati spostati. Volendo ad esempio cifrare la prima R di ARRIVANO si individuerà la colonna della R, quindi si scenderà lungo la colonna fino alla riga corrispondente della corrispondente lettera del verme (qui E); la lettera trovata all'incrocio è la lettera cifrata (qui V); la seconda R invece sarà cifrata con la lettera trovata sulla riga della R di VERME, e cioè con la I
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 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 A C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z 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
Come si decifra il messaggio
Chi riceve il messaggio per decifrarlo deve semplicemente usare il metodo inverso (sottrarre invece che sommare); riferendosi all'esempio di sopra si avrà:
Testo cifrato - VVIUZVRFUVDRWAVUM Verme - VERMEVERMEVERMEVE Testo chiaro - ARRIVANOIRINFORZI
Usando la tavola quadrata si potrà decifrare la seconda V ricercandola nella riga della corrispondente lettera del verme, la E; la colonna dove si trova la V ha al primo posto in alto la lettera chiara, la R.
Crittanalisi del Vigenère
Come si è detto questo cifrario ha goduto per tre secoli fama di cifrario inattaccabile; nel 1863 il colonnello prussiano Friedrich Kasiski pubblicò un primo metodo di decrittazione; in seguito si sono trovati diversi altri efficienti metodi per forzare questo cifrario.
La debolezza del Vigenère sta nel fatto di essere di fatto un insieme di n cifrari di Cesare, dove n è la lunghezza della chiave; se il crittanalista riesce a determinare n la decrittazione diventa cosa semplicissima; e con metodi statistici non è difficile trovare n alla sola condizione che il testo sia molto più lungo della chiave (grosso modo: almeno dieci volte), cosa molto frequente, visto che per motivi pratici era abituale usare chiavi non troppo lunghe.
Se si usa una chiave di lunghezza paragonabile al testo, la crittanalisi diventa difficile ma non impossibile, potendo basarsi sulla natura del testo usato come chiave.
Nei linguaggi naturali, infatti, ogni carattere contiene solo una limitata quantità di entropia e i diversi caratteri, gruppi di caratteri e parole hanno di conseguenza diverse probabilità di occorrenza, ciò rende il cifrario insicuro essendo possibile di conseguenza una analisi statistica del testo cifrato che consenta progressivamente di scartare carattere per carattere o gruppo per gruppo le soluzioni di coppie (testo in chiaro) più (chiave) meno probabili a favore delle più probabili che portino a recuperare una parte di testo in chiaro, o di chiave, di senso compiuto. Lo sviluppo del calcolo automatizzato a partire dalla seconda metà dell'800 rese estremamente più efficacie e praticabile una simile analisi statistica rendendo definitivamente obsolete le cifre basate su chiavi in linguaggi naturali (numerosi furono gli esempi di cifrari violati dallo stesso Babbage).
Inoltre, se per praticità un testo noto è usato come chiave il recupero di porzioni della stessa rende possibile l'identificazione del testo-chiave con la definitiva compromissione della cifra; questo fattore diviene estremamente importante se parte del testo in chiaro è conosciuta (plaintext attack) o può essere scelta dall'attaccante (chosen plaintext attack) e diviene di conseguenza banale recuperare la porzione di chiave ad essa associata.
Il logico passo successivo fu di dotare il flusso di dati della chiave di caratteristiche tali a resistere ad analisi statistiche sul testo cifrato ed al recupero della chiave a partire da porzioni della stessa; nel secolo successivo tale idea portò a sviluppare funzioni matematiche sempre più evolute che coprissero completamente le caratteristiche statistiche del testo in chiaro se combinate ad esso anche con una funzione molto semlpice (es xor tra ogni elemento di input ed ogni elemento della chiave) , essendo gli output distribuiti in maniera pseudocasuale (e senza mostrare periodicità per una lunghezza almeno pari a quella del testo in chiaro), e che impedissero, noto un ammontare arbitrario di output, di prevedere output successivi o precedenti (caratteristica evidentemente incompatibile con un testo in linguaggio naturale come le chiavi usate nel cifrario di Vigenere).
Tali funzioni sono dette PRNG, generatori di numeri pseudocasuali, quando è verificata la prima preposizione, e quando è verificata anche la seconda preposizione sono dette crittograficamente forti ed è possibile usare tali funzioni come stream cypher.
Se il flusso di dati della chiave non è pseudo-random, ma random, generato ad esempio da un rilevatore (non accessibile all'attaccante!) di fenomeni casuali (come decadimenti radioattivi, rumore elettrico o termico ecc...) vengono verificate tutte le precedenti condizioni di resistenza agli attacchi:
- non vi è periodicità;
- non vi sono caratteristiche statistiche utili né nella chiave né nel conseguente testo cifrato;
- non è possibile estendere la conoscenza della chiave a partire da una quantità arbitraria di chiave conosciuta.
Il limite delle PRNG è dato dal fatto che tali proprietà statistiche (periodo, uniformità statistica dell'output, correlazione non coputazionalmente sfruttabile degli output) devono essere dimostrate, inoltre ciascuna funzione non può generare tutte le possibili chiavi ma solo un numero (estremamente elevato, tale da non consentire praticamente la precomputrazione da parte dell'attaccante) determinato dalla natura della funzione stessa, pertanto tali funzioni sono sempre forzabili con un numero di tentativi non superiore al numero delle chiavi generabili.
Al contrario per un RNG tali proprietà statistiche sono vere per definizione ed inoltre, potendo un RNG generare in modo equiprobabile tutti i possibili output della lunghezza desiderata, ne consegue che ogni output di tale lungezza è, equiprobabilmente, il corrispondente testo in chiaro, non consentendo all'attaccante nessuna verifica dell'esattezza della decifrazione.
Vernam, partendo da una ennesima reinvenzione del cifrario di Vigenere, arrivò poi negli anni '20 ad incorporare queste nozioni nel suo cifrario e Claude Shannon nel 1949 portò una dimostrazione matematica di come un cifrario con tali caratteristiche (chiave generata da un RNG, lunga almeno quanto il testo, mai riutilizzata: One Time Pad) sia teoricamente inattaccabile (cifrario perfetto).
è di questo tipo il noto cifrario di Vernam, usato come base di alcune macchine cifranti e anche sulla famosa linea rossa tra Mosca e Washington.
Bibliografia e collegamenti esterniLuigi Sacco, Manuale di Crittografia, Roma 1947
Andrea Sgarro, Crittografia, Padova 1993, ISBN 88-7021-640-3
La Crittografia da Atbash a RSA --> Il Cifrario di Vigenère
Java Vigenere applet con codice sorgente (GNU GPL)
- Ultima modifica per la pagina: 15:31, 2 giu 2007.
- Tutti i testi sono disponibili nel rispetto dei termini della GNU Free Documentation License.
