Dopo il cifrario di Cesare, in questo articolo vedremo un’altro importante cifrario: quello di Vigenère.

Il Cifrario di Vigenère può essere considerato una variante del cifrario di Cesare: non a caso infatti, si tratta sempre di un sistema di criptografia a sostituzione monoalfabetica.

Vigenere

Di questo metodo di criptografia, ne esistono molte varianti: il primo a descriverlo comunque, sembra essere stato Giovan Battista Bellaso nel 1553 con il suo libro La cifra del. Sig. Giovan Battista Bellaso. Nonostante questo, il cifrario viene erroneamente attribuito a Blaise de Vigenère a cui appunto è associato “Il cifrario di Vigenère”.

Per molti secoli questo cifrario è stato ritenuto inattaccabile: abbiamo infatti dovuto aspettare fino al diciannovesimo secolo per scoprire che il primo ad aver rotto questo cifrario è stato  Charles Babbage già nel 1854 senza aver però pubblicato il suo lavoro, mentre ci penserà Kasiski a rompere completamente il cifrario ritenuto inattaccabile, nel 19 ° secolo.

Il cifrario

Questo cifrario, più che una variante, può essere considerato una versione più avanzata del Cifrario di Cesare: quello infatti, per cifrare una stringa sostituisce ogni lettera con quella dell’alfabeto che si trova di n posti davanti (dove n è la nostra chiave).

Il cifrario di Vigenère invece, utilizza praticamente n cifrari di cesare: infatti ogni lettera della stringa viene spostata di un valore differente.

Per stabilire di quanto ogni lettera deve essere “spostata”, si utilizza sempre una chiave, che in gergo viene definita “Verme”.

Vediamo quindi un esempio:

Stringa: CIFRARIODIVIGENERE
Verme: INFORMATICALABINF
Codice: KVKFRDIHLKVTGFVRWS

Il verme è appunto una parola, e la prima lettera della stringa, deve essere spostata un numero di volte pari alla posizione della prima lettera del verme nell’alfabeto.

Un esempio (ed anche un metodo) facile per capire subito come funziona questo cifrario, è visualizzare la Tavola di Vigenère (o quadrato di Vigenère):

Tavola di Vigenère. Clicca per Ingrandire
Tavola di Vigenère, usata per cryptare e decryptare.

In questa tabella vengono elencati tutti i possibili spostamenti di un cifrario di cesare (26 righe * 26 colonne): se vogliamo vedere come diventerà la lettera C cifrata con la chiave-lettera I, ci basterà andare a vedere che c’è nell’elemento che si trova a coordinate (C, I): la K, appunto.

Una volta terminata la chiave in lunghezza, questa si deve ripetere fino al completarsi della stringa da criptare:

Stringa: INFORMATICALAB
Verme:  CIAOCIAOCIAOCI
Codice: KVFCTUAHKKAZCJ

Per quanto riguarda il decrypt del criptogramma, basterà eseguire l’operazione inversa (sempre conoscendo il verme, ovviamente):

Codice: KVFCTUAHKKAZCJ
Verme:  CIAOCIAOCIAOCI
Stringa Decriptata: INFORMATICALAB

In simboli matematici, possiamo esprimere questo sistema di cryptaggio così:

Mettiamo in relazione biunivoca i numeri da 0 a 25 con le lettere dell’alfabeto (a-z) ed eseguiamo le addizioni in modulo 26, perciò:

Ci = Ek(Mi) = (Mi + Ki) mod 26

Il decriptaggio, come abbiamo visto poco fà, è l’operazione inversa perciò:

Mi = Dk(Ci) = (Ci – Ki) mod 26

Dove:

  • E è il sistema di cryptaggio di Vigenère,
  • M = M0, M1, M2…. Mn è il nostro messaggio
  • C = C0, C1, C2… Cn è il testo cryptato
  • K = K0, K1, K2… Kn è la nostra chiave

Criptanalisi

La chiave per rompere questo sistema di cifratura, è quella di trovare la lunghezza del verme: dopodichè, si potrà trattare il criptogramma come un insieme di n cifrari di cesare.

Quindi, quello che ci interessa, è riuscire a determinare la lunghezza del verme: per farlo, possiamo usare il metodo di Kasiski o quello di Friedman.

Kasiski

Il metodo kasiski si basa su questa intuizione: due parti di chiave uguale, che criptano in punti differenti parti del nostro “plaintext” (testo in chiaro) uguale, genereranno nel codice delle ripetizioni. La distanza fra queste due ripetizioni corrisponde alla lunghezza della chiave o ad un suo multiplo.

Questo ci permette, sopratutto in testi lunghi, di trovare diverse sequenza ripetute che quindi ci permettono di capire (quasi sicuramente) che la lunghezza della chiave è il massimo comun divisore tra le distanze tra sequenze ripetute o al massimo un suo minimo.

Una volta capita la lunghezza della chiave, per ritornare al messaggio ci bastera decifrare n messaggi cifrati con un Cifrario di Cesare.

Quindi, i passaggi in generale sono:

  1. Trovare ed elencare i gruppi di lettere ripetuti con la posizione della lettera iniziale rispetto al crittogramma
  2. Calcolo degli intervalli fra le ripetizioni (facendo delle sottrazioni)
  3. Scomposizione degli intervalli nei rispettivi sottomultipli (es: 55 i sottomultipli sono 5 e 11)
  4. Trovare i fattori che ricorrono più frequentemente tenendo a mente che i gruppi di lettere più grandi sono meno probabilmente causali

Implemenazione in programmazione

Come il sistema che abbiamo visto la settimana scorsa, quello di cesare, vi chiediamo di mandarci le vostre soluzioni nei linguaggi di programmazione che conoscete.

Ecco la nostra versione in python:

#Creates the base Alphabet which is used for finding preceeding characters from the ciphertext.
baseAlphabet = ('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')
print ("Welcome to a Vigenere Cipher encrypter. You will first be asked to enter the plain text to be encrypted and then the key you would like to use in the encryption process. The resulting text will be the cipher text.")
plainText = raw_input("Please enter the plain text")
key = raw_input("Please enter the key")
keyList = []
keyLength = 0
while keyLength < len(plainText):
    for char in key:#Adds the users entered key into a list character by character. Also makes the key the same length as plainText
        if keyLength < len(plainText):
            keyList.append(str(char))
            keyLength = keyLength + 1
completeCipherText = [] #The variable each processed letter is appended to
cipherCharIndexValue = 0#This is the value used to temporaily store the ciphertext character during the iteration
keyIncrement = 0
for plainTextChar in plainText:#iterates through the plain text
        cipherCharIndexValue = baseAlphabet.index(keyList[keyIncrement]) + baseAlphabet.index(plainTextChar)#Adds the base alphabets index value of the key and the plain text char
        while cipherCharIndexValue > 25:
            cipherCharIndexValue = cipherCharIndexValue - 26#makes the addition value under 26 as to not go out of range of base alphabet tuple
   completeCipherText.append(baseAlphabet[cipherCharIndexValue])#appends the ciphertext character to the completeCipherText variable. The character is the index of the key + index of the plainTextChar from baseAlphabet
        keyIncrement = keyIncrement + 1#Moves onto the next key
print ''.join(completeCipherText)#Makes the result a strings for printing to the console.