Wykład 10
Logarytm dyskretny
10.1 Definicja
Załóżmy, że (G, ć%) jest grupą skończoną i ą " G. Niech
H = Ä… = {Ä…i : i " N"}, r = rank H.
Definicja 10.1. Niech ² " H. JedynÄ… liczbÄ™ caÅ‚kowitÄ… l takÄ…, że 0 l r - 1 oraz
Ä…l = ²
nazywamy logarytmem dyskretnym elementu ² w grupie H i oznaczamy jÄ… logÄ… ².
Przykład 10.1. Niech n " N i rozważmy grupę (Zn, +n) i niech ą " ZnĄ"n. W tej grupie
Ä…k = Ä… +n Ä… +n . . . +n Ä… = (kÄ…) MOD n,

k składników
wiÄ™c obliczenie logarytmu dyskretnego x = logÄ… ² sprowadza siÄ™ do rozwiÄ…zania kongru-
encji liniowej
Ä…x a" ² (mod n),
co jest zadaniem Å‚atwym obliczeniowo.
Przykład 10.2. Niech G = Z+ będzie grupą multyplikatywną. A
atwo można sprawdzić,
7
że G = 3 . W grupie H = G mamy:
log3 1 = 6, log3 2 = 2, log3 3 = 1, log3 4 = 4, log3 5 = 5, log3 6 = 3.
30
Uwaga 10.1. W zastosowaniach najczęściej przyjmuje siÄ™ G = Z+ z dziaÅ‚aniem · , gdzie
p
p
p jest dużą liczbą pierwszą. Wtedy rank G = p - 1. Najprostszym wyborem podgrupy
H jest przyjęcie H = G. Okazuje się jednak, że taki wybór nie jest najlepszy z kryp-
tograficznego punktu widzenia. Lepiej jest wybrać H w sposób następujący. W grupie
G znajdujemy (losowo) element ą, którego rząd q (oczywiście q|p - 1) jest dużą liczbą
pierwszÄ… i przyjmujemy H = Ä… .
10.2 Kryptosystem ElGamala
Niech (G, ć%) będzie grupą skończoną, ą " G, H = ą , r = rank H. Przyjmijmy
P = G,
C = G × G,
K = {(G, Ä…, l, ²) : ² " H '" ² = Ä…l}.
Dla (G, Ä…, l, ²) " K publicznÄ… częściÄ… klucza jest (G, Ä…, ²), a częściÄ… prywatnÄ… jest l.
Jeżeli K = (G, Ä…, l, ²) jest ustalonym kluczem i k " Zr jest losowo wybranÄ… tajnÄ…
liczbÄ…, to definiujemy
"x"P EK(x, k) = (Ä…k, x ć% ²k)
oraz
-l
"(y , y2)"C DK(y1, y2) = y2 ć% y1 .
1
Twierdzenie 10.1. Jeżeli K = (G, Ä…, l, ²) jest poprawnie wybranym kluczem krypto-
systemu ElGamala i k " Zrank ą jest losowo wybraną tajną liczbą, to dla każdego x " P
zachodzi równość
DK(EK(x, k)) = x.
PrzykÅ‚ad 10.3. Niech G = H = Z23, Ä… = 5, G = Ä… , l = 6. Wówczas ² = 8, ponieważ
Ä…l = 56 a" 8 (mod 23).
Tekst jawny: x = 21.
Klucz: K = (Z23, 5, 6, 8).
Losowa tajna liczba: k = 3 (Ò! ²k MOD 23 = 83 MOD 23 = 6).
Tekst tajny:
EK(x, k) = EK(21, 3) = (53 MOD 23, 21 · 6 MOD 23) = (10, 11).
Deszyfrowanie:
DK(10, 11) = [11 · ((106)-1 mod 23)] MOD 23 = 11 · 4 MOD 23 = 21.
31
10.3 Dystrybucja i uzgadnianie klucza
Definicja 10.2. Dystrybucją klucza nazywamy proces, podczas którego jedna ze stron
wybiera tajny klucz i przekazuje go drugiej stronie (lub drugim stronom) przez kanał
publiczny. Uzgadnianie klucza polega na ustaleniu wspólnego tajnego klucza za pośred-
nictwem kanału publicznego przez dwie strony (lub więcej), przy czym wszystkie strony
mają wpływ na wartość ustalonego klucza.
Fakt: Bezpieczna dystrybucja klucza jest możliwa dzięki użyciu kryptosystemu asyme-
trycznego.
10.4 Algorytm Diffiego-Hellmana uzgadniania klu-
cza
Problem bezpiecznego uzgadniania klucza (za pomocÄ… sieci publicznej i bez wykorzy-
stywania asymetrycznego systemu kryptograficznego) po raz pierwszy rozwiÄ…zali Diffie
i Hellman w roku 1976 wykorzystujÄ…c logarytm dyskretny.
Załóżmy, że dwaj użytkownicy U i V sieci publicznej chcą uzgodnić wspólny tajny
klucz. Dla p " P niech ą " Z+ będzie generatorem grupy multyplikatywnej Z+. Liczby
p p
p i ą są publicznie znane  mogą być ustalone przez jednego z użytkowników i przesła-
ne drugiemu kanałem publicznym. Liczba p powinna być tak dobrana, aby znalezienie
logarytmu dyskretnego w grupie Z+ było trudne obliczeniowo.
p
Protokół Diffiego-Hellmana uzgadniania klucza
(1) U wybiera losowo liczbÄ™ cU " Zp-1, oblicza
U
²U = Ä…c MOD p
i otrzymany wynik przekazuje użytkownikowi V .
(2) V wybiera losowo liczbÄ™ cV " Zp-1, oblicza
V
²V = Ä…c MOD p
i otrzymany wynik przekazuje użytkownikowi U.
(3) U i V obliczajÄ… odpowiednio
U V
KU = (²V )c MOD p oraz KV = (²U)c MOD p.
Twierdzenie 10.2. KU = KV .
32
Uwaga 10.2. Znalezienie klucza uzgodnionego za pomocą protokołu Diffiego-Helmana
(bez znajomości liczb cU i cV ) jest równoważne rozwiązaniu nastepującego problemu.
Problem Diffiego-Hellmana
Niech p " P i niech ą będzie generatorem grupy multyplikatywnej Z+. Dla pewnych
p
liczb m, n " Zp-1 znane są wartości
Ä…m MOD p i Ä…n MOD p.
Znalez
ć
Ä…mn MOD p
(bez znajomości m i n).
Twierdzenie 10.3. Rozwiązanie problemu Diffiego-Helmana jest równoważne złama-
niu systemu kryptograficznego ElGamala dla grupy multyplikatywnej Z+.
p
10.5 Atak typu wróg-w-środku
" Wróg W w sposób niezauważalny włącza się do kanału przesyłania wiadomości,
pomiędzy użytkowników U i V .
U
" W odbiera od U wygenerowaną liczbę ąc MOD p, blokuje jej przesłanie do V , ale
W
przesyła do V własną liczbę ąc MOD p.
W V
" Korzystając z tej liczby użytkownik V generuje klucz KV = (ąc )c MOD p i
V
przesyła do W swoją liczbę ąc MOD p.
V
" Za pomocą liczby ąc MOD p wróg W uzgadnia z użytkownikiem V wspólny klucz
KV .
V
" Wróg W blokuje przepływ wiadomości o liczbie ąc MOD p do U, w zamian uzgad-
niając z U wspólny klucz KU.
Od tej chwili W może wiadomości napływające od U i szyfrowane kluczem KU deszyfro-
wać i, po ewentualnej zmianie ich treści, szyfrować kluczem KV , a potem przesyłać do
V . Oczywiście w ten sam sposób może przechwytywać wiadomości wysłane przez użyt-
kownika V do użytkownika U. W ten sposób W może kontrolować wymianę wiadomości
pomiędzy U i V , sam nie będąc rozpoznany.
33
Uwaga 10.3. Na ogół uzyskane w powyższy sposób klucze KU i KV są różne. Tak więc,
aby pozostać nierozpoznanym, W musi przechwytywać całą korespondencję pomiędzy
użytkownikami U i V .
Istnieją modyfikacje algorytmu Diffiego-Hellmana, które uniemożliwiają atak typu
wróg-w-środku. Polegają one na wykorzystaniu protokołu podpisu cyfrowego lub proto-
kołu identyfikacji. Znane są także inne algorytmy wymiany klucza, które są odporne na
atak tego typu.
34