Przeskocz do treści

Delta mi!

Kocha, lubi, szyfruje...

Tomasz Kazana

o artykule ...

  • Publikacja w Delcie: maj 2012
  • Publikacja elektroniczna: 28-04-2012
  • Autor: Tomasz Kazana
    Afiliacja: Instytut Informatyki, Uniwersytet Warszawski
  • Wersja do druku [application/pdf]: (258 KB)

W fizyce szkolnej nieustannie przewijającym się motywem są dwa znane miasta: miasto A oraz miasto B. W kryptografii takimi gwiazdami są Alicja i Bob, którzy ciągle się komunikują, uwierzytelniają, a zwykle przeszkadza im w tym złowroga Ewa.

obrazek

Tym razem jednak zadanie stojące przed Alicją i Bobem jest wyjątkowo trudne. Chcą sprawdzić, czy się nawzajem kochają, jednak bez ujawniania swoich uczuć. Co przez to rozumiemy? Otóż chcemy opracować następujący protokół komunikacyjny.

Alicja posiada bit math który informuje o tym, czy kocha Boba, czy nie (to oznacza, że math jeśli Alicja jest zakochana w Bobie, jeśli zaś nie jest, to math). Analogicznie, Bob posiada bit math opisujący jego uczucia względem Alicji. Oczywiście teraz ich wzajemna miłość może być opisana w tej notacji przez wyrażenie math  które jest równe math tylko wtedy, gdy math Naszym celem jest opracowanie takiego protokołu, w wyniku którego Alicja na końcu będzie znała math oraz math  (i nic więcej!), natomiast Bob math  oraz math Intuicja stojąca za takimi założeniami jest następująca: chcemy uniknąć krępującej sytuacji, gdy, na przykład, Alicja kocha Boba, ale Bob nie odwzajemnia tych uczuć, a dowiaduje się o uczuciu Alicji. Innymi słowy: jeśli Bob wie, że math oraz math  to nie powinien umieć wyznaczyć math

Powyższe założenia łatwo uzyskać, gdy dopuścimy trzecią zaufaną stronę, która, gdy pozna math i math obliczy math  oraz przekaże tę informację obu zainteresowanym osobom. Nasze zadanie jest jednak bardziej ambitne, ponieważ pożądany efekt chcemy uzyskać za pomocą protokołu, w którym jedynymi stronami są Alicja i Bob. Zadanie samo w sobie wydaje się trudne, a wręcz można by przypuszczać, że tak określony protokół nie jest możliwy do zrealizowania. Pokażemy jednak, że jest to możliwe, ale przy pewnych założeniach obliczeniowych. Mamy tu na myśli klasyczne założenia dotyczące szyfrowania algorytmem RSA: a więc, że strona posiadająca jakąś wiadomość zaszyfrowaną oraz klucz publiczny bez znajomości klucza prywatnego nie jest w stanie odtworzyć wiadomości jawnej. Należy tu poczynić uwagę, że bez założeń tego typu (tj. bez ograniczeń obliczeniowych, inaczej mówiąc: bezpiecznie teorio-informacyjnie) żądanego protokołu nie da się skonstruować.

Wróćmy teraz do naszej Alicji i naszego Boba, którzy już za chwilę zaczną ze sobą rozmawiać.

Szukany protokół opiera się na idei tak zwanego transferu utajnionego (ang. oblivious transfer). Jest to bardzo ciekawy i użyteczny protokół, niejednokrotnie wykorzystywany jako cegiełka do budowy innych protokołów. Założenia są następujące: Alicja posiada parę liczb math a Bob bit math Po zakończeniu protokołu Alicja nie dowie się niczego nowego, natomiast Bob pozna liczbę math Taki protokół istnieje, pokażemy go później. Natomiast korzystając z transferu utajnionego, możemy już łatwo wykonać nasz docelowy protokół.

Niech mianowicie Alicja przyjmie:

display-math

a Bob:

display-math

W pierwszej fazie testu na miłość wykonujemy klasyczny transfer utajniony dla podanych parametrów. W jego wyniku Bob otrzymuje wartość math Wówczas wysyła ją Alicji i jest to wynik naszego protokołu.

Łatwo sprawdzamy poprawność: jeśli math to wynikiem protokołu jest math co jest zgodne z oczekiwaniami, gdyż

display-math

niezależnie od wartości math W drugim przypadku math wynikiem jest math co również jest poprawną odpowiedzią, gdyż:

display-math

Transfer utajniony

W tej części pokażemy, jak zrealizować transfer utajniony. Jako narzędzia potrzebujemy szyfrowania z kluczem publicznym i prywatnym – dobrym przykładem jest tu wspomniany już algorytm RSA. Przypomnijmy założenia: Alicja posiada parę liczb math oraz math natomiast Bob ustala bit math Teraz:

1.
Alicja inicjalizuje algorytm RSA, tzn. wybiera liczbę math oraz klucze math i math Zakładamy, że math Swój klucz publiczny, czyli parę math wysyła do Boba.
2.
Alicja losuje niezależnie dwie różne liczby math oraz wysyła je Bobowi.
3.
Bob losuje liczbę math i oblicza math Bob wysyła wartość math do Alicji.
4.
Alicja oblicza kolejno: math oraz math  math  math oraz wysyła Bobowi math i math 
5.
Bob potrafi obliczyć math 

Sprawdźmy, że obliczona przez Boba wartość to rzeczywiście math:

pict

Aby opisany protokół był użyteczny, potrzebne są dwie własności:

*
Alicja nie poznaje bitu math Ten fakt jest prosty – wynika z symetrii. To znaczy: z punktu widzenia Alicji nie ma w protokole żadnego rozróżnienia między math a  math gdyż jedyny komunikat otrzymany od Boba (wartość math) jest – z punktu widzenia Alicji – losowy i niezależny od wartości math
**
Bob nie poznaje liczby math

Pełny dowód (**) pominiemy i pozostawimy Czytelnikowi: wskazówka jest taka, że należy pokazać (metodą nie wprost), że gdyby można było złamać nasz protokół (a więc Bob dowiedziałby się czegoś na temat math), to złamać potrafilibyśmy również RSA. Rozumowania tego typu są bardzo częste w dowodach w kryptografii, czasem nazywamy je symulacją jednego protokołu przez drugi.

Na sam koniec warto dodać, że opisany tutaj problem jest tylko drobnym przykładem na to, co potrafimy robić. Otóż okazuje się, że funkcja math została wybrana zupełnie arbitralnie: tak naprawdę można podać protokół obliczający wartość dowolnej funkcji opisanej za pomocą obwodu logicznego. Wówczas ilość potrzebnej informacji, którą wymienią między sobą Alicja i Bob, jest proporcjonalna do liczby węzłów wspomnianego obwodu. Zainteresowanego Czytelnika zachęcamy do dalszych poszukiwań.