ADFGVX i frakcjonowanie

Do 1918 roku niemieckie wojsko mierzyło się z poważnym problemem: alianccy kryptoanalitycy łamali ich szyfry polowe szybciej, niż można było je zastępować. Na potrzeby ofensywy wiosennej z 1918 roku pilnie potrzebny był nowy, silniejszy szyfr.

Pułkownik Fritz Nebel opracował szyfr ADFGVX, który łączył dwie klasyczne techniki w sposób, jakiego wcześniej nie stosowano w kryptografii wojskowej.

Nazwa szyfru pochodzi od jego sześciu liter szyfrogramu: A, D, F, G, V, X. Litery te wybrano celowo, ponieważ ich reprezentacje w kodzie Morse’a znacznie się od siebie różnią.

Ograniczało to liczbę błędów transmisji za pośrednictwem polowej łączności radiowej. Pomylenie jednej litery z inną mogło uszkodzić całą wiadomość, dlatego projektanci wybrali litery, których wzorce Morse’a można było maksymalnie łatwo rozróżnić.

Pierwszym krokiem jest podstawienie za pomocą kwadratu Polibiusza 6×6. Jego 36 komórek zawiera 26 liter oraz cyfry 0–9 ułożone w kolejności określonej przez klucz. Nagłówki wierszy i kolumn stanowi sześć liter: A, D, F, G, V, X.

Każdy znak tekstu jawnego zastępuje się dwiema literami: nagłówkiem wiersza i nagłówkiem kolumny jego komórki. Na przykład jeśli H znajduje się w wierszu A i kolumnie F, staje się "AF".

Po podstawieniu podwojony szyfrogram zapisuje się w siatce, której liczba kolumn jest równa długości klucza. Drugie słowo kluczowe określa kolejność kolumn.

Kolumny odczytuje się w kolejności alfabetycznej liter klucza. W ten sposób przestawia się podstawione pary, zrywając pozostałe wzorce i tworząc szyfr odporny zarówno na analizę częstościową, jak i na dopasowywanie wzorców.

Frakcjonowanie to technika polegająca na rozdzieleniu każdego znaku tekstu jawnego na wiele symboli szyfrogramu przed wykonaniem transpozycji. W szyfrze ADFGVX każda litera staje się dwoma symbolami (wierszem i kolumną), które następnie są niezależnie mieszane.

Oznacza to, że dwie „połówki” jednej litery tekstu jawnego trafiają do różnych pozycji w końcowym szyfrogramie, przez co nie można analizować podstawienia i transpozycji osobno.

Szyfry czystego podstawienia, takie jak Playfair, są podatne na analizę częstościową. Szyfry czystej transpozycji, takie jak szyfr płotkowy, są podatne na odtwarzanie tekstu za pomocą anagramowania. Połączenie obu technik pozwala wyeliminować te słabości.

ADFGVX utrudnia analizę częstościową dzięki frakcjonowaniu i transpozycji podstawionych symboli. Złamanie transpozycji wymaga znajomości klucza podstawienia i odwrotnie.

Francuski kryptoanalityk Georges Painvin złamał szyfr ADFGVX w czerwcu 1918 roku, zaledwie kilka dni przed niemiecką ofensywą, którą szyfr miał chronić. Uznano to za jedno z najbardziej błyskotliwych osiągnięć kryptoanalizy podczas I wojny światowej.

Metoda Painvina wykorzystywała wzorce w wiadomościach wysyłanych tego samego dnia za pomocą tego samego klucza. Porównując szyfrogramy o podobnej długości, mógł on określić granice kolumn i prześledzić transpozycję wstecz.

Przełom Painvina dostarczył aliantom informacji wywiadowczych, które pomogły powstrzymać niemiecką ofensywę wiosenną. Ofensywa zakończyła się niepowodzeniem częściowo z powodu przewagi wywiadowczej uzyskanej dzięki złamaniu ADFGVX.

Ta historia pokazała, że nawet pomysłowe konstrukcje szyfrów można złamać, gdy bezpieczeństwo operacyjne jest niewystarczające. Niemcy ponownie używali kluczy i wysłali zbyt wiele wiadomości w krótkim czasie, dostarczając Painvinowi potrzebnego materiału.

W transpozycji kolumnowej tekst jawny zapisuje się w wierszach pod słowem kluczowym, a następnie odczytuje kolumny w kolejności alfabetycznej liter słowa kluczowego. Słowo kluczowe "KEY" daje kolejność kolumn 2-1-3 (E przed K, a K przed Y).

Kolumny wyjściowe przeplatają oryginalny tekst w sposób niszczący lokalne wzorce. Odszyfrowywanie wymaga ponownego zapisania szyfrogramu w kolumnach w tej samej kolejności i odczytania go wierszami.

Każda warstwa klasycznego szyfru eliminuje inną słabość. Podstawienie ukrywa tożsamość liter, a transpozycja ukrywa ich położenie. Razem tworzą szyfr, którego złamanie wymaga jednoczesnego zaatakowania obu warstw.

Zasada łączenia konfuzji (podstawienia) i dyfuzji (transpozycji) została później sformalizowana przez Claude’a Shannona i stała się teoretyczną podstawą współczesnych szyfrów blokowych, takich jak AES.

Przed ADFGVX Niemcy używali ADFGX — prostszego wariantu z pięcioma literami, który nie zawierał cyfr w kwadracie Polybiusza. W ADFGVX powiększono kwadrat do rozmiaru 6×6, aby uwzględnić wszystkie 10 cyfr, co umożliwiło szyfrowanie danych liczbowych.

Rozszerzenie ADFGX do ADFGVX było odpowiedzią na częściowe sukcesy aliantów w łamaniu ADFGX. Dodanie cyfr zwiększyło przestrzeń kluczy i utrudniło analizę częstości digramów, ponieważ wzorce były rozłożone na większą liczbę par symboli.

Sprawdź swoją wiedzę na temat frakcjonowania w ADFGVX.

ADFGVX łączył podstawienie za pomocą kwadratu Polybiusza z przestawieniem kolumnowym, wykorzystując frakcjonowanie do ich przeplatania. Sześcioliterowy alfabet wybrano w celu ograniczenia błędów transmisji w kodzie Morse’a.

Pomimo swojej zaawansowanej konstrukcji szyfr został złamany przez Painvina, który wykorzystał ponowne użycie klucza. Szyfr ten pokazał zarówno siłę łączenia klasycznych technik, jak i kluczowe znaczenie bezpieczeństwa operacyjnego.