Cyklometr

Ten artykuł dotyczy urządzenia kryptologicznego. Aby zapoznać się z urządzeniem używanym podczas jazdy na rowerze, zobacz cyklokomputer . „Cyclometer” oznacza również osobę, która pracuje albo nad klasycznym problemem kwadratury koła , albo nad geometrią okręgów .

Cyklometr , opracowany w połowie lat 30-tych przez Rejewskiego do katalogowania cyklicznej struktury permutacji Enigmy . 1: Pokrywa rotora zamknięta, 2: Pokrywa rotora otwarta, 3: Reostat, 4: Lampy jarzeniowe, 5: Przełączniki, 6: Litery.

Rekonstrukcja wyglądu cyklometru na podstawie szkiców ze wspomnień Mariana Rejewskiego

Cyklometr był urządzeniem kryptologicznym zaprojektowanym „prawdopodobnie w 1934 lub 1935 roku” przez Mariana Rejewskiego z niemieckiej sekcji Polskiego Biura Szyfrów (BS-4) w celu ułatwienia odszyfrowania niemieckiego szyfrogramu Enigmy . Uważa się, że oryginalne maszyny zostały zniszczone na krótko przed niemiecką inwazją na Polskę, która rozpoczęła drugą wojnę światową , aby Niemcy nie dowiedzieli się, że ich szyfr został złamany.

Korzystając z rysunków wykonanych przez Rejewskiego, Hala Evansa i Tima Flacka z Wydziału Inżynierii Uniwersytetu Cambridge , w 2019 roku skonstruowano działającą wersję cyklometru.

Historia

Przykładowa wiadomość

Maszyna Enigma - elektromechaniczna maszyna wirnikowa z szyfratorem składająca się (od prawej do lewej) bębna wejściowego, trzech wirników, reflektora. Zmodyfikowana wersja została przyjęta później w latach dwudziestych XX wieku przez wojsko niemieckie.

Frode Weierud przedstawia procedurę, tajne ustawienia i wyniki, które zostały użyte w niemieckiej instrukcji technicznej z 1930 roku.

Klucz dzienny (wspólny sekret): Kolejność koła : II I III Ringstellung : 24 13 22 (XMV) Odbłyśnik : A Tablica wtyczek : AM, FI, NV, PS, TU, WZ Grundstellung: FOL Klucz wiadomości wybrany przez operatora : ABL Zaszyfrowany zaczynając od FOL : PKPJXI Wiadomość tekstowa do wysłania i wynikowy tekst jawny: Feindliche Infanteriekolonne beobachtet. Anfang Südausgang Bärwalde. Ende drei km ostwärts Neustadt. FEIND LIQEI NFANT ERIEK OLONN EBEOB AQTET XANFA NGSUE DAUSG ANGBA ERWAL DEXEN DEDRE IKMOS TWAER TSNEU STADT Wynikowa wiadomość: 1035 – 90 – 341 – PKPJX IGCDS EAHUG WTQGR KVLFG XUCAL XVYMI GMMNM FDXTG NVHVR MMEVO U YFZS LRHDR RXFJW CFHUH MUNZE FRDIS IKBGP MYVXU Z

Pierwsza linia wiadomości nie jest szyfrowana. „1035” to czas, „90” to liczba znaków zaszyfrowanych kluczem wiadomości, a „341” to wskaźnik systemowy, który mówi odbiorcy, w jaki sposób wiadomość została zaszyfrowana (tj. przy użyciu Enigmy z określonym kluczem dziennym). Pierwsze sześć liter w treści („PKPJXI”) to podwójny klucz („ABLABL”) zaszyfrowany przy użyciu codziennych ustawień klucza i rozpoczynający szyfrowanie od ustawienia podstawowego / Grundstellung „FOL”. Odbiorca odszyfrowałby pierwsze sześć liter, aby odzyskać klucz wiadomości („ABL”); następnie ustawiał wirniki maszyny na „ABL” i odszyfrowywał pozostałe 90 znaków. Zauważ, że Enigma nie ma cyfr, znaków interpunkcyjnych ani umlautów. Liczby zostały zapisane. Większość spacji została zignorowana; „X” był używany przez okres. Umlauty używały swojej alternatywnej pisowni z końcowym „e”. Użyto niektórych skrótów: zamiast „CH” użyto „Q”.

Mariana Rejewskiego

Mariana Rejewskiego , ok. 1932

Marian Rejewski był studentem matematyki na Uniwersytecie Poznańskim . W tym czasie Polskie Biuro Szyfrów zwerbowało Rejewskiego i kilku innych studentów matematyki, w tym Jerzego Różyckiego i Henryka Zygalskiego , na sponsorowany przez Biuro kurs kryptologii. Biuro zatrudniło później niektórych studentów do pracy w niepełnym wymiarze godzin w lokalnym oddziale Biura. Rejewski opuścił Poznań, aby studiować matematykę na Uniwersytecie w Getyndze , ale po roku wrócił do Poznania. We wrześniu 1932 r. Rejewski, Różycki i Zygalski udali się do Warszawy i rozpoczęli pracę na pełen etat w Polskim Biurze Szyfrów.

W grudniu 1932 r. Biuro Szyfrów zleciło Marianowi Rejewskiemu pracę nad niemiecką Enigmą. Biuro próbowało się złamać kilka lat wcześniej, ale nie powiodło się. W ciągu kilku tygodni Rejewski odkrył, jak złamać niemiecką maszynę szyfrującą Enigma. Niemieckie procedury wiadomości Enigmy w tamtym czasie wykorzystywały powszechne, ale tajne codzienne ustawienia maszyny, ale procedury wymagały również, aby każdy urzędnik kodowy wybierał trzyliterowy klucz wiadomości. Na przykład urzędnik może wybrać „ABL” jako klucz wiadomości. Klucz wiadomości był używany do ustawiania początkowej pozycji wirników podczas szyfrowania (lub deszyfrowania) treści wiadomości. Wybór innego klucza wiadomości był środkiem bezpieczeństwa: pozwalał uniknąć wysyłania wszystkich wiadomości z tego samego dnia przy użyciu tego samego klucza wieloalfabetowego, co naraziłoby wiadomości na atak polialfabetyczny. Jednak nadawca musiał przekazać klucz wiadomości odbiorcy, aby odbiorca mógł odszyfrować wiadomość. Klucz wiadomości został najpierw zaszyfrowany przy użyciu dziennego Grundstellung (tajna początkowa pozycja wirników Enigmy, np. „FOL”).

Komunikacja była czasami zniekształcona, a jeśli klucz wiadomości był zniekształcony, odbiorca nie byłby w stanie odszyfrować wiadomości. W związku z tym Niemcy podjęli środki ostrożności i dwukrotnie wysłali klucz wiadomości; jeśli wystąpił błąd, odbiorca powinien być w stanie znaleźć klucz wiadomości. Tutaj Niemcy popełnili zasadniczy błąd. Zamiast wysyłać zaszyfrowany klucz wiadomości (np. „PKP”) dwa razy, aby uzyskać „PKP PKP”, Niemcy podwoili klucz wiadomości (np. „ABL ABL”), zaszyfrowali zdublowany klucz, aby uzyskać („PKP JXI”), i wysłał zaszyfrowany podwójny klucz. Ten błąd pozwolił Rejewskiemu zidentyfikować sześć kolejnych permutacji Enigmy i wykorzystać wiedzę, którą zaszyfrowali tym samym kluczem wiadomości.

Z pomocą komercyjnej maszyny Enigma, niektórych niemieckich materiałów uzyskanych przez francuskiego szpiega Hansa Thilo-Schmidta i niemieckich szyfrantów, którzy wybierali słabe klucze, Rejewki był w stanie odtworzyć okablowanie wirników i reflektora Enigmy. Polskie Biuro Szyfrów zbudowało następnie kilka polskich sobowtórów Enigmy , których można było użyć do odszyfrowania niemieckich wiadomości.

Charakterystyka

Niemiecka procedura, która wysłała zaszyfrowany podwójny klucz, była błędem, który dał Rejewskiemu wejście. Rejewski postrzegał Enigmę jako permutację liter zwykłego tekstu na tekst zaszyfrowany. Dla każdej pozycji znaku w wiadomości maszyna stosowała inną permutację. Niech ABCDEF będzie odpowiednimi permutacjami dla liter od pierwszej do szóstej. Rejewski wiedział, że pierwsza i czwarta litera są takie same, druga i piąta litera są takie same, a trzecia i szósta litera są takie same. Rejewski mógłby wtedy zbadać dzienny ruch wiadomości; przy wystarczającym ruchu mógł złożyć złożone permutacje.

Na przykład dla klucza dziennego w podręczniku technicznym z 1930 r. (z wystarczającą liczbą wiadomości) Rejewski mógł znaleźć następujące cechy:

${\ Displaystyle {\ rozpocząć {wyrównane}AD&={\texttt {(pjxroquctwzsy)(kvgledmanhfib)}}\\BE&={\texttt {(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}}\\CF&={\texttt {(yvxqtdhpim )(skgrjbcolw)(un)(fa)(e)(z)}}\\\end{wyrównane}}}$

Notacja jest notacją cyklu Cauchy'ego . Badając ruch uliczny w ciągu dnia, Rejewski zauważyłby, że gdyby „p” było pierwszą literą wskaźnika, to „j” byłoby czwartą literą. Na innym wskaźniku „j” byłoby pierwszą literą, a „x” czwartą literą. Rejewski kontynuował śledzenie listów. W końcu pojawi się wiadomość, której pierwszą literą będzie „y”, a czwarta litera wróci do „p”. Te same uwagi byłyby poczynione dla drugiej i piątej litery; zwykle byłoby kilka cykli.

Metoda grillowa

Główny artykuł: Grill (kryptologia)

Rejewski mógł wykorzystać te informacje o cyklu i niektóre niechlujne nawyki urzędników kodów do obliczenia poszczególnych permutacji ABCDEF za pomocą metody grilla , ale ta metoda była żmudna. Po użyciu grilla Polacy znali prawy wirnik i jego położenie, połączenia wtykowe i Q (permutacja reflektora i pozostałych dwóch wirników). Aby zdobyć klucz dzienny, Polacy mieliby jeszcze dużo pracy, a ta praca mogłaby polegać na wypróbowaniu wszystkich możliwych rozkazów i pozycji dla dwóch lewych wirników, aby znaleźć pozycję dla Grundstellung. Polacy zaczęli używać Q -katalogu, aby ułatwić część metody grillowania; katalog ten zawierał 4056 wpisów (26 × 26 × 6). Aby znaleźć ustawienia pierścienia, metoda grillowania może wymagać wypróbowania 17 576 możliwości.

Metoda grillowania działała dobrze do 1 października 1936 r., kiedy to Niemcy przestali używać sześciu steckerów (połączeń wtykowych) i zaczęli używać od pięciu do ośmiu steckerów. Więcej steckerów może udaremnić metodę grillowania.

Polacy szukali kolejnego ataku i zdecydowali się na inną metodę katalogową. Było tylko 105 456 indywidualnych permutacji, które Polacy rozważali (Polacy ignorowali przypadki, w których dwa lewe bębny poruszały się podczas szyfrowania wskaźnika). Gdyby Polacy mieli katalog tych permutacji, mogliby sprawdzić kolejność i położenie wirników. Niestety, notacja cyklu Cauchy'ego nie jest odpowiednia. Notację cyklu dla AD można by umieścić w kanonicznej kolejności alfabetycznej, aby służyła jako klucz, ale ten klucz byłby inny dla każdego z 7 bilionów możliwych ustawień wtyczki.

Długości cykli

Zamiast indeksować katalog według rzeczywistych cykli, Polacy wpadli na indeksowanie katalogu według długości cykli. Chociaż tablica wtyczek zmieniła tożsamość liter w permutacji, tablica wtyczek nie zmieniła długości cykli.

Okazuje się, że istnieje 101 możliwych wzorców długości cyklu permutacji wskaźnika. Przy trzech permutacjach w charakterystyce istnieje około miliona możliwych kombinacji długości cyklu ( 101 ³ = 1 030 301 ). W związku z tym długości cykli można wykorzystać jako funkcję skrótu w tablicy skrótów zawierającej 105 456 możliwych kombinacji. Polacy patrzyli na dzienny ruch, odzyskiwali charakterystykę wskaźnika, a potem zaglądali do kartoteki. Szanse byłyby duże, gdyby tylko jedna (a może kilka) kart miała taką długość cyklu.

Rezultatem byłaby odpowiednia kolejność wirników i pozycje wszystkich wirników bez większego nakładu pracy. Metoda była prostsza niż metoda grillowania i działała, gdy było wielu steckerów.

Odzyskiwanie wtyczki

Katalog nie ujawnił ustawień wtyczki. W przypadku sześciu wtyczek ( steckerów ) istnieje około 100 miliardów możliwych układów. Wypróbowanie ich wszystkich jest niewykonalne. Jednak kryptograf mógłby znaleźć charakterystykę dla tej kolejności wirników bez wtyczki, użyć tej samej charakterystyki w ataku ze znanym tekstem jawnym, a następnie określić ustawienia wtyczki, porównując je z charakterystyką dzienną.

Z pewnego dziennego ruchu kryptoanalityk obliczyłby charakterystykę.

${\ Displaystyle {\ rozpocząć {wyrównane}AD&={\texttt {(pjxroquctwzsy)(kvgledmanhfib)}}\\BE&={\texttt {(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}}\\CF&={\texttt {(yvxqtdhpim )(skgrjbcolw)(un)(fa)(e)(z)}}\\\end{wyrównane}}}$

W metodzie grilla powyższą charakterystykę rozwiązano by dla poszczególnych permutacji ABCDEF , a następnie dokonano by pracochłonnego wyszukiwania. Zamiast tego obliczane byłyby sparowane długości cykli charakterystyki:

AD: 13 BE: 10 3 CF: 10 2 1

Długości te byłyby wyszukiwane w katalogu kartkowym i znajdowany byłby wpis określający kolejność kół (II, I, III) oraz początkową pozycję każdego koła.

Katalog kartkowy nie zawierał faktycznej charakterystyki: cyklometr wskazywał jedynie przynależność do cyklu; nie określał kolejności liter w cyklu. Po znalezieniu wpisu w katalogu kryptoanalityk obliczałby następnie charakterystykę bez steckerów (tylko ustawienia katalogu). Kryptoanalityk może określić każdą z indywidualnych permutacji A* B* C* D* E* F*, ustawiając Enigmę w podanej kolejności kół i pozycjach początkowych. Następnie kryptoanalityk naciska i przytrzymuje; odpowiednia lampka zapala się i jest zapisywana; nie puszczając pierwszej litery, kryptoanalityk naciska b , a następnie puszcza pierwszą literę; który powstrzymuje maszynę przed posuwaniem się naprzód wirników i zapala lampkę odpowiadającą b . Po zmapowaniu całego A kryptoanalityk może przejść do B i innych permutacji. Cyptoanalityk odzyskuje niesterowaną charakterystykę:

${\ Displaystyle {\ rozpocząć {wyrównane} A ^ {*} D ^ {*} & = {\ texttt {(jxroqtcuzwpys) (kngledamvhifb)}} \\ B ^ {*} E ^ {*} i = {\ texttt {(kxucofgzeh)(wnibpylrvs)(aqm)(dtj)}}\\C^{*}F^{*}&={\texttt {(colzpkgrjb)(ynxqudhsfa)(vt)(mi)(e)( w)}}\\\koniec {wyrównany}}}$

Te dwie cechy są następnie używane do rozwiązania permutacji steckera S .

W tym przykładzie jest sześć steckerów i wpłynęłyby one na 12 znaków. Patrząc na CF , cykle tablicy wtykowej (un)(fa) muszą być transponowane z cyklami niesteckerowanymi (vt)(mi) . Żadna z liter nie jest taka sama, więc wszystkie z tych ośmiu liter są ułożone. Spojrzenie na cykle singletonowe CF i C*F* pokazuje nie tylko, że „e” nie jest sklejone, ale także, że „w” i „z” są sklejone razem. W ten sposób można szybko zidentyfikować dziesięć z dwunastu naklejonych liter. Większość z pozostałych 16 liter, takich jak „b”, „d”, „g” i „l”, prawdopodobnie nie jest zszyta. Notację cykliczną A*D* , B*E* i C*F* można zmienić tak, aby pasowała do prawdopodobnie niesklejonych znaków. (Początkowa litera notacji cyklu nie jest znacząca: w cyklu litery muszą zachować tę samą kolejność, ale mogą być obracane. Na przykład (dtj) jest tym samym, co (tjd), co jest tym samym , co jdt . )

${\ Displaystyle { \begin{aligned}AD&={\texttt {(pjxroquctwzsy)(kvgledmanhfib)}}\\A^{*}D^{*}&={\texttt {(sjxroqtcuzwpy)(kngledamvhifb)}}\\BE&={ \texttt {(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}}\\B^{*}E^{*}&={\texttt {(kxucofgzeh)(wnibpylrvs)(tjd)(aqm)}}\ \CF&={\texttt {(yvxqtdhpim)(skgrjbcolw)(un)(fa)(e)(z)}}\\C^{*}F^{*}&={\texttt {(ynxqudhsfa)(pkgrjbcolz )(tv)(im)(e)(w)}}\\\end{wyrównane}}}$

W tym momencie potencjalne steckery można odczytać z różnic w pierwszych dwóch wierszach; można je również sprawdzić pod kątem spójności wymiany. Wynik to

PS TU WZ NV AM FI

Te steckery pasują do przykładu Enigmy z 1930 roku.

Jedynym pozostałym sekretem są pozycje pierścieni ( Ringstellung ).

Budowanie katalogu

Cyklometr posłużył do sporządzenia katalogu długości i liczby cykli w „charakterystyce” dla wszystkich 17 576 położeń wirników dla danej sekwencji wirników. Ponieważ było sześć takich możliwych sekwencji, powstały „katalog cech” lub „ katalog kartkowy ” zawierał w sumie (6) (17 576) = 105 456 wpisów.

Użyteczność katalogu kartkowego , pisze Rejewski, była niezależna od liczby wtyczek używanych przez Niemców w ich maszynach Enigma (i od rekonstrukcji kluczy depesz). Przygotowanie katalogu „było pracochłonne i trwało ponad rok, ale kiedy było gotowe… codzienne klucze [można było uzyskać] w ciągu około piętnastu minut”.

Jednak 1 listopada 1937 r. Niemcy zmienili „bęben zwrotny”, czyli „ reflektor ”. Zmusiło to Biuro Szyfrów do rozpoczęcia od nowa nowego katalogu kartkowego, „zadania”, pisze Rejewski, „które pochłonęło, ze względu na nasze większe doświadczenie, prawdopodobnie nieco mniej niż rok czasu”.

Ale wtedy, 15 września 1938 roku, Niemcy całkowicie zmienili procedurę szyfrowania kluczy wiadomości, w wyniku czego metoda kartowo-katalogowa stała się całkowicie bezużyteczna. Stało się to bodźcem do wynalezienia bomby kryptologicznej Rejewskiego i blach perforowanych Zygalskiego .

Zobacz też

• Bomba kryptologiczna : maszyna zaprojektowana około października 1938 roku przez Mariana Rejewskiego w celu ułatwienia odzyskiwania kluczy Enigmy.
• Bomba : maszyna zainspirowana „bombą (kryptologiczną)” Rejewskiego, której używali brytyjscy i amerykańscy kryptolodzy podczas II wojny światowej.
• Kryptoanaliza Enigmy i maszyny Enigma .
• Arkusze Zygalskiego : wynalezione około października 1938 roku przez Henryka Zygalskiego i nazywane przez Polaków „arkuszami perforowanymi”, umożliwiły odzyskanie całego klucza szyfrującego Enigmy.

Notatki

•   Władysław Kozaczuk , Enigma : Jak złamano niemiecki szyfr maszynowy i jak odczytali go alianci podczas II wojny światowej , zredagowane i przetłumaczone przez Christophera Kasparka , Frederick, MD, University Publications of America, 1984, ISBN 0-89093-547 -5 .
•   Rejewski, Marian (lipiec 1981), „Jak polscy matematycy rozszyfrowali zagadkę”, Annals of the History of Computing , IEEE, 3 (3): 213–234, doi : 10.1109 / MAHC.1981.10033 , S2CID 15748167
• Marian Rejewski , „Podsumowanie naszych metod rekonstrukcji ENIGMY i rekonstrukcji codziennych kluczy oraz niemieckich wysiłków zmierzających do udaremnienia tych metod”, Dodatek C do Władysława Kozaczuka , Enigma: Jak złamano niemiecki szyfr maszynowy i jak go odczytali alianci w II wojnie światowej , 1984, s. 241–45.
• Marian Rejewski , „Matematyczne rozwiązanie szyfru Enigmy”, dodatek E do Władysława Kozaczuka , Enigma: jak złamano niemiecki szyfr maszynowy i jak go odczytali alianci podczas II wojny światowej , 1984, s. 272–291.

Linki zewnętrzne

• „Polski sobowtór Enigmy”
• O Enigmie (Agencja Bezpieczeństwa Narodowego) zarchiwizowane 14.04.2004 w Wayback Machine
• „Złamanie szyfru Enigmy” Jana Bury'ego
• „Enigma” i inteligencja
• „Łamanie szyfrów i tajna broń podczas II wojny światowej” Billa Momsena
• Krótka historia technologii komputerowej, 1930-1939
•   Kuhl, Alex (październik 2007), „Katalog Rejewskiego” (PDF) , Cryptologia , Taylor & Francis, 31 (4): 326–331, doi : 10.1080/01611190701299487 , S2CID 14254844 , zarchiwizowane z oryginału (PDF) w latach 2015- 07-24