Szyfr Vigenère’a

Algorytm Vigenère’a (wymowa: /viʒˈnɛːʁ/) – jeden z klasycznych algorytmów szyfrujących. Należy on do grupy tzw. polialfabetycznych szyfrów podstawieniowych. Szyfr ten błędnie został przypisany twórcy bardziej skomplikowanego szyfru Blaise’owi de Vigenère.

Szyfr, który obecnie nazywamy szyfrem Vigenère’a, po raz pierwszy został opisany przez Giovana Batista Belaso w 1553, w broszurze zatytułowanej La cifra del. Sig. Giovan Batista Belaso[1]

Historyczny szyfr Vigenère’a edytuj

Działanie szyfru Vigenère’a oparte jest na następującej tablicy:

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

Każdy z wierszy tablicy odpowiada szyfrowi Cezara, przy czym w pierwszym wierszu przesunięcie wynosi 0, w drugim 1 itd.

Aby zaszyfrować pewien tekst, potrzebne jest słowo kluczowe. Słowo kluczowe jest tajne i mówi, z którego wiersza (lub kolumny) należy w danym momencie skorzystać.

Przypuśćmy, że chcemy zaszyfrować prosty tekst, np.:

TO JEST BARDZO TAJNY TEKST

Do tego celu użyjemy znanego tylko nam słowa kluczowego, np.: TAJNE

Na początku zauważamy, że użyte słowo kluczowe jest zbyt krótkie, by wystarczyło do zaszyfrowania całego tekstu, więc należy użyć jego wielokrotności. Będzie to miało następującą postać:

TO JEST BARDZO TAJNY TEKST
TA JNET AJNETA JNETA JNETA

Następnie wykonujemy szyfrowanie w następujący sposób: litera szyfrogramu odpowiada literze z tabeli znajdującej się na przecięciu wiersza, wyznaczanego przez literę tekstu jawnego i kolumny wyznaczanej przez literę słowa kluczowego, np. po kolei „T” i „T” daje „M”, „O” i „A” daje „O” itd. W efekcie otrzymujemy zaszyfrowany tekst:

MO SRWM BJEHSO CNNGY CROLT

Nie ma znaczenia, czy litera tekstu jawnego będzie wyznaczała wiersz, a słowa kluczowego kolumnę, czy na odwrót, efekt szyfrowania będzie zawsze taki sam.

Odszyfrowywanie przebiega podobnie. Bierzemy kolejne litery szyfrogramu oraz odpowiadające im litery słowa kluczowego (podobnie, jak przy szyfrowaniu). Wybieramy kolumnę odpowiadającą literze słowa kluczowego. Następnie w tej kolumnie szukamy litery szyfrogramu. Numer wiersza odpowiadający znalezionej literze jest numerem litery tekstu jawnego. Np. w kolumnie 'T' litera „M” znajduje się w wierszu 'T', w kolumnie 'A' litera „O” znajduje się w wierszu 'O' itd.

Istnieje jednakże prostszy, szczególnie dla celów implementacyjnych, sposób deszyfrowania. Wymaga on wykonania operacji „odwrócenia” hasła, jak poniżej:

K2(i) = [26 – K(i)] mod 26

gdzie K(i) – kolejna litera słowa kluczowego, numerowane A=0, B=1 itd., a K2(i) – kolejna litera hasła „odwróconego”. 26 oznacza liczbę liter alfabetu łacińskiego.

Efektem działania takiego przekształcenia dla hasła „TAJNE” będzie słowo „HARNW”.

Następnie należy na szyfrogramie wykonać operację szyfrowania z otrzymanym hasłem. Wynikiem, jak można się przekonać, będzie postać jawna tekstu.

Oryginalny szyfr Vigenère’a edytuj

Oryginalny szyfr Vigenère’a używał autoklucza, pierwsza litera klucza była ustalana, a kolejnymi literami były kolejne litery tekstu jawnego.

Niech naszą literą szyfrującą będzie „N”:

       tekst jawny:  TO JEST BARDZO TAJNY TEKST
             klucz:  NT OJES TBARDZ OTAJN YTEKS
tekst zaszyfrowany:  GH XNWL UBRUCN HTJWL RXOCL

Odszyfrowanie przebiega w następujący sposób: pierwszą literę szyfrogramu odszyfrowywujemy ustaloną literą („N”), kolejne litery dopiero co odszyfrowanymi literami:

G   N → T
H TO
X O → J

...

        szyfrogram:  G H  X N W L ...
             klucz:  N T  O J E S ...
tekst odszyfrowany:  T O  J E S T ...

Szyfr ten, ze względu na to, że długość klucza była równa długości tekstu jawnego, opierał się analizie statystycznej.

Kryptoanaliza edytuj

Oba szyfry były często mylone i określane terminem „le chiffre indéchiffrable” (nierozszyfrowalny szyfr).

Pierwszy opis złamania szyfru Vigenère’a został opublikowany w książce pruskiego dowódcy Fryderyka KasiskiegoDie Geheimschriften und die Dechif-frir-kunst („Szyfrogramy i sztuka deszyfracji”), opublikowanej w 1863.

Metoda złamania opierała się na obserwacji, że powtórzenia w szyfrogramie mogą odpowiadać powtórzeniom w tekście jawnym i kluczu. To z kolei ułatwiało odgadnięcie długości klucza, następnie samego klucza i odszyfrowania szyfrogramu.

Oczywiście metoda ta dotyczyła historycznej wersji szyfru Vigenère’a, która miała skończoną (i w praktyce zazwyczaj krótką) długość klucza.

Pierwsze złamanie szyfru nastąpiło jednak wcześniej – w roku 1854, przy użyciu kryptoanalizy statystycznej i zostało dokonane przez Charles’a Babbage’a. Istotą złamania szyfru było podzielenie wiadomości na części w ilości równej długości klucza. W wyniku podziału otrzymywano urywki wiadomości, które można było traktować jak zaszyfrowane szyfrem monoalfabetycznym.

Charles Babbage prawdopodobnie złamał również szyfr Vigenère’a z autokluczem.

Bezwarunkowe bezpieczeństwo edytuj

Szyfr Vigenère’a może być szyfrem nie do złamania (zostało to udowodnione w 1949 przez Claude’a Elwooda Shannona) przy zachowaniu trzech reguł:

  • klucz użyty do szyfrowania wiadomości musi być dłuższy lub równy szyfrowanej wiadomości;
  • klucz musi być wygenerowany w sposób całkowicie losowy (nie może istnieć sposób na odtworzenie klucza na podstawie znajomości działania generatorów liczb pseudolosowych);
  • klucz nie może być użyty do zaszyfrowania więcej niż jednej wiadomości.

Dodatkowo jest wymagane, aby osoba znająca klucz nikomu go nie zdradziła.

Zobacz też edytuj

Przypisy edytuj

  1. David Kahn – The Codebreakers. The Story of Secret Writing, rozdział 05. On The Origin of a Species