17701 Str060 (2)

116    4 Kludf* publiczne

okresowo wymieniają klucze, stosując do tego wolniejsze systemy z publicz. nym kluczem; wielkie iloAci informacji są przesyłane szybko za pomocą szyb* szych, dawniejszych metod.

Szyfrowanie probabilistyczne. Większość systemów kryptograficznych stosowanych przy przesyłaniu danych i opartych na teorii liczb, to systemy deterministyczne. tzn. takie, w których dany tekst otwarty będzie za każdym razem zaszyfrowany tak samo, dając ten sam kryptogram. Jednakże system deterministyczny ma dwie wady: (1) jeśli osoba trzecia wic, że teksty otwarte pochodzą z pewnego małego zbioru (np. wiadomością jest albo „tak”, albo „nic"), to może ona po prostu zaszyfrować wszystkie możliwości po to, by stwierdzić, która z nich jest daną tajną wiadomością; oraz (2) wydaje się, że będzie bardzo trudno udowodnić coś o bezpieczeństwie systemu, jeśli szyfrowanie jest deterministyczne. Z tych powodów wprowadzono szyfrowanie probabilistyczne. Nie będziemy go dalej omawiać ani podawać przykładów w tej książce. Więcej informacji można znaleźć w podstawowych pracach na ten temat, napisanych przez Goldwassera i Micaliego (Proc. 14th ACM Symp. Theory of Computing, 1982, s. 365-377 oraz/. Comput. System Sci. 1984,28, s. 270-299),

Ćwiczenia

1.    Przypuśćmy, że m użytkowników chce porozumiewać się ze sobą, korzystając z klasycznego systemu kryptograficznego. Każdy użytkownik chce móc porozumiewać się z każdym innym w taki sposób, by pozostali m — 2 użytkownicy nie mogli dowiedzieć się o treści wymienianych wiadomości. Ile różnych kluczy K = (K_E, K_D) trzeba użyć? Ile trzeba kluczy, jeśli użytkownicy korzystają z systemu z publicznym kluczem? Ile różnych kluczy potrzeba dla każdego typu systemu, jeśli m = 1000?

2.    Przypuśćmy, że w sieci grupującej inwestorów i maklerów używa się systemu z publicznym kluczem. Inwestorzy obawiają się, że ich maklerzy mogą kupować akcje bez potwierdzania tożsamości (po to, by pobierać prowizję) i gdy pieniądze inwestora zostaną utracone, twierdzić, że otrzymali odpowiednie instrukcje (pokazując jako dowód zaszyfrowane polecenia zakupu akcji i twierdząc, że pochodzą one od danego inwestora). Maklerzy natomiast obawiają się, że gdy zakupią akcje wskazane przez inwestora i stracą one na wartości, inwestor będzie twierdził, że nigdy nie wysłał takiego polecenia i że zostało ono wysłane przez kogoś innego lub przez samego maklera. Wyjaśnij, w jaki sposób ten problem może być rozwiązany za pomocą systemu z publicznym kluczem tak, by istniały dowody wskazujące, kto jest winny rujnujących inwestycji i straty pieniędzy wtedy, kiedy d wszyscy podejrzliwi ludzie znajdą się w sądzie, wzajemnie się oskarżając. (Załóż, że jeśli dojdzie do sprawy sądowej pomiędzy inwestorem A i maklerem B, sędzia otrzyma całą potrzebną dokumentację dotyczącą szyfrowania i rozszyfrowywania - klucze K_A = (K_{E A}, K_{D A}) i K_g =

= (Kr s* K_{d b}) oraz oprogramowanie potrzebne do szyfrowania i rozszyfrowywania.)

3.    Przypuśćmy, że dwa kraje A i B chcą osiągnąć porozumienie dotyczące ograniczenia podziemnych eksplozji jądrowych. Żadne państwo nie ufa drugiemu, i nie bez powodu. Jednakże muszą się one zgodzić na zainstalowanie urządzeń kontrolnych w różnych miejscach obu krajów. Każde urządzenie kontrolne składa się z precyzyjnych sejsmografów, małego komputera przetwarzającego odczyty sejsmografów i generującego komunikat o nich oraz nadajnika radiowego. Wyjaśnij, w jaki sposób można użyć systemu kryptograficznego z publicznym kluczem, aby spełnić następujące (na pierwszy rzut oka sprzeczne ze sobą) warunki;

a.    Państwo A domaga się tekstów jawnych wszystkich komunikatów wysyłanych z jego terytorium po to, by mieć pewność, że państwo B nie wykorzystuje urządzeń kontrolnych do celów szpiegowskich.

b.    Państwo B domaga się, by państwo A nie mogło podrobić komunikatu nadanego przez urządzenie kontrolne zainstalowane na jego terytorium (tzn. komunikatu stwierdzającego, że wszystko jest w porządku, podczas gdy w rzeczywistości sejsmograf wykrył naruszenie traktatu).

c.    Państwo A domaga się, by w wypadku gdy państwo B niezgodnie z prawdą ogłosi, że otrzymało ze swego urządzenia kontrolnego komunikat o naruszeniu postanowień traktatu, każde zainteresowane trzecie państwo będzie mogło stwierdzić, że taki komunikat w rzeczywistości nie został wysłany.

d.    To samo co w przypadkach a-c, ale z zamienioną rolą obu państw.

e.    Urządzenia kontrolne obu państw mają być identyczne i muszą być zaprojektowane wspólnie przez naukowców z obu państw.

4.    Celem tego ćwiczenia jest zaprojektowanie metody rzucania monetą na odległość za pomocą dowolnej funkcji progowej o takiej własności, że każdy element przeciwdziedziny jest obrazem dokładnie dwóch elementów dziedziny. Przypuśćmy na przykład, że dwóch graczy z dwóch różnych stron świata gra ze sobą w szachy korespondencyjnie lub przez telefon i chcą oni w uczciwy sposób zdecydować, który z nich zagra białymi. Lub też przypuśćmy, że w czasie przygotowań do międzypaństwowego meczu hokejowego przedstawiciele obu drużyn decydują się na rzucanie monetą po to, by wybrać gospodarza meczu, ale nie chcą przedtem organizować spotkania (czy zaufać komuś innemu), by „rzucić monetą".

System funkcji progowych 2-1 jest to algorytm, w którym, mając dany odpowiedni klucz K_E, konstruuje się funkcję/: 9 -»V taką, że każdy element c przeciwdziedziny /ma dokładnie dwa przedwobrazy p₂,p₂^s^ takie, że f(p,) — c, oraz algorytm, który mając dany klucz K_D, „odwrotny do K_e \ znajduje oba przedwobrazy dowolnego elementu c przeciwdziedziny funkcji / Zakładamy tu, że znalezienie K_D jest praktycznie niemożliwe za pomocą obliczeń komputerowych, jeśli znamy tylko K_E. Zauważmy, że dla danego elementu możemy znaleźć drugi element p₂