Informatyka MIMUW

Klucz kodowania - \( K_K \) to parametr(y) funkcji kodującej. Znając je można wysyłać zakodowane wiadomości.

Klucz dekodowania - \( K_D \) to paramert(y) funkcji dekodującej. Znając je można dekodować wiadomości.

Przez wieki uważano, że w dowolnym kryptosystemie znajomość klucza kodujacego \( K_K \) pozwala na szybkie poznanie klucza dekodującego znajomość \( K_D \), czyli że każdy kto umie kodować wiadomości może je też dekodować. Tak jest w rozważanym powyżej kryptosystemie Cezara. Jeśli Cezar używał tego samego kryptosystemu do kontaktu ze wszystkimi swoimi generałami, wtedy mogło dochodzić do sytuacji niepożądanych np. gdy generał A wysłał Cezarowi zaszyfrowaną wiadomość, generał B przechwytując kuriera po drodze mógł ją odczytać.

Kryptosystem z kluczem publicznym to system \( (\mathcal{J},f,K_K, K_D) \), gdzie \( K_K \) i \( K_D \) są odpowiednio kluczem kodującym i dekodującym, w którym

• \( K_K \) jest powszechnie dostępny; \( K_D \) jest zachowywany w tajemnicy,

• znajomość \( K_K \) pozwala na szybkie kodowanie jednostki tekstu, czyli obliczanie \( f(P) \) dla \( P\in\mathcal{J} \),

• znajomość \( K_K \) nie pozwala (bez znajomości \( K_D \)) na szybkie dekodowanie jednostki szyfrogramu, czyli obliczanie \( f^{-1}(C) \) dla \( C\in\mathcal{J} \),

• znajomość \( K_D \) daje możliwość szybkiego zdekodowania jednostki szyfrogramu.

Szukamy więc funkcji \( f \) którą w jedną stronę liczy się relatywnie szybko na podstawie znajomości \( K_K \). Natomiast jej odwrotna \( f^{-1} \) jest bardzo trudna do policzenia bez dodatkowej informacji \( K_D \). W sposób naturalny przychodzi tu na myśl problem znajdowania rozkładu na czynniki pierwsze liczb naturalnych. W szczególności: wymnożenie dwu dużych liczb pierwszych jest łatwe (można to zrobić w czasie wielomianowym od długości ich zapisu), natomiast szybkie znalezienie rozkładu na czynniki pierwsze ich iloczynu (bez znajomości wyjściowych liczb lub innych dodatkowych informacji) wydaje się być problemem ekstremalnie trudnym. Właśnie na tym spostrzeżeniu oparta jest idea kryptosystemu RSA.

Kryptosystem RSA.

Nazwa kryptosystemu pochodzi od pierwszych liter nazwisk jego trzech pomysłodawców: Rivest, Shamir i Adelman. Choć jest to jeden z najstarszych kryptosystemów z kluczem publicznym (wynaleziony w 1977 roku) wciąż jest szeroko stosowany w komercyjnych protokołach. Jedynie długości kluczy rosną wraz ze wzrostem mocy obliczeniowej komputerów.

Opis działania RSA:

• Wybierz losowo dwie bardzo duże różne liczby pierwsze \( p \) i \( q \).
  • To jak duże mają być to liczby zależy właśnie od mocy obliczeniowej komputerów. Oczywiście, im większe liczby tym trudniej złamać kod (obliczyć \( K_D \)) ale jednocześnie, im większe liczby, tym dłużej trwa proces kodowania i dekodowania wiadomości.
  • To, że liczba ma być wybrana losowo oznacza, że jest uzyskana z pomocą generatora liczb pseudo-losowych. Ale co to oznacza wybrać (pseudo)losowo liczbę pierwszą?
    • Wylosuj odpowiednio dużą liczbę \( m \). Jeśli jest ona parzysta to podstaw \( m:=m+1 \).
    • Zaaplikuj testy pierwszości (szczegółowo omówimy je w kolejnej części wykładu) do \( m \). Jeśli okaże się złożona podstaw \( m:=m+2 \) i tak aż do znalezienia liczby pierwszej. Z Twierdzenia o Liczbach Pierwszych wiemy, że częstotliwość występowania liczb pierwszych w pobliżu liczby \( m \) wynosi \( \frac{1}{\ln{m}} \), a więc możemy oczekiwać że po \( O(\lg{m}) \) próbach test pierwszości zwróci wynik pozytywny.
  • Wkrótce przedstawimy test pierwszości działający w czasie \( O(\lg^{3}m) \). A więc oczekiwany czas "wylosowania" liczby pierwszej w pobliżu \( m \) wynosi \( O(\lg^4{m}) \).

Uwaga: jest to oczekiwany czas działania, a nie maksymalny (pesymistyczny).

• Niech \( n=p\cdot q \). Wtedy \( \varphi(n)=\varphi(p)\cdot\varphi(q)=(p-1)\cdot(q-1) \). Wybierz losowo \( e\in{\{ {1,2,3,\ldots,\varphi(n)-1} \} } \) względnie pierwsze z \( \varphi(n) \). Niech \( d\in{\{ {1,\ldots,\varphi(n)-1} \} } \) takie, że \( e\cdot d\ \equiv_{\varphi(n)}1 \).
  • Podobnie jak wcześniej szukaliśmy losowo liczb pierwszych teraz możemy szukać liczby \( e \). Zamiast aplikować test pierwszości sprawdzamy algorytmem Euklidesa względną pierwszość z \( \varphi(n) \) (\( O(\lg^3{\varphi(n)}) \)). Kiedy uda nam sie trafić (statycznie po \( O(\log{\varphi(n)}) \) krokach) rozszerzony algorytm Euklidesa wyznaczy nam \( d \), w czasie \( O(\log^3{\varphi(n)}) \).
  • oczekiwany czas działania tego kroku to \( O(\log^4{n}) \).

• Opublikuj klucz publiczny: \( K_K=(n,e) \) i zachowaj do własnego użytku klucz dekodujący \( K_D=(n,d) \).
• Zdefiniuj:
  • zbiór jednostek wiadomości jako \( \mathbb{Z}_n={\{ {0,1,\ldots,n-1} \} } \),
  • funkcję kodującą: \( f(P)=P^e {\sf mod} n ,\qquad \) dla \( P \in \mathbb{Z}_n \).
  • funkcję dekodującą:\( f^{-1}(C)=C^d {\sf mod} n ,\qquad \) dla \( C \in \mathbb{Z}_n \).

Poprawność tego kryptosystemu, czyli że \( f^{-1}(f(P))=P \), dla dowolnego \( P\in\mathbb{Z}_n \) wynika bezpośrednio z następującej obserwacji:

Obserwacja 7.1 [Poprawność RSA]

\( P^{ed}\ \equiv_{n}1 ,\qquad \) dla dowolnego \( P \in \mathbb{Z}_n \).

Dowód

Ponieważ \( ed\ \equiv_{\varphi(n)}1 \) mamy \( ed=a\varphi(n)+1 \) dla pewnego \( a \).

Załóżmy najpierw, ze \( p\perp n \). Wtedy z Twierdzenia Eulera dostajemy \( P^{\varphi(n)}\ \equiv_{n}1 \), a zatem \( P^{ed}=P^{a\varphi(n)+1}\equiv_n P \).

Jeśli zaś \( p\not\perp n \), to \( p|P \) lub \( q|P \). Załóżmy, bez straty ogólności, że \( q|P \), czyli \( P=bq \) dla pewnego \( 0 < b < p \), bo \( bq=P < n=pq \). Na mocy Małego Twierdzenia Fermata mamy:

\( \begin{align*} b^{p-1} & \equiv_p & 1, \\ q^{p-1} & \equiv_p & 1, \end{align*} \)

skąd:

\( \begin{align*} b^{a(p-1)(q-1)} & \equiv_p & 1, \\ q^{a(p-1)(q-1)} & \equiv_p & 1, \end{align*} \)

i dalej

\( \begin{align*} b\cdot(bq)^{a(p-1)(q-1)} & \equiv_p & b \cdot 1 = b. \end{align*} \)

Mnożąc obie strony ostatniej kongruencji przez \( q \) dostajemy

\( \begin{align*} bq\cdot(bq)^{a(p-1)(q-1)} & \equiv_{pq} & bq \end{align*} \)

czyli

\( P^{ed} = (bq)^{a(p-1)(q-1)+1}= (bq)\cdot (bq)^{a(p-1)(q-1)} \equiv_n bq = P, \)

co było do udowodnienia.

Bezpieczeństwo RSA.

Bezpieczeństwo kryptosystemu RSA opiera się na domniemaniu trudności następującego problemu:

• Problem RSA: znajdź \( e \)-ty pierwiastek liczby \( C\in\mathbb{Z}_n \) modulo \( n \), a więc posiadając \( e \),\( n \) oraz \( C \) znajdź takie \( P \), że \( P^e\ \equiv_{n}C \). Oczywiście, rozwiązanie tego problemu jest równoważne złamaniu RSA. Jednak wydaje się, że jest to równie trudny problem jak problem faktoryzacji (choć nie zostało to udowodnione).

Szybkie rozwiązanie problemu faktoryzacji rozwiązałoby problem RSA. Gdyby ktoś znał rozkład \( n \), to znaczy liczby \( p \) i \( q \), miałby także \( \varphi(n)=(p-1)(q-1) \). Wtedy, korzystając z publicznie dostępnego \( e \), obliczyłby rozszerzonym algorytmem Euklidesa \( d \). Dopóki nie jest znany efektywny algorytm rozwiązujący jeden z tych problemów (problem RSA, problem faktoryzacji) kryptosystem RSA pozostaje bezpieczny. Wzrastająca szybkość komputerów zmusza użytkowników RSA do zwiększania długości kluczy. Obecnie stosowane klucze mają najczęściej \( 1024 \) lub \( 2048 \) bitów. Największy złamany klucz (klucz dla którego znaleziono rozkład) ma długość \( 663 \) bity (stan z roku 2005).

W praktyce wiadomość przed zakodowaniem podlega wstępnej obróbce (padding). Zauważmy, że wartości \( 0 \) i \( 1 \) nie podlegają zmianie przy kodowaniu (z własności potęgowania), przez co stanowią one część informacji czytelnej dla wszystkich nawet w szyfrogramie. W praktyce różnymi metodami unika się takich wartości. Rozważania te już jednak wykraczają poza tematykę tego wykładu.

Przykład

Widzieliśmy, że znając rozkład \( n= pq \) można łatwo obliczyć \( \varphi(n) \), a tym samym klucz \( d \) odpowiadający publicznemu kluczowi \( e \). Na odwrót, znając \( n \) oraz \( \varphi(n) \) można szybko rozłozyć liczbę \( n \) na czynniki pierwsze:

• znamy bowiem iloczyn szukanych czynników \( p \cdot q = n \)

• oraz sumę tych czynników \( p+q = n+1 -\varphi(n) \)

a zatem mamy rozwiązać układ równań postaci:

\( \begin{align*} x \cdot y & = a \\ x + y & = 2b \end{align*} \)

skąd \( x,y \) wynoszą \( b \pm \sqrt{b^2-a} \).
Pokazuje to, że wartości funkcji Eulera sa równie trudne do policzenia, jak faktoryzacja liczb.

Uwaga

Kryptosystem RSA wykorzystywany jest poza szyfrowaniem również w wielu innych protokołach kryptograficznych. Na bazie tego systemu można na przykład zbudować podpis elektroniczny. Mimo, że zagadnienia te wykraczają już znacznie poza treść tego wykładu, pokazują one jak wielką rolę odgrywa obecnie teoria liczb w informatyce.