62726 Str062 (2)

120    4. Klucze publiczne

Przekształceniem rozszyfrowującym jest funkcja zc zbioru Z/n_A7j w siebie, dana wzorem/ ^l(C) • (niod n_A). Nietrudno zauważyć, że te dwa przekształcenia są do siebie odwrotne, zc względu na nasz wybór d_A. Mianowicie, wykonanie najpierw/ a potem / “ \ lub najpierw/"^l, a potem /, oznacza podniesienie liczby do potęgi o wykładniku d_Ae_A. Ale ponieważ wykładnik d_Ae_A daje resztę 1 przy dzieleniu przez <p(n ₄), ta potęga jest równa potędze o wykładniku 1 (por. wniosek do twierdzenia 1.3.5, w przypadku gdy liczba P nic ma wspólnych dzielników z n<; por. ćwiczenie 6 poniżej, jeśli NWD(P, n_A) > 1).

Na podstawie opisu w ostatnim akapicie mogłoby się wydawać, że mamy tu do czynienia zc zbiorami P i # jednostek tekstu jawnego i zaszyfrowanego różnych dla różnych użytkowników. W praktyce chcielibyśmy wybrać 9 i takie same dla całego systemu. Załóżmy na przykład, że używamy ^-literowego alfabetu. Wtedy niech k < l będą liczbami naturalnymi dobranymi tak, by przykładowo liczby N^k i N^l miały po około 200 cyfr dziesiętnych. Jako jednostki tekstu jawnego weźmiemy bloki po k liter, które będziemy traktować jako liczby fc-cyfrowe w systemie pozycyjnym o podstawie N, tzn. przypiszemy im odpowiedniki liczbowe o wartościach między 0 i N^k. Podobnie, jednostkami tekstu zaszyfrowanego będą bloki /-literowe naszego AMiterowego alfabetu. Wtedy każdy użytkownik musi wybrać swoje liczby pierwsze p_A i q_A tak, by liczba n_A = p_Aq_A spełniała nierówności N^k < n_A < N^l. Każda jednostka tekstu jawnego, tzn. liczba mniejsza niż N^k, będzie wtedy odpowiadała pewnemu elementowi Z)n_AZ (dla liczby n_A dowolnego użytkownika); ponieważ n_A <N*_t wartość f(P)eZjn_AZ może być zapisana jednoznacznie w postaci /-literowego bloku. (Nie wszystkie bloki /-literowe powstaną w ten sposób - tylko te, które odpowiadają liczbom mniejszym od liczby n_A określonego użytkownika.)

Przykład 1. Dla wygody czytelnika nie mającego pod ręką komputera (lub nie mającego odpowiedniego oprogramowania wysokiej precyzji) zrezygnujemy z realizmu i wybierzemy większość naszych przykładów tak, by operowały względnie małymi liczbami. Przyjmijmy, że N — 26, k — 3, / = 4. Zatem jednostki tekstu jawnego są trigramami, a jednostki tekstu zaszyfrowanego są blokami czteroliterowymi zwykłego alfabetu 26-literowego. Aby przesłać wiadomość „YES” do użytkownika A, mającego klucz szyfrujący (n_A, e_A) = = (46927, 39423), najpierw znajdujemy odpowiednik liczbowy trigramu „YES”, mianowicie: 24 • 26² + 4 • 26 + 18 = 16346, a następnie obliczamy 16346³⁹⁴²³ mod 46927, otrzymując w wyniku 21166 = 1 • 26³ 4* 5 • 26² +

+ 8 • 26 + 2 = „BFIC”. Adresat A zna klucz rozszyfrowujący (n_At d_A) = = (46927, 26767), a więc oblicza 21166²⁶⁷⁶⁷ mod 46927 = 16346 = „YES”. W jaki sposób użytkownik A wygenerował swoje klucze? Najpierw pomnożył przez siebie liczby pierwsze p_A = 281 i q_A ~ 167 i otrzymał n_A; potem wybrał losowo liczbę e_A (jednak tak, by NWD(e_A, 280) = NWD(e_A) 166) = 1). Następnie znalazł d_A = e_A^l mod 280 • 166. Liczby p_A, q_A i d_A zachował w tajemnicy.

Jak bardzo czasochłonne są obliczenia w przykładzie i? Najwięcej czasu pochłonie podnoszenie do potęgi modulo n, np. I6346³*⁴*³ mod 46927. Ale to można zrobić za pomocą algorytmu iterowanego podnoszenia do kwadratu (por. podrozdział 1.3), wykonując 0(k³) operacji na bitach, gdzie & jest liczbą cyfr naszych liczb. W rzeczywistości, jeśli mamy do czynienia z bardzo dużymi liczbami, to najwięcej czasu zajmie każdemu użytkownikowi znalezienie dwóch bardzo dużych liczb pierwszych p_A i q_A. Aby możliwie szybko znaleźć odpowiednie duże liczby pierwsze, musimy użyć efektywnych testów pierwszości. Takie testy będą opisane w następnym rozdziale.

Uwagi:

1.    Przy wyborze liczb pierwszych p i q użytkownik A musi zadbać o spełnienie pewnych warunków. Najważniejszymi warunkami są: obie liczby nie mogą być zbyt bliskie siebie (np. jedna powinna mieć o kilka cyfr dziesiętnych więcej niż druga); liczby p — 1 i q — 1 powinny mieć dość mały największy wspólny dzielnik oraz każda z nich powinna mieć co najmniej jeden duży dzielnik pierwszy. Pewne powody, dla których te warunki powinny być spełnione, są przedstawione w ćwiczeniach poniżej. Oczywiście, jeśli ktoś odkryje metodę rozkładu na czynniki, która działa szybko, gdy p i q spełniają pewne warunki, to przyszli użytkownicy systemu RSA powinni wziąć również te warunki pod uwagę.

2.    W podrozdziale 1.3 widzieliśmy, że jeśli liczba n jest iloczynem dwóch liczb pierwszych p i q, to znajomość q>(n) jest równoważna znajomości rozkładu liczby n na czynniki. Przypuśćmy teraz, że udało nam się złamać szyfr RSA w ten sposób, iż znaleźliśmy liczbę d taką, że a⁰⁴ = a (mod ń) dla wszystkich liczb a względnie pierwszych z n. Jest to równoważne temu, że liczba ed — 1 dzieli się przez najmniejszą wspólną wielokrotność liczb p — 1 i q — 1 - Znajomość tej liczby m = ed — 1 w rzeczywistości oznacza mniej niż znajomość q>(n). Jednakże pokażemy teraz procedurę, która z dużym prawdopodobieństwem pozwoli nam rozłożyć liczbę n na czynniki, korzystając tylko ze znajomości liczby m.

Przyjmijmy zatem, że znamy liczbę n - będącą iloczynem dwóch nie znanych liczb pierwszych — oraz liczbę m taką, że a^w = 1 (mod ń) dla wszystkich liczb a względnie pierwszych z n. Zauważmy, że każda taka liczba m musi być parzysta (co łatwo zobaczymy, podstawiając a = — 1). Sprawdzamy najpierw, czy liczba m/2 ma tę samą własność i w takim przypadku zastąpimy m przez m/2. Jeśli af^n,z nie przystaje do 1 modulo n dla wszystkich liczb a względnie pierwszych z /*, to musimy mieć a"*² # 1 (mod n) dla co najmniej 50% liczb a ze zbioru (Z//iZ)* (dowodzi się tego w taki sam sposób, jak części (a) ćwiczenia 21 z podrozdziału 2.2). Zatem, jeśli przetestujemy kilkadziesiąt losowo wybranych liczb a i stwierdzimy, że we wszystkich przypadkach a^łn/2 = 1 (mod n), to z bardzo dużym prawdopodobieństwem możemy przyjąć, że ta kongruencja zachodzi dla wszystkich liczb a względnie pierwszych z n, a więc możemy zastąpić m przez m/2. Kontynu-