Szyfry i szpiedzy
W dzisiejszym kąciku matematycznym przyjrzę się tematowi, który omawiałem na corocznym obozie naukowym dla dzieci National Children's Foundation. Fundacja poszukuje dzieci i młodzieży o zainteresowaniach naukowych. Nie musisz być wybitnie uzdolniony, ale musisz mieć „zacięcie naukowe”. Bardzo dobre stopnie szkolne nie są wymagane. Spróbuj, może ci się spodoba. Jeśli jesteś uczniem szkoły podstawowej lub liceum, aplikuj. Zazwyczaj raporty sporządzają rodzice lub szkoła, ale nie zawsze tak jest. Znajdź stronę Fundacji i przekonaj się.
W szkole coraz częściej mówi się o „kodowaniu”, odnosząc się do czynności znanej dawniej jako „programowanie”. Jest to powszechna procedura dla nauczycieli teoretyków. Odkopują stare metody, nadają im nową nazwę, a „postęp” robi się sam. Obszarów, w których występuje takie cykliczne zjawisko, jest kilka.
Można stwierdzić, że dewaluuję dydaktykę. NIE. W rozwoju cywilizacji czasami wracamy do tego, co było, zostało porzucone i teraz jest odradzane. Ale nasz zakątek jest matematyczny, a nie filozoficzny.
Przynależność do określonej wspólnoty oznacza także „wspólne symbole”, wspólne czytania, powiedzenia i przypowieści. Ten, kto doskonale nauczył się języka polskiego „w Szczebrzeszynie wielka gąszcz, w trzcinach brzęczy chrząszcz”, od razu zostanie zdemaskowany jako szpieg obcego państwa, jeśli nie odpowie na pytanie, co robi dzięcioł. Oczywiście, że się dusi!
To nie jest tylko żart. W grudniu 1944 r. Niemcy wielkim kosztem rozpoczęli ostatnią ofensywę w Ardenach. Mobilizowali żołnierzy mówiących płynnie po angielsku do zakłócania ruchu wojsk alianckich, np. poprzez prowadzenie ich w złym kierunku na rozdrożach. Po chwili zaskoczenia Amerykanie zaczęli zadawać żołnierzom podejrzane pytania, na które odpowiedzi byłyby oczywiste dla osoby z Teksasu, Nebraski czy Georgii, a nie do pomyślenia dla kogoś, kto tam nie dorastał. Nieznajomość realiów doprowadziła bezpośrednio do egzekucji.
Do momentu. Polecam czytelnikom książkę Łukasza Badowskiego i Zasława Adamaszka "Laboratorium w szufladzie biurka - matematyka". To wspaniała książka, która w błyskotliwy sposób pokazuje, że matematyka naprawdę się do czegoś przyda i że „eksperyment matematyczny” to nie puste słowa. Obejmuje on między innymi opisaną konstrukcję „kartonowej zagadki” – urządzenia, którego stworzenie zajmie nam zaledwie piętnaście minut i które działa jak poważna maszyna szyfrująca. Sam pomysł był tak dobrze znany, że wspomniani autorzy pięknie go opracowali, a ja go trochę zmienię i zawinę w bardziej matematyczne szaty.
piły do \uXNUMXb\uXNUMXbmetalu
Na jednej z ulic mojej wiejskiej wsi pod Warszawą został niedawno rozebrany chodnik z „trlinki” – sześciokątnych płyt chodnikowych. Jazda była niewygodna, ale dusza matematyka się radowała. Pokrycie płaszczyzny regularnymi (czyli regularnymi) wielokątami nie jest łatwe. Mogą to być tylko trójkąty, kwadraty i sześciokąty foremne.
Może trochę żartowałem z tą duchową radością, ale sześciokąt to piękna figura. Z niego możesz zrobić całkiem udane urządzenie szyfrujące. Geometria pomoże. Sześciokąt ma symetrię obrotową - przy obrocie o wielokrotność 60 stopni zachodzi na siebie. Pole oznaczone np. literą A w lewym górnym rogu Figa. 1 po obróceniu o ten kąt wpadnie również do pudełka A - i to samo z innymi literami. Wytnijmy więc sześć kwadratów z siatki, każdy z inną literą. Uzyskaną w ten sposób siatkę nakładamy na kartkę papieru. W wolnych sześciu polach wpisz sześć liter tekstu, który chcemy zaszyfrować. Obróćmy arkusz o 60 stopni. Pojawi się sześć nowych pól - wpisz kolejne sześć liter naszej wiadomości.
Ryż. 1. Trlinks radości matematyki.
W prawo Figa. 1 mamy tekst zakodowany w ten sposób: „Na stacji stoi ogromny, ciężki parowóz”.
Teraz przyda się trochę szkolnej matematyki. Na ile sposobów można ustawić względem siebie dwie liczby?
Co za głupie pytanie? Dla dwojga: albo jeden z przodu, albo drugi.
Świetnie. A trzy liczby?
Nie jest również trudno wymienić wszystkie ustawienia:
123, 132, 213, 231, 312, 321.
No to na cztery! Nadal można to jasno określić. Zgadnij regułę kolejności, którą umieściłem:
1234, 1243, 1423, 4123, 1324, 1342,
1432, 4132, 2134, 2143, 2413, 4213,
2314, 2341, 2431, 4231, 3124, 3142,
3412, 4312, 3214, 3241, 3421, 4321
Kiedy cyfr jest pięć, otrzymujemy 120 możliwych ustawień. Nazwijmy ich permutacje. Liczba możliwych permutacji n liczb to iloczyn 1 2 3 ... n, tzw silny i oznaczone wykrzyknikiem: 3!=6, 4!=24, 5!=120. Dla następnej liczby 6 mamy 6!=720. Użyjemy tego, aby uczynić naszą sześciokątną tarczę szyfrującą bardziej złożoną.
Wybieramy permutację liczb od 0 do 5, np. 351042. Nasz sześciokątny dysk szyfrujący ma w środkowym polu kreskę - dzięki czemu można go ustawić "w pozycji zerowej" - kreskę w górę, jak na ryc. 1. Kładziemy w ten sposób krążek na kartce, na której mamy napisać nasz raport, ale nie zapisujemy go od razu, tylko obracamy go trzy razy o 60 stopni (czyli 180 stopni) i wpisujemy sześć liter w puste pola. Wracamy do pozycji wyjściowej. Tarczę obracamy pięć razy o 60 stopni, czyli o pięć „ząbków” naszej tarczy. Drukujemy. Następna pozycja skali to pozycja obrócona o 60 stopni wokół zera. Czwarta pozycja to 0 stopni, to jest pozycja początkowa.
Czy rozumiesz, co się stało? Mamy dodatkową możliwość - skomplikować naszą „maszynę” ponad siedemset razy! Mamy więc dwie niezależne pozycje „automatu” – wybór siatki i wybór permutacji. Siatkę można wybrać na 66 = 46656 sposobów, permutacja 720. Daje to 33592320 możliwości. Ponad 33 miliony szyfrów! Prawie trochę mniej, bo niektórych siatek nie da się wyciąć z papieru.
W dolnej części Figa. 1 mamy wiadomość zaszyfrowaną w ten sposób: „Wysyłam cztery dywizje spadochronowe”. Łatwo zrozumieć, że wróg nie powinien się o tym dowiedzieć. Ale czy zrozumie cokolwiek z tego:
TPOROPVMANVEORDISZ
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
nawet z podpisem 351042?
Budujemy Enigmę, niemiecką maszynę szyfrującą
Ryż. 2. Przykład początkowej konfiguracji naszej maszyny szyfrującej.
Permutacje (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).
Jak już wspomniałem, pomysł stworzenia takiej kartonowej maszyny zawdzięczam książce „Laboratorium w Szufladzie – Matematyka”. Moja „konstrukcja” jest nieco inna od tej, którą podali jej autorzy.
Maszyna szyfrująca używana przez Niemców podczas wojny miała genialnie prostą zasadę, nieco podobną do tej, którą widzieliśmy w przypadku szyfru szesnastkowego. Za każdym razem to samo: przerwać trudne przypisanie litery do innej litery. Musi być wymienny. Jak to zrobić, żeby mieć nad tym kontrolę?
Wybierzmy nie jakąkolwiek permutację, ale taką, która ma cykle o długości 2. Najprościej mówiąc, coś w rodzaju opisanego tu kilka miesięcy temu "Gaderipoluk", ale obejmującego wszystkie litery alfabetu. Umówmy się na 24 litery - bez ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Ile takich permutacji? To zadanie dla maturzystów (powinni umieć je rozwiązać od razu). Ile? Dużo? Kilka tysięcy? Tak:
1912098225024001185793365052108800000000 (nawet nie próbujmy czytać tej liczby). Możliwości ustawienia pozycji „zero” jest mnóstwo. I to może być trudne.
Nasza maszyna składa się z dwóch okrągłych dysków. Na jednym z nich, który nadal stoi, wypisane są litery. To trochę jak tarcza starego telefonu, w której wybiera się numer, obracając tarczę do końca. Rotary jest drugim z kolorystyką. Najprościej jest założyć je na zwykły korek za pomocą szpilki. Zamiast korka można użyć cienkiej tektury lub grubej tektury. Łukasz Badowski i Zasław Adamaszek zalecają umieszczenie obu płyt w pudełku CD.
Wyobraź sobie, że chcemy zakodować słowo ARMACJA (Ryż. 2 i 3). Ustaw urządzenie w pozycji zerowej (strzałka w górę). Litera A odpowiada literze F. Obróć obwód wewnętrzny o jedną literę w prawo. Mamy literę R do zakodowania, teraz odpowiada ona A. Po kolejnym obrocie widzimy, że litera M odpowiada U. Kolejny obrót (czwarty diagram) daje zgodność A – P. Na piątej tarczy mamy T - A. Wreszcie (szósty krąg ) T – T Wróg raczej nie domyśli się, że nasze CFCFA będą dla niego niebezpieczne. A jak „nasi” odczytają depeszę? Muszą mieć tę samą maszynę, tę samą „zaprogramowaną”, czyli z tą samą permutacją. Szyfr zaczyna się od pozycji zero. Zatem wartość F wynosi A. Obróć pokrętło zgodnie z ruchem wskazówek zegara. Litera A jest teraz powiązana z R. Przekręca tarczę w prawo i pod literą U znajduje M itp. Szyfrator biegnie do generała: „Generale, melduję, nadchodzą pistolety!”
Ryż. 3. Zasada działania naszej papierowej Enigmy.
| Ryż. 3. Zasada działania naszej papierowej Enigmy. | ||
Możliwości nawet tak prymitywnej Enigmy są niesamowite. Możemy wybrać inne permutacje wyjściowe. Możemy – a tu możliwości jest jeszcze więcej – nie jednym „szeryfem” regularnie, ale w określonej, codziennie zmieniającej się kolejności, podobnej do sześciokąta (np. najpierw trzy litery, potem siedem, potem osiem, cztery… .. itd.).
Jak możesz zgadywać?! A jednak dla polskich matematyków (Marian Rejewski, Henryka Zigalskiego, Eży Ruzicki) stało się. Uzyskane w ten sposób informacje były bezcenne. Wcześniej mieli równie ważny wkład w historię naszej obronności. Wacław Sierpiński i Stanisław Mazurkiewiczktóry naruszył kodeks wojsk rosyjskich w 1920 r. Przechwycony kabel dał Piłsudskiemu możliwość wykonania słynnego manewru znad rzeki Vepsz.
Pamiętam Wacława Sierpińskiego (1882-1969). Wyglądał jak matematyk, dla którego świat zewnętrzny nie istnieje. O swoim udziale w zwycięstwie w 1920 r. nie mógł mówić ani ze względów militarnych, ani… politycznych (władza PRL nie lubiła tych, którzy bronili nas przed Związkiem Sowieckim).
Ryż. 4. Permutacja (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).
Ryż. 5. Piękna dekoracja, ale nie nadaje się do szyfrowania. Zbyt regularnie.
Zadanie 1. Na Figa. 4 masz kolejną permutację do stworzenia Enigmy. Skopiuj rysunek do kserografu. Zbuduj samochód, zakoduj swoje imię i nazwisko. Mój CWONUE JTRYGT. Jeśli chcesz zachować prywatność swoich notatek, użyj Cardboard Enigma.
Zadanie 2. Zaszyfruj swoje imię i nazwisko jednego z „samochodów”, które widziałeś, ale (uwaga!) z dodatkową komplikacją: skręcamy nie o jeden ząbek w prawo, ale zgodnie ze schematem {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - czyli najpierw o jeden, potem o dwa, potem o trzy, potem o 2, potem znowu o 1, potem o 2 itd., taka „falka” . Upewnij się, że moje imię i nazwisko są zaszyfrowane jako CZTTAK SDBITH. Czy teraz rozumiesz, jak potężna była maszyna Enigma?
Rozwiązywanie problemów dla absolwentów szkół średnich. Ile opcji konfiguracyjnych dla Enigmy (w tej wersji, jak opisano w artykule)? Mamy 24 litery. Wybieramy pierwszą parę liter - można to zrobić dalej
sposoby. Można wybrać następną parę
metody, dalej
itp. Po odpowiednich obliczeniach (wszystkie liczby należy pomnożyć) otrzymujemy
151476660579404160000
Następnie podziel tę liczbę przez 12! (12 silni), ponieważ te same pary można otrzymać w innej kolejności. Więc w końcu otrzymujemy „całkowity”
316234143225,
to nieco ponad 300 miliardów, co nie wydaje się oszałamiająco dużą liczbą dla dzisiejszych superkomputerów. Jeśli jednak weźmie się pod uwagę losową kolejność samych permutacji, liczba ta znacznie wzrasta. Możemy również pomyśleć o innych rodzajach permutacji.
Zobacz także:
