Systemy szyfrowania z akluczem jawnym



Pobieranie 65.99 Kb.
Data08.05.2016
Rozmiar65.99 Kb.
Systemy szyfrowania z akluczem jawnym
W systemach szyfrowania konwencjonalnego klucze stosowane do szyfrowania i deszyfrowania danego komunikatu są takie same. Nie jest to warunek konieczny. Można stworzyć algorytm kryptograficzny, który opiera się na jednym kluczu do szyfrowania, i innym, lecz związanym z pierwszym, kluczu do deszyfrowania. Algorytmy takie mają następującą ważną cechę:

  • Nie jest możliwe na drodze obliczeń określenie klucza deszyfrującego przy znajomości algorytmu kryptograficznego i klucza szyfrującego.

Ponadto niektóre algorytmy, np. RSA, wykazują także następującą cechę:

  • Któregokolwiek z (związanych ze sobą) kluczy można użyć do szyfrowania, drugiego zaś do deszyfrowania.


Powyższy rysunek ilustruje proces szyfrowania z kluczem jawnym. Główne etapy tego procesu są następujące:



  1. Każdy system końcowy w sieci generuje parę kluczy do szyfrowania i deszyfrowania otrzymanych komunikatów.

  2. Każdy system publikuje swój klucz szyfrujący przez umieszczenie go w publicznym rejestrze do pliku. To jest klucz jawny. Drugi klucz pozostaje prywatny.

  3. Jeżeli A chce wysłać komunikat do B, szyfruje go za pomocą klucza jawnego B.

  4. Gdy B otrzymuje komunikat, deszyfruje go za pomocą prywatnego klucza B. Żaden inny odbiorca nie może odszyfrować komunikatu, ponieważ tylko B zna swój prywatny klucz.

Przy stosowaniu takiej metody wszyscy użytkownicy mają dostęp do kluczy publicznych, a klucze prywatne są generowane lokalnie przez każdego uczestnika i nie muszą być nigdy przesyłane.

Dopóki system ma kontrolę nad swoim kluczem prywatnym, dopóki nadchodzące do niego komunikaty są bezpieczne. W każdej chwili system może zmienić swój klucz prywatny i ogłosić odpowiadający mu klucz jawny, który zastąpi stary.

W poniższej tabeli zebrano niektóre najważniejsze aspekty szyfrowania konwencjonalnego i szyfrowania z kluczem jawnym. Dla odróżnienia klucz stosowany w szyfrowaniu konwencjonalnym nazywany będzie kluczem tajnym. Klucze stosowane w szyfrowaniu z kluczem jawnym nazywane są kluczem jawnym i kluczem prywatnym. W dalszej części stosowane będą następujące oznaczenia:


  • Klucz tajny Km, gdzie m oznacza jakieś określenie, np. Ks to klucz sesji.

  • Klucz jawny KUa (dla użytkownika A), a odpowiadający mu klucz prywatny KRa. Szyfrowanie

Szyfrowanie konwencjonalne

Szyfrowanie z kluczem jawnym

Niezbędne do działania


  1. Ten sam algorytm i ten sam klucz używany do szyfrowania i deszyfrowania.

  1. Jeden algorytm jest używany do szyfrowa-nia i deszyfrowania, wraz z parą kluczy: jeden do szyfrowania, drugi do deszyfrowania.

  1. Nadawca i odbiorca muszą mieć taki sam algorytm i klucz.

  1. Nadawca i odbiorca muszą mieć jeden z pary kluczy.

Niezbędne do bezpieczeństwa


  1. Klucz musi być trzymany w tajemnicy.

  1. Jeden z dwóch kluczy musi być trzymany w tajemnicy.

  1. Odszyfrowanie komunikatu bez posiada-nia innych informacji musi być niemożli-we lub co najmniej niepraktyczne.

  1. Odszyfrowanie komunikatu bez posiada-nia innych informacji musi być niemożli-we, lub co najmniej niepraktyczne.

  1. Znajomość algorytmu oraz próbki tekstu zaszyfrowanego nie mogą wystarczać do odkrycia klucza

  1. Znajomość algorytmu, jednego z kluczy oraz próbki tekstu zaszyfrowanego nie mogą wystarczyć do odkrycia drugiego klucza

Klucz prywatny jest także trzymany w tajemnicy, lecz określany jest nazwą „klucz prywatny”, aby uniknąć mylenia go z kluczem stosowanym w szyfrowaniu konwencjonalnym.

Najważniejsze elementy systemu szyfrowania z kluczem jawnym można przeanalizować wykorzystując kolejny rysunek. Źródłem komunikatu jest A, które generuje komunikat w postaci tekstu otwartego X=[X1, X2,....,XM]. Elementy XM są literami pewnego skończonego alfabetu. Komunikat jest przeznaczony dla B. B generuje powiązany parę kluczy: klucz jawny KUb i klucz prywatny KRb. KRb jest tajny i zna go tylko B, a KUb jest powszechnie dostępny, a więc dostępny dla A.

Dysponując komunikatem X i kluczem szyfrującym KUb w charakterze danych wejściowych , A tworzy tekst zaszyfrowany Y=[Y1, Y2, ...,YN]:

Y=EKUb(X)

Odbiorca będący w posiadaniu odpowiedniego klucza prywatnego, może odwrócić przekształcenie:

X=DKRb(Y)

Przeciwnik, który śledzi Y i ma dostęp do KUb, lecz nie ma dostępu do KRb lub X, musi starać się uzyskać X i/lub KRb. Zakładamy, że przeciwnik zna algorytm szyfrowania (E) i deszyfrowania (D). Jeśli interesuje go tylko jeden konkretny komunikat, skoncentruje się na uzyskaniu X przez generowanie hipotetycznego tekstu jawnego. Częstokroć jednak przeciwnikowi zależy na możliwości odczytania również przyszłych komunikatów, będzie więc starał się uzyskać KRb, generując hipotetyczny klucz .

Jak wspomniano wcześniej, którykolwiek z dwóch powiązanych kluczy może być zastosowany do szyfrowania, wtedy drugi można zastosować do deszyfrowania. Umożliwia to zastosowanie innego systemu kryptograficznego. System przedstawiony na powyższym rysunku zapewnia poufność, a na kolejnym rysunku przedstawione zostanie zastosowanie szyfrowania z kluczem jawnym do zapewnienia uwierzytelniania:

Y=EKRa(X)

X=DKUa(Y)

W tym przypadku A przygotowuje komunikat dla B i przed przesłaniem szyfruje go za pomocą swojego klucza prywatnego. B może odszyfrować komunikat za pomocą klucza jawnego A. Ponieważ komunikat został zaszyfrowany za pomocą klucza prywatnego należącego do A, tylko A mógł go przygotować. W ten sposób cały komunikat pełni funkcję sygnatury cyfrowej (podpisu cyfrowego). Ponadto nie można zmienić komunikatu nie mając dostępu do klucza prywatnego A, więc komunikat jest uwierzytelniony zarówno pod względem nienaruszalności danych.



W powyższym systemie cały komunikat jest zaszyfrowany, co wprawdzie zapewnia autentyczność autora i komunikatu, jednak wymaga przechowywania dużych ilości danych. Każdy dokument musi być przechowywany w postaci jawnej dla celów praktycznych. Trzeba także przechowywać kopię w postaci zaszyfrowanej, aby umożliwić weryfikację pochodzenia i treści w przypadku wątpliwości. Bardziej efektywnym sposobem na osiągnięcie tego samego rezultatu jest zaszyfrowanie niewielkiego bloku bitów, będącego funkcją dokumentu. Taki blok, zwany wartością uwierzytelniającą (authenticator), musi mieć taką własność, by wprowadzenie zmian do dokumentu bez powstania różnicy w tej wartości było niemożliwe. Jeśli wartość uwierzytelniająca została zaszyfrowana za pomocą prywatnego nadawcy, pełni ona rolę sygnatury potwierdzającej pochodzenie, treść i kolejność. Technika ta umawiana jest w części sygnatury cyfrowe.

Należy podkreślić, że opisany powyżej proces szyfrowania nie zapewnia poufności. Przesyłany komunikat jest zabezpieczony przed wprowadzaniem zmian, lecz nie przed podsłuchem. Jest to oczywiste w przypadku sygnatury opartej na fragmencie komunikatu, ponieważ reszta komunikatu jest przesyłana w postaci jawnej. Nawet w przypadku pełnego zaszyfrowania, co pokazano na powyższym rysunku, nie ma ochrony poufności, ponieważ każdy obserwator może odszyfrować komunikat, korzystając z klucza jawnego nadawcy.

Jest jednak możliwe jednoczesne zapewnienie uwierzytelniania i poufności przez podwójne zastosowanie systemu szyfrowania z kluczem jawnym:

Z = EKUb[EKRa(X)]

X = DKUa[DKRb(Z)]

W tym przypadku, jak poprzednio, opis rozpoczyna się od zaszyfrowania komunikatu za pomocą klucza prywatnego nadawcy. Otrzymuje się więc sygnaturę cyfrową. Następnie szyfruje się ponownie kluczem jawnym odbiorcy. Ostateczny tekst zaszyfrowany może odszyfrować tylko odbiorca, który jako jedyny posiada odpowiedni klucz prywatny. W ten sposób zapewniona zostaje poufność. Metoda ta ma jednak wadę: algorytm szyfrowania z kluczem jawnym, który jest skomplikowany, musi zostać wykonany cztery razy, a nie, jak przedtem, dwa razy na każdy akt komunikacji.

Zastosowania systemów szyfrowania z kluczem jawnym

Systemy szyfrowania z kluczem jawnym charakteryzują się zastosowaniem algorytmu kryptograficznego z dwoma kluczami: jednego prywatnego, drugiego dostępnego publicznie. W zależności od zastosowania nadawca używa do wykonania danego rodzaju funkcji kryptograficznej prywatnego klucza nadawcy lub jawnego klucza odbiorcy, lub też obydwu. Ogólniej możemy podzielić zastosowania systemów szyfrowania z kluczem jawnym na trzy grupy:


  • Szyfrowanie/deszyfrowanie: nadawca szyfruje komunikat za pomocą jawnego klucza odbiorcy.

  • Sygnatura cyfrowa: nadawca „sygnuje” komunikat swoim kluczem prywatnym. Sygnowanie odbywa się przez zastosowanie algorytmu kryptograficznego do komunikatu lub do niewielkiego bloku danych powiązanego w jakiś sposób z komunikatem.

  • Wymiana kluczy: obie strony współpracują przy wymianie klucza sesji. Możliwe jest kilka różnych metod, z udziałem klucza(-y) prywatnego(-ych) jednego lub obu partnerów.

Algorytm


Szyfrowanie /deszyfrowanie

Sygnatura cyfrowa


Wymiana kluczy

RSA

Tak: niepraktyczny dla dużych bloków

Tak

Tak

LUC

Tak: niepraktyczny dla dużych bloków

Tak

Tak

DSS

Nie

Tak

Nie

Diffiego-Helmana

Nie

Nie

Tak



Wymagania dotyczące systemów kryptograficznych

z kluczem jawnym

System przedstawiony na powyższych rysunkach opiera się na algorytmie kryptograficznym bazującym na dwóch powiązanych za sobą kluczach. Diffie i Hellman zaproponowali taki system, nie udowadniając, że takie algorytmy istnieją. Określili jednak warunki, które muszą być przez takie algorytmy spełnione:



  1. Strona B może łatwo na drodze obliczeń wygenerować parę (klucz jawny KU, klucz prywatny KR).

  2. Nadawca A, znając klucz jawny i wiadomość do szyfrowania, może łatwo na drodze obliczeń wygenerować odpowiedni tekst zaszyfrowany:

C = EKUb(M)

  1. Odbiorca B może łatwo na drodze obliczeń odszyfrować otrzymany tekst zaszyfrowany za pomocą klucza prywatnego i uzyskać oryginalny komunikat:

M = DKRb( C) = DKRb[EKUb(M)]

  1. Dla przeciwnika znającego klucz jawny KUb określenie klucza prywatnego KRb na drodze obliczeń jest niewykonalne.

  2. Dla przeciwnika znającego klucz jawny KUb i tekst zaszyfrowany C uzyskanie na drodze obliczeń wiadomości M jest niewykonalne.

Można dodać jeszcze szósty warunek. Jest on pożyteczny, lecz nie musi być koniecznie spełniony dla wszystkich zastosowań szyfrowania z kluczem jawnym:

  1. Funkcje szyfrowania i deszyfrowania mogą być zastosowane w dowolnym porządku:

M = EKUb[DKRb(M)]

Wymagania te są trudne do spełnienia, czego dowodzi fakt, że tylko jeden spełniający je algorytm uzyskał powszechną akceptację w czasie ostatniego ćwierćwiecza od czasu pojawienia się koncepcji szyfrowania z kluczem jawnym.

Zanim zastanowimy się, dlaczego warunki te tak trudno spełnić, najpierw przeformułujmy je. Sprowadzają się one do potrzeby funkcji jednokierunkowej - z bocznym wejściem. Funkcja jednokierunkowa to taka, która przekształca dziedzinę na przedział w taki sposób, ze każda wartość funkcji ma tylko jedną odwrotność, z tym, ze obliczenie funkcji jest łatwe, a obliczenie odwrotności niewykonalne:

Y = f(X) łatwe

X = f -1(Y) niewykonalne

Łatwe definiujemy jako problem możliwy do rozwiązania w czasie wielomianowym jako funkcji długości danych wejściowych. Jeśli dane wejściowe mają długość n bitów, czas obliczenia funkcji jest proporcjonalny do na, gdzie a jest ustalone (nie zależy od n). O takich algorytmach mówimy, że należą do klasy złożoności (czasowej) P. Termin niewykonalny jest dużo bardziej rozmyty. Mówimy, że zadanie jest niewykonalne, jeżeli wysiłek włożony w jego rozwiązanie rośnie szybciej niż czas wielomianowy jako funkcja rozmiaru danych wejściowych. Na przykład, jeżeli dane wejściowe mają długość n bitów, a czas obliczenia funkcji jest proporcjonalny do 2n, zadanie uważamy za niewykonalne. Niestety trudno określić, czy dany algorytm jest tak złożony. Ponadto tradycyjne podejście do złożoności obliczeniowej koncentruje się na złożonościach średnich lub złożonościach dla najgorszego przypadku. Miary te są bezwartościowe dla kryptografii, kt6ra wymaga, by odwrócenie funkcji było niewykonalne dla praktycznie każdych danych wejściowych, czego nie obejmuje ani przypadek średni, ani najgorszy. Krótkie wprowadzenie do niektórych z tych koncepcji znajduje się w dodatku 4B.

Przejdziemy teraz do definicji funkcji jednokierunkowej z bocznym wejściem (trapdoor one-way function), której obliczenie, tak jak w przypadku funkcji jednokierunkowej, jest łatwe w jednym kierunku, a niewykonalne w drugim, chyba że przy znajomości pewnych dodatkowych informacji. Przy znajomości dodatkowych informacji można obliczyć odwrotność w czasie wielomianowym. Możemy to streścić następująco: funkcja jednokierunkowa z bocznym wejściem to rodzina odwracalnych funkcji fk, takich, że:

Y = fk(X) łatwe przy znajomości k i X

X = fk-1 (Y) łatwe przy znajomości k i X

X = fk-1(Y) niewykonalne, gdy znamy Y, a nie znamy k

Stworzenie praktycznego systemu szyfrowania z kluczem jawnym polega więc na opracowaniu odpowiedniej funkcji jednokierunkowej z bocznym wejściem.



Kryptoanaliza systemów szyfrowania z kluczem jawnym

Tak jak system szyfrowania konwencjonalnego, system szyfrowania z kluczem jawnym jest zagrożony atakiem metodą brutalną. Środek zaradczy jest taki sam: należy używać długich kluczy. Mamy tu jednak sytuację typu "coś za coś". Systemy szyfrowania z kluczem jawnym opierają się na stosowaniu pewnego rodzaju odwracalnych funkcji matematycznych. Złożoność obliczania tych funkcji nie musi zależeć liniowo od liczby bitów klucza, lecz rosnąć szybciej. Rozmiar klucza musi więc być wystarczająco duży, by atak metodą brutalną był niepraktyczny oraz odpowiednio mały dla praktycznego szyfrowania i deszyfrowania. Zaproponowane dotąd rozmiary kluczy faktycznie powodują, że ataki metodą brutalną są niepraktyczne, lecz szybkości szyfrowania/deszyfrowania za pomocą tych kluczy są dużo za małe dla ogólnych zastosowań. Za to, jak wspomniano wcześniej, zastosowanie szyfrowania z kluczem jawnym ogranicza się do zarządzania kluczami i sygnatur.

Inną formą ataku są próby obliczenia klucza prywatnego na podstawie klucza jawnego. Do tej pory nie udowodniono matematycznie, ze dla konkretnego algorytmu szyfrowania z kluczem jawnym ta forma ataku jest niewykonalna. Dlatego każdy algorytm, w tym powszechnie stosowany algorytm RSA, jest podejrzany. Historia kryptoanalizy pokazuje, ze problem, który wygląda na nierozwiązalny, może okazać się rozwiązalny, jeśli rozważymy go z zupełnie innej perspektywy.

Istnieje forma ataku właściwa systemom szyfrowania z kluczem jawnym. Jest to, w skrócie, atak prawdopodobnego komunikatu. Załóżmy, na przykład, że ma zostać wysłany komunikat, którego treścią jest tylko 5ó-bitowy klucz DES. Przeciwnik może zaszyfrować wszystkie możliwe klucze za pomocą klucza jawnego i rozszyfrować jakikolwiek komunikat przez porównanie go z przesłanym tekstem zaszyfrowanym. W ten sposób niezależnie od rozmiaru klucza łamanie sprowadza się do ataku metodą brutalną na 5ó-bitowy klucz. Takiemu atakowi można zapobiec przez dodanie losowych bitów do tego typu prostych komunikatów.



Algorytm plecakowy

Dla systemów szyfrowania z kluczem jawnym zaproponowano wiele algorytmów. Wiele z nich, które z początku wyglądały obiecująco, okazało się możliwe do złamania. Pouczające będzie omówienie najważniejszego z takich systemów.

D
o tej pory najsławniejszy z pokonanych rywali to algorytm plecakowy, który opracowali Ralph Merkle [MERK78]. Problem plecakowy polega na określaniu, które przedmioty znajdują się w pojemniku, na przykład w plecaku. Prosty przykład przedstawiono na kolejnym rysunku. W plecaku znajduje się podzbiór przedmiotów o wyszczególnionej wadze w gramach. Zadanie polega na określeniu, które przedmioty znajdują się w plecaku, przy danej wadze wypełnionego plecaka, 1156 gramów.

Opisane tu zadanie jest dość proste, lecz staje się niewykonalne obliczeniowo, jeżeli mamy danych np. 100 przedmiotów, a nie 10, jak w tym przykładzie. Merkle pokazał (1), jak na podstawie problemu plecakowego zbudować system szyfrowania i deszyfrowania oraz (2) jak wbudować do niego tajną informację, która umożliwiłaby szybkie rozwiązanie tego problemu.

Na początek opiszmy ogólną metodę szyfrowania/deszyfrowania opartą na problemie plecakowym. Powiedzmy, że chcemy wysyłać komunikaty w blokach n-bitowych. Zdefiniujmy:

wektor ładunku a=(a1, a2, ..., an) ai liczba calkowita

blok tekstu jawnego x=(x1, x2, ..., xn) xi liczba binarna

odpowiadający tekst zaszyfrowany S=a . x=

Niech wektor ładunku a będzie listą elementów, które mogą potencjalnie zostać włożone do plecaka, gdzie każdy element jest równy wadze odpowiedniego elementu ładunku. Niech x będzie wyborem elementów wektora ładunku, gdzie xi= 1 dla każdego elementu ładunku ai, wybranego do włożenia do plecaka. Wtedy produkt wektorowy S jest po prostu sumą wybranych obiektów, co stanowi wagę zawartości plecaka.

Przy szyfrowaniu stosujemy a jako klucz jawny. Strona zamierzająca wysłać komunikat x wykonuje S=a . x i przesyła S. Przy deszyfrowaniu strona, która otrzymała komunikat, musi uzyskać x przy danym S i a.

Pierwszy warunek jest następujący: dla każdej wartości S jest tylko jedna odwrotność. Na przykład rozważmy:

a=(1, 3, 2, 5)

S=3


Taki problem ma dwa rozwiązania: x= 1010 i x=0100. Elementy a muszą więc być dobrane tak, żeby każda kombinacja elementów dała jedną wartość.

Drugie wymaganie jest następujące: deszyfrowanie jest ogólnie trudne, lecz staje się łatwe przy dostępie do specjalnych informacji. Oczywiście, dla dużych wartości n, problem plecakowy jest ogólnie trudny. Jednak w pewnych okolicznościach jest on łatwy do rozwiązania. Postawmy następujący warunek: każdy element a ma być większy niż suma poprzedzających go elementów:



l Jest to wektor szybko rosnący. W tym przypadku rozwiązanie jest łatwe. Na przykład, rozważmy wektor



a' = ( 171, 197, 459, I 191, 2410)

który spełnia warunek. Załóżmy, że mamy S'=a' . x'=3798. Ponieważ 3798>2410, trzeba włączyć a5 (x5 = 1 ), ponieważ bez a5 inne elementy nie wystarczyłyby do 3798.

Zważmy, ze 3798-2410= 1388. Ponieważ liczba ta jest większa niż 1191, musimy także włączyć a4 (x4=1). Postępując dalej tą metodą znajdziemy x3=0, x2=1 i xi=0. Merkle znalazł sposób połączenia łatwego "szybko rosnącego" problemu plecakowego z trudnym ogólnym problemem plecakowym.

Przypuśćmy, że losowo wybraliśmy łatwy wektor plecakowy a', o n elementach. Wybierzmy także dwie liczby całkowite m i w takie, ze m jest większe od sumy elementów a', oraz m i w są względnie pierwsze. To jest:



nwd (w, m) = 1

Zbudujemy teraz trudny wektor plecakowy a przez pomnożenie łatwego wektora a' przez w modulo m.

a = wa' mod m

Wektor a nie będzie szybko rosnący, można więc stosować go do konstruowania trudnych problemów plecakowych. Znajomość w i m umożliwia jednak konwersję tego trudnego problemu plecakowego do postaci łatwej. Aby się o tym przekonać, zauważmy najpierw, że ponieważ w i m są względnie pierwsze, istnieje tylko jedno w- 1 modulo m. Więc:



w –1a = a' mod m

Możemy teraz zbudować system plecakowy. Jego składniki będą następujące:



a' - wektor szybko rosnący (prywatny, wybrany)

m - liczba całkowita większa od (prywatna, wybrana)

w - liczba całkowita względnie pierwsza z m (prywatna, wybrana)

w -1 - odwrotność w, modulo m (prywatna, obliczona)

a - równy w a' mod m (jawny, obliczony)

Klucz prywatny składa się z trojki {w -1, m, a'}, a klucz jawny stanowi wartość a. Przypuśćmy, że użytkownik A opublikował swój klucz jawny a i że użytkownik B zamierza wysłać komunikat x do A. B oblicza więc sumę

S = a . x

Generowanie klucza

Łatwy problem plecakowy, a'

1

3

7

13

26

65

119

267

Czynnik w=467 Dzielnik m=523 w –1= 28(mod 523)

Trudny problem plecakowy, a

467

355

131

318

113

21

135

215

Klucz jawny, KU=a Klucz prywatny, KR={w-1, m, a'}

Szyfrowanie

Tekst jawny = 01001011

Tekst zaszyfrowany = 0*467+1*355+0*131+0*318+1*113+0*21+1*135+1*215 = 818

Deszyfrowanie

818*w-1 = 818*28 = 415(mod 523)

415>=267  x8=1

415-267=148 >=119  x7=1

148-119=29<65  x6=0

29>=26  x5=1

29-26=3<13  x4=0

3<7  x3=0

3>=3  x2=1

3-3=0<1  x1=0

Tekst jawny = x1x2x3x4x5x6x7x8 = 01001011

Określenie x przy danym S i a jest trudne, więc transmisja jest bezpieczna. Użytkownik A może jednak łatwo odszyfrować komunikat. Niech S'=w-1 S mod m. Mamy:

S=a . x=wa'·x

S'=w-1S mod m

=w-1,wa'·x mod m

= a' . x

W ten sposób sprowadziliśmy trudny problem znajdowania x przy danym S i a do łatwego problemu znajdowania x przy danym S' i a'.

W przykładzie omówionym powyżej przy danym komunikacie w postaci jawnej x=01001011 użytkownik B oblicza a . x=818. Użytkownik A najpierw oblicza S'=w-1 S mod m=415, a następnie rozwiązuje łatwy problem plecakowy i uzyskuje 01001011.



Algorytm plecakowy ogłoszono jako system niemożliwy do złamania. Merkle, pewny siebie, lecz niebogaty, obiecał 100 dolarów nagrody każdemu, komu uda się złamać algorytm. Minęły cztery lata i Adi Shamir, jeden z wynalazców RSA, złamał system i otrzymał 100 dolarów.

Lecz Merkle nie rezygnował. Zauważył, że trudny problem plecakowy można jeszcze utrudnić, stosując wielokrotne przekształcenia (w1, m1), (w2, m1) itd. Całkowite otrzymane w ten sposób przekształcenie nie jest odpowiednikiem żadnego pojedynczego przekształcenia (w, m). Wiedząc o tym, Merkle podwyższył stawką do 1000 dolarów dla każdego, kto umiałby złamać problem z wieloma iteracjami. Tym razem musiał czekać tylko dwa lata na wypłacenie nagrody. Odtąd nie brano już poważnie pod uwagę "plecaków" jako podstawy dla systemów kryptografii z kluczem jawnym.


©absta.pl 2016
wyślij wiadomość

    Strona główna