Szyfr Czterokwadratowy
Szyfr czterokwadratowy jest ulepszoną wersją szyfru Playfair, zapewniającą lepszą ochronę przekazywanych wiadomości. Został wynaleziony w XIX wieku przez francuskiego kryptologa, Félix'a Delastelle'a.
Zastosowanie
Szyfr czterokwadratowy był stosowany na wszystkich frontach podczas II Wojny Światowej, przez wszystkie strony konfliktu. Obecnie uważany jest za przestarzały, głównie z racji skutecznych i szybkich ataków siłowych, możliwych do przeprowadzenia za pomocą komputerów.
Algorytm
Szyfr czterokwadratowy jest szyfrem podstawieniowym poligramowym. Oznacza to, że podczas szyfrowania tekst jawny wiadomości jest dzielony na grupy znaków, a następnie każdej z tych grup jest przyporządkowywana jedna ze wcześniej przyporządkowanych jej grup znaków. Szyfr czterokwadratowy operuje na grupach dwuliterowych.
Przed rozpoczęciem szyfrowania, należy przygotować cztery tabele. Wszystkie one mają wymiary 5 na 5 liter i zawierają 25 liter alfabetu łacińskiego. Z racji tego, że alfabet łaciński ma 26 liter, zwykle pomija się jedną z rzadkich liter (na przykład x lub q) albo traktuje się litery i oraz j jako jedną literę. Wszystkie cztery tabele powinny być rozmieszczone tak, aby razem tworzyły kwadrat o boku długości dwóch tabel. Należy zadbać o to, żeby linie wierszy i linie kolumn zostały zachowane.
Dwie tabele (lewa górna oraz prawa dolna) zawierają litery zapisane w kolejności alfabetycznej. Natomiast do wypełnienia pól w pozostałych tabelach, wykorzystuje się dwa sekretne słowa kluczowe. Najpierw usuwa się z każdego z nich wszystkie powtarzające się litery (opuszczając ponownie pojawiające się w danym kluczu powtórzenia tych samych liter). Następnie, pozostałymi literami kluczy wypełnia się tabele - do jednej z pozostałych tabel wpisuje się litery pierwszego klucza, a do drugiej litery drugiego klucza. Obie strony muszą ustalić wcześniej, w jakiej kolejności należy wypełnić tabele literami (na przykład kolejno wierszami od lewej do prawej, z góry na dół) oraz które słowo kluczowe odpowiada której tabeli. Resztę pozycji w tych tabelach wypełnia się literami alfabetu, które nie zostały do nich jeszcze wpisane, zazwyczaj w kolejności alfabetycznej.
Przykładowo, używając jako sekretnych kluczy imion obojga rodziców rzymskiego cesarza Wespazjana: Titus Flavius Sabinus i Vespasia Polla oraz traktując litery i oraz j wspólnie i wypełniając tabele wierszami z góry na dół, otrzyma się następujące cztery tabele:
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 |
t | i | u | s | f |
l | a | v | b | n |
c | d | e | g | h |
k | m | o | p | q |
r | w | x | y | z |
v | e | s | p | a |
i | o | l | b | c |
d | f | g | h | k |
m | n | q | r | t |
u | 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 |
Następnym krokiem szyfrowania jest podzielenie tekstu jawnego na pary, z których każda zawiera dwie kolejne litery. W razie potrzeby, należy dopełnić oryginalny tekst wstawiając na końcu jakąś rzadko używaną literę, na przykład X lub Q.
Szyfruje się po dwie litery jednocześnie. Najpierw znajduje się pierwszą literę z każdej pary w górnej-lewej tabeli, a drugą literę w dolnej-prawej tabeli. Następnie wyznacza się prostokąt, którego boki tworzą dwa wiersze i dwie kolumny, w których znajdują się dwie znalezione litery. Tak utworzony prostokąt rozciąga się na wszystkie cztery tabele. Na koniec należy podmienić dwie oryginalne litery, na dwie inne litery, wyznaczone przez pozostałe dwa rogi prostokąta. Takie samo należy postąpić ze wszystkimi pari w aktualnie szyfrowanej wiadomości, zastępując je literami otrzymywanymi na podstawie tych samych czterech tabel szyfrujących.
Przykładowo, szyfrując parę liter AS za pomocą powyższych tabel, otrzyma się jedną z dóch możliwych par: UM lub MU.
Komunikujące się strony powinny wcześniej ustalić w jakiej kolejności będą dopisywać znalezione litery do tworzonego szyfrogramu. Przykładowo, jako pierwszą literę można brać literę z górnej-prawej tabeli, a jako drugą literę z dolnej-lewej tabeli.
Proces odkodowywania szyfrogramu przebiega w analogiczny sposób. Odbiorca musi najpierw utworzyć (korzystając ze znanych sobie sekretnych kluczy) taki sam układ czterech tabel, jakich używał nadawca wiadomości. Następnie musi odkodować litery parami, wyszukując po dwie litery szyfrogramu w tabelach górnej-prawej i dolnej-lewej oraz zmieniając je na litery znalezione w tabelach górnej-lewej i dolnej-prawej.
Siła szyfru czterokwadratowego
Algorytm szyfru czterokwadratowego zapewnia lepsze zabezpieczenie danych, niż szyfr Playfair i szyfr dwukwadratowy. Dzięki zastosowaniu czterech tabel, można uniknąć typowych słabości tych dwóch szyfrów (czyli braku powtarzających się liter w szyfrogramie lub takiego samego kodowania odwrotnych par w tekście jawnym). Pewną wadą szyfru czterokwadratowego jest nieco powolniejsze i bardziej uciążliwe stosowanie, w porównaniu z dwoma poprzednimi szyframi. Powodem tego jest konieczność używania większej ilości tabel i zapamiętania większej (w porównaniu do szyfru Playfair) ilości sekretnych kluczy.
Najskuteczniejszą metodą łamania szyfru czterokwadratowego jest stosowanie analizy częstotliwości pojawiania się dwuznaków w szyfrogramie oraz próby odgadnięcia na tej podstawie fragmentów tekstu jawnego. Dzięki zastosowaniu komputerów, zabezpieczenia szyfru czterokwadratowego można złamać stosunkowo szybko.
Implementacja
Szyfr Czterokwadratowy jest stosunkowo nieskomplikowany. Po wstępnym przygotowaniu tekstu wejściowego i obu haseł, głównym zadaniem jest odpowiednie manipulowanie numerami kolumn i wierszy tabel szyfrujących, dla każdej przetwarzanej pary znaków.
Poniżej przedstawiono funkcję JavaScript, która przeprowadza szyfrowanie wiadomości wejściowej i zwraca utworzony szyfrogram. Oba słowa kluczowe są przekazywane do funkcji jako jednowymiarowe ciągi znaków:
var messageOutput = "";
var pos = 0;
while (pos < messageInput.length) {
var m1 = messageInput[pos];
var m2 = '';
if (pos + 1 < messageInput.length) {
m2 = messageInput[pos + 1];
pos += 2;
} else {
m2 = 'Q' // some dummy letter
pos += 1;
}
var idx1 = alphabet.indexOf(m1); // upper-left table
var idx2 = alphabet.indexOf(m2); // lower-right table
var c1 = keyword[0][(5 * Math.floor(idx1 / 5)) + idx2 % 5];
var c2 = keyword[1][(5 * Math.floor(idx2 / 5)) + idx1 % 5];
messageOutput = messageOutput.concat(c1);
messageOutput = messageOutput.concat(c2);
}
return messageOutput;
}
Działanie Szyfru Czterokwadratowego online jest zaprezentowane na stronie Crypto-Online.