Turingery - Turingery

Metoda Turingery'ego lub Turinga (żartobliwie nazwana Turingismus przez Petera Ericssona, Petera Hiltona i Donalda Michie ) była ręczną metodą łamania kodów opracowaną w lipcu 1942 roku przez matematyka i kryptoanalityka Alana Turinga w British Government Code and Cypher School w Bletchley Park podczas II wojny światowej . To było do stosowania w kryptoanalizy szyfru Lorenz wytwarzanego przez SZ40 SZ42 i dalekopis wirnika szyfru strumieniowego maszyn, jeden z Niemców ' Geheimschreiber (tajny writer) maszyny. Brytyjczycy o kryptonimie non- Morse traffic „Fish” , a ten z tej maszyny „Tunny” (inne określenie tuńczyka ).

Odczytanie komunikatu Tunny'ego wymagało, po pierwsze, aby była znana logiczna struktura systemu, po drugie, aby wyprowadzić okresowo zmieniany wzór aktywnych krzywek na kołach, a po trzecie, że pozycje początkowe kół szyfrujących dla tej wiadomości - klucz wiadomości - były ustanowiony. Logiczna struktura Tunny została opracowana przez Williama Tutte i jego współpracowników przez kilka miesięcy do stycznia 1942 roku. Wyprowadzenie klucza wiadomości nazywane było „ustawieniem” w Bletchley Park, ale było to wyprowadzenie wzorców krzywek - które było znane jako „ łamanie koła ”- to był cel Turingery'ego.

Błędy niemieckiego operatora przy przesyłaniu więcej niż jednej wiadomości z tym samym kluczem, dające „głębię” , pozwoliły na wyprowadzenie tego klucza. Turingery został zastosowany do takiego strumienia kluczy, aby uzyskać ustawienia krzywki.

SZ40 i SZ42

Logiczne funkcjonowanie systemu Tunny zostało opracowane na długo przed tym, jak kryptoanalitycy z Bletchley Park zobaczyli jedną z maszyn - co miało miejsce dopiero w 1945 roku, na krótko przed zwycięstwem aliantów w Europie.

Maszyny Lorenz SZ miały 12 kół, każde z inną liczbą krzywek (lub „sworzni”).
Numer koła 1 2 3 4 5 6 7 8 9 10 11 12
Nazwa koła BP 1 2 3 4 5 37 61 1 2 3 4 5
Liczba krzywek (pinów) 43 47 51 53 59 37 61 41 31 29 26 23

Maszyny SZ były 12- kołowymi maszynami szyfrującymi wirnik , które implementowały szyfr strumieniowy Vernama . Zostały dołączone w linii do standardowych drukarek Lorenz. Znaki wiadomości zostały zakodowane w 5-bitowym międzynarodowym alfabecie telegraficznym nr 2 (ITA2) . Znaki wyjściowego tekstu zaszyfrowanego zostały wygenerowane przez połączenie pseudolosowego strumienia klucza znak po znaku ze znakami wejściowymi przy użyciu funkcji „ wyłącznej lub ” (XOR), oznaczonej jako w notacji matematycznej. Relacja między tekstem jawnym , tekstem zaszyfrowanym i kluczem kryptograficznym jest zatem następująca:

Podobnie w przypadku odszyfrowania tekst zaszyfrowany został połączony z tym samym kluczem, aby uzyskać tekst jawny:

Daje to niezbędną wzajemność, pozwalającą na użycie tej samej maszyny z tymi samymi ustawieniami zarówno do szyfrowania, jak i deszyfrowania.

Każdy z pięciu bitów klucza dla każdego znaku został wygenerowany przez odpowiednie koła w dwóch częściach maszyny. Nazywały się one kołami chi ( ) i kołami psi ( ). Wszystkie koła chi przesunęły się o jedną pozycję dla każdej postaci. W psi koła też wszystko przeniósł się razem, ale nie po każdym znaku. Ich ruch był kontrolowany przez dwa mu ( ) lub „motorowe” koła.

Strumień klucza generowany przez maszyny SZ miał zatem komponent chi i komponent psi , które zostały połączone razem z funkcją XOR. Zatem klucz, który został połączony z tekstem jawnym do zaszyfrowania - lub z tekstem zaszyfrowanym do odszyfrowania - można przedstawić w następujący sposób.

Symbolicznie:

Każde z dwunastu kół miało wokół siebie szereg krzywek (lub „szpilek”). Te krzywki mogą być ustawione w pozycji podniesionej lub opuszczonej. W pozycji podniesionej generowały „znak” „ × ” (binarnie „1”), w pozycji obniżonej generowały „spację” „ · ” (binarnie „0”). Liczba krzywek na każdym kole odpowiadała liczbie impulsów potrzebnych do wykonania pełnego obrotu. Wszystkie te liczby są sobie równe , dając najdłuższy możliwy czas przed powtórzeniem wzoru. Przy łącznej liczbie 501 krzywek daje to 2 501, czyli około 10 151 , czyli astronomicznie dużą liczbę. Jeśli jednak pięć impulsów zostanie rozpatrzonych niezależnie, liczby są znacznie łatwiejsze do opanowania. Produkt okresu obrotu każdej pary chi kół daje numery między 41 x 31 = 1271 i 26 x 23 = 598.

Różnicowanie

Kryptanaliza często polega na znalezieniu pewnego rodzaju wzorców, które pozwalają wyeliminować szereg kluczowych możliwości. W Bletchley Park kombinacja XOR wartości dwóch sąsiednich liter w kluczu lub zaszyfrowanym tekście została nazwana różnicą (symbolizowaną przez grecką literę delta ), ponieważ XOR jest tym samym, co odejmowanie modulo 2 (bez „pożyczki”) - i nawiasem mówiąc , dodawanie modulo 2 (bez "przenoszenia"). Tak więc dla znaków w klawiszu (K) różnicę otrzymano w następujący sposób, gdzie podkreślenie wskazuje na kolejny znak:

(Podobnie z tekstem jawnym, tekstem zaszyfrowanym i dwoma składnikami klucza).

Relacja między nimi ma zastosowanie, gdy są różni. Na przykład, a także:

Jest tak, że:

Jeśli tekst jawny jest reprezentowany przez P, a zaszyfrowany przez Z, to również obowiązuje:

I:

Powodem, dla którego różnicowanie umożliwiło drogę do Tunny'ego, było to, że chociaż rozkład częstotliwości znaków w zaszyfrowanym tekście nie mógł być odróżniony od losowego strumienia, to samo nie dotyczyło wersji zaszyfrowanego tekstu, z której element chi klucza miał został usunięty. Dzieje się tak, ponieważ tam, gdzie tekst jawny zawierał powtarzający się znak, a koła psi nie poruszały się dalej, zróżnicowany znak psi ( ) byłby znakiem zerowym („ ····· ” lub 00000) lub, w terminologii Bletchley Park, „ / ”. Po wykonaniu operacji XOR z dowolnym znakiem ten znak zerowy nie ma żadnego efektu, więc w tych okolicznościach . Powtarzające się znaki w tekście jawnym były częstsze, zarówno ze względu na cechy niemieckiego (EE, TT, LL i SS są stosunkowo powszechne), jak i dlatego, że telegrafiści często powtarzali znaki z przesunięciem cyfr i liter jako ich utratę w zwykłym telegrafie. wiadomość może prowadzić do bełkotu .

Cytując raport ogólny dotyczący Tunny:

Turingery wprowadził zasadę, że klucz różniący się od jednego, teraz nazywany , może dostarczać informacji nieosiągalnych ze zwykłego klucza. Zasada ta miała być fundamentalną podstawą prawie wszystkich statystycznych metod łamania i ustawiania kół.

Różnicowanie na poziomie bitów

Oprócz różnicowania pełnych 5-bitowych znaków kodu ITA2 , zastosowano je również do poszczególnych impulsów (bitów). Tak więc dla pierwszego impulsu, który został zaszyfrowany przez koła i różnił się jednym:

A dla drugiego impulsu:

I tak dalej.

Warto również zauważyć, że cykliczność kół chi i psi dla każdego impulsu (odpowiednio 41 i 43 dla pierwszego) znajduje odzwierciedlenie w jego wzorze . Jednak biorąc pod uwagę, że koła psi nie przesuwały się dla każdego znaku wejściowego, tak jak koła chi , nie było to po prostu powtórzenie wzoru co 41 × 43 = 1763 znaków , ale bardziej złożona sekwencja.

Metoda Turinga

W lipcu 1942 r. Turing spędził kilka tygodni w Sekcji Naukowej. Zainteresował się problemem wyłamania Tunny'ego z kluczy zdobytych z głębin . W lipcu opracował metodę wyprowadzenia ustawień krzywki na podstawie długości klucza. Obejmował iteracyjny , prawie próbny i błędny proces. Polegał on na fakcie, że gdy zróżnicowany znak psi jest znakiem zerowym (" ····· " lub 00000),  / , wówczas XOR- owanie tego z jakimkolwiek innym znakiem go nie zmienia. Zatem znak klucza delta nadaje charakter pięciu kołom chi (tj .).

Biorąc pod uwagę, że charakter delta psi był znakiem zerowym średnio przez połowę czasu, założenie miało 50% szans na poprawność. Proces rozpoczął się od potraktowania określonego znaku jako Δ dla tej pozycji. Wynikowy przypuszczalny wzór bitowy × i · dla każdego koła chi zapisano na arkuszu papieru, który zawierał tyle kolumn, ile było znaków w kluczu, oraz pięć wierszy reprezentujących pięć impulsów . Biorąc pod uwagę wiedzę z pracy Tutte, o okresowości każdego z kół, pozwoliło to na propagację tych wartości w odpowiednich pozycjach w pozostałej części klucza.

Przygotowano również zestaw pięciu arkuszy, po jednym dla każdego koła chi . Zawierały one zestaw kolumn odpowiadających liczbie krzywek dla odpowiedniego koła chi i były określane jako „klatka”. Czyli klatka miała 29 takich kolumn. Kolejne „domysły” wartości dały następnie dalsze domniemane wartości stanu krzywki. Mogą one zgadzać się z wcześniejszymi założeniami lub nie zgadzać się z nimi, a na arkuszach tych zamieszczono szereg uzgodnień i nieporozumień. Tam, gdzie spory znacznie przeważały nad umowami, zakładano, że znak ten nie jest pustym znakiem „ / ”, więc odpowiednie założenie zostało zdyskontowane. Stopniowo wyprowadzono wszystkie ustawienia krzywek kół chi , a na ich podstawie ustawienia krzywki psi i koła silnikowego.

W miarę rozwoju metody wprowadzono ulepszenia, które pozwoliły na użycie jej z dużo krótszymi kluczami niż oryginalne 500 lub więcej znaków.

Zobacz też

Odniesienia i uwagi

Bibliografia