Rozdział Elementy teorii złożoności



Pobieranie 1,74 Mb.
Strona3/19
Data23.02.2018
Rozmiar1,74 Mb.
1   2   3   4   5   6   7   8   9   ...   19

Definicja 1.8


Problem decyzyjny (poszukiwawczy) z dołączonym pewnym warunkiem nazywamy problemem z obietnicą.
Analizując algorytm dla problemu z obietnicą nie przejmujemy się, jeśli warunek nie jest spełniony i algorytm daje złą odpowiedź (albo nie daje jej wcale).
Problem łamania kryptosystemu z kluczem publicznym jest problemem z obietnicą.
Dane: E, fE: P→C, cC.

Obietnica: fE jest różnowartościowa i c należy do jej obrazu.

Wynik: pP takie, że fE(p) = c.
Poniższa definicja opisuje jeszcze jedną, bardzo ważną klasę problemów, która ma duże znaczenie we współczesnej kryptografii.
Definicja 1.9

Problem decyzyjny A jest klasy RP problemów rozwiązywalnych probabilistycznie w czasie wielomianowym jeżeli istnieje algorytm czasu wielomianowego, który zawiera pewien losowy wybór w zależności od którego daje odpowiedź „tak” lub „nie”, przy czym odpowiedź „tak” jest zawsze odpowiedzią poprawną, natomiast prawdopodobieństwo, że odpowiedź „nie” jest poprawna jest większe niż .

Podobnie jak w definicji 1.5 definiuje się klasę problemów co-RP.


Wiele kryptosystemów można złamać za pomocą niedeterministycznego algorytmu czasu wielomianowego. Na przykład dysponując szyfrogramem c można odgadywać tekst otwarty p oraz klucz k, a następnie stosować k i p w algorytmie szyfrującym. Czynności te powtarzamy tak długo, aż w wyniku szyfrowania wiadomości p za pomocą klucza k otrzymamy szyfrogram c. Z praktycznego punktu widzenia takie postępowanie nie ma większego sensu. Teoretycznie daje ono górną granicę złożoności kryptoanalizy dla danych systemów kryptograficznych. W rzeczywistości najlepszym rozwiązaniem jest znalezienie deterministycznego algorytmu czasu wielomianowego.

          1. Funkcje jednokierunkowe

Przejdźmy teraz do zagadnienia funkcji jednokierunkowych, które są podstawą działania kryptosystemów z kluczem jawnym.


Definicja 1.10

Funkcja wzajemnie jednoznaczna f: X→Y jest jednokierunkowa, jeżeli dla danego xX łatwo obliczyć f(x) ale wyliczenie f –1(y) dla przypadkowo wybranego yY jest trudne.


Powyższa definicja funkcji jednokierunkowej jest mało precyzyjna. Użyte w tym kontekście słowo „trudno” oznacza, że wyliczenie funkcji odwrotnej jest z praktycznego punktu widzenia niemożliwe (obliczenia mogą być zbyt kosztowne i długotrwałe). Definicję funkcji jednokierunkowej można bardziej sprecyzować za pomocą elementów teorii złożoności obliczeniowej.
Definicja 1.11

Funkcja wzajemnie jednoznaczna f: X→Y jest jednokierunkowa, jeżeli spełnia następujące warunki:



  1. istnieje deterministyczny algorytm, który dla danego xX oblicza f(x) w czasie wielomianowym ze względu na |x|,

  2. nie istnieje probabilistyczny algorytm, który dla losowo wybranego yY oblicza f 1(y),

  3. długość x i długość y = f(x) są porównywalne tzn.:

R |x|  |y|, |y|  |x|.
Postulat 2 definicji 1.11 trzeba jeszcze uściślić. Niech P(Z) oznacza prawdopodobieństwo zajścia zdarzenia Z. Dla każdego probabilistycznego algorytmu wielomianowego A i dla każdego wielomianu p istnieje stała kR, że dla każdego n > k zachodzi nierówność P(f(A(z))=z) < p1(n), gdzie z jest zmienną losową z rozkładem jednostajnym na zbiorze Y.

Nie wykluczamy więc, że dla pewnych yY znalezienie takiego xX, że f(x) = y jest łatwe. Jednak dla odpowiednio dużego zbioru Y prawdopodobieństwo tego jest bardzo bliskie zera.


Nie ma formalnego dowodu matematycznego, że funkcje jednokierunkowe istnieją. Znaleziono jednak wiele funkcji, które zachowują się jak funkcje jednokierunkowe.
Z praktycznego punktu widzenia wiadomość zaszyfrowana za pomocą funkcji jednokierunkowej nie jest użyteczna, ponieważ nikt nie mógłby jej odszyfrować w rozsądnym czasie. Dlatego w kryptografii potrzebna jest specjalna klasa funkcji jednokierunkowych – tzw. jednokierunkowe funkcje zapadkowe. Są to funkcje, które można łatwo obliczyć, natomiast odwracanie ich jest praktycznie wykonalne tylko pod warunkiem, że zna się pewien sekret (zapadkę). Dobrą analogią jest tutaj skrzynka pocztowa. Każdy może łatwo włożyć list do skrzynki, jednak otwarcie jej bez użycia odpowiedniego klucza nie jest już takie proste. Na podobnej zasadzie opiera się kryptografia z kluczem jawnym.
Problem obliczenia funkcji jednokierunkowej jest klasy P, natomiast problem jej odwracania jest klasy NP. Jak już było omówione wcześniej, do tej pory nie zostało udowodnione, czy P  NP. Jeżeli zachodziłaby równość P = NP, to odwracanie funkcji uważanej za jednokierunkową byłoby wykonalne przez algorytm deterministyczny w czasie wielomianowym co oznaczałoby, że funkcje jednokierunkowe nie istnieją!


1   2   3   4   5   6   7   8   9   ...   19


©operacji.org 2017
wyślij wiadomość

    Strona główna