Str070

136    4. > Cl»we publfc/nc

ciuła F„ (por przykład 2 w podrozdziale 2.1) jako g wybierzemy pj_erwi stek a wielomianu A'*’ - A* - 1, to utworzymy następującą tablicę:

n	f	a	log,a
1	a	1	8
m	* + 1	^-1	4
3	-a+1	a	1
4	-1	a+1	2
5	—a	a-l	7
6	-a-l	—a	5
7	a-l	-a+1	3
8	1	-a-l	6

Wtedy mnożenie lub dzielenie sprowadza się do dodawania lub odejmowania modulo ę — li wyszukiwania w tablicy. Jeśli na przykład chcemy pomnożyć a - 1 przez —a — 1, znajdujemy te dwa elementy w trzeciej kolumnie i dodajemy odpowiednie logarytmy: 7 + 6 = 5 (mod 8), a następnie znajdujemy wynik —a w drugiej kolumnie, obok liczby 5.

(a)    Sporządź tablicę logarytmów dla grupy FJj i użyj jej do obliczenia 16 • 17,19 • 13, 1/17, 20/23.

(b)    Sporządź tablicę logarytmów dla grupy FJ i użyj jej do obliczenia (gdzie a jest pierwiastkiem wielomianu X³ + X + 1; Twoje wyniki nie powinny zawierać potęg a wyższych niż druga): (a + l)(a² + a), (a² + a + l)(a² + 1), l/(a² + 1), a/(a² + a + 1).

2. Na pierwszy rzut oka wydaje się, że moglibyśmy użyć grupy cyklicznej (Z/p“Z)* (por. ćwiczenie 2(a) w podrozdziale 2.1) zamiast grupy FJ w sformułowaniu problemu logarytmu dyskretnego. Okazuje się jednak, że rozwiązanie problemu logarytmu dyskretnego dla (Z/p“Z)*, gdzie a > 1, nie wymaga zasadniczo więcej czasu (nawet gdy a jest dość duże) niż dla a = 1 (tzn. w F_p). Dokładniej, stosując metody opisane w tym ćwiczeniu, można dowieść, że jeśli umiemy rozwiązać problem logarytmu dyskretnego modulo p, to zrobienie reszty (tzn. rozwiązanie go modulo /?“) wymaga czasu wielomianowego względem log(p“) = alogp. (Przypomnijmy tu, że nie jest znany żaden algorytm rozwiązujący w czasie wielomianowym problem logarytmu dyskretnego modulo p dla dużych p\ eksperci wątpią w to, że taki algorytm istnieje). W tym ćwiczeniu pokażemy, że dla p = 3 istnieje bezpośredni algorytm rozwiązujący problem logarytmu dyskretnego modulo 3* w czasie wielomianowym względem a.

Przypuśćmy zatem, że g = 2 (można łatwo pokazać, że 2 jest generatorem grupy (Z/3“Z)* dla dowolnego a), mamy daną liczbę a niepodzielną przez 3 i chcemy rozwiązać kongruencję 2* = a (mod 3*). Udowodnij, że następujący algorytm zawsze znajduje x w czasie wielomianowym

względem a i oszacuj (w notacji O) liczbę operacji na bitach potrzebnych do znalezienia x:

(i)    Pokaż, że problem logarytmu dyskretnego jest równoważny rozwiązaniu kongruencji, w której liczba a została przeniesiona na lewą stronę (tzn. 2^xa s 1). Następnie pokaż, że bez straty ogólności możemy założyć, że a s 1 (mod 3) i że liczba x jest parzysta. Zatem możemy zastąpić naszą kongruencję przez kongruencję 4^xa = I (mod 3*).

(ii)    Zapisz x w postaci x = x₀ + 3x, +... + 3*” ²x_f _ ₂, gdzie Xj są cyframi w systemie trójkowym. Podstaw x ~ i = 0. Wtedy kongruencja

₄xo+3x,-f...₊3/-^._{2fl s} j (_mod 3^;)    (*)_;

zachodzi dla y = 1. Przyjmij g, = 4. W czasie działania algorytmu będziemy przy okazji obliczać g_} = 4^3/_s mod 3*. Przyjmij a_r = a i dla / > 1 zdefiniuj a_} jako resztę z dzielenia 4***    przez 3^a;

algorytm będzie obliczał kolejne wartości a_r

(iii)    Załóż, źe/> 1 oraz że zostały już obliczone wartości x_(h ..., tak, że zachodzi kongruencja (*)^_, (tzn. kongruencja (*), w której zamiast j mamy j — 1). Załóż też, że zostały obliczone wartości gj-i = 4³'”^ł mod 3“ oraz ay__r. Teraz jako x_h2 weź (1 - a_hl)lV'¹ modulo 3. (Zauważ, że _l = 1 (mod 3^j~^l) ze względu na (*)_;_,). Następnie oblicz aj = gj^J_-{ a_}_ _L mod 3^a. Wreszcie, jeśli y < a, to oblicz gj, podnosząc g_;__Ł do trzeciej potęgi, modulo 3*.

(iv)    Gdy j — a, kończysz wykonywanie algorytmu.

3.    Ustaliliście ze swoją przyjaciółką, że będziecie ze sobą korespondować, używając afinicznych przekształceń szyfrujących C = AP + B (mod N) (por. przykłady 3 i 4 w podrozdziale 3.1, w których współczynniki były oznaczane małymi literami). Jednostkami tekstu będą pojedyncze litery 31-literowego alfabetu, w którym litery A-Z mają odpowiedniki liczbowe 0-25, odstęp = 26, . = 27, ? = 28, ! = 29, ’ = 30. Klucz szyfrujący K_e = (A, B) traktujesz jako element A + Bi ciała 31 Elementowego (gdzie i oznacza pierwiastek kwadratowy z -1 w tym ciele). Ustaliliście również, że wymienicie się kluczami, korzystając z systemu Diffiego-Hellmana i wybraliście g = 4 + i. Twoją losowo wybraną tajną liczbą całkowitą jest a = 209. Twoja przyjaciółka przysłała Ci swoją liczbę g^b = I + 19/.

(a)    Znajdź klucz szyfrujący.

(b)    Jaki element ciała F₉₆₁ musisz wysłać swojej przyjaciółce po to, by ona również znała klucz?

(c)    Znajdź przekształcenie rozszyfrowujące.

(d)    Odczytaj wiadomość „BUVCFlWOUJTZ!H^,\

4.    Otrzymałeś kryptogram „VHNHDOAM”, który został zaszyfrowany za pomocą macierzy