68700 Str075

146    4 Klucze publiczne

4.    Przypuśćmy, źc jednostkami tekstu otwartego są pojedyncze litery zwy. kłego 26-lilerowcgo alfabetu A-Z z odpowiednikami liczbowymi 0-25. Otrzymaliśmy ciąg jednostek kryptogramu 14, 25, 89, 3, 65, 24, 3, 49, 89, 24, 41, 25, 68, 41, 71. Publicznym kluczem szyfrującym jest ciąg liczb {57, 14, 3, 24, 8), a tajnym kluczem rozszyfrowującym jest para liczb b « 23, m = 61.

(a)    Spróbuj odczytać wiadomość bez użycia klucza rozszyfrowującego; sprawdź wynik, stosując klucz rozszyfrowujący i algorytm dla łatwego problemu pakowania plecaka.

(b)    Wyślij wiadomość TENFOUR, korzystając z podanego publicznego klucza.

5.    Przypuśćmy, że jednostkami tekstu otwartego są trigramy 32-literowego alfabetu, w którym odpowiednikami liczbowymi liter A-Z są liczby 0-25, odstęp as 26, ? = 27, ! = 28, . = 29, ’ = 30, $ = 31. Otrzymujesz ciąg następujących jednostek tekstu zaszyfrowanego: 152472, 116116, 68546, 165420, 168261. Publicznym kluczem jest ciąg liczb {24038, 29756, 34172, 34286, 38334,1824,18255,19723,143,17146,35366,11204, 32395,12958, 6479}, a tajnym kluczem rozszyfrowującym jest para liczb b — 30966, m — 47107. Odczytaj wiadomość.

6.    Przypuśćmy, że jednostkami tekstu otwartego są digramy 32-literowego alfabetu z ćwiczenia 5. Otrzymujesz ciąg jednostek kryptogramu 33219, 7067, 18127, 43099, 37953, zaszyfrowanego za pomocą systemu opartego na iterowanym problemie pakowania plecaka z publicznym kluczem {23161, 6726, 4326, 16848, 21805, 11073, 120, 15708, 2608, 341}. Tajnym kluczem rozszyfrowującym jest: b_v = 533, m_L = 2617, b₂ — 10175, m₂ = 27103. Odczytaj wiadomość.

Bibliografia

1.    Brickcjl E.t Breaking iterated knapsacks. Aduances in Cryptology - Crypto '84, Springer-Vcrlag 1985, s. 342-358.

2.    BrickeU E., Odlyzko A.: Cryptanalysis: A survey of rccent results. Proc. IEEE, 1988, 76, s. 578-593.

3.    Chor B., RWesl R.: A knapsack-lype public key cryptosyslem bascd on arilhmetjc in finite lields. Adoances in Cryptology - Crypto ‘84, Springer-Verlag 1985, s. 54-65, wersja poprawiona w IEEE Transąclions on Information Theory IT-34, 1988, s. 901-909.

4.    Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Comp-leteness. W. H. Freeman 1979.

5.    Goodman R.M.F., McAuley AJ.: A new trapdoor knapsack public key cryptosyslem. Advan-ces in Cryptography, Proceedings of Eurocrypt 84, Springer 1985, s. 150-158.

6.    Hellman M.E.: The mathemalics of public-key cryptography. Scienilfic American, 1979, 241, 6.146-157.

7.    Hellman M.E., Merkle R.C.: Hiding informalion and signalures in trapdoor knapsack. IEEE Transactions on Information Theory IT-24, 1978, s. 525-530.

8.    Odlyzko A.: The risc and fali of knapsack eryptosystems. Cryptology and Computallonal Num-ber Theory, Proc. Symp. Appl. Math., 1990, 42, s. 75-88.

Schnorr C.: Efficient idcnlificalion and signatows for wnari carris. Adnancu in Cryptolopy - Crypto W# Springer-Verlag 1990, i, 239-251,

10    Shamir A.: A polynomial limę algorithm for breaking Ute baśc MerUe-Hedman eryptosyt-tent- Proc. 2ird Annual Symposium on ihe Poundations of Computer Science, 1982, •. 145-152.

11    yan Oorschot P.: A comparlson of praclicsii pobfic-key cryptoayitemi baied on integer fac-lori/ation and discrelc logarilhms. W: Contmpornry Cryptology: The Science of Information lnicy,rity. Red. O. Simmons, IEEE Press 1992, s. 299-322.

4.5. Protokoły o zerowej wiedzy i przekazy nierozróźnialne

„Zerowa wiedza” to nazwa pojęcia kryptograficznego, wprowadzonego na początku lat osiemdziesiątych w związku z następującym problemem. Przypuśćmy, że ktoś chce udowodnić, iż wie, jak coś zrobić - znaleźć rozwiązanie równania, udowodnić twierdzenie, rozwiązać łamigłówkę - nie przekazując jednocześnie żadnej wiedzy na temat swojego dowodu lub rozwiązania. Czy może to być zrobione? Czy możemy przekonać kogoś, że mamy rozwiązanie, nie ujawniając go? Jest dość zaskakujące, że w wielu sytuacjach można to zrobić.

Osoba „uzasadniająca”, która będzie się nazywać Urszula, jest to osoba znająca rozwiązanie; „sprawdzającego” Stefana musi ona w końcu przekonać, że zna rozwiązanie, tak jednak, by nie miał on najmniejszego pojęcia o tym, jakie jest to rozwiązanie^.

W tym podrozdziale przedstawimy najpierw prosty, obrazowy przykład interakcyjnego dowodu o zerowej wiedzy (tzn. wymagającego dialogu pomiędzy Urszulą i Stefanem). Ten przykład będzie dotyczył kolorowania map i nie będzie się w nim korzystać z teorii liczb. Następnie podamy drugi przykład, w którym pokażemy, w jaki sposób udowodnić, że znamy logarytm dyskretny, nie dając jednocześnie sprawdzającemu wskazówek, ile ten logarytm dyskretny wynosi. Potem zajmiemy się pojęciem „przekazów nierozróżnialnych” (ang. oblmous transfer), za pomocą których można skonstruować nieinterakcyjny dowód o zerowej wiedzy. Wreszcie wykorzystamy przekazy nierozróźnialne do dowodów faktoryzacji, mających zerową wiedzę.

Kolorowanie map. Oto nasz pierwszy przykład. Wiadomo, że każda mapa na płaszczyźnie może być pokolorowana za pomocą czterech kolorów. Niektóre mapy można pokolorować trzema kolorami, innych nie można. Przypuśćmy, że Urszula ma bardzo skomplikowaną mapę, którą po wielkim wysiłku udało się jej pokolorować trzema kolorami (czerwonym, niebieskim i zielonym). Jak może ona przekonać Stefana, że rzeczywiście to zrobiła, nie dając mu jednocześnie żadnej wskazówki, jak można to zrobić?

¹¹ W literaturze anglojęzycznej tradycyjnie używa się określeń: Provcr - uzasadniający i Verificr - sprawdzający, stosując skróty P i V tub imiona rozpoczynające się od tych liter. Stąd w oryginale imiona Plcara i Vivalcs, a tutaj Urszula i Stefan (przyp. tłum.).