O przejmowaniu liścików przez nauczycieli, czyli zajęcia dodatkowe z matematyki z elementami kryptografii

Inspiracją do poprowadzenia przeze mnie zajęć, podczas których pokazałam uczniom gimnazjum zastosowanie matematyki w kryptografii, były wiadomość ukryta na karteczce przekazywanej przez uczniów, a przechwyconej przeze mnie na lekcji matematyki, oraz praca licencjacka mojego studenta, zatytułowana „Elementy algebry i teorii liczb w szyfrowaniu”.
Poniżej przedstawię dwie najprostsze pod względem algorytmicznym techniki szyfrowania, które z powodzeniem można wykorzystać na zajęciach dodatkowych w najstarszych klasach szkoły podstawowej. Przy omawianiu niniejszych zagadnień utrwalona zostanie wiedza dotycząca dzielenia z resztą i liczb pierwszych, a także poszerzone zostaną umiejętności kryptograficzne, które przyprawią o ból głowy niejednego nauczyciela czy rodzica przechwytującego korespondencję swoich podopiecznych.
Metody mające na celu utajnienie tekstu znane były już w starożytności. Juliusz Cezar w I w. p.n.e. do szyfrowania swoich rozkazów, zabezpieczając je przed przejęciem przez wroga, stosował szyfr polegający na zamianie liter – dzięki temu tekst wydawał się pozbawiony sensu. Nie była to, oczywiście, przypadkowa zamiana – polegała na zastąpieniu każdej litery w tekście literą, która znajduje się trzy pozycje dalej. Jeżeli zastosujemy klasyczny alfabet składający się z 26 liter, od A do Z, to np. A zostanie zastąpione przez D, E przez H itd. Do dzisiejszego dnia szyfr oparty na powyższym algorytmie nazywany jest szyfrem Cezara.
 

Oczywiście, możemy zastosować inny klucz i przesunąć litery o inną liczbę miejsc do przodu lub do tyłu. Taki szyfr nazywamy szyfrem podstawieniowym. Aby odszyfrować podaną wiadomość, wystarczy zastosować klucz deszyfrujący, który polega na przesunięciu liter w przeciwnym kierunku o tyle samo znaków, co w kluczu szyfrującym.
 

Liczenie liter nie jest zajęciem zbyt trudnym, jednakże dość uciążliwym. Co więcej, w takiej postaci zastosowanie matematyki wydaje się być raczej symboliczne. Aby odszyfrowywanie przebiegało sprawniej, a Czytelnik przekonał się o wkładzie matematyki w omawiane zagadnienie, zastąpmy litery liczbami.
Zastosujmy klasyczny alfabet składający się z 26 znaków i zacznijmy numerowanie liter od 0 (Tab. 1).
Weźmy słowo MATEMATYKA. Zaszyfrujmy je szyfrem podstawieniowym o kluczu 7. Pierwotnie mamy więc ciąg liczb 12 0 19 4 12 0 19 24 10 0. Jeżeli do każdej liczby dodamy 7, otrzymamy ciąg 19 7 26 11 19 7 26 31 17 7. Nie wszystkie z podanych liczb mają swoje odpowiedniki w literach. Ponieważ zastosowaliśmy alfabet składający się z 26 znaków, wystarczy wziąć resztę z dzielenia podanych liczb przez 26. Ostatecznie otrzymujemy więc: 19 7 0 11 19 7 0 5 17 7. Co odpowiada zaszyfrowanemu ciągowi liter THALTHAFRH.
Oczywiście, liczba 7 może zostać zastąpiona praktycznie każdą liczbą całkowitą (choć po kilku próbach łatwo zorientujemy się, że przesunięcia powtarzają się cyklicznie co 26 i tak naprawdę mamy 25 różnych przesunięć, które dadzą nam tekst inny od utajnionego). Liczba 26 jest tu również symboliczna, bo może być zastąpiona inną w zależności od wyboru alfabetu, a także uwzględnienia (bądź nie) spacji, znaków specjalnych i interpunkcyjnych. Dla odczytania informacji ważne jest to, aby osoba, do której trafia wiadomość, wiedziała, jakim alfabetem się posługujemy i jaki jest klucz.
 

Tab. 1

Odkąd zaczęto szyfrować rozkazy wojskowe, ambicją wroga było przechwycenie wiadomości i złamanie szyfru zastosowanego przez przeciwnika. Naukę, która zajmuje się przełamywaniem szyfrów bez znajomości klucza deszyfrującego, nazywamy kryptoanalizą. Pierwsze informacje o złamaniu szyfru Cezara pochodzą z IX w. od arabskiego matematyka o imieniu Al-Kindi.
Z pomocą kryptoanalizie przychodzą statystyka i rachunek prawdopodobieństwa oraz własności języka, którym posługuje się osoba pisząca wiadomość. Jeżeli przeanalizujemy słowotwórstwo danego języka, to możemy wyciągnąć wnioski co do tego, które litery alfabetu występują najczęściej. Każdy język ma swój własny, przypisany tylko jemu, rozkład częstości występowania poszczególnych liter – taki swoisty odcisk palca danego języka.
Według IPI PAN, częstość występowania liter w języku polskim jest taka, jak na rycinie 1.
Pozwala to przypuszczać, że w losowo wybranym tekście napisanym w języku polskim najczęściej występującą literą będzie a. Oczywiście, pamiętajmy, iż jest to jedynie rachunek prawdopodobieństwa, a im krótszy tekst, tym mniej dokładnie dane statystyczne mogą go dotyczyć. Niemniej jednak analiza częstości występowania liter pozwala nam na ograniczenie liczby prób deszyfrujących dany tekst.
Weźmy tekst, o którym wiemy, że został napisany w języku polskim, wraz ze znakami zapożyczonymi (V, X, Q). Mamy wówczas 35 znaków (Tab. 2).

Spróbujemy odgadnąć klucz szyfrujący do zdania JV IDSV LV LVŚĄ. Na wejściu mamy 34 możliwości. Zauważmy, że w tekście najczęściej pojawia się litera V. W języku polskim najczęstszą literą jest A. Litera A ma numer 0, a V 28. To pozwala przypuszczać, że nastąpiło przesunięcie o 28. Sprawdźmy, co otrzymamy, jeżeli cofniemy się o 28 miejsc:
12 − 28 = −16 = −1 · 35 + 19 Litera O zamiast J,
11 − 28 = −17 = −1 · 35 + 18 Litera Ń zamiast I,
5 − 28 = −23 = −1 · 35 + 12 Litera J zamiast D,
24 − 28 = −4 = −1 · 35 + 31 Litera Y zamiast S.

Mamy: OA ŃJYA, co jest pozbawione sensu w języku polskim.

Tab. 2

Kolejną najczęściej pojawiającą się literą w języku polskim jest I. Gdyby I miało być zastąpione przez V, to musielibyśmy przesunąć się o 17 miejsc. Takie podstawienie również nie da nam tekstu, który ma sens w języku polskim, co łatwo sprawdzić w sposób analogiczny do powyższego. Kolejna, co do częstości, jest litera O. Jeżeli zastosujemy klucz deszyfrujący polegający na przesunięciu się o 9 w lewo, otrzymamy tekst: CO BYŁO DO DOMU… Nasi uczniowie nie są pewni, czy odrobili pracę domową. Analizując częstość występowania liter, już za trzecim razem odgadliśmy klucz.

Łatwość złamania szyfru podstawieniowego jest jego największą wadą. Jego słabą stroną jest również fakt, że znajomość klucza szyfrującego daje gwarancję deszyfryzacji.
Dość prosty algorytm szyfrujący charakteryzuje inny szyfr, zwany RSA, od pierwszych liter nazwisk jego twórców (R. Rivesta, A. Shamira oraz L. Adlemana) – jest on o wiele trudniejszy do złamania. Został wprowadzony w drugiej połowie XX w. i przy zastosowaniu odpowiednio dużych liczb jest wykorzystywany do szyfrowania danych w systemach informatycznych. Szyfr ten oparty jest na dwóch kluczach – publicznym, wykorzystanym do szyfrowania, i prywatnym – znanym osobie, do której ma trafić wiadomość.

Pokażemy jego działanie na niewielkich liczbach:

• Bierzemy dwie liczby pierwsze p, q. 
  Niech p = 2 i q = 11. 
• Znajdujemy iloczyn tych liczb: n = 2 · 11 = 22.
• Szukamy liczby e względnie pierwszej z p − 1 = 1 i q − 1 = 10 mniejszej od n. Weźmy e = 3.

Kluczem szyfrującym podanym do wiadomości publicznej jest tu e = 3.

• Chcemy zaszyfrować literę J = 9 z alfabetu składającego się z 26 znaków.
• Liczymy Je = 93 = 729.
• Wyznaczamy resztę z dzielenia Je przez n: 729 : 22 = 33 r. 3.
• Reszta ta będzie liczbą, która znajdzie się w wiadomości. 
  A zatem litera J zostanie zaszyfrowana przez liczbę x = 3.

Jak obliczyć klucz deszyfrujący d?

• Szukamy liczby d takiej, że reszta z dzielenia iloczynu ed przez (p − 1) · (q − 1) = 10 wynosi 1 (i zawsze jest to 1 w tym algorytmie). Zauważmy, że:
  3 · 7 = 21 oraz 21 : 10 = 2 r. 1, czyli d = 7.

Zarówno d, jak i p, q powinny zostać tajne i znane jedynie osobie, do której trafia wiadomość. 
Adresat chce teraz odszyfrować wiadomość o treści: 
x = 3, którą otrzymał. Jaki jest algorytm deszyfrujący? Pamiętajmy, że osoba ta zna klucz publiczny e = 3 oraz klucze prywatne d = 7, p = 2, q = 11.

• Aby odszyfrować wiadomość, należy znaleźć resztę z dzielenia xd przez n.
• Mamy xd = 37 = 2187 oraz xd: n = 2187: 22 = 99 r. 9. 
• Reszta ta stanowi niejawną wiadomość. Tajny tekst ma więc wartość 9, co w alfabecie składającym się z 26 znaków numerowanych od 0 odpowiada literze J.

Tekst został rozszyfrowany.
Algorytm ten nie wydaje się zbyt trudny, natomiast przy zastosowaniu bardzo dużych liczb pierwszych p i q jego złamanie bez znajomości klucza prywatnego jest niemal niemożliwe.
 

Pamiętajmy, że łamanie szyfrów jest ważnym elementem historii Polski – wszyscy znamy wkład Polaków w łamanie szyfru Enigmy. Powyższe proste przykłady pokazują, że kryptografia to nic innego jak umiejętne zastosowanie własności liczb. Odpowiedni dobór liczb do zastosowanych algorytmów może skutecznie uniemożliwić przejęcie tajnych informacji przez wroga – w tym również nauczyciela czy rodzica.

Bibliografia:

1. Ufnal P., Elementy algebry i teorii liczb w szyfrowaniu, Praca licencjacka napisana w Zakładzie Algebry i Teorii Liczb Instytutu Matematyki i Fizyki Wydziału Nauk Ścisłych Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach, Siedlce 2017.