U provedbi ove ideje ključnu ulogu igraju tzv. osobne jednosmjerne funkcije. Za funkciju f kažemo da je jednosmjerna (one-way) ako je f lako, a f -1 teško izračunati. Ako je pritom f -1 lako izračunati ukoliko nam je poznat neki dodatni podatak (trapdoor - skriveni ulaz), onda f nazivamo osobna jednosmjerna funkcija.
U konstrukciji osobnih jednosmjernih funkcija koriste se teški matematički problemi, kao što su
Sada ćemo opisati
ElGamalov kriptosustav koji je 1985. godine
predložio Taher ElGamal,
a zasnovan na teškoći računanja diskretnog logaritma u
u grupi (*,
.
).
Najbolji poznati algoritam za problem diskretnog logaritma u
*
je jedna varijanta "index calculus metode" koja se naziva
sito polja brojeva. Očekivani broj operacija za računanje
diskretnog logaritma tom metodom je
exp(1.92 (ln p)1/3 (ln ln p)2/3).
Algoritmi ovakve složenosti nazivaju se subeksponencijalni algoritmi. Pokazuje se da je po složenosti ovaj problem vrlo sličan problemu faktorizacije, a i metode koje koriste u najboljim poznatim algoritmima za rješavanje tih problema su vrlo slične. No, kako ćemo nešto kasnije vidjeti, problem diskretnog logaritma u
ElGamalov kriptosustav: Neka je p prost broj i ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
![]() ![]() Za K = (p, ![]() ![]() ![]() ![]() ![]() ![]()
eK(x, k) = ( ![]() ![]() ![]() dK(y1, y2) = y2(y1a)-1 mod p. |
Mogli bismo reći da se otvoreni tekst x "zamaskira" množeći s
k.
Onaj tko poznaje tajni eksponent a može iz
k
izračunati
k
i "ukloniti masku".
Da bi eksponent a stvarno bio tajan, prost broj p mora biti dovoljno velik da bi u
*
problem diskretnog logaritma bio praktički nerješiv. Stoga se danas
preporuča korištenje prostih brojeva od oko 1024 bita. Također bi,
zbog razloga koje ćemo kasnije objasniti, red grupe, tj. broj
p - 1, trebao imati barem jedan veliki prosti faktor
(od barem 160 bitova).
Primjer: Neka je u ElGamalovom kriptosustavu
p = 2579,
= 2,
a = 765. Tada je
=
2765 mod 2579 = 949.
y1 = 2853 mod 2579 = 435,
y2 = 1299
949853 mod 2579 =
1299
2424 =
2396,
x = 2396
(435765)-1 mod 2579 =
2396
2424-1
= 2396
1980 =
1299,
Napomenimo da se operacija potenciranja modulo p može efikasno provesti "metodom uzastopnog kvadriranja", tj. tako da se eksponent prikaže u bazi 2. Inverz modulo p se također može efikasno izračunati i to primjenom Euklidovog algoritma, pomoću kojeg za broj n koji je relativno prost s p nalazimo brojeve u i v za koje vrijedi nu + pv = 1.
Web stranica seminara | Andrej Dujella - osobna stranica |