Matematyka dyskretna 2/Ćwiczenia 7: Zastosowanie teorii liczb w kryptografii

From Studia Informatyczne

Zastosowania teorii liczb w kryptografii

Ćwiczenie 1

Przechwyciłeś zakodowaną wiadomość i pragniesz poznać jej treść. Oto kod wiadomości:


24,28,17,39,14,42,24,18,10,40,38,15,10,26,27,42,40,18,10,46,17,20,
14,26,18,10,45,28,17,15,14,46,12,14,26,37,18,10,14,28,14,43,23,45,
17,36,42,31,40,6,18,15,10,26,14,12,24,28,17,14,6,10,14,46,6,10,14,
46,6,18,10,14,31,6,12,29,10,29,14,13,45,12,37,18,14,45,42,45,17,27,
45,12,28,34,38,24,28,14,29,38,40,38,20,0,39,38,4,14,46,28,18,6,37,
17,14,46,12,14,28,18,10,26,18,14,26,37,18,10,14,34,45,28,17,13,18,15,0.


Wiadomo, że użyto kryptosystemu afinicznego o następujących parametrach:

  • symbole alfabetu, tak jak i numeracja jest taka sama jak w tabeli z przykładu rozważanego podczas wykładu,
  • jednostka wiadomości składa się z jednego symbolu; zbiór jednostek wiadomości to \displaystyle \mathbb{Z}_{47}, (w porównaniu z wykładem dodana została jedna wartość - \displaystyle 46 - oznaczająca "," (przecinek) także po to aby moc zbioru jednostek wiadomości była liczbą pierwszą),
  • funkcja kodująca \displaystyle f jest postaci


\displaystyle f(P)=aP+b { mod} \displaystyle   47,


gdzie \displaystyle a,b\in\mathbb{Z}_{47} są nieznanymi Ci kluczami.

Złam te klucze i poznaj treść wiadomości!

Wskazówka

Klucze kryptosystemu afinicznego można próbować odgadywać poprzez analizę częstotliwościową. Wystarczy czasem zgadnąć znaczenie dwu symboli i rozwiązać odpowiedni układ równań z dwiema niewiadomymi \displaystyle a i \displaystyle b.

Rozwiązanie

Przeprowadź analizę częstotliwościową zakodowanej wiadomości. Spróbuj odgadnąć znaczenie dwu symboli. Podejrzewając, że \displaystyle f(x_0)=y_0 i \displaystyle f(x_1)=y_1 mamy (modulo \displaystyle 47):


\displaystyle \aligned ax_0+b&=y_0,\\ ax_1+b&=y_1. \endaligned


Rozwiązując ten układ dwu równań z dwiema niewiadomymi otrzymujemy \displaystyle a=(y_1-y_0)(x_1-x_0)^{-1} i \displaystyle b=y_0-(y_1-y_0)(x_1-x_0)^{-1}x_0. Znając hipotetyczne wartości kluczy, zdekoduj wiadomość i sprawdź czy ma sens. Jeśli nie spróbuj jeszcze raz zgadnąć znaczenie obu symboli ...

Pozostawiamy satysfakcję z odczytania tej wiadomości ...

Ćwiczenie 2

Otrzymałeś wiadomość w kryptosystemie RSA następującej postaci:


\displaystyle 1087,167,279,523.


Wiadomość jest zakodowana przy nastepujących założeniach:

  • symbole alfabetu, tak jak i numeracja jest taka sama jak w tabeli z przykładu omawianego podczas wykładu,
  • jednostka wiadomości składa się z dwu symboli, odpowiedniość między jednostkami wiadomości, a kolejnymi liczbami jest taka sama jak we wspomnianym przykładzie, zbiór jednostek wiadomości to \displaystyle \mathbb{Z}_{2279} (\displaystyle 2279 jest iloczynem dwu liczb pierwszych), przy czym wartości większe od \displaystyle 2115 nie są wykorzystywane,
  • klucz kodujący to \displaystyle (2279,1552).

Odczytaj otrzymaną wiadomość.

Wskazówka

\displaystyle 2279= 43 \cdot 53 .

Rozwiązanie

Znając rozkład liczby \displaystyle 2279 łatwo już policzyć klucz dekodujący \displaystyle d=1000.

Ćwiczenie 3

Pokaż, że dla liczby pierwszej \displaystyle p oraz \displaystyle 1<b<p^2, liczba \displaystyle p^2 jest pseudopierwsza przy podstawie \displaystyle b wtedy i tylko wtedy, gdy \displaystyle b^{p-1}\equiv_{p^2}1.

Wskazówka

Wykorzystaj Twierdzenie Eulera.

Rozwiązanie

Załóżmy najpierw, że \displaystyle p^2 jest pseudopierwsza przy podstawie \displaystyle b, czyli:

  • \displaystyle b\perp p^2,
  • \displaystyle b^{p^2-1}\equiv_{p^2}1.

Drugi punkt, wraz z informacją \displaystyle b^{p^2-p}\equiv_{p^2}1 otrzymaną z Twierdzenia Eulera daje \displaystyle b^{p-1}\equiv_{p^2}1.

Na odwrót, niech \displaystyle b^{p-1}\equiv_{p^2}1.

Ponieważ \displaystyle p-1|p^2-1, to \displaystyle b^{p^2-1}\equiv_{p^2}1. Oczywiście implikuje to też, że \displaystyle b\perp p^2.

Ćwiczenie 4

Pokaż, że dla dowolnej ustalonej liczby pierwszej \displaystyle r jest skończenie wiele liczb Carmichaela postaci \displaystyle rpq, gdzie \displaystyle p,q są liczbami pierwszymi. Przy pomocy wypracowanej metody:

  • wypisz wszystkie liczby Carmichaela postaci \displaystyle 3pq i \displaystyle 5pq,
  • udowodnij, że \displaystyle 561 jest najmniejszą liczbą Carmichaela.

Wskazówka

Wykorzystać twierdzenie charakteryzujące liczby Carmichaela.

Rozwiązanie

Rozważmy liczbę Carmichaela postaci \displaystyle rpq. Ponieważ w rozkładzie liczb Carmichaela czynniki pierwsze nie powtarzają się, bez straty ogólności możemy przyjąć, że \displaystyle p<q. Z twierdzenia charakteryzującego liczby Carmichaela mamy \displaystyle q-1|rpq-1, co wraz z \displaystyle rpq-1\equiv_{q-1}rp-1 daje \displaystyle rp-1=a(q-1) dla pewnego \displaystyle a=1,\ldots,r-1. Analogicznie dostajemy \displaystyle p-1|rq-1. W konsekwencji \displaystyle p-1|a(rq-1)=r(aq)-a=r(a+rp-1)-a\equiv_{p-1}(r-1)(a+r). Zatem przy ustalonym \displaystyle r mamy skończenie wiele możliwości wyboru \displaystyle a, tzn. \displaystyle a=1,\ldots,r-1 i potem skończenie wiele możliwości wyboru \displaystyle p tak, by \displaystyle p-1|(r-1)(a+r). Wybór \displaystyle p deteminuje \displaystyle q poprzez \displaystyle rp-1=a(q-1). Oczywiście nie wszystkie wybory \displaystyle a, bądź też później \displaystyle p, prowadzą do liczb Carmichaela, choćby dlatego, że wyliczone \displaystyle q może nie być liczbą pierwszą, bądź wartości którejś z liczb \displaystyle r,p,q się powtórzą.

Zastosujemy tę metodę do wskazania wszystkich liczb Carmichaela postaci \displaystyle 3pq (tzn. \displaystyle r=3):

  • jest tylko jedna możliwość wyboru \displaystyle a, tzn. \displaystyle a=2,
  • liczba pierwsza \displaystyle p ma być tak dobrana, by \displaystyle p-1|(r-1)(a+r)=10:
    • \displaystyle p=2, wtedy jednak \displaystyle 2q=7, czyli nie prowadzi to do liczby pierwszej (a nawet całkowitej) \displaystyle q,
    • \displaystyle p=3, ten wybór jest zabroniony, gdyż wtedy liczba \displaystyle 3pq miałaby w rozkładzie kwadrat \displaystyle p=r liczby pierwszej,
    • \displaystyle p=11, wtedy \displaystyle 3\cdot11-1=2(q-1) i \displaystyle q=17. Wszystkie warunki zostały spełnione, zatem \displaystyle 3\cdot11\cdot17=561 jest liczbą Carmichaela.

Ponieważ wszystkie możliwe wartości parametrów \displaystyle a i \displaystyle p zostały przejrzane, to \displaystyle 561=3\cdot11\cdot17 jest jedyną liczbą Carmichaela postaci \displaystyle 3pq. Stosując tę samą metodę można pokazać, że jedyne liczby Carmichaela postaci \displaystyle 5pq to:


\displaystyle 1105=5\cdot13\cdot17,\quad2465=5\cdot17\cdot29,\quad10585=5\cdot29\cdot73.


Pozostało jeszcze pokazać, że \displaystyle 561 jest najmniejszą liczbą Carmichaela. Zauważmy, że poza powyżej wypisanymi liczbami wszystkie liczby Carmichaela są iloczynem przynajmnej trzech, różnych, liczb pierwszych nie mniejszych od \displaystyle 7. Najmniejszy możliwy iloczyn (to nawet nie jest liczba Carmichaela) to \displaystyle 7\cdot11\cdot13=1001, co było do pokazania.

Ćwiczenie 5

Pokaż, że jeśli \displaystyle n jest silnie pseudopierwsza przy podstawie \displaystyle b, to jest też silnie pseudopierwsza przy podstawie \displaystyle b^k dla dowolnego \displaystyle k\in\mathbb{N}.

Wskazówka

Przedstaw \displaystyle k w postaci \displaystyle k=2^i j, gdzie \displaystyle j jest nieparzyste.

Rozwiązanie

Ponieważ \displaystyle n jest silnie pseudopierwsza przy podstawie \displaystyle b, to \displaystyle n-1=2^st dla pewnej liczby nieparzystej \displaystyle t>1 oraz zachodzi jeden z dwu warunków:

  • \displaystyle b^t\equiv_n1, wtedy oczywiście \displaystyle b^{kt}\equiv_n1,
  • \displaystyle b^{2^rt}\equiv_n -1 dla pewnego \displaystyle r\in\left\lbrace 0,\ldots,s-1 \right\rbrace,

Ustalmy \displaystyle k\in\mathbb{N} i niech \displaystyle k=2^ij, gdzie \displaystyle j jest liczbą nieparzystą. Wtedy dla \displaystyle i>r mamy


\displaystyle (b^k)^t  =(b^{2^ij})^t  =(b^{2^rt})^{2^{i-r}j} \equiv_n(-1)^{2^{i-r}j} =1,


zaś dla \displaystyle i\leqslant r mamy


\displaystyle (b^k)^{2^{r-i}t} =b^{2^i j 2^{r-i} t}  =b^{2^r j t}  \equiv_n (-1)^j  =-1.


Ćwiczenie 6

Rozłóż na czynniki pierwsze liczbę:

251959084756578934940271832400483985714292821262040320277771
378360436620207075955562640185258807844069182906412495150821
892985591491761845028084891200728449926873928072877767359714
183472702618963750149718246911650776133798590957000973304597
488084284017974291006424586918171951187461215151726546322822
168699875491824224336372590851418654620435767984233871847744
479207399342365848238242811981638150106748104516603773060562
016196762561338441436038339044149526344321901146575444541784
240209246165157233507787077498171257724679629263863563732899
121548314381678998850404453640235273819513786365643912120103
97122822120720357

Wskazówka

RSA płaci za taki rozkład 200 000 USD.
http://http://www.rsasecurity.com/rsalabs/node.asp?id=2093RSA2048
Wynajmij więc kogoś za 3/4 tej kwoty.