50427 Str073

142    4. KJimbd publtone

Za pomocą następującego algorytmu rozwiązuje się w czasie wielomianowym problem pakowania plecaka dla supcrrosnącego ciągu {u/} i liczby V\

1.    Niech W = V i niech jmk,

2.    Począwszy od , i zmniejszając indeks r., przyjmujemy c, = 0 tak długo, aż napotkamy pierwszy indeks i nazwijmy go r'₀ - taki, że v_t ś W. Podstawiamy 6( = 1.

3.    Zastępujemy W przez W - u_ło, podstawiamy j - i₀ i jeśli W > 0, to wracamy do kroku 2.

4.    Jeśli W = 0, to mamy rozwiązanie. Jeśli W > 0 i wszystkie pozostałe v, są większe od IV, to nic istnieje rozwiązanie n — (e*_ _x ...e₀)₂ naszego problemu.

Zauważmy, że rozwiązanie (o ile w ogóle istnieje) jest jedyne.

Przykład 2. Niech liczby p, będą takie jak w przykładzie 1 i niech V = 24. Wtedy, przeglądając nasz ciąg {2, 3,7,15,31} od prawej do lewej, stwierdzimy, że = 0, e₃ = 1 (iw tej chwili zastępujemy 24 przez 24 — 15 = 9), e₂ = 1 (i teraz zastępujemy 9 przez 9 - 7 = 2),    = 0, e₀ = 1. Zatem n = (01101)₂ =

= 13.

Opiszemy teraz, jak problem pakowania plecaka można przekształcić w system kryptograficzny (zwany też systemem Merklego-Hellmana). Najpierw założymy, że odpowiednikami liczbowymi jednostek tekstu otwartego będą k-bitowe liczby całkowite P. Jeśli na przykład używamy pojedynczych liter alfabetu 26-literowego, to każda litera odpowiada w zwykły sposób jakiejś liczbie pięciobitowęj od 0 = (00000)₂ do 25 = (11001)₂.

Następnie każdy użytkownik wybiera superrosnący ciąg k-wyrazowy

k—1

{a₀, ..., liczbę m większą niż £ v_t oraz liczbę o, względnie pierwszą

1=0

z m i taką, że 0 < a < m. Ten wybór jest dokonywany w pewien losowy sposób. Możemy na przykład wybrać dowolny ciąg k + 1 liczb całkowitych dodatnich z,-, i = 0,1,..., k, mniejszych od pewnej dogodnie dobranej liczby; wtedy przyjmujemy v₀ = z₀, v_i — z_t +    + u_l_₂ + ... + v₀ dla z = 1,..., k — 1 oraz

k-t

jako m bierzemy liczbę z_k + J] v_t. Następnie wybieramy losową liczbę a₀<m 1=0

i jako a bierzemy najmniejszą liczbę >a₀ względnie pierwszą z m. Wtedy obliczamy b = a — 1 mod m (tzn. b jest najmniejszą liczbą całkowitą dodatnią taką, że ab = 1 (mod ni)) oraz obliczamy wyrazy ciągu {wj określone wzorem w, = at>i mod m (tzn.    jest resztą z dzielenia av_t przez ni). Każdy użytkownik

trzyma w tajemnicy swoje liczby v_lt m, a i b oraz publikuje ciąg liczb {w,}. Zatem kluczem szyfrującym jest K_R = {w₀,..., w_fc__l}. Kluczem rozszyfrowującym jest para K_D = (b, m) (która wraz z kluczem szyfrującym umożliwia odtworzenie ciągu {u₀,..., c_k_,}).

Ktoś, kto chce wysłać ^-bitowy tekst otwarty P ~ (e_t^ j *1-2 "**1*0)1 do użytkownika używającego klucza szyfrującego {w,}, oblicza C=f(F)~

k-1

-s V 6j w, i wysyła tę liczbę.

1*0    tHH

Aby odczytać wiadomość, adresat najpierw oblicza resztę V z dzielenia bC przez m. Ponieważ bC = T,R_ibw_l a (mod mf (bowiem bw_t = bao_{ s p/ (mod m)), więc F = Xf:,v,. (Korzystamy tu z tego, źe V < m oraz •< ^ u, < m, by przystawanie modulo m zamienić na równość). Teraz może zastosować podany wyżej algorytm rozwiązywania łatwego problemu pakowania plecaka, by znaleźć jedyne rozwiązanie (e_k._l ...e₀)₂ = P zadania polegającego na znalezieniu podzbioru zbioru liczb {o,}, którego sumą jest V. W ten sposób odtwarza wiadomość P.

Zauważmy, że inne osoby, znające tylko {w,}, mają do czynienia z problemem pakowania plecaka C = który nie jest łatwym problemem pakowania plecaka, gdyż własność „supermonotoniczności” ciągu [v_{] została naruszona, gdy liczby v_t zastąpiliśmy resztami z dzielenia av, ptm m. Zatem ten sam algorytm nie może już być użyty i, na pierwszy rzut oka, osoba nie upoważniona ma do czynienia ze znacznie poważniejszym problemem. Powrócimy później do tej kwestii.

Przykład 3. Przypuśćmy, że jednostkami tekstu otwartego są pojedyncze litery mające odpowiedniki liczbowe od (00000)₂ do (11001)₂, tak jak powyżej. Przyjmijmy, że naszym tajnym kluczem rozszyfrowującym jest ciąg superros* nący z przykładu 1. Wybierzmy m = 61, a = 17; wtedy b = 18 i kluczem szyfrującym jest ciąg (34, 51, 58, 11, 39). Aby wysłać wiadomość „WHY”, nasz korespondent kolejno oblicza: „W” = (10110)₂>-*51 + 58 + 39 = 148, „H” = = (00111)₂t-^34 + 51 + 58 = 143, „Y” = (11000)₂h>11 + 39 = 50. Aby odczytać wiadomość 148,143,50, najpierw mnożymy przez 18 modulo 61, otrzymując 41, 12, 46. Postępując tak, jak w przykładzie 2 dla F = 41, F= 12 i F=46, odtwarzamy tekst otwarty (10110)₂, (00111)₂, (11000)₂.

Oczywiście, jak zwykle system, w którym używa się pojedynczych liter jako jednostek tekstu i tak małej wartości k, nie jest bezpieczny; przykład 3 tylko wyjaśnia sposób działania systemu.

Przez pewien czas wydawało się, że systemy oparte na problemie pakowania plecaka oferują duże możliwości. Ponieważ problem pakowania plecaka jest jednym ze znanych bardzo trudnych problemów (problemy NP-zupełne), zdawało się, że taki system będzie bezpieczny.

Jednakże w tym rozumowaniu tkwił błąd. Ten rodzaj problemu pakowania plecaka C = który musi być rozwiązany, nie jest wprawdzie łatwym problemem pakowania plecaka, ale jednak jest bardzo szczególnym problemem, mianowicie powstaje on z łatwego problemu pakowania plecaka przez prostą transformację: pomnożenie wszystkich liczb przez a i zredukowanie modulo m. W 1982 roku Shamir znalazł algorytm rozwiązujący taki