39418 Str063 (2)

122    4. Kłucie puhlkunc

„jemy to postępowanie dopóty, dopóki nic będziemy mogli zastąpić danej kongnicncji prze/ kongruencję z wykładnikiem dwa razy mniejszym. Mamy wtedy dwie możliwości:

(i)    Liczba m/2 dzieli się przez jedną z liczb p — 1, g — 1 (np. dzieli się przez p - I), ale nic dzieli się przez obie. Wtedy liczba a^ml2 zawsze przystaje do 1 modulo p, ale dokładnie w 50% przypadków przystaje do -1, a nie do 1, modulo q.

(ii)    Liczba m/2 nic dzieli się przez żadną z liczb p — 1 i q — 1. Wtedy liczba a^ml2 przystaje do 1 modulo p i modulo q (a więc i modulo n) w dokładnie 25% przypadków, przystaje do — 1 modulo p i modulo q również w 25% przypadków oraz przystaje do 1 względem jednego modułu i do -1 względem drugiego modułu w pozostałych 50% przypadków.

Testując zatem losowo wybrane liczby o, z dużym prawdopodobieństwem znajdziemy wkrótce liczbę a, dla której liczba a^m/2 — 1 dzieli się przez jedną z tych liczb pierwszych (np. przez p) i nie dzieli się przez drugą. (Każda losowo wybrana liczba a ma tę własność z prawdopodobieństwem 50%). Z chwilą gdy znajdziemy taką liczbę o, natychmiast rozłożymy liczbę n na czynniki, gdyż NWD(n, cT¹² — 1) = p.

Powyższa procedura jest przykładem algorytmu probabilistycznego. W następnym rozdziale poznamy inne algorytmy probabilistyczne.

3. W jaki sposób przesyłamy swój podpis za pomocą szyfru RSA? Gdy w poprzednim podrozdziale omawialiśmy zagadnienie potwierdzania tożsamości, zakładaliśmy dla uproszczenia, że ^ = W przypadku szyfru RSA mamy do czynienia z trochę bardziej skomplikowaną sytuacją. Oto jeden ze sposobów uniknięcia problemu różnych liczb n_A i różnych rozmiarów bloków liter (liczba k liter w jednostce tekstu jawnego jest mniejsza od liczby / liter w jednostce tekstu zaszyfrowanego). Przypuśćmy, że tak jak w ostatnim podrozdziale, Alicja wysyła Bolkowi swój podpis (czyli pewien tekst jawny P). Zna ona klucz szyfrujący Bolka K_{E B} = (n_B, e_B) i swój klucz rozszyfrowujący K_{d a} = {n_A, d_A). Wysyła wtedy f_Bf~_A^l(P), jeśli n_A < n_B, lub //^ł/_B(P), jeśli n_A > n_B. Zatem w pierwszym przypadku oblicza resztę z dzielenia P^ć* przez n_A\ następnie, biorąc pod uwagę to, że wynik jest mniejszy od n_B> oblicza (P*^A mod n_Ay’ mod n_B i wysyła jako jednostkę tekstu zaszyfrowanego. Natomiast gdy n_A> n_B, najpierw oblicza P^a* mod n_B, a potem podnosi wynik do potęgi d_A modulo n_A. Oczywiście Bolek może sprawdzić autentyczność podpisu w pierwszym przypadku, najpierw podnosząc go do potęgi d_B modulo n_B, a potem do potęgi e_A modulo n_A\ w drugim przypadku wykonuje te operacje w odwrotnej kolejności.

Ćwiczenia

1. Załóżmy, że używamy następującego 40-literowego alfabetu do zapisywania tekstów jawnych i zaszyfrowanych: A-Z z odpowiednikami liczbowy-

mi 0*25, odstęp = 26,. ~ 27,7 -- 28, 8 * 29, cyfry 0*9 z odpowiednikami 10-39. Przypuśćmy, że jednostkami tekstu jawnego są digramy, a jednostkami tekstu zaszyfrowanego są trigramy (tzn. k = 2, / — 3, 40² <n_A<40³ dla wszystkichn_A).

(a)    Wyślij wiadomość „SEND 87500” do użytkownika, którego kluczem szyfrującym jest (n_A, e_A) = (2047,179).

(b)    Złam szyfr, rozkładając n_A na czynniki i znajdując klucz rozszyfrowu-

jący K. d_A).

(c)    Wyjaśnij, dlaczego nawet bez rozkładania n_A na czynniki, kryptoiog mógłby szybko znaleźć klucz rozszyfrowujący. Innymi słowy, dlaczego (niezależnie od małego rozmiaru) wybór liczby 2047 jest szczególnie zły jako liczby n_A?

2.    Spróbuj złamać szyfr, którego kluczem szyfrującym jest (n# ej = = (536813567, 3602561). Wykorzystaj komputer do rozłożenia liczby n_A na czynniki pierwsze za pomocą najgłupszego możliwego algorytmu, tzn. dzieląc przez wszystkie liczby nieparzyste 3, 5, 7,.... Jeśli nie masz komputera, spróbuj odgadnąć czynniki pierwsze liczby n_A, próbując różnych specjalnych liczb pierwszych. Po rozłożeniu n_A na czynniki znajdź klucz rozszyfrowujący. Potem rozszyfruj wiadomość BNBPPKZAVQZLBJ przy założeniu, że tekst jawny składa się z bloków sześdoliterowych zapisanych za pomocą zwyczajnego 26-literowego alfabetu (przekształconych na liczby zawarte między 0 i 26⁶ - 1 w zwykły sposób), a tekst zaszyfrowany składa się z bloków siedmioliterowych zapisanych w tym samym alfabecie.

To ćwiczenie powinno pokazać, że nawet 29-bitowa liczba n_A jest o wiele za mała.

3.    Przypuśćmy, że zarówno teksty otwarte, jak i kryptogramy składają się z trigramów, ale teksty otwarte są zapisane za pomocą alfabetu 27-litero-wego (składającego się z liter A-Z i odstępu = 26), podczas gdy kryptogramy są zapisane za pomocą alfabetu 28-literowego, otrzymanego przez dodanie symbolu „/” (z odpowiednikiem liczbowym 27) do alfabetu 27-literowego. Wymagamy, by każdy użytkownik A wybrał liczbę n_A zawartą między 27³ = 19683 i 28³ = 21952 tak, by trigram tekstu otwartego w 27-literowym alfabecie odpowiadał reszcie P modulo n_A i wtedy liczba C = P°^A mod n_A odpowiadała trigramowi kryptogramu zapisanemu w 28--literowym alfabecie.

(a)    Odczytaj wiadomość „YSNAUOZHXXH ” (jeden odstęp na końcu), jeśli kluczem rozszyfrowującym jest K_D = (n, d) = (21583, 20787).

(b)    Znajdź (i) e = d~^l mod <p(ń) i (ii) rozkład liczby n na czynniki, jeśli wiesz, że w punkcie (a) <p(n) = 21280.

4.    Wykaż, że 35-bitowa liczba naturalna 23360947609 jest wyjątkowo złym kandydatem na n — pq, gdyż jej dzielniki pierwsze są zbyt bliskie siebie; pokaż mianowicie, żc liczba n może być łatwo rozłożona na czynniki pierwsze „metodą Fermata”. Zauważ, że jeśli n-pq (i np. p > q)_t to