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

28.01.2010 - Agata Murawska

Ponownie odwiedziny u RSA

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.