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

Zastosowania teorii liczb w kryptografii

Ćwiczenie ex krypto afiniczny

Przechwyciłeś zakodowaną wiadomość i pragniesz poznać jej treść. Oto kod 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$):

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $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 ex krypto rsa

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{\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 ex krypto pseudopierwszosc

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 ex krypto carmichael

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,\dots ,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,\dots ,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,2465=5\cdot 17\cdot 29,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 ex krypto silna pseudpierwszosc

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{\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 \{0,\dots ,s-1\}$,

Ustalmy $k\in \mathbb{\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⩽r$ mamy

$(b^k{)}^{2^{r-i}t}=b^{2^{i}j{2}^{r-i}t}=b^{2^{r}jt}{\equiv }_n(-1{)}^j=-1.$

Ćwiczenie ex krypto

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.