Metoda rusztu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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[edytuj]

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

Wiedząc, że permutacja H (na bębenku wstępnym) jest identycznością zapisano następujące równanie, opisujące permutację Ai 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.

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+1NPx+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:

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+1NPx+i-1:

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+1NPx+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 Ai w następujący sposób:

Metoda rusztu.png

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 SAiS-1 znajdują się permutację będące swoimi odwrotnościami. Aby posługiwać się rusztem należało wprowadzić pomocnicze twierdzenie:

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

Skoro wiadomo było, że Q i SAiS-1 miały mieć taki sam rozkład na cykle to wystarczyło patrzeć na ruszt na permutację Ai tam gdzie nie było otworów i w miejscu dziur obliczyć złożenie permutacii Ai i P-x-i+1NPx+i-1. Aby to zrobić przesuwano ruszt nad kartka z permutacjami P-x-i+1NPx+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 A1, . . . , A6 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:

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

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 teks 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 17576 razy.

Zobacz też[edytuj]

Bibliografia[edytuj]

  • 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, pp. 241–45
  • Rejewski, Marian (1984d), How the Polish Mathematicians Broke Enigma: Appendix D of Kozaczuk 1984, pp. 246–71
  • Rejewski, Marian (1984e), The Mathematical Solution of the Enigma Cipher: Appendix E of Kozaczuk 1984, pp. 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.