28000 Str066

128    4. Kłucie |nihlic/ni

System kryptograficzny Maweya-Omury do przesyłaniu informacji. Przypuśćmy, żc wszyscy użytkownicy systemu /.godzili się używać ustalonego, powszechnie znanego ciała skończonego F_f. Każdy użytkownik wybiera w tajemnicy przed innymi losową liczbę e między 0 i q - 1 tak, by NWD(e_t q - 1)« m I, i za pomocą algorytmu Euklidesa oblicza liczbę odwrotną do niej modulo q - 1, de m 1 (mod q — 1). Jeśli użytkownik A (Alicja) chce wysłać wiadomość Pdo użytkownika B (Bolka), najpierw wysyła mu element P\ Ten element nie ma żadnego znaczenia dla Bolka, który nic zna d_A (gdyż nie zna e_A), a więc nie umie odtworzyć P. Ale nic próbując dociekać sensu w tej wiadomości, podnosi otrzymany element do potęgi e_p, używając swojej liczby e_B i wynik P'*'* odsyła Alicji. W trzecim kroku Alicja częściowo odsłania tajemnicę, podnosząc otrzymany od Bolka element ciała do potęgi d_A; ponieważ P⁴*⁹* = P (na podstawie twierdzenia 2.1.1), więc oznacza to, że Bolek otrzymał P*» i teraz może już odczytać wiadomość, podnosząc otrzymany element do potęgi d_B.

Pomysł leżący u podstaw tego systemu jest raczej prosty i może być uogólniony na sytuacje inne niż potęgowanie w ciałach skończonych. Jednakże należy zachować tu pewną ostrożność. Po pierwsze, zauważmy, że system Mas-seya-Omury koniecznie wymaga stosowania dobrej metody potwierdzania tożsamości. W przeciwnym razie dowolny użytkownik C, który nie powinien poznać informacji P, mógłby podszyć się pod Bolka i odesłać Alicji P*^a9% Alicja nie zdając sobie sprawy z tego, że jakiś intruz użył swojego klucza e_c, podniosłaby otrzymany wynik do potęgi d_A i w ten sposób pozwoliłaby intruzowi C odczytać wiadomość. Zatem wiadomość P*⁴**, przesyłana od Bolka do Alicji, powinna zawierać jakieś potwierdzenie tożsamości, tj. taką wiadomość zgodną z jakimś systemem przesyłania podpisów, którą tylko Bolek mógłby wysłać.

Po drugie, ważne jest, by użytkownik taki jak B lub C, który odczytał różne wiadomości P, a więc zna wiele par (P, P*⁴), nie mógł wykorzystać posiadanych informacji do obliczenia e_A. Załóżmy bowiem, że Bolek mógłby rozwiązać problem logarytmu dyskretnego w FJ, a więc mógłby obliczyć e_A na podstawie P i P*⁴. Wtedy szybko obliczyłby d_A = e_A* mod q — 1 i od tej chwili mógłby odczytywać wszystkie komunikaty wysyłane przez Alicję, niezależnie od tego, czy byłyby przeznaczone dla niego czy dla kogoś innego.

System kryptograficzny EIGamala. Na początku ustalamy bardzo duże ciało skończone F_fl i jeden jego element ge FJ (najlepiej, żeby był to generator grupy FJ, choć nie jest to konieczne). Zakładamy, że odpowiednikami liczbowymi jednostek tekstu otwartego będą elementy P ciała F₄. Każdy użytkownik A wybiera losowo liczbę całkowitą a — a_A z przedziału 0 < a < q — 1. Ta liczba a jest tajnym kluczem rozszyfrowującym. Powszechnie znanym kluczem szyfrującym jest element g^a ciała F_fl.

Jeśli chcemy wysłać komunikat P do użytkownika A, to wybieramy losową liczbę k i wysyłamy następującą parę elementów F :

ii pg*).

Zauważmy, żc bez znajomości a możemy obliczyć g**, po prostu podnosząc g* do potęgi k. Teraz A, który zna a, może odzyskać P z tej pary, najpierw podnosząc g^k do potęgi o, a potem dzieląc następnik pary przez otrzymana potęgę (lub równoważnie, podnosząc g^k do potęgi q~ I - a i mnożąc wynik przez następnik pary). Innymi słowy, to, co wysyłamy do A, składa się z zamaskowanej wiadomości - jest to wiadomość P „ukryta za maską” g*^k - wraz ze „wskazówką” g^k, wyjaśniającą, w jaki sposób zdjąć maskę (jednak ta wskazówka może być użyta tylko przez kogoś, kto zna a).

Ktoś, kto umie rozwiązać problem logarytmu dyskretnego w ciele F_f, może złamać ten system, znajdując tajny klucz rozszyfrowujący a z powszechnie znanego klucza szyfrującego g°. Teoretycznie może istnieć sposób na wykorzystanie g^k i g^a do znalezienia g^A - a zatem złamania szyfru - bez rozwiązywania problemu logarytmu dyskretnego. Jednakże, jak już o tym wspomnieliśmy przy omawianiu systemu wymiany kluczy Diffiego-Hdlmana, przypuszcza się, że nie istnieje żaden sposób obliczenia g^A z g^k i g“, nie rozwiązujący przy okazji problemu logarytmu dyskretnego.

Standard podpisów cyfrowych (ang. Digital Signature Standard - DSS). Został on zaproponowany w 1991 roku przez rządowy instytut Stanów Zjednoczonych, National Institute of Standards and Technology (NIST). Można się spodziewać, że rola DSS będzie analogiczna do roli, jaką odegrał znacznie starszy standard szyfrowania danych (ang. Data Encryption Standard - DES), tzn. zakłada się, że DSS stanie się standardową metodą cyfrowego podpisywania korespondencji, stosowaną przez organizaqe rządowe i handlowe. Ale o ile DES był klasycznym systemem kryptograficznym (z „prywatnym kluczem”), to podpisy cyfrowe wymagają użycia systemów z publicznym kluczem. NIST zdecydował się oprzeć swój system podpisywania na problemie logarytmu dyskretnego w skończonych ciałach prostych. DSS jest bardzo podobny do metody podpisów zaproponowanej przez Schnorra (por. bibliografię na końcu tego podrozdziału). Jest również podobny do systemu podpisów cyfrowych ElGa-mala (por. ćwiczenie 9 w tym podrozdziale). Opiszemy teraz, w jaki sposób działa DSS.

Aby zapoczątkować tę metodę (tak, by móc później podpisywać wiadomości), każdy użytkownik (niech będzie nim Alicja) postępuje według następującego schematu: (1) wybiera liczbę pierwszą q mającą około 160 bitów (stosuje do tego generator liczb losowych i test pierwszości); (2) wybiera następnie drugą liczbę pierwszą p, przystającą do 1 module 4 i mającą około 512 bitów; (3) wybiera generator jedynej podgrupy cyklicznej grupy F* rzędu q (obliczając g_B~^l)lq modulo p dla losowo wybranej liczby g₀; jeśli wynik jest różny od 1, to g₀ będzie generatorem); (4) wybiera losową liczbę x z przedziału 0 < x < q_t będącą kluczem tajnym, i oblicza klucz publiczny za pomocą wzoru y s g* (mod p).

Przypuśćmy teraz, że Alicja chce podpisać wiadomość. Najpierw oblicza wartość funkcji skrótu dla argumentu, którym jest jej tekst jawny (por.