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

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 $\mathbb {Z} _{47}$, (w porównaniu z wykładem dodana została jedna wartość - $46$ - oznaczająca "," (przecinek) także po to aby moc zbioru jednostek wiadomości była liczbą pierwszą),
• funkcja kodująca $f$ jest postaci

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

gdzie $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 $a$ i $b$.

Rozwiązanie

Przeprowadź analizę częstotliwościową zakodowanej wiadomości. Spróbuj odgadnąć znaczenie dwu symboli. Podejrzewając, że $f(x_{0})=y_{0}$ i $f(x_{1})=y_{1}$ mamy (modulo $47$):

${\begin{aligned}ax_{0}+b&=y_{0},\\ax_{1}+b&=y_{1}.\end{aligned}}$

Rozwiązując ten układ dwu równań z dwiema niewiadomymi otrzymujemy $a=(y_{1}-y_{0})(x_{1}-x_{0})^{-1}$ i $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:

$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 $\mathbb {Z} _{2279}$ ($2279$ jest iloczynem dwu liczb pierwszych), przy czym wartości większe od $2115$ nie są wykorzystywane,
• klucz kodujący to $(2279,1552)$.

Odczytaj otrzymaną wiadomość.

Wskazówka

$2279=43\cdot 53$ .

Rozwiązanie

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

Ćwiczenie 3

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

Wskazówka

Wykorzystaj Twierdzenie Eulera.

Rozwiązanie

Załóżmy najpierw, że $p^{2}$ jest pseudopierwsza przy podstawie $b$, czyli:

• $b\perp p^{2}$,
• $b^{p^{2}-1}\equiv _{p^{2}}1$.

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

Na odwrót, niech $b^{p-1}\equiv _{p^{2}}1$. Ponieważ $p-1|p^{2}-1$, to $b^{p^{2}-1}\equiv _{p^{2}}1$. Oczywiście implikuje to też, że $b\perp p^{2}$.

Ćwiczenie 4

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

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

Wskazówka

Wykorzystać twierdzenie charakteryzujące liczby Carmichaela.

Rozwiązanie

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

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

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

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

$1105=5\cdot 13\cdot 17,\quad 2465=5\cdot 17\cdot 29,\quad 10585=5\cdot 29\cdot 73$

Pozostało jeszcze pokazać, że $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 $7$. Najmniejszy możliwy iloczyn (to nawet nie jest liczba Carmichaela) to $7\cdot 11\cdot 13=1001$, co było do pokazania.

Ćwiczenie 5

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

Wskazówka

Przedstaw $k$ w postaci $k=2^{i}j$, gdzie $j$ jest nieparzyste.

Rozwiązanie

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

• $b^{t}\equiv _{n}1$, wtedy oczywiście $b^{kt}\equiv _{n}1$,
• $b^{2^{r}t}\equiv _{n}-1$ dla pewnego $r\in \left\lbrace 0,\ldots ,s-1\right\rbrace$,

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

$(b^{k})^{t}=(b^{2^{i}j})^{t}=(b^{2^{r}t})^{2^{i-r}j}\equiv _{n}(-1)^{2^{i-r}j}=1$,

zaś dla $i\leqslant r$ mamy

$(b^{k})^{2^{r-i}t}=b^{2^{i}j2^{r-i}t}=b^{2^{r}jt}\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.