Cifrario di Vigenère
Il cifrario di Vigenère è il più semplice dei cifrari polialfabetici. Si basa sull'uso di un versetto per controllare l'alternanza degli alfabeti di sostituzione, concetto introdotto per la prima volta da Giovan Battista Bellaso ne La cifra del Sig. Giovan Battista Belaso del 1553.
Storia modifica
Pubblicato nel 1586, il cifrario di Blaise de Vigenère fu ritenuto per secoli inattaccabile, godendo di una fama in buona parte immeritata essendo molto più debole di altri cifrari polialfabetici precedenti, quali il disco cifrante dell'Alberti, o le cifre del Bellaso.[senza fonte] Una fama che è durata per molti anni anche dopo la scoperta del primo metodo di crittanalisi da parte di Charles Babbage, e la successiva formalizzazione da parte del maggiore Friedrich Kasiski: il Metodo Kasiski del 1863.
Il metodo modifica
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 ma ripetuto, determinato in base ad una parola chiave, da concordarsi tra mittente e destinatario, e da scrivere ripetutamente 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 in chiaro - RAPPORTOIMMEDIATO Verme - VERMEVERMEVERMEVE Testo cifrato - MEGBSMXFUQHIUUEOS
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 (come il cifrario di Cesare o quelli per sostituzione delle lettere con simboli/altre lettere) è evidente: il testo è cifrato con n alfabeti cifranti. In questo modo, la stessa lettera viene cifrata (se ripetuta consecutivamente) n volte; ciò rende quindi più complessa la crittoanalisi del testo cifrato.
Si può usare ovviamente una funzione matematica per la criptazione e decriptazione; in entrambe useremo sempre le stesse lettere:
Numero prima lettera del cifrario (A) = 0
Numero ultima lettera del cifrario (Z) = 25
L = Lunghezza del cifrario = Numero elementi dell'insieme (26)
a = Numero della lettera della parola in Chiaro (0-25)
b = Numero della lettera della parola Chiave/Verme (0-25)
c = Numero della lettera della parola Criptata (0-25)
Per criptare: n = a + b (mod 26)
Per decriptare: n = c - b + 26
r [parte intera del numero] = n / L
F(x) = n - ( L * r ) = Numero della lettera della parola in Chiaro/Criptata (0-25)
La funzione si basa semplicemente sulla somma/sottrazione dei numeri delle lettere e dividere per la lunghezza del cifrario per ottenere il numero della lettera desiderata. Per ottenere SEMPRE un numero n positivo anche per la decriptazione, in quanto una sottrazione, basta ricorrere al semplice aritificio di aggiungere 26, in quanto verrà poi eliminato grazie ad r.
Esempio di criptazione con le prime due lettere dell'esempio testo/chiave precedente.
L = 26
a[R] = 17
b[V] = 21
n = 17 + 21 = 38
r = 38 / 26 = 1,461... = 1
F(x) = 38 - ( 26 * 1 ) = 38 - 26 = 12
F(12) = M
---------------------------------------------------------
L = 26
a[A] = 0
b[E] = 4
n = 0 + 4 = 4
r = 4 / 26 = 0,153... = 0
F(x) = 4 - ( 26 * 0 ) = 4 - 0 = 4
F(4) = E
Esempio di decriptazione con le prime due lettere dell'esempio testo/chiave precedente.
L = 26
b[V] = 21
c[M] = 12
n = 12 - 21 + 26 = 17
r = 17 / 26 = 0,653... = 0
F(x) = 17 - ( 26 * 0 ) = 17 - 0 = 17
F(17) = R
---------------------------------------------------------
L = 26
b[E] = 4
c[E] = 4
n = 4 - 4 + 26 = 26
r = 26 / 26 = 1 = 1
F(x) = 26 - ( 26 * 1 ) = 26 - 26 = 0
F(0) = A
La tavola di Vigenère modifica
Per semplificare la cifratura, Vigenère propose l'uso della seguente "matrice" quadrata, composta da alfabeti ordinati e spostati. Se si vuole cifrare, con la chiave dell'esempio precedente, la lettera "R" della parola rapporto basterà trovare la lettera "R" nella prima riga, individuando la colonna relativa. Basterà poi trovare la "V" di "verme" nella prima colonna per trovare la riga, individuando, tramite l'incrocio, la lettera corretta da usare.
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
Nell'esempio, la prima lettera della chiave "v" (verme) e la prima lettera del messaggio "r" (rapporto), usate come coordinate nella matrice per trovare "m", lettera criptata.
Decifrazione del messaggio modifica
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 - MEGBSMXFUQHIUUEOS Verme - VERMEVERMEVERMEVE Testo chiaro - RAPPORTOIMMEDIATO
Usando la tavola quadrata si potrà decifrare la prima "M" ricercandola nella riga della corrispondente lettera del verme, la V; la colonna dove si trova la M ha quindi al primo posto in alto la lettera chiara, la R.
Crittanalisi del Vigenère modifica
Come si è detto questo cifrario ha goduto per tre secoli la fama di essere un 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. In realtà il cifrario di Vigenère fu già forzato da Charles Babbage, ma i risultati della sua ricerca non furono mai pubblicati.
La debolezza del Vigenère sta nell'essere, di fatto, un insieme di n cifrari di Cesare, dove n è la lunghezza della chiave; se il crittoanalista riesce a determinare la lunghezza della chiave (nel nostro caso, n) la decrittazione diventa molto semplice.
Per far ciò si possono utilizzare metodi statistici per trovare n, e successivamente applicare l'analisi delle frequenze a ciascun alfabeto cifrante. Ovvero, se abbiamo come chiave VERME, basta operare l'analisi delle frequenze per tutte le lettere cifrate dalla V, poi per quelle cifrate dalla E, ecc. Perciò, la prima, la sesta, l'undicesima, ecc. lettera avranno lo stesso alfabeto cifrante. La parte più complicata sta dunque nello scoprire la lunghezza della chiave cifrante anche se la cosa non è impossibile. Nel testo cifrato infatti, se la chiave utilizzata è breve, vi saranno probabilmente delle serie di lettere ripetute. Queste serie di lettere, se abbastanza lunghe (5-6 caratteri), saranno generate probabilmente dalla stessa parola in chiaro. Basterà allora calcolare la distanza tra una parola e l'altra e la lunghezza della ripetizione per risalire alla lunghezza n della chiave. Così facendo si può capire quali lettere usano il primo alfabeto cifrante, quali il secondo, e così via procedendo poi con l'analisi delle frequenze per ciascun alfabeto.
Per ovviare a questo problema, si è provato a scegliere chiavi molto lunghe (e quindi, non ripetute o solo in minima parte). Così facendo, gli alfabeti cifranti sono molti di più e le probabilità di ripetizioni sono inferiori.
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 un'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'Ottocento rese estremamente più efficace e praticabile una simile analisi statistica rendendo definitivamente obsolete le cifre basate su chiavi in linguaggi naturali (numerosi furono gli esempi di cifrari violati da Charles 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 semplice (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 Vigenère).
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-casuale, ma casuale stricto sensu, 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 computazionalmente 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 precomputazione 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 lunghezza è, 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 Vigenère, arrivò poi negli anni venti 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[senza fonte].
Bibliografia modifica
- Luigi Sacco, Manuale di Crittografia, Roma 1947
- Andrea Sgarro, Crittografia, Padova 1993, ISBN 88-7021-640-3
- Caterina Marrone, I segni dell'inganno. Semiotica della crittografia, Stampa Alternativa&Graffiti, Viterbo, 2010, pp. 199, ISBN 978-88-6222-132-0
- Simon Singh, Codici & segreti, Milano 2011, ISBN 978-88-17-12539-0
- Chi ha paura del Vigenere? (JPG), in MCmicrocomputer, n. 101, Roma, Technimedia, novembre 1990, pp. 179-183, ISSN 1123-2714.
Altri progetti modifica
Wikibooks contiene testi o manuali sul cifrario di Vigenère
Collegamenti esterni modifica
- (EN) Gustavus J. Simmons, Vigenère cipher, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Gustavus J. Simmons, Vernam-Vigenère cipher, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- Implementazione Java di alcuni dei più famosi cifrari della storia, tra cui quello di Vigenère., su angelusworld.com. URL consultato il 19 agosto 2007 (archiviato dall'url originale il 30 settembre 2007).
- Implementazione Visual Basic di alcuni cifrari monoalfabetici e polialfabetici, incluso quello di Vigenère (ZIP), su furo.altervista.org. URL consultato l'8 aprile 2014 (archiviato dall'url originale il 9 aprile 2014).
