A jednak się da!

Odtajniamy transfer utajniony (AJSD IV)

Ence-pence w której ręce? - za moich dziecięcych lat przedstawiona formułka, której towarzyszyły często dwie wyciągnięte przez wypowiadającą ją osobę ręce, była zwiastunem jakiejś bardzo przyjemnej (najczęściej słodkiej) niespodzianki. Każda wyciągnięta dłoń skrywała bowiem coś dobrego, jednak jako szkrab i tak poświęcałem chwilę zastanowienia nad jej wyborem, będąc świadomym ryzyka, że niewskazana przeze mnie ręka zawiera bardziej atrakcyjny podarek i powędruje on do mojego brata.

Ta dziecięca wyliczanka będzie dla nas punktem wyjścia do rozważań nad problemem pozornie niemającym zastosowania w rzeczywistości. Zapytajmy bowiem, czy dziecko jest w stanie dowiedzieć się, co znajduje się w wybranej przez nie ręce, tak aby spełnione były dwa warunki:

(1): dziecko nie dowiaduje się, co znajduje się w drugiej ręce rodzica,
(2): rodzic nie dowiaduje się, którą rękę wybrało dziecko.

Powyższe założenia wydają się sprzeczne, a procedura, która miałaby je spełniać, zakrawa o sztuczkę magiczną. Jest to jednak możliwe - stosowny protokół nazywa się transferem utajnionym. Pisał o nim Tomasz Kazana w Delcie 5/2012. Transfer utajniony jest jednak na tyle ważną "cegiełką" kryptograficzną, że dla pełności naszego cyklu postanowiliśmy przypomnieć go w tym krótkim artykule.

Rozpocznijmy od przedstawienia naszego problemu w bardziej matematycznym języku. Aby biedny rodzic nie musiał utrzymywać przez cały czas rąk w górze, załóżmy, że przyporządkowuje on wartości dwóm zmiennym: $x0$ (lewa ręka) i $x1$ (prawa ręka); dla ułatwienia opisu załóżmy, że wartości te są liczbami naturalnymi. Dziecko wybiera natomiast $s ∈{0,1}.$ Jego zadaniem jest poznanie wartości $x s$ bez ujawniania $|s,$ natomiast rodzic nie może wyjawić wartości $x1−s.$

Pierwszym krokiem protokołu jest stworzenie bazy do szyfrowania z kluczem publicznym, tak jak opisane to zostało w pierwszym odcinku serii, opublikowanym w Delcie 10/2018. Rodzic wybiera dwie duże liczby pierwsze $p,q$ tak, aby $|n = pq$ było większe od każdej z liczb $x 0$ i $|x. 1$ Następnie rodzic oblicza $|m = (p− 1)(q −1)$ i znajduje takie dwie liczby naturalne $|e$ i $|d,$ że $|ed ≡1(mod m)$ (tzn. $ed |$ daje resztę 1 z dzielenia przez $|m$ ). Ponadto rodzic losuje liczby $y0$ i $y1$ i wyjawia dziecku wartość każdej z nich. Dziecko natomiast losuje liczbę $|k,$ której nigdy nie ujawni rodzicowi. Zamiast tego przesyła mu wartość $e v = (ys + k mod n).$ Na jej podstawie rodzic oblicza $|k0 = ((v− y0)d mod n)$ oraz $|k1 = ((v− y1)d mod n).$ Zauważmy, że wówczas $ks = (ked mod n) = k$ (po szczegóły odsyłamy do pierwszej części sagi). Jeśli zatem rodzic prześle dziecku wartości $˜x = x + k 0 0 0$ oraz $|˜x1 = x1 + k1,$ to dziecko będzie mogło obliczyć wartość $|xs = ˜xs− k.$

Wiemy już, że w opisany wyżej sposób dziecko poznaje wartość $|xs.$ Jedyna informacja, jaką rodzic dostaje od dziecka, to wartość $|v.$ Na jej podstawie rodzic nie jest w stanie powiedzieć niczego o $|s$ ze względu na losowy wybór $k.$ Pozostaje wykazać, że dziecko nie jest w stanie obliczyć wartości $x . 1−s$ Zauważmy, że

e e e d e e (˜x1− s− x1− s) ≡ k1−s≡ ((ys+ k − y1− s) ) ≡ ys+ k − y1− s ( mod n).

Ponieważ $y0$ i $y1$ były losowane przez rodzica, to z punktu widzenia dziecka liczba $|ys + ke + y1−s$ jest losowa. Gdyby dziecko potrafiło obliczyć $|x1− s,$ to ponieważ zna $x˜1−s$ - potrafiłoby obliczyć lewą stronę powyższej równości. Rozwiązałoby zatem równanie $e |a ≡ b( mod n)$ dla losowo wybranej wartości $b.$ Z pierwszego odcinka sagi wiemy, że zadanie to jest równie trudne, co złamanie szyfru RSA, jeśli zatem wierzymy w bezpieczeństwo tego ostatniego, nie powinniśmy mieć skrupułów w używaniu przedstawionego protokołu transferu ujawnionego. A o tym, że kryptologia opiera się na wierze (lecz również zrozumieniu!) pisaliśmy już w Delcie niejednokrotnie...