Szyfr vigenère'a jest szyfrowanie oparte na polialfabetyczny substytucji: a litera alfabetu w postaci zwykłego tekstu mogą być szyfrowane na kilka sposobów. Zasada ta wraca do pracy z historii, że od Blaise de Vigenère w XVI th wieku ale Vigenère był jednym z pierwszych, aby wprowadzić ten typ szyfrowania w postaci tabeli z obecnością tajnego klucza. Szyfr Vigenère pozostanie nienaruszalny przez kilka stuleci.
Uważa się, że Charles Babbage wykonał pierwszą prawdziwą kryptoanalizę szyfru Vigenère'a około 1854 roku . W tym samym czasie emerytowany oficer pruski Fryderyk Wilhelm Kasiski osiągnął ten sam rezultat, nie słysząc o pracach Babbage'a, który ich nie opublikował. Kasiski napisał Die Geheimschriften und die Dechiffrierkunst w 1863 roku, w którym przedstawił test, który miał nosić jego imię: test Kasiskiego, który pozwala oszacować wielkość klucza.
Polega na szukaniu powtórzeń w zaszyfrowanym tekście. Weźmy na przykład słowo kluczowe „ABCD”, które jest używane do szyfrowania „MESSENGER VERY MESQUIN MESOPOTAMIEN”.
Powtórzony klucz | W | b | VS | re | W | b | VS | re | W | b | VS | re | W | b | VS | re | W | b | VS | re | W | b | VS | re | W | b | VS | re | W | b | VS |
Zwykły tekst | M | mi | S | S | W | sol | mi | R | T | R | mi | S | M | mi | S | Q | U | ja | NIE | M | mi | S | O | P. | O | T | W | M | ja | mi | NIE |
Zaszyfrowany tekst | M | fa | U | V | W | H. | sol | U | T | S | sol | V | M | fa | U | T | U | jot | P. | P. | mi | T | Q | S | O | U | VS | P. | ja | fa | P. |
W powyższym przykładzie trygram „MES” jest szyfrowany dwukrotnie jako „MFU” i raz „PET”. Babbage i Kasiski zdali sobie sprawę, że takie próby dały im siłę, której potrzebowali, by zaatakować Vigenere.
Te nadmiarowe sekwencje mogą wskazywać na dwie cechy:
W pierwszym przypadku, najbardziej prawdopodobnym, obliczamy liczbę liter między dwoma identycznymi sekwencjami. W naszym przypadku między dwoma „MFU” znajduje się 12 liter, wnioskujemy, że długość klucza jest dzielnikiem 12 (w przeciwnym razie klucz i dwa „MES” nie byłyby wyrównane). Klucz może zatem mieć 12, 6, 4, 3 lub 2 litery (z literą mielibyśmy szyfrowanie monoalfabetyczne, które można łatwo złamać za pomocą analizy częstotliwości ). Przy dłuższym tekście odkrylibyśmy inne sekwencje, które pozwoliłyby dopracować wynik i zredukować rozmiar klucza do jednej lub dwóch możliwości.
Albo zaszyfrowany tekst składający się z kilkuset znaków z kluczem o nieznanej długości. Ten tekst wydaje się a priori przypadkowy, a mimo to zawiera interesujące nadmiarowości.
KQOWEFVJPUJUUNUKGLMEKJINMWUXFQMKJBGWRLFNFGHUDWUUMBSVLPS
NCMUEKQCTESWREEKOYSSIWCTUAXYOTAPXPLWPNTCGOJBGFQHTDWXIZA
YGFFNSXCSEYNCTSSPNTUJNYTGGWZGRWUUNEJUUQEAPYMEKQHUIDUXFP
GUYTSMTFFSHNUOCZGMRUWEYTRGKMEEDCTVRECFBDJQCUSWVBPNLGOYL
SKMTEFVJJTWWMFMWPNMEMTMHRSPXFSSKFFSTNUOCZGMDOEOYEEKCPJR
GPMURSKHFRSEIUEVGOYCWXIZAYGOSAANYDOEOYJLWUNHAMEBFELXYVL
WNOJNSIOFRWUCCESWKVIDGMUCGOCRUWGNMAAFFVNSIUDEKQHCEUCPFC
MPVSUDGAVEMNYMAMVLFMAOYFNTQCUAFVFJNXKLNEIWCWODCCULWRIFT
WGMUSWOVMATNYBUHTCOCWFYTNMGYTQMKBBNLGFBTWOJFTWGNTEJKNEE
DCLDHWTYYIDGMVRDGMPLSWGJLAGOEEKJOFEKUYTAANYTDWIYBNLNYNP
WEBFNLFYNAJEBFR
KQOWEFVJPUJUUNUKGLMEKJINMWUXFQMKJBGWRLFNFGHUDWUUMBSVLPS
NCMUEKQCTESWREEKOYSSIWCTUAXYOTAPXPLWPNTCGOJBGFQHTDWXIZA
YGFFNSXCSEYNCTSSPNTUJNYTGGWZGRWUUNEJUUQEAPYMEKQHUIDUXFP
GUYTSMTFFSHNUOCZGMRUWEYTRGKMEEDCTVRECFBDJQCUSWVBPNLGOYL
SKMTEFVJJTWWMFMWPNMEMTMHRSPXFSSKFFSTNUOCZGMDOEOYEEKCPJR
GPMURSKHFRSEIUEVGOYCWXIZAYGOSAANYDOEOYJLWUNHAMEBFELXYVL
WNOJNSIOFRWUCCESWKVIDGMUCGOCRUWGNMAAFFVNSIUDEKQHCEUCPFC
MPVSUDGAVEMNYMAMVLFMAOYFNTQCUAFVFJNXKLNEIWCWODCCULWRIFT
WGMUSWOVMATNYBUHTCOCWFYTNMGYTQMKBBNLGFBTWOJFTWGNTEJKNEE
DCLDHWTYYIDGMVRDGMPLSWGJLAGOEEKJOFEKUYTAANYTDWIYBNLNYNP
WEBFNLFYNAJEBFR
Następnie patrzymy na odległość między powtórzeniami. Szukamy czynników dla każdej pary:
Możliwe długości kluczy (dzielniki dystansowe) | ||||||||
Powtórzona sekwencja | Odległość między powtórzeniami | 2 | 3 | 5 | 19 | |||
WUU | 95 | x | x | |||||
EEK | 200 | x | x | |||||
WXIZAYG | 190 | x | x | x | ||||
NUOCZGM | 80 | x | x | |||||
DOEOY | 45 | x | x | |||||
GMU | 90 | x | x | x |
W tabeli podano czynniki pierwsze liczby znaków między dwoma początkami ciągu (np. 95 = 5 x 19). W tabeli widać, że wszystkie okresy są podzielne przez 5. Wszystko pasuje idealnie do słowa kluczowego składającego się z 5 liter. Inną metodą znajdowania długości klucza jest użycie wskaźnika koincydencji .
Po znalezieniu długości klucza tekst można podzielić na dowolną liczbę podtekstów, w tym przypadku 5, z których każdy jest uzyskiwany za pomocą tego samego szyfru Cezara i można go odszyfrować za pomocą analizy częstotliwości . Każdy tekst k będący ciągiem liter znajdujących się na pozycji k modulo 5 Porównanie rozkładów liter w każdym z podtekstów (można użyć wskaźnika koincydencji zdefiniowanego między dwoma rozkładami), pozwala odkryć przesuwa się między literami słowa kluczowego i ułatwia rozwiązanie.
Poniższy program w Pythonie oblicza długość używanego klucza, starając się zmaksymalizować indeks koincydencji .
#frequence des lettres frequence_theorique = [8.4, 1.06, 3.03, 4.18, 17.26, 1.12, 1.27, 0.92, 7.34, 0.31, 0.05, 6.01, 2.96, 7.13, 5.26, 3.01,0.99, 6.55, 8.08, 7.07, 5.74, 1.32, 0.04, 0.45, 0.3, 0.12] #fonction decaler = chiffre de cesar de clef d decaler = lambda code, d : ''.join([chr((ord(lettre)- 65 + d) % 26 + 65)if lettre.isalpha() else lettre for lettre in code]) def calculer_IC (code, pas): """ calcule l'indice de coincidence de 'code' en decoupant'code' en 'pas' sous-textes """ somme = lambda nb : nb * (nb - 1) IC = [] for i in range (pas): nb_lettre = [0] * 26 for compteur, lettre in enumerate(code [i::pas]): nb_lettre [ord(lettre)- 65] += 1 IC.append(sum(map(somme, nb_lettre)) / float(compteur * (compteur + 1))) return sum(IC) / float(len(IC)) def calculer_decalage (code): """ casse un chiffre de cesar en renvoyant la clef utilisee """ longueur = float(len(code)) m = [0, 100] for i in range (26): diff = sum(abs(b - frequence_theorique[a]) for a, b in enumerate([100 * lettre / longueur for lettre in map(code.count, "ABCDEFGHIJKLMNOPQRSTUVWXYZ")])) if diff < m[1]: m = i, diff code = decaler (code, 1) return m [0] def recoller (liste): """ recolle les sous-textes """ f = '' try : for i in range (len(liste[0])): for z in liste: f += z[i] except : pass return f def decrypter (code, plancher = 0.065): code = code.upper() pas = 1 while calculer_IC (code, pas) < plancher : pas += 1 code_fractionne = [code[dep::pas] for dep in range (pas)] code_fractionne_decode = [decaler (bout, calculer_decalage(bout)) for bout in code_fractionne] return recoller (code_fractionne_decode)Kryptoanaliza szyfru Vigenère'a metodą Kasiskiego lub innymi metodami, takimi jak indeks koincydencji, wymaga wystarczająco długiego tekstu w stosunku do klucza. W skrajnym przypadku, gdy klucz ma długość równą długości wiadomości i jest używany tylko raz, możliwe są wszystkie teksty o długości równej długości zaszyfrowanej wiadomości: szyfr nie może zostać złamany; to jest szyfr Vernama lub jednorazowa maska .