Kryptografia-wyklad_10.pdf

Wykład 10

Logarytm dyskretny

10.1 Deﬁnicja

Załóżmy, że (G, ◦) jest grupą skończoną i ∈ G. Niech

H = = { i

: i ∈ N ∗ },

r = rank H.

Deﬁnicja 10.1. Niech ∈ H . Jedyną liczbę całkowitą l taką, że 0 l r − 1 oraz

nazywamy logarytmem dyskretnym elementu w grupie H i oznaczamy ją log .

Przykład 10.1. Niech n ∈ N i rozważmy grupę (Z n , + n ) i niech ∈ Z n ⊥n. W tej grupie

= + 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 ≡ (mod n),

co jest zadaniem łatwym obliczeniowo.

Przykład 10.2. Niech G = Z 7 będzie grupą multyplikatywną. Łatwo można sprawdzić,

że G = 3. W grupie H = G mamy:

log 3 1 = 6, log 3 2 = 2, log 3 3 = 1, log 3 4 = 4, log 3 5 = 5, log 3 6 = 3.

Uwaga 10.1. W zastosowaniach najczęściej przyjmuje się G = Z p z działaniem p , gdzie

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

tograﬁcznego 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,

= {(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 ∈ Z r jest losowo wybraną tajną

liczbą, to deﬁniujemy

∀ x∈P E K (x, k) = ( k , x ◦ k )

oraz

∀ (y 1 , y 2 )∈C D K (y 1 , y 2 ) = y 2 ◦ y − 1 .

Twierdzenie 10.1. Jeżeli K = (G, , l, ) jest poprawnie wybranym kluczem krypto

systemu ElGamala i k ∈ Z rank jest losowo wybraną tajną liczbą, to dla każdego x ∈ P

zachodzi równość

D K (E K (x, k)) = x.

Przykład 10.3. Niech G = H = Z 23 , = 5, G = , l = 6. Wówczas = 8, ponieważ

l = 5 6 ≡ 8 (mod 23).

Tekst jawny: x = 21.

Klucz: K = (Z 23 , 5, 6, 8).

Losowa tajna liczba: k = 3 (⇒ k MOD 23 = 8 3 MOD 23 = 6).

Tekst tajny:

E K (x, k) = E K (21, 3) = (5 3 MOD 23, 21 6 MOD 23) = (10, 11).

Deszyfrowanie:

D K (10, 11) = [11 ((10 6 ) −1

mod 23)] MOD 23 = 11 4 MOD 23 = 21.

10.3 Dystrybucja i uzgadnianie klucza

Deﬁnicja 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 Di egoHellmana uzgadniania klu

cza

Problem bezpiecznego uzgadniania klucza (za pomocą sieci publicznej i bez wykorzy

stywania asymetrycznego systemu kryptograﬁcznego) po raz pierwszy rozwiązali Di e

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 p będzie generatorem grupy multyplikatywnej Z p . Liczby

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 p

było trudne obliczeniowo.

Protokół Diffiego-Hellmana uzgadniania klucza

(1) U wybiera losowo liczbę c U ∈ Z p−1 , oblicza

U = c U

MOD p

i otrzymany wynik przekazuje użytkownikowi V .

(2) V wybiera losowo liczbę c V ∈ Z p−1 , oblicza

V = c V

MOD p

i otrzymany wynik przekazuje użytkownikowi U .

(3) U i V obliczają odpowiednio

K U = ( V ) c U

MOD p oraz K V = ( U ) c V

MOD p.

Twierdzenie 10.2. K U = K V .

Uwaga 10.2. Znalezienie klucza uzgodnionego za pomocą protokołu Di egoHelmana

(bez znajomości liczb c U i c V ) jest równoważne rozwiązaniu nastepującego problemu.

Problem Diffiego-Hellmana

Niech p ∈ P i niech będzie generatorem grupy multyplikatywnej Z p . Dla pewnych

liczb m, n ∈ Z p−1 znane są wartości

m MOD p i n MOD p.

Znaleźć

mn MOD p

(bez znajomości m i n).

Twierdzenie 10.3. Rozwiązanie problemu Di egoHelmana jest równoważne złama

niu systemu kryptograﬁcznego ElGamala dla grupy multyplikatywnej Z p .

10.5 Atak typu wrógwś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 .

• W odbiera od U wygenerowaną liczbę c U MOD p, blokuje jej przesłanie do V , ale

przesyła do V własną liczbę c W MOD p.

• Korzystając z tej liczby użytkownik V generuje klucz K V = ( c W ) c V

MOD p i

przesyła do W swoją liczbę c V MOD p.

• Za pomocą liczby c V MOD p wróg W uzgadnia z użytkownikiem V wspólny klucz

K V .

• Wróg W blokuje przepływ wiadomości o liczbie c V

MOD p do U , w zamian uzgad

niając z U wspólny klucz K U .

Od tej chwili W może wiadomości napływające od U i szyfrowane kluczem K U deszyfro

wać i, po ewentualnej zmianie ich treści, szyfrować kluczem K V , 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.

Uwaga 10.3. Na ogół uzyskane w powyższy sposób klucze K U i K V są różne. Tak więc,

aby pozostać nierozpoznanym, W musi przechwytywać całą korespondencję pomiędzy

użytkownikami U i V .

Istnieją modyﬁkacje algorytmu Di egoHellmana, które uniemożliwiają atak typu

wrógwśrodku. Polegają one na wykorzystaniu protokołu podpisu cyfrowego lub proto

kołu identyﬁkacji. Znane są także inne algorytmy wymiany klucza, które są odporne na

atak tego typu.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: