RSA szyfrowanie asymetryczne¶
O scenariuszu¶
Scenariusz ten jest materiałem do przeprowadzenie 3h zajęć lekcyjnych.
Został on opracowany w ramach projektu iCSE4school na podstawie lekcji prowadzonych w latach 2015-2017 w III Liceum Ogólnokształcącym im. Stefana Batorego w Chorzowie przez Krzysztofa Jarczewskiego.
Uwaga!
W każdym z okien programu można zmieniać liczby, tekst, zmienne lub cały kod. Nie trzeba się martwić, jeśli program przestanie działać, bo po odświeżeniu strony powróci do ustawień początkowych. Często następny kod wynika z poprzedniego, więc należy ćwiczenia (algorytmy) wykonywać według kolejności.
Wstęp¶
Uczniowie powinni znać i rozumieć:
działania na potęgach, NWD, dzielenie z resztą. (1.1, 1.4, 1.5 mat_p),
podstawowy algorytm Euklidesa a najlepiej rozszerzoną jego wersję, (1.0-II-5.11.a inf_r),
podstawowe komendy programistyczne w SageMath: działania, funkcję warunkową, pętle (1.0-II-5.22-23 inf_r),
potrzebę szyfrowania wiadomości (1.0-II-2.5, 1.0-II-5.11.e inf_r),
kodowanie znaków ASCI (1.0-II-5.11.d inf_r).
Uczniowie na poniższych zajęciach poznają:
własności działania modulo (kongruencję), chińskie twierdzenie o resztach,
małe twierdzenie Fermata, proste szyfrowanie asymetryczne,
szyfrowanie asymetryczne RSA – oparte na liczbach pierwszych (1.0-II-5.11.e inf_r).
Powyżej w nawiasach jest wpisany szczegółowy zakres nauczanych treści.
mat_p – matematyka poziom podstawowy, inf_r – informatyka poziom rozszerzony.
Część teoretyczna¶
Definicja kongruencji.
Dwie liczby całkowite : \(a, b\) przystają do siebie modulo n, jeśli: \((a-b) \cdot k=n,\hspace{2mm} k \in Z.\)
Kongruencję zapisujemy symbolicznie: \(a = b (mod \hspace{2mm} n)\).
Przykłady:¶
2 = 2 (mod 8), ponieważ 2 - 2 = 0, 0 jest podzielne przez 8,
3 = 18 (mod 5), ponieważ 3 - 18 = -15, -15 jest podzielne przez 5,
100 = 1 (mod 9), ponieważ 100 - 1 = 99, 99 jest podzielne przez 9,
250 = 206 (mod 22), ponieważ 250 - 206 = 44, 44 jest podzielne przez 22.
Ćwiczenie 1.¶
Znajdź x takie, że: \(3x = 1 (mod \hspace{2mm} 4), \hspace{2mm} 5<x<10\).
Ćwiczenie 2.¶
Znajdź x takie, że: \(3x+2 = 1 (mod \hspace{2mm} 5)\).
Oczywiście istnieje nieskończenie takich rozwiązań. Dodatkowo te rozwiązania wyznaczają ciąg arytmetyczny.
Ćwiczenie 3.¶
Znajdź x takie, że: 3x = 1 (mod 6).
W powyższym ćwiczeniu nie istnieje żadna liczba, która spełnia powyższą kongruencję.
Informacja
Chińskie twierdzenie o resztach.
Poniższe ćwiczenie można rozwiązać przy użyciu chińskiego twierdzenia o resztach. Jedno z najważniejszych twierdzeń z teorii liczb i kryptografii. Twierdzenie to pozwala dzielić sekret wśród kilku osób (ważne hasło liczbowe).
Ćwiczenie 4.¶
Tabliczka czekolady składa się z mniej niż 100 kawałków. Przy podziale na trzy równe części, pozostaje 1 kawałek czekolady. Dzieląc na 5 równych części, zostają 3 kawałki czekolady, a przy podziale na 7 równych części, pozostają 2 kawałki.
Wiemy, że liczba kawałków czekolady musi spełniać poniższe kongruencje:
x = 1 mod 3,
x = 3 mod 5,
x = 2 mod 7.
Małe twierdzenie Fermata.
Jeśli p jest liczbą pierwszą oraz a, p są względnie pierwsze, wtedy \(a^{p-1} - 1\) jest wielokrotnością liczby p. Zapisujemy to symbolicznie: \(a^{p-1}=1 (mod \hspace{2mm} p)\).
Sprawdźmy poprawność powyższego twierdzenia, dla kolejnych liczb pierwszych, numerycznie z wykorzystaniem języka Python.
Dla a = 35 i p = 5 lub p = 7 liczby nie spełniają założeń twierdzenia. Możemy dodatkowo stwierdzić, że liczba \(a^{p-1} - 1\) jest podzielna przez p.
Część informatyczna¶
Informacja
Szyfrowanie wiadomości.
Pierwsze wzmianki o kryptografii pochodzą już ze starożytności. Można stwierdzić, że szyfrowanie powstało równocześnie z wynalezieniem pisma. Szyfrowanie było stosowne przy przekazywaniu wiadomości wojskowych lub politycznych. Na lekcjach informatyki poznaliśmy (lub poznamy) szyfr Cezara. Jest to prosty szyfr, w którym zamieniamy litery. Co prawda zaszyfrowana wiadomość jest niezrozumiała, ale także prosta do odszyfrowania. Inne metody starożytnych były bardziej wyrafinowane i trudniejsze do odszyfrowania. Do lat sześćdziesiatych dwudziestego wieku znane były tylko szyfry symetryczne, to znaczy takie, które mają jeden klucz (jedną metodę) dzięki, któremu szyfrujemy i deszyfrujemy wiadomości.
W latach siedemdziesiątych dwudziestego wieku kryptografowie dzięki informatyzacji, zwiększeniu mocy obliczeniowej komputerów oraz potrzebie zabezpieczenia danych wymyślili szyfr asymetryczny, czyli taki, w którym używamy dwóch różnych kluczy – jeden do zaszyfrowania, a drugi do odszyfrowania (kolejność kluczy jest nieważna). Jeden z kluczy udostępniamy osobie, która ma przesłać nam tajną wiadomość. Możemy nawet udostępnić klucz na naszej stronie internetowej (dostępny dla wszystkich - klucz publiczny). Drugi klucz jest tajny (klucz prywatny) znamy go tylko my i nie możemy go nikomu udostępnić. Tylko i wyłącznie dzięki kluczowi prywatnemu możemy odszyfrować wiadomość.
Poniżej opiszemy prosty szyfr asymetryczny, który można złamać (czyli znając liczby d, n można szybko znaleść liczbę e). Będzie to Wasze zadanie dodatkowe.
Jak matematycznie stworzyć szyfr asymetryczny?
Do stworzenia prostego szyfru asymetrycznego będą nam potrzebne różne liczby naturalne: \(a, b, a1, b1\).
Czym większe liczby tym szyfr jest bezpieczniejszy - trudniejszy do odszyfrowania bez znajomości odpowiedniego klucza.
Dla naszego przykładu wystarczą liczby dwu, trzy cyfrowe.
Obliczamy: \(M=a \cdot b-1\), wtedy: \(e=a1 \cdot M+a, \hspace{3mm} d=b1\cdot M+b, \hspace{3mm} n=(e \cdot d-1)/M\)
Otrzymujemy parę kluczy, klucz publiczny: \((d, n)\) i klucz prywatny: \((e, n)\).
Poniżej przykład generowania kluczy oraz zaszyfrowania liczby.
Co zrobić gdy liczba jest więsza od n?
Obliczamy resztę z dzielenia przez n (otrzymujemy „porcję” do zaszyfrowania).
Szyfrujemy otrzymaną „porcję”.
Do szyfru dodajemy zaszyfrowaną „porcję” w kolejnej potędze liczby n.
Dzielimy liczbę przez n.
Jeśli otrzymana liczba jest większa od 0, to powtarzamy kroki 1-4
W podobny sposób deszyfrujemy wiadomość:
Pomoc:
number → szyfr |
szyfr → deszyfr |
d→e |
Spróbuj poniżej odszyfrować liczbę:
Zazwyczaj chcemy zaszyfrować tekst, a nie liczbę, czyli musimy zamienić litery (znaki) na liczbę. Do tego posłużymy się kodem ASCII.
Każdej literze, znakowi przyporządkowana jest liczba z przedziału od 1 do 128.
Poniżej algorytm szyfrowania wiadomości tekstowej (ten kod został napisany i wprowadzony przez uczniów na zajęciach).
Pełny algorytm szyfrujący¶
Po złożeniu powyższych programów otrzymujemy pełny algorytm szyfrowania i deszyfrowania wiadomości tekstowych.
Pełny algorytm deszyfrujący¶
Szyfrowanie asymetryczne RSA¶
RSA jeden z pierwszych i najpopularniejszy asymetryczny algorytm kryptograficzny z kluczem publicznym, zaprojektowany w 1977 przez Rona Rivesta, Adi Szamira oraz Leonarda Adlemana (jego nazwa pochodzi od pierwszych liter nazwisk jego twórców).
Bezpieczeństwo szyfru RSA opiera się na rozkładzie dużych (ponad dwustucyfrowych) liczb złożonych na liczby pierwsze (trudność faktoryzacji).
Poniżej przykład¶
Wybieramy liczby pierwsze 20-34 cyfrowe.
Mnożymy je i wyznaczamy podział otrzymanej liczby złożonej na czynniki pierwsze (to trwa bardzo długo).
Zobacz jeszcze przewidywania dla dłuższych liczb.
Generowanie szyfru RSA¶
Wybieramy dwie duże liczby pierwsze: \(p, q\) (w praktyce wykorzystuje się liczby ponad stocyfrowe, ale dla naszych porzeb wystarczą liczby trzycyfrowe).
Obliczamy: \(n=p \cdot q, \hspace{2mm} f=(p-1)(q-1)\).
Wybieramy dowolną nieparzystą liczbę e, taką że:\(1 < e < f\) and \(gcd(d,\hspace{2mm} f) = 1\).
Wyznaczamy liczbę \(d\) as: \(de=1 \hspace{1mm} (mod \hspace{1mm} f)\).
Klucz publiczny to para liczb: \((d, n)\).
Klucz prywatny to para liczb: \((e, n)\).
Ostatecznie należy wyznaczyć liczbę \(e\) taką, że: \((d \cdot e) \hspace{1mm} mod f=1\).
Możemy użyć rozszerzonego algorytmu Euklidesa do wyznaczenia liczby e. Moi uczniowie zmieniając istniejący program w Internecie napisali poniższy program, ale nie zawsze generuje on prawidłową liczbę. Spróbuj poprawić ten kod!
Pełny algorytm szyfrowania RSA¶
Wystarczy skopiować algorytm szyfrowania z punktu 2 i zamienić: pomoc*d na pomoc^d.
Pełen algorym deszyfrujący RSA¶
Wystarczy skopiować algorytm deszyfrowania z punktu 2 i zamienić: pomoc*d na pomoc^d.
Wnioski¶
Uczniowie naszej szkoły przed projektem iCSE mogli usłyszeć wykład o metodach szyfrowania. Wykazali oni duże zainteresowanie tą sprawą. Dlatego zdecydowałem się zorganizować lekcje z asymetrycznego szyfrowania przy użyciu języka programowania Python. Język SageMath umożliwia pracę na dużych liczbach przekraczających zakres zmiennych typu float, double, a jednocześnie szybkość obliczeniowa jest naprawdę imponująca. W ten sposób uczniowie mieli możliwość praktycznego sposobu szyfrowania i deszyfrowania wiadomości przy użyciu publicznych i prywatnych kluczy. Zajęcia odbywały się na dodatkowych godzinach w ramach iCSE for school w III Liceum Ogólnokształcącym im. Stefana Batorego w Chorzowie. Celem zajęć było rozszerzenie nauczania matematyki i informatyki w drugiej klasie liceum. Powyższy temat nadaje się również jako praca projektowa, która łączy wiedzę matematyczno-informatyczną. Jak wiadomo powyższe elementy są istotne w dziedzinie kryptografii, która łączy teorię liczb z praktyką programistyczną. Nie przekracza to zakresu materiału przewidzianego na rozszerzeniu z informatyki liceum lub technikum. Dlatego też postanowiłem przeprowadzić lekcje dotyczące asymetrycznego szyfrowania wiadomości RSA.
Materiał dla uczniów jest podzielony na trzy rozdziały (trzy godziny dydaktyczne). Pierwszy z nich wprowadza pojęcia kongruencji oraz istotne matematyczne twierdzenia, które są wykorzystywane w kryptografii. Co prawda dowody i szczegóły zagadnień są pominięte, ale zainteresowani uczniowie bez problemu znajdą te informacje w internecie. Drugi rozdział to szczegółowe wprowadzenie szyfrowania asymetrycznego stosowanego na początku lat 70 poprzedniego stulecia (obecnie stosowanego już tylko w celach dydaktycznych). Trzeci rozdział to już pełne szyfrowanie RSA. W każdej części są wyszczególnione ćwiczenia i zadania dla uczniów.
Zadaniem uczniów było uzyskanie matematycznej znajomości kongruencji, małego twierdzenia Fermata i algorytmu euklidesowego. Te kwestie zostały zaprezentowane na początku, a uczniowie rozwiązywali swoje zadania podczas warsztatów. Każdy uczeń wygenerował własną parę kluczy, szyfrował i deszyfrował własne wiadomości. Pomimo wiedzy teoretycznej uczniów, było dość zaskakujące dla nich, że nie można odszyfrować wiadomości z tym samym kluczem i że klucze można zamienić. Oznacza to, że prywatny klucz może stać się publicznym i odwrotnie. Największą niespodzianką dla uczniów była symulacja złamania hasła RSA - dla liczby dwustucyfrowej szacowany podział na czynniki pierwsze dla szybkiego komputera zająłby to ponad 3000 lat.
