"Alicjo, czy to naprawdę Ty?" , albo o podpisach cyfrowych.

29.11.2009 - Agata Murawska
TrudnośćTrudność

Kryptografia z wykorzystaniem algorytmu RSA

Ważnym dla nas przykładem kryptografii z kluczem publicznym jest algorytm RSA. Jego bezpieczeństwo opiera się na założeniu, że dla dużej liczby, znalezienie jej rozkładu na czynniki pierwsze jest trudne. Pary kluczy w RSA znajduje się w następujący sposób:

1
2
3
4
5
6
7
    Znajdujemy dwie duże liczby pierwsze, p i q.
    Szukamy liczby e, względnie pierwszej z (p-1)*(q-1)
    Obliczamy d takie, że c*(p-1)*(q-1) + d*e = 1
    //rozszerzony algorytm Euklidesa znajduje c oraz d
    n = p*q
    klucz_publiczny = (e,n)
    klucz_prywatny = (d,n)

Dlaczego mówimy, że RSA jest bezpieczne, jeśli problem faktoryzacji (czyli rozkładu na czynniki pierwsze) jest trudny?
Jeśli znamy $ e $ i $ n $, to znaleźć $ d $ jest łatwo, pod warunkiem, że zna się rozkład $ n $ na czynniki pierwsze - wtedy możemy, tak jak przy generowaniu pary kluczy, użyć rozszerzonego algorytmu Euklidesa do znalezienia $ d $ i odszyfrowywać wiadomości nieprzeznaczone dla nas.
Na szczęście znalezienie dwóch naprawdę dużych liczb pierwszych wydaje się być znacznie prostsze, niż znalezienie rozkładu ich iloczynu.



Powiedzmy, że $ m $ jest wiadomością do wysłania, którą chcemy zaszyfrować tak, żeby tylko odbiorca mógł ją odczytać. Jeśli wyślemy mu wiadomość $ m^e \mod n $, gdzie $ (e,n) $ jest kluczem publicznym odbiorcy, to odszyfrowanie wiadomości polega na podniesieniu jej do odpowiedniej potęgi $ d $ ($ d $ jest fragmentem klucza prywatnego, zatem zna je tylko odbiorca):

$ (m^e \mod n)^d \mod n =  $
$  (m^e)^d \mod n =  $
$  m^{e*d} \mod n =  $
$  m \mod n $
Ta ostatnia równość wynika z chińskiego twierdzenia o resztach.

Oczywiście, jeśli wiadomość $ m $ jest długa, to trzeba ją podzielić na bloki krótsze, niż $ n $.

Podpisy z kryptografią asymetryczną

Bogatsza o tę wiedzę Alicja zastanawia się dalej. A gdyby tak napisać wiadomość dla Boba i zaszyfrować ją swoim kluczem prywatnym? Wtedy on mógłby użyć pasującego klucza publicznego i stwierdzić, że to na pewno ona jest autorką! Możemy tak zrobić, jeśli algorytmy szyfrowania i deszyfrowania są symetryczne - ale jeśli używamy RSA, to tak właśnie jest, bo przecież $ m^{e*d} = m^{d*e} $.

Alicja i Bob

Czy ta metoda ma jakieś wady? Oczywiście! Podpis jest tak długi, jak wiadomość, którą podpisujemy. Możemy oczywiście wysłać, oprócz podpisanej wiadomości, także jej jawny odpowiednik, ale weryfikacja tożsamości autora nadal będzie wymagać wiele obliczeń, a dodatkowo podwoimy ilość wysyłanych danych. Będziemy wtedy musieli też sprawdzać, czy wiadomość po deszyfrowaniu odpowiada wiadomości niezaszyfrowanej. Wydaje się, że to trochę za dużo zachodu, prawda?

Zastanówmy się jeszcze, czy wymagane na początku własności, dotyczące podpisów cyfrowych, są spełnione:

  • czy tylko Alicja może się podpisać w taki sposób wiadomość?
    Nie, gdyż możemy zostać ofiarami fałszerstwa egzystencjalnego. Pod tą tajemniczą nazwą kryją się ataki na protokoły kryptograficzne, nie oparte na znajomości par (wiadomość, podpis). Jeśli naszym celem nie jest odkrycie klucza prywatnego Alicji, lecz podszycie się pod nią, wówczas możemy spreparować podpis $ s $ taki, że jego odkodowanie przy pomocy klucza publicznego Alicji daje sensowną wiadomość $ m $. Wtedy ofiara myśli, że rozmawia z Alicją, podczas gdy to my wysłaliśmy do niej komunikat.

  • czy podpis na pewno został złożony pod tą wiadomością?
    Niestety także nie. Innym możliwym atakiem na przytoczony protokół jest wykorzystanie własności potęg: atak
    Jeśli $ s_1 $ i $ s_2 $ są podpisami pod wiadomościami, odpowiednio, $ m_1 $ i $ m_2 $
    ($ s_1 = (m_1)^d \mod n $, $ s_2 = (m_2)^d \mod n $)
    to podpisem dla wiadomości $ m_1 m_2 $ jest
    $ (m_1 m_2)^d \mod n=  $
    $ ((m_1)^d \mod n) * ((m_2)^d \mod n) =  $
    $ s_1 s_2 \mod n $

4
Twoja ocena: Brak Ocena: 4 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com