Metoda rusztu

Maszyna szyfrująca Enigma

Metoda rusztu – metoda łamania szyfrów Enigmy wynaleziona przez polskich matematyków z Biura Szyfrów i stosowana w kryptologii przed wynalezieniem cyklometru. Służyła do znajdowania kluczy dziennych.

Historia

W początkowym okresie używania Enigmy kolejność wirników w maszynie zmieniana była raz na kwartał, priorytetem było więc sprawne określanie nastawienia bębenków. W tym celu opracowana została metoda rusztu bazująca na założeniu, że łącznica kablowa zamieniała tylko 6 par liter.

Po 1 października 1936 roku Niemcy po raz kolejny zmienili procedury szyfrowania, zwiększając liczbę połączeń na łącznicy kablowej Enigmy. W rezultacie metoda rusztu znacznie straciła na efektywności i korzystanie z niej stało się uciążliwe. Aby ułatwić sobie pracę, polscy matematycy wynaleźli cyklometr, który posłużył im do stworzenia katalogu z permutacjami.

Wspomagając się katalogiem, Polacy korzystali z metody rusztu aż do 15 września 1938 roku, kiedy Niemcy zmienili zasady dotyczące szyfrowania depesz i wszystkie do tej pory wynalezione metody łamania Enigmy stały się bezużyteczne.

Opis działania

Wiedząc, że permutacja H (na bębenku wstępnym) jest identycznością, zapisano następujące równanie, opisujące permutację A_i szyfrującą i-tą literę tekstu:

Schemat okablowania w Enigmie. Wciśnięcie klawisza na klawiaturze powodowało przepływ prądu do łącznicy kablowej, a potem przez bębenek wstępny, bębenki N, M, L i bębenek odwracający. Następnie sygnał zawracał przechodząc przez wirniki szyfrujące, bębenek wstępny, aż do jednej z lampek.

$A_{i}=S^{-1}P^{-x-i+1}N^{-1}P^{x+i-1}QP^{-x-i+1}NP^{x+i-1}S,\qquad \qquad i=1...6$

gdzie

$Q=P^{-y}M^{-1}P^{y}P^{-z}N^{-1}P^{z}RP^{-z}NP^{z}P^{-y}MP^{y},\quad x,y,z=0...25.$

S to permutacja na łącznicy kablowej, N, M, L, R to permutacje na wirnikach i bębenku odwracającym, x, y, z – określają, o ile pozycji obrócony był dany wirnik w stosunku do położenia domyślnego (z literą ‘a’ w okienku), permutacja P jest to permutacja, w której każda litera przechodzi na literę znajdującą się bezpośrednio po niej w alfabecie łacińskim, a wyrażenie P^-x-i+1NP^x+i-1 opisuje permutacje na wirniku N przy szyfrowaniu i-tej litery dla początkowego ustawienia wirnika N w pozycji x względem pozycji domyślnej. Ewentualne obroty bębenków M i L zostały pominięte, ponieważ była duża szansa, że w trakcie szyfrowania pierwszych 6 liter wiadomości bębenki M i L nie obróciły się.

Równanie przekształcono, aby Q znalazło się po lewej stronie:

$Q=P^{-x-i+1}NP^{x+i-1}SA_{i}S^{-1}P^{-x-i+1}N^{-1}P^{x+i-1},\qquad \qquad i=1...6.$

W tamtym czasie Polacy wynaleźli już metody znajdowania kluczy indywidualnych wiadomości, okablowanie w militarnej wersji Enigmy również było znane, jedynymi niewiadomymi w równaniu były więc x, y, z i permutacja S.

Na dużym arkuszu papieru wypisano pod sobą 26 permutacji P^-x-i+1NP^x+i-1:

$N$	${\quad }$	$(kjpzydtiohxcsgubrnwfmveqla)$
$P^{-1}NP$		$(ioyxcshngwbrftaqmveludpkzj)$
$P^{-2}NP^{2}$		$(nxwbrgmfvaqeszpludktcojyih)$
$\vdots \vdots$
$P^{-4}NP^{4}$		$(uzpekdtyocqxnjsbiramhwgflv)$

Dla każdego początkowego ustawienia bębenka N (dla wszystkich x od 0 do 25) sześć kolejnych wyrażeń w postaci P^-x-i+1NP^x+i-1 odpowiadało permutacjom na wirniku N przy szyfrowaniu 1, 2, …, 6 litery wiadomości.

Następnie na ruszcie, czyli karcie z sześcioma otworami, wypisano permutacje A_i w następujący sposób:

Jeden układ otworów na ruszcie odpowiadał jednej permutacji na łącznicy kablowej (dziury odpowiadały połączonym parom liter).

Jeżeli przypatrzyć się równaniu na Q, to można zauważyć, że po lewej i prawej stronie wyrażenia SA_iS⁻¹ znajdują się permutacje będące swoimi odwrotnościami. Aby posługiwać się rusztem, należało wprowadzić pomocnicze twierdzenie:

Niech:

$p={\begin{pmatrix}1&2&\dots &26\\p(1)&p(2)&\dots &p(26)\end{pmatrix}}=(a_{1}a_{2}\dots a_{k_{1}})(b_{1}b_{2}\dots b_{k_{2}})\dots$

$q={\begin{pmatrix}1&2&\dots &26\\q(1)&q(2)&\dots &q(26)\end{pmatrix}},$

gdzie

$i,k_{i}\in N,i\leq 26,\textstyle \sum _{i}k_{i}=26.$

Wtedy

$qpq^{-1}={\begin{pmatrix}1&2&\dots &26\\q(1)&q(2)&\dots &q(26)\end{pmatrix}}(a_{1}a_{2}\dots a_{k_{1}})(b_{1}b_{2}\dots b_{k_{2}})\dots {\begin{pmatrix}q(1)&q(2)&\dots &q(26)\\1&2&\dots &26\end{pmatrix}}=$$(q(a_{1})q(a_{2})\dots q(a_{k_{1}}))(q(b_{1})q(b_{2})\dots q(b_{k_{2}}))\dots$

Z powyższego twierdzenia wynika, że Q i SA_iS⁻¹ są do siebie podobne (mają taki sam rozkład na cykle), a znając SA_iS⁻¹ i P^-x-i+1NP^x+i-1 można łatwo obliczyć, jakie litery znajdują się w poszczególnych cyklach Q.

Skoro wiadomo było, że Q i SA_iS⁻¹ miały mieć taki sam rozkład na cykle, to wystarczyło patrzeć na ruszt na permutację A_i tam, gdzie nie było otworów i w miejscu dziur obliczyć złożenie permutacji A_i i P-x-i+1NPx+i-1. Aby to zrobić, przesuwano ruszt nad kartką z permutacjami P^-x-i+1NP^x+i-1 i szukano pozycji, w której permutacje Q w każdym z sześciu równań były podobne (miały taki sam rozkład na cykle). Następnie argumenty i litery obrazu w A₁, …, A₆ należało pozamieniać miejscami w taki sposób, aby uzyskać identyczne Q we wszystkich równaniach. W ten sposób znajdywano permutację S oraz nastawienie wirnika N. Pozostawało rozwiązać równanie:

$Q=P^{-x-i+1}NP^{x+i-1}SA_{i}S^{-1}P^{-x-i+1}N^{-1}P^{x+i-1}$

i znaleźć nastawienie pozostałych wirników. Robiono to ręcznie, sprawdzając wszystkie z 676 możliwych przypadków. Po odnalezieniu nastawienia wszystkich wirników określano skręcenie obręczy alfabetycznej przy pomocy metody anx.

Metoda anx

Dzięki odszyfrowanym wiadomościom z września i października 1932 r. polscy matematycy wiedzieli, że większość niemieckich depesz zaczynała się od ‘anx’ (‘an’ to niemieckie ‘do’, a ‘x’ było znakiem przestankowym). Mając taką wiedzę, należało postępować następująco. Z depesz z danego dnia należało wybrać taką, która mogła zaczynać się od ‘a’. Dla przykładu powiedzmy, że trzy pierwsze litery zaszyfrowanej depeszy to ‘tuv’. Następnie należało wciskać przycisk „t” tak długo, aż zapali się lampka z literą „a”. Skoro w danym stanie maszyny ‘t’ szyfrowane było jako ‘a’, to z symetrii Enigmy ‘a’ musiało szyfrować ‘t’. Trzeba było wcisnąć po kolei klawisze z literami ‘u’, ‘v’ i sprawdzić, czy szyfrują one ‘n’, ‘x’. Jeśli tak, to istniało ustawienie maszyny, w którym ‘anx’ szyfrowane jest jako ‘tuv’, czyli z dużym prawdopodobieństwem tekst depeszy zaczynał się od ‘anx’. Pozostało już tylko przestawić pierścienie tak, aby litery widoczne w górnej części maszyny zgadzały się z kluczem dziennym. Była to metoda niezawodna, ale w pesymistycznym przypadku należało wcisnąć przycisk „t” 17 576 razy.

Zobacz też

• Enigma
• łamanie szyfru Enigmy

Bibliografia

• Kozaczuk, Władysław (1984), Enigma. How the German Machine Cipher was Broken, and how it was Read by the Allies in World War Two, edited and translated by Christopher Kasparek [a revised and augmented translation of W kręgu enigmy, Warsaw, Książka i Wiedza, 1979, supplemented with appendices by Marian Rejewski], Frederick, MD, University Publications of America, ISBN 0-89093-547-5.
• Rejewski, Marian (1984c), Summary of Our Methods for Reconstructing ENIGMA and Reconstructing Daily Keys, and of German Efforts to Frustrate Those Methods, Appendix C of Kozaczuk 1984, s. 241–245.
• Rejewski, Marian (1984d), How the Polish Mathematicians Broke Enigma, Appendix D of Kozaczuk 1984, s. 246–271.
• Rejewski, Marian (1984e), The Mathematical Solution of the Enigma Cipher, Appendix E of Kozaczuk 1984, s. 272–291.
• Joanna Wąsik: Złamanie szyfru Enigmy przy użyciu teorii permutacji. Warszawa: Instytut Matematyki Wydział Matematyki i Informatyki, Uniwersytet Jagielloński, 2009.