A jednak się da!

Bez zobowiązań o zobowiązaniach (AJSD II)

Zapewne każdy z czytających te słowa grał kiedyś w marynarza, ale na wypadek gdyby któryś z Czytelników miał smutne dzieciństwo pozbawione tej gry, pokrótce wyjaśnię zasady: na ustalony sygnał każdy z uczestników przedstawia wybraną przez siebie liczbę (najczęściej przy użyciu własnych palców). Następnie rozpoczyna się (cykliczne) wyliczanie uczestników aż do sumy przedstawionych przez nich liczb (oczywiście, należy zawczasu ustalić, od kogo rozpoczyna się wyliczanka). Osoba, na której zakończy się wyliczanie, jest "zwycięzcą" (wziętym w cudzysłów, gdyż "nagrodą" może być, na przykład, zmywanie naczyń)...

Niestety, przedstawiona procedura ma pewną techniczną trudność, która była źródłem niejednej podwórkowej kłótni - jeśli któryś z uczestników opóźni się z przedstawieniem swojej liczby, może zostać oskarżony o celową zwłokę, która przy pewnej sprawności rachunkowej mogłaby zostać wykorzystana w celu osiągnięcia z góry założonego wyniku gry. Aby tego uniknąć, uczestnicy mogliby zapisywać wybrane przez siebie liczby na kartkach, które wrzucane byłyby do jednego worka. Co jednak począć w sytuacji, kiedy taka operacja nie jest możliwa, na przykład gdybyśmy chcieli zagrać w marynarza przez telefon (lub raczej, ze względu na potencjalnie dużą liczbę uczestników, gdybyśmy chcieli to uczynić, prowadząc grupową konwersację na pewnym popularnym serwisie społecznościowym)? Okazuje się, że wciąż jest to możliwe; wystarczy użyć kryptologicznego narzędzia zwanego zobowiązaniem.

Kryptologiczne zobowiązanie jest "skrzynką", do otwarcia której potrzebny jest klucz. Najczęściej zamykamy w niej wiadomość, wysyłamy całość nadawcy, a po pewnym czasie dosyłamy mu klucz (gdy uznamy, że może on już zapoznać się z zawartością). Dokonujemy jednak w ten sposób pewnego zobowiązania - nie mamy do dyspozycji kilku różnych kluczy o tej własności, że w zależności od użytego klucza skrzynka odsłoni adresatowi inną zawartość.

Opisana przed chwilą skrzynka reprezentowana jest przez funkcje Commit i Open takie, że jeśli Aldona chce "zobowiązać się" Bogumiłowi do wiadomości $m,$ oblicza $(c, | k) = Commit(m)$ i wysyła mu $c. |$ Aby odkryć zobowiązanie, musi ona jeszcze dosłać $k,$ dzięki czemu Bogumił oblicza $|m$ Aby protokół był poprawny, muszą być spełnione następujące warunki:

(i): $Open(Commit(m))$ (dzięki czemu Bogumił odczytuje $m$ po dosłaniu klucza),
(ii): sama znajomość $c$ nie dostarcza żadnej informacji o $m,$
(iii): Aldona nie może skonstruować takich dwóch kluczy $k1,k2,$ że $Open(c, k1)≠ Open(c, k2).$

Podobnie jak w poprzednim odcinku sagi, możemy dostrzec pewien szkopuł w przedstawionych warunkach. Podpunkty (ii) i (iii) nie mogą być bowiem spełnione jednocześnie. Istotnie, z punktu (iii) wynika, że istnieje tylko jedna wartość klucza $k,$ dla której $Open(c, k)$ jest sensowną wiadomością - Bogumił po odebraniu wiadomości $|c$ mógłby zatem przeglądać wszystkie możliwe wartości kluczy, aż znajdzie ten właściwy. Innymi słowy, $|c$ jednoznacznie definiuje $m,$ co przeczy podpunktowi (ii). Musimy zatem zgodzić się na pewien kompromis - któryś ze wspomnianych warunków będzie naruszony, jednak możemy zadbać o to, by realizacja tego naruszenia była bardzo trudna obliczeniowo. W świetle tego spostrzeżenia kryptologiczne zobowiązania możemy podzielić na bezwarunkowo kryjące i bezwarunkowo wiążące.

Zobowiązania bezwarunkowo kryjące naruszają podpunkt (iii), zatem znajomość $c$ nie mówi zupełnie nic o $|m,$ a Aldona teoretycznie mogłaby znaleźć dwa klucze prowadzące do różnych odczytów ze skrzynki, choć będzie to dla niej bardzo trudne obliczeniowo. Przedstawimy przykład protokołu, który realizuje te założenia. Zauważmy najpierw, że wystarczy ograniczyć potencjalne wiadomości do 0 lub 1. Rzeczywiście, dowolnie skomplikowaną informację możemy rozbić na bity i zobowiązać się do każdego z nich z osobna. Aldona wybiera dużą liczbę pierwszą $p |$ oraz $|g$ niepodzielne przez $p,$ po czym wysyła Bogumiłowi $p$ i $g.$ Bogumił wybiera dowolnie $x < p$ i odsyła Aldonie $|s = (gx mod p).$ Aby zobowiązać się do bitu $b,$ Aldona wybiera dowolnie klucz $k < p$ i wysyła Bogumiłowi $b k |c = (s g mod p).$ Widzimy, że liczba otrzymana przez Bogumiła to $|(gbx+k mod p),$ zatem bez znajomości $|k$ nie ma on bladego pojęcia o $|b.$ Kiedy jednak Aldona dośle $|k,$ sprawa jest dla Bogumiła jasna, wystarczy bowiem, że obliczy $(gk mod p)$ i $|(gx+k mod p)$ i sprawdzi, która z tych liczb jest równa $|c.$ Zastanówmy się teraz, w jaki sposób Aldona mogłaby "oszukać system". Byłoby to równoznaczne ze znalezieniem dwóch kluczy $k1,k2,$ przy których Bogumił odczytałby różne wartości $|b.$ Spełniona byłaby zatem równość

gk1 = sgk2 (mod p), czyli gk1− k2 = s ( mod p).

Oznaczałoby to, że Aldona jest w stanie na podstawie $|g,s$ wybranych przez Bogumiła znaleźć $|l$ spełniające $gl = s (mod p).$ Rozwiązałaby zatem problem logarytmu dyskretnego, o którym sądzimy, że jest trudny obliczeniowo. Wierzymy zatem, że nie byłaby w stanie dostarczyć dwóch różnych kluczy do wysłanej Bogumiłowi skrzynki.

Na Marginesie

Niech $n$ będzie liczbą naturalną. Resztą kwadratową z dzielenia przez $n$ nazwiemy taką liczbę naturalną $r,$ że istnieje $|x,$ dla którego $r x2 mod n .$ Dla przykładu, 2 jest resztą kwadratową z dzielenia przez 7, gdyż $2 32 mod 7 ,$ ale 3 już nią nie jest. Łatwo sprawdzić, czy $r$ jest resztą kwadratową z dzielenia przez liczbę pierwszą $|p$ - na mocy kryterium Eulera wystarczy obliczyć $p2 1 | r mod p$ ; już wiemy, że jest to szybkie. Jeśli wyjdzie 1, i tylko w takim przypadku, mamy do czynienia z resztą kwadratową (w przeciwnym przypadku dostajemy $| 1$ ). Wracając do naszego przykładu, mamy $3 |2 1 mod 7 ,$ ale $3 |3 1 mod 7 .$ Sprawa komplikuje się, gdy $n$ jest liczbą złożoną (na przykład $|n pq,$ gdzie $|p$ i $q$ są pierwsze). Wiemy co prawda, że $r$ jest resztą kwadratową z dzielenia przez $n$ wtedy i tylko wtedy, gdy jest resztą kwadratową z dzielenia przez $p$ oraz z dzielenia przez $q,$ jeśli jednak nie dysponujemy rozkładem $|n$ na czynniki pierwsze (jak wiemy, dla dużych $n$ jest to trudne obliczeniowo), nie mamy do dyspozycji tak wygodnego warunku, jak kryterium Eulera dla liczb pierwszych. Decyzja, czy dana liczba jest resztą kwadratową względem dużej liczby złożonej, uznawana jest za trudną obliczeniowo, co wykorzystamy obok.

Zobowiązania bezwarunkowo wiążące to takie, w których "skrzynka" może zostać otwarta tylko na jeden sposób, w związku z czym teoretycznie Bogumił mógłby wyznaczyć $|c$ na podstawie $|m.$ Postaramy się jednak, by w praktyce było to niemożliwe. Aby przedstawić przykład takiego protokołu, przypomnimy (lub nauczymy się) kilku interesujących faktów z teorii liczb.

Oto, co powinna tym razem zrobić Aldona, aby zobowiązać się do bitu $|b.$ Podobnie, jak w opisanym w poprzedniej części sagi protokole RSA, wybiera ona dwie duże liczby pierwsze $|p,q$ i oblicza $n = pq.$ Jeśli chce zobowiązać się do 1, wybiera $r$ będące resztą kwadratową z dzielenia przez $|n.$ Wybór $|r$ niebędącego resztą kwadratową z dzielenia przez $n$ oznacza zobowiązanie do 0. Sposób wyboru odpowiedniego $r$ polega na "losowaniu do skutku" - nietrudno wykazać, że nie trzeba zbyt długo czekać na sukces, a ponieważ Aldona zna liczby $p,q,$ jest w stanie rozstrzygać, czy wylosowane liczby są resztami kwadratowymi z dzielenia przez $n.$ Następnie Aldona wysyła Bogumiłowi liczby $n,r.$ Aby przekonać się o wartości $|b,$ Bogumił musiałby rozstrzygnąć, czy $r$ jest resztą kwadratową z dzielenia przez $n$ ; wiemy już, że jest to dla niego trudne, gdyż nie zna on rozkładu $|n$ na czynniki pierwsze. Oczywiście, w ramach klucza Aldona wysyła Bogumiłowi liczby $p,q$ ; wówczas bez trudu sprawdza on "kwadratowość" reszty $r$ względem każdego z czynników pierwszych, tym samym odczytując zobowiązanie Aldony.

A tak na poważnie, po co to wszystko?

Oczywiście, przedstawienie gry w marynarza jako przykładu zastosowania kryptologicznych zobowiązań miało raczej żartobliwy charakter. Poważniejszym wykorzystaniem są przetargi; łatwo wyobrazić sobie, dlaczego zobowiązania są bardzo pożyteczne w tym kontekście. Tak naprawdę jednak waga tego narzędzia jest związana z faktem, że jest bardzo wygodną "cegiełką" stosowaną przy konstrukcji innych kryptologicznych protokołów. Protokoły te często mają bardzo nieoczekiwane własności - będziemy o nich pisać w kolejnych odcinkach cyklu "A jednak się da!".