"Nie wiesz, co podpisujesz" - protokoły ślepych podpisów

28.01.2010 - Agata Murawska
TrudnośćTrudność

Ponownie odwiedziny u RSA

David Chaum
David Chaum jest pomysłodawcą i twórcą pierwszych protokołów dla ślepych podpisów i elektronicznych pieniędzy. Przyczynił się także do powstania pierwszych sieci anonimowych.
RSA jest jednym z najlepiej opisanych i zbadanych algorytmów w kryptografii. Nic zatem dziwnego, że podstawowy protokół ślepego podpisu będzie oparty właśnie na podpisach RSA. Autorem poniższego schematu jest pomysłodawca ślepych podpisów, David Chaum.












Kolejne kroki schematu opisanego w poprzedniej części są realizowane w następujący sposób:
1. (Generowanie klucza) Podpisujący generuje klucz publiczny RSA $ (n,e) $ oraz klucz prywatny $ (n,d) $
2. (Zaciemnianie) Zaciemniający wybiera dla danej wiadomości $ m $ pewną losową liczbę $ k $, taką, że $ k<n $ i $ k $ względnie pierwsze z $ n $. Następnie oblicza zaciemnienie $ m' = mk^e \mod n $ i wysyła $ m' $ jako wiadomość do podpisu.
3. (Generowanie podpisu) Podpisujący oblicza $ s' = (m')^d \mod n $ jako podpis pod wiadomością $ m' $ i wysyła $ s' $ do zaciemniającego.
4. (Zdejmowanie zaciemnienia) Zaciemniający oblicza (przy pomocy rozszerzonego alg. Euklidesa) $ k^{-1} \mod n $, a następnie odtwarza podpis pod niezaciemnioną wiadomością:
$ s=k^{-1} s' \mod n $
5. (Weryfikacja podpisu) Mając wiadomość $ m $, podpis $ s $ i klucz $ (n,e) $ podpisującego, sprawdza się, jak przy zwykłym podpisie cyfrowym, czy $ s^e = m \mod n $

Dlaczego to działa?
Policzmy, że faktycznie podpisanie wiadomości $ m $ nieznanym nam kluczem $ (d,n) $ daje w efekcie podpis $ s $:
$ k^{-1} s' \mod n = k^{-1} (m')^d \mod n =  $
$ k^{-1} (m k^e)^d \mod n = k^{-1}m^d k^{ed} \mod n =  $
$ k^{-1} m^d k^1 = m^d  k^{-1} k \mod n = $
$  m^d = s $

Zgadza się!

Poświęćmy jeszcze chwilę na analizę przedstawionego schematu. Przede wszystkim, interesują nas odpowiedzi na trzy pytania:

Czy podpisujący może poznać tożsamość zaciemniającego podczas weryfikacji?
Wiemy, że podpisujący zna tożsamość autora wiadomości podczas jej podpisywania. Czy może w jakiś sposób wykorzystać te informacje, żeby skojarzyć wiadomość $ m $ z jej zaciemnioną wersją $ m' $?
Wszystko, co dzieje się podczas podpisywania, może być zapisywane przed składającego podpis - załóżmy zatem, że ma on bazę zaciemnionych wiadomości i podpisów (czyli trójek $ (\mathrm{użytkownik} ,m', s') $).
Czy dostając wiadomość $ m $ i podpis $ s $ może coś powiedzieć o $ m' $?

  • Jak było wygenerowane $ m' $, zaciemniona wiadomość powstała z $ m $?
    Do jego stworzenia użyliśmy jakiejś losowej liczby $ k $, o której podpisujący nic nie wie - zatem odtworzenie $ m' $ na podstawie $ m $ nie jest możliwe.
  • Może zatem uda się odzyskać podpis $ s' $ i znaleźć pasującą trójkę w bazie?
    Też nie - skoro $ s' $ powstaje przez podpisanie $ m' $, to nie odzyskamy go bez wiedzy o zaciemnionej wiadomości, wysłanej do podpisu.
Jesteśmy zatem bezpieczni - nie da się, nie znając naszych wszystkich sekretów, powiązać zaciemnionej i niezaciemnionej wiadomości.

Czy spełnione są warunki dotyczące bezpiecznego ślepego podpisu?
Problem może wystąpić, jeśli uda się znaleźć takie $ m_1 $ i $ m_2 $, które przemnożone odpowiednio przez $ k_1 ^e $ i $ k_2 ^e $ dają tę samą zaciemnioną wiadomość $ m' $. Wówczas uzyskanie podpisu dla jednej z tych wiadomości, umożliwia posługiwanie się obiema. Na szczęście, znalezienie dla ustalonej wiadomości $ m_1 $ pasującego $ m_2 $ jest obliczeniowo bardzo trudne.

Czy można do podpisów ślepych używać tej samej pary kluczy, co do szyfrowania wiadomości?
Możliwe zagrożenie ilustruje poniższy obrazek:
Atak

Bob wysyła do Notariusza bardzo ważny i tajny dokument $ t $, zaszyfrowany kluczem publicznym Notariusza, $ e_N $. Annie udaje się przechwycić ten dokument, zatem zaciemnia go i wysyła do podpisu Notariuszowi, który w dobrej wierze podpisuje i odsyła do Anny. Co tu się dzieje?
Anna przechwyciła wiadomość $ m = t^{e_N} $, przemnożyła przez pewne $ k^{e_N} $ i wysłała do Notariusza. Notariusz podpisał całość i odesłał, zatem Anna otrzymała wiadomość $ (mk^{e_N})^{d_N} = (t^{e_N} k^{e_N})^{d_N} $. Teraz wystarczy, że obliczy podpis dla wiadomości $ t^{e_N} $ - będzie to, jak widać, $ (t^{e_N})^{d_N} \mod n = t $. Notariusz nie miał szansy zauważyć, że odszyfrował dla Anny wiadomość nieprzeznaczoną dla niej, gdyż była ona zaciemniona!
Z drugiej strony, Anna może po prostu wysłać korzystną dla niej, zaciemnioną wiadomość do podpisu - ot, na przykład, "Ja, Notariusz, zrzekam się całego mojego majątku na rzecz Anny". Po zaciemnieniu wiadomość będzie nieczytelna i niewzbudzająca podejrzeń, zostanie więc podpisana - Anna będzie wówczas dysponowała pismem "od Notariusza" (no przecież je podpisał!), w którym zrzeka się on majątku na rzecz Anny. Nic, tylko wyegzekwować wykonanie!
Widzimy więc, że pod żadnym pozorem nie można używać tej samej pary kluczy do protokołu ślepych podpisów i szyfrowania.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com