Szyfr Vigenère'a

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Algorytm Vigenère'a jest jednym 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 | edytuj kod]

Działanie szyfru Vigenere’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

Jak można zauważ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

Warto zauważyć, że tak naprawdę 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 bardzo 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 prostej operacji "odwrócenia" hasła, jak poniżej:

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

gdzie K(i) – kolejne litery słowa kluczowego, numerowane A=0, B=1 itd., a K2(i) – kolejne litery 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 | edytuj kod]

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 | edytuj kod]

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 Kasiskiego - 'Die 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 | edytuj kod]

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 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.
Information icon.svg Osobny artykuł: Szyfr z kluczem jednorazowym.

Przypisy

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

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]