Wykład 10

Logarytm dyskretny

10.1

Definicja

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

H

= hαi = {α

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ę (Z

n

,

+

n

) i niech α ∈ Z

n

⊥n. W tej grupie

α

k

= α +

n

α

+

n

. . .

+

n

α

|

{z

}

k

składników

= (kα) MOD n,

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 = h3i. 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.

30

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-

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 = hαi.

10.2

Kryptosystem ElGamala

Niech (G, ◦) będzie grupą skończoną, α ∈ G, H = hαi, 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 ∈ Z

r

jest losowo wybraną tajną

liczbą, to definiujemy

∀

x

∈P

E

K

(x, k) = (α

k

, x

◦ β

k

)

oraz

∀

(y

1

, y

2

)∈C

D

K

(y

1

, y

2

) = y

2

◦ y

−l

1

.

Twierdzenie 10.1.

Jeżeli K

= (G, α, l, β) jest poprawnie wybranym kluczem krypto-

systemu ElGamala i k

∈ Z

rankhαi

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 = hαi, 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.

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

+

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

.

32

Uwaga 10.2.

Znalezienie klucza uzgodnionego za pomocą protokołu Diffiego-Helmana

(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 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 .

• 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.

33

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ą 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