Kto jest najbogatszy i czy to naprawdę miłość?

25.02.2010 - Agata Murawska
TrudnośćTrudność

Na początek - coś dziwnego

Zaczniemy od skonstruowania funkcji transferu utajnionego. Cóż to takiego?
Alicja zna $ 2 $ liczby: $ m_0, m_1 $. Bob chce poznać jedną z tych liczb, ale tak, żeby Alicja nie wiedziała, o którą liczbę poprosił. Nie może przy tym poznać drugiej z liczb posiadanych przez Alicję.
Protokół dla funkcji transferu utajnionego wygląda tak:

Oznaczenia:
$ (e_A,N) $ - klucz publiczny Alicji (z protokołu RSA)
$ (d_A,N) $ - klucz prywatny Alicji (j.w.)
$ (m_0, m_1) $ - argument Alicji
$ b $ - argument Boba ($ b \in \{0,1\} $)
1. Alicja losuje dwie liczby, $ x_0 $ i $ x_1 $.
2. Alicja przekazuje Bobowi swój klucz publiczny $ (e_A, N) $ oraz wylosowaną parę $ (x_0, x_1) $.
3. Bob losuje liczbę $ k $ i wybiera $ b $ - numer wiadomości, którą chce otrzymać.
4. Bob szyfruje $ k $ przy pomocy klucza publicznego Alicji, a następnie dodaje do niego $ x_b $ - $ b $-tą liczbę przekazaną mu przez Alicję. Sumę przekształca dalej $ \mod N $.
5. Otrzymane $ v=k^{e_A}+x_b \mod N $ Bob przesyła do Alicji.
6. Alicja oblicza $ k_0 $ jako wynik odszyfrowania $ v-x_0 $ oraz $ k_1 $ jako odszyfrowane $ v-x_1 $. Zauważmy w tym miejscu, że $ k_b=k $, druga z wartości nas nie interesuje.
7. Ponieważ Alicja nie wie, o którą wartość mogło chodzić Bobowi, odsyła do niego parę $ (k_0+m_0, k_1+m_1) $
8. Bob, odejmując od interesującego go elementu pary $ k_b+m_b $ znaną sobie liczbę $ k $, otrzymuje $ b $-ty element pary.

  • To, że Alicja nie ma szansy dowiedzieć się, którą z liczb chciał poznać Bob, jest widoczne gołym okiem — w jedynym miejscu, gdzie Bob używa $ b $, robi to w połączeniu ze zsumowaniem pewnej wartości z liczbą otrzymaną losowo. Losowe liczby mają to do siebie, że trudno je odgadnąć, zatem sekret Boba można uznać za bezpieczny.
  • A dlaczego Bob nie ma pojęcia, jaka była wartość $ m_{1-b} $? Alicja wysyła do niego $ k_{1-b}+m_{1-b} $, gdyby zatem Bob mógł obliczyć $ k_{1-b} $, potrafiłby też znaleźć $ m_{1-b} $.
    Czemu jest to niemożliwe? $ k_{1-b} $ jest efektem odszyfrowania wiadomości kluczem prywatnym Alicji. Złamanie go nie jest może całkowicie niemożliwe, ale uznajemy, że jest to zadanie obliczeniowo niewykonalne. Zatem bezpieczeństwo sekretu Alicji opiera się na bezpieczeństwie systemu RSA.

Ćwiczenie
Spróbuj uogólnić powyższą procedurę na protokół transferu utajnionego dla wyboru jednej z $ k $ wartości.

..ale co z tą miłością?!

Wszystko to bardzo pięknie, ale jak to się ma do problemu potencjalnej miłości Boba i Alicji? Myli się, kto sądzi, że nijak. Używając transferu utajnionego możemy rozwiązać problem zakochanych niemal od ręki!

Zauważmy, że jeśli Alicja kocha Boba, to po wykonaniu tego protokołu, wie, czy jej uczucie jest odwzajemnione. Podobnie jest, jeśli Bob kocha Alicję.
Przypomnijmy, że $ A = 1 $ jeśli Alicja kocha Boba i $ A=0 $ w przeciwnym razie, podobnie dla wartości $ B $.Teraz wystarczy, że argumentem Alicji będzie para $ (0,A) $, zaś argumentem Boba (czyli liczbą, o którą pyta Bob) będzie $ B $. Bob po otrzymaniu wyniku przesyła go jeszcze do Alicji.
Dlaczego to działa? No cóż, jeśli $ B=0 $ to Bob otrzyma $ 0 $ niezależnie od tego, co sądzi o nim jego dziewczyna. Jeśli zaś $ B=1 $, to Bob w wyniku dostanie odpowiedź Alicji, gdyż to jej głos jest w tym wypadku decydujący. Kryzys zażegnany!

No, może nie do końca. Na początku powiedzieliśmy, że zakładamy o obu uczestnikach, że są uczciwi. A przecież jeśli Bob nie kocha Alicji, może zdobyć informacje o jej uczuciu w prosty sposób:
Klucz


Wystarczy, że zechce poznać wartość $ m_1 $, ale odpowie tak, jakby prosił o $ m_0 $. Czy Alicja może zorientować się, że Bob ją oszukuje? Tak, ale tylko jeśli go kocha. Czy potrafisz to pokazać?
Rozwiązanie

Ataki na protokoły kryptograficzne można podzielić na dwie zasadnicze kategorie:
  • atak pasywny - w którym wszyscy uczestnicy przestrzegają protokołu
  • atak aktywny - w którym ktoś protokołu nie przestrzega.
O protokole przedstawionym powyżej można zatem powiedzieć, że nie jest odporny na atak aktywnego oszusta.

Jeśli Alicja nie kocha Boba, to nie ma pojęcia, o którą wartość on pytał – a w efekcie, czy ją oszukał, czy nie. Wydaje się to trochę nieuczciwe – niekochająca Alicja nie wie, czy jest niekochana, a niekochający Bob potrafi to sprawdzić.
Może zatem nie powinniśmy trzymać się ról w protokole? Prosty rzut monetą pozwoli na ustalenie, która ze stron będzie tworzyć parę liczb, a która będzie jedną z tych liczb pobierać. Czy jednak potrafimy uczciwie rzucać monetą?

5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com