Podręcznik

5.5. Funkcja jednokierunkowa

Funkcja f : X  Y , gdzie X, Y są dowolnymi niepustymi zbiorami, jest nazywana funkcją jednokierunkową (ang. one way function) jeśli:

• Dla każdego x  X łatwo potrafimy obliczyć wartość f(x).
• Dla każdego y  f ( X ) , znalezienie takiego x  X , że y = f(x) jest praktycznie nierealizowalne (z uwagi na złożoność obliczeniową problemu).

Nie znamy żadnego dowodu na to, że jakaś funkcja jednokierunkowa w ogóle istnieje. Jesteśmy jednak przekonani, że funkcje jednokierunkowe w przyrodzie istnieją.

A oto trzy kandydatki na funkcje jednokierunkowe. Są to permutacje podzbioru liczb całkowitych Z_p . Ogólnie rzecz biorąc jednak funkcja jednokierunkowa nie musi być różnowartościowa.

• Funkcja wykładnicza modulo p (ang. exponentation modulo p), gdzie p jest liczbą pierwszą. Niech p będzie liczbą pierwszą i niech  będzie generatorem grupy multiplikatywnej Z_p ^* . Funkcja wykładnicza modulo p f : Z_p ^*  Z_p ^* jest zdefiniowana  dla każdego x  Z_p ^* wzorem

f (x)   ^x (mod p) ,

• lub wzorem f (x)   ^x , jeśli mnożenie traktujemy jako mnożenie w Z _p . Odwrócenie p Z funkcji f jest dokładnie problemem znalezienia wartości logarytmu dyskretnego w grupie multiplikatywnej Z_p ^* (jeśli y  f (x) , czyli y   ^x , to x  log_ y ). Nie są znane efektywne obliczeniowo algorytmy obliczania wartości logarytmu dyskretnego w grupie Z_p ^* .
• Funkcja RSA (ang. RSA function). Niech p, q będą różnymi nieparzystymi liczbami pierwszymi i niech n  p  q . Niech ponadto NWD(e,( p  1)(q  1))  1. Funkcja RSA zdefiniowana jest tak f : Z_n  Z_n , f (x)  x^e (mod n) dla każdego x  Z_n .
• Funkcja Rabina. Niech n  p  q gdzie p i q są różnymi liczbami pierwszymi takimi, że p  3(mod 4) i q  3(mod 4) (n jest tzw. liczbą Bluma). Funkcja Rabina f zdefiniowana jest następująco

f : Q_n  x  n f (x)  x ² (mod n)  Q

gdzie Q_n  Z_n jest tzw. zbiorem reszt kwadratowych modulo n. Można pokazać, że f jest permutacją zbioru Q_n . Odwracanie funkcji f, czyli obliczanie pierwiastka kwadratowego w pierścieniu Z_n jest dla dużych n praktycznie nierealizowalne, tzn. nie są znane żadne efektywne obliczeniowo algorytmy rozwiązujące ten problem, chyba, ze potrafimy rozłożyć liczbę n na czynniki pierwsze.