Testy pierwszości. Liczby pseudopierwsze Lucasa i liczby silnie pseudopierwsze Lucasa. Test BPSW

22.11.2023

Protokół Diffiego-Hellmana

Uwaga Q1
Metoda ta została opracowana przez W. Diffiego i M. Hellmana w 1976 roku. Opisana niżej procedura nie jest metodą szyfrowania i z założenia jej cel jest zupełnie inny. Umożliwia ona osobom mogącym kontaktować się ze sobą jedynie przez niezabezpieczone przed podsłuchem środki łączności ustalenie (tajnej) liczby, zwanej kluczem. Dysponując wspólną liczbą-kluczem osoby te mogą kodować i odczytywać wiadomości wybraną metodą szyfrowania. Przedstawimy w punktach procedurę postępowania wraz z przykładowymi danymi.

1. Agencja i Bolek wybierają (jawną) liczbę pierwszą [math]\displaystyle{ p = 541 }[/math] i (jawną) liczbę [math]\displaystyle{ g = 2 }[/math]

2. Agencja ustala (tajny, znany tylko sobie) wykładnik [math]\displaystyle{ a = 2718 }[/math]

3. Bolek ustala (tajny, znany tylko sobie) wykładnik [math]\displaystyle{ b = 3141 }[/math]

4. Agencja oblicza (jawną) liczbę [math]\displaystyle{ X = R_p (g^a) = 300 }[/math] i wysyła ją do Bolka

5. Bolek oblicza (jawną) liczbę [math]\displaystyle{ Y = R_p (g^b) = 191 }[/math] i wysyła ją do Agencji

6. Agencja oblicza (tajną) liczbę [math]\displaystyle{ k_A = R_p (Y^a) = 493 }[/math]

7. Bolek oblicza (tajną) liczbę [math]\displaystyle{ k_B = R_p (X^b) = 493 }[/math]

8. Modulo [math]\displaystyle{ p }[/math] mamy

[math]\displaystyle{ k_A = R_p (Y^a) \equiv Y^a = [R_p (g^b)]^a \equiv (g^b)^a \equiv g^{a b} \equiv (g^a)^b \equiv [R_p (g^a)]^b = X^b \equiv R_p (X^b) = k_B \!\! \pmod{p} }[/math]

9. Z definicji liczby [math]\displaystyle{ k_A, k_B \in [0, p - 1] }[/math], zatem [math]\displaystyle{ 0 \leqslant | k_A - k_B | \leqslant p - 1 }[/math]. Ponieważ liczby [math]\displaystyle{ k_A, k_B }[/math] przystają do siebie modulo [math]\displaystyle{ p }[/math], to muszą być sobie równe, czyli liczba [math]\displaystyle{ k = k_A = k_B }[/math] jest poszukiwanym kluczem.

Uwaga Q2
Liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] mogą być losowo wybranymi liczbami dodatnimi nie większymi od [math]\displaystyle{ p }[/math]. Istotnie, jeżeli [math]\displaystyle{ a = k \cdot (p - 1) + r }[/math], to

[math]\displaystyle{ g^a \equiv (g^{p - 1})^k \cdot g^r \equiv g^r \!\! \pmod{p} }[/math]

W naszym przykładzie możemy użyć liczb [math]\displaystyle{ a = 18 }[/math] oraz [math]\displaystyle{ b = 441 }[/math] otrzymując te same rezultaty. W praktyce ten problem nie występuje, bo gdy liczba pierwsza [math]\displaystyle{ p }[/math] ma co najmniej sto cyfr, to trudno wybrać jeszcze większy wykładnik.

Przykład Q3
Zobaczmy, jak wpłynie na protokół zmiana liczby [math]\displaystyle{ g }[/math]. Niech [math]\displaystyle{ p = 541 }[/math] i [math]\displaystyle{ g = 15 }[/math].

[math]\displaystyle{ \boldsymbol{a} }[/math]	[math]\displaystyle{ \boldsymbol{b} }[/math]	[math]\displaystyle{ \boldsymbol{R_p(g^a)} }[/math]	[math]\displaystyle{ \boldsymbol{R_p(g^b)} }[/math]	[math]\displaystyle{ \boldsymbol{R_p(g^{a b})} }[/math]
[math]\displaystyle{ 2985 }[/math]	[math]\displaystyle{ 4683 }[/math]	[math]\displaystyle{ 411 }[/math]	[math]\displaystyle{ 129 }[/math]	[math]\displaystyle{ 1 }[/math]
[math]\displaystyle{ 4270 }[/math]	[math]\displaystyle{ 8998 }[/math]	[math]\displaystyle{ 312 }[/math]	[math]\displaystyle{ 214 }[/math]	[math]\displaystyle{ 15 }[/math]
[math]\displaystyle{ 9749 }[/math]	[math]\displaystyle{ 3921 }[/math]	[math]\displaystyle{ 225 }[/math]	[math]\displaystyle{ 411 }[/math]	[math]\displaystyle{ 129 }[/math]
[math]\displaystyle{ 8993 }[/math]	[math]\displaystyle{ 6479 }[/math]	[math]\displaystyle{ 225 }[/math]	[math]\displaystyle{ 505 }[/math]	[math]\displaystyle{ 214 }[/math]
[math]\displaystyle{ 2146 }[/math]	[math]\displaystyle{ 8663 }[/math]	[math]\displaystyle{ 312 }[/math]	[math]\displaystyle{ 352 }[/math]	[math]\displaystyle{ 225 }[/math]
[math]\displaystyle{ 9941 }[/math]	[math]\displaystyle{ 6182 }[/math]	[math]\displaystyle{ 352 }[/math]	[math]\displaystyle{ 505 }[/math]	[math]\displaystyle{ 312 }[/math]
[math]\displaystyle{ 8944 }[/math]	[math]\displaystyle{ 8120 }[/math]	[math]\displaystyle{ 214 }[/math]	[math]\displaystyle{ 225 }[/math]	[math]\displaystyle{ 352 }[/math]
[math]\displaystyle{ 2928 }[/math]	[math]\displaystyle{ 9314 }[/math]	[math]\displaystyle{ 129 }[/math]	[math]\displaystyle{ 505 }[/math]	[math]\displaystyle{ 411 }[/math]
[math]\displaystyle{ 7436 }[/math]	[math]\displaystyle{ 3172 }[/math]	[math]\displaystyle{ 225 }[/math]	[math]\displaystyle{ 312 }[/math]	[math]\displaystyle{ 505 }[/math]

Czytelnik może wybierać dowolne inne wykładniki [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math], ale innych wartości [math]\displaystyle{ R_p (g^{a b}) }[/math] już nie uzyska. Wybór liczby [math]\displaystyle{ g = 2 }[/math] w zamieszczonym powyżej opisie metody, nie był przypadkowy. Liczba [math]\displaystyle{ 2 }[/math] jest generatorem modulo [math]\displaystyle{ 541 }[/math]. Generator modulo liczba pierwsza [math]\displaystyle{ p }[/math], to taka liczba [math]\displaystyle{ g }[/math], że zbiór potęg

[math]\displaystyle{ \{ g^1, g^2, g^3, \ldots, g^{p - 1} \} }[/math]

rozpatrywany modulo [math]\displaystyle{ p }[/math] jest identyczny ze zbiorem

[math]\displaystyle{ \{ 1, 2, 3, \ldots, p - 1 \} }[/math]

Wybierając liczbę [math]\displaystyle{ g }[/math] tak, aby była generatorem modulo [math]\displaystyle{ p }[/math], zapewniamy sobie, że w ostatniej kolumnie mogą pojawić się wszystkie liczby od [math]\displaystyle{ 1 }[/math] do [math]\displaystyle{ p - 1 }[/math]. Taki wybór [math]\displaystyle{ g }[/math] zwiększa ilość możliwych wartości dla ustalanego klucza [math]\displaystyle{ k = R_p (g^{a b}) }[/math], a tym samym zwiększa bezpieczeństwo procedury. Zauważmy, że liczby [math]\displaystyle{ p }[/math] i [math]\displaystyle{ g }[/math] są jawne. Osoba próbująca poznać ustalony klucz [math]\displaystyle{ k }[/math] z pewnością ucieszy się, gdy sprawdzi, że niewłaściwy wybór liczby [math]\displaystyle{ g }[/math] zredukował ilość możliwych kluczy i ułatwił jej pracę.

Każda liczba pierwsza ma generator modulo, ale znalezienie go dla dużych liczb pierwszych nie jest proste i może trwać bardzo długo. Pomocne w tej sytuacji jest następujące twierdzenie.

Twierdzenie Q4
Niech [math]\displaystyle{ p = 2 q + 1 }[/math] będzie liczbą pierwszą, gdzie [math]\displaystyle{ q \geqslant 3 }[/math] jest również liczbą pierwszą. Jeżeli [math]\displaystyle{ g }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math] i [math]\displaystyle{ g \not\equiv - 1 \!\! \pmod{p} }[/math], to [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math].

Dowód

Dowód jest na tyle prosty i elegancki, że postanowiliśmy go zamieścić, choć wykracza on poza omówiony wcześniej materiał. Czytelnik może ten dowód pominąć. Dowód poprzedzamy kilkoma prostymi, ale istotnymi komentarzami.

Komentarz 1.

Bez dowodu przyjmujemy fakt, że istnieje dokładnie [math]\displaystyle{ \varphi (p - 1) }[/math] różnych generatorów modulo [math]\displaystyle{ p }[/math], gdzie [math]\displaystyle{ \varphi }[/math] jest funkcją Eulera. Funkcja Eulera [math]\displaystyle{ \varphi (n) }[/math] jest równa ilości liczb całkowitych dodatnich nie większych od [math]\displaystyle{ n }[/math] i względnie pierwszych z [math]\displaystyle{ n }[/math].

Komentarz 2.

Udowodnimy, że jeżeli [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], to [math]\displaystyle{ g }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math].

Przypuśćmy, że [math]\displaystyle{ g }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math], zatem (zobacz J31)

[math]\displaystyle{ g^{(p - 1) / 2} \equiv 1 \!\! \pmod{p} }[/math]

Wynika stąd, że zbiór

[math]\displaystyle{ S = \{ g^1, g^2, g^3, \ldots, g^{p - 1} \} }[/math]

[math]\displaystyle{ \;\;\,\, = \left\{ g^1, g^2, g^3, \ldots, g^{\tfrac{p - 1}{2} - 3}, g^{\tfrac{p - 1}{2} - 2}, g^{\tfrac{p - 1}{2} - 1}, g^{\tfrac{p - 1}{2}}, g^{\tfrac{p - 1}{2} + 1}, g^{\tfrac{p - 1}{2} + 2}, g^{\tfrac{p - 1}{2} + 3}, \ldots, g^{p - 3}, g^{p - 2}, g^{p - 1} \right\} }[/math]

jest identyczny modulo [math]\displaystyle{ p }[/math] ze zbiorem

[math]\displaystyle{ S' = \left\{ g^1, g^2, g^3, \ldots, g^{\tfrac{p - 1}{2} - 3}, g^{\tfrac{p - 1}{2} - 2}, g^{\tfrac{p - 1}{2} - 1}, 1, g^1, g^2, g^3, \ldots, g^{\tfrac{p - 1}{2} - 3}, g^{\tfrac{p - 1}{2} - 2}, g^{\tfrac{p - 1}{2} - 1} \right\} }[/math]

[math]\displaystyle{ \quad \, = \left\{ 1, g^1, g^2, g^3, \ldots, g^{\tfrac{p - 1}{2} - 3}, g^{\tfrac{p - 1}{2} - 2}, g^{\tfrac{p - 1}{2} - 1} \right\} }[/math]

i nie może być identyczny modulo [math]\displaystyle{ p }[/math] ze zbiorem [math]\displaystyle{ T = \{ 1, 2, 3, \ldots, p - 1 \} }[/math], bo [math]\displaystyle{ S' }[/math] zawiera co najwyżej połowę elementów zbioru [math]\displaystyle{ T }[/math]. Uzyskana sprzeczność dowodzi, że generator musi być liczbą niekwadratową modulo [math]\displaystyle{ p }[/math].

Komentarz 3.

Ponieważ funkcja Eulera [math]\displaystyle{ \varphi (n) }[/math] jest równa ilości liczb całkowitych dodatnich nie większych od [math]\displaystyle{ n }[/math] i względnie pierwszych z [math]\displaystyle{ n }[/math], to dla liczby pierwszej [math]\displaystyle{ p }[/math] mamy [math]\displaystyle{ \varphi (p) = p - 1 }[/math], bo wszystkie liczby [math]\displaystyle{ 1, 2, 3, \ldots, p - 1 }[/math] są względnie pierwsze z liczbą pierwszą [math]\displaystyle{ p }[/math].

Komentarz 4.

Ponieważ funkcja Eulera [math]\displaystyle{ \varphi (n) }[/math] jest równa ilości liczb całkowitych dodatnich nie większych od [math]\displaystyle{ n }[/math] i względnie pierwszych z [math]\displaystyle{ n }[/math], to dla liczby pierwszej nieparzystej [math]\displaystyle{ p }[/math] mamy [math]\displaystyle{ \varphi (2 p) = p - 1 }[/math], bo

• wszystkie liczby parzyste [math]\displaystyle{ 2, 4, 6, \ldots, 2 p - 2 }[/math] mają z liczbą [math]\displaystyle{ 2 p }[/math] wspólny dzielnik równy [math]\displaystyle{ 2 }[/math] i nie mogą być względnie pierwsze z liczbą [math]\displaystyle{ 2 p }[/math]
• wszystkie liczby nieparzyste [math]\displaystyle{ 1, 3, 5, \ldots, 2 p - 1 }[/math] (których jest [math]\displaystyle{ p }[/math]) są względnie pierwsze z liczbą [math]\displaystyle{ 2 p }[/math], poza liczbą nieparzystą [math]\displaystyle{ p }[/math], która nie jest względnie pierwsza z liczbą [math]\displaystyle{ 2 p }[/math]

Wracając do dowodu twierdzenia Q4, zauważmy, że liczba [math]\displaystyle{ - 1 }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p = 2 q + 1 }[/math]. Istotnie, obliczając symbol Jacobiego, otrzymujemy

[math]\displaystyle{ \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} = (- 1)^{\tfrac{p - 1}{2}} = (- 1)^q = - 1 }[/math]

Zauważmy też, że dla liczb pierwszych [math]\displaystyle{ p \geqslant 5 }[/math] liczba [math]\displaystyle{ - 1 }[/math] nie jest generatorem modulo [math]\displaystyle{ p }[/math]. Ponieważ [math]\displaystyle{ (- 1)^n = \pm 1 }[/math], to zbiór potęg

[math]\displaystyle{ \{ g^1, g^2, g^3, \ldots, g^{p - 1} \} }[/math]

składa się tylko z dwóch elementów [math]\displaystyle{ \{ - 1, 1 \} }[/math] i dla liczb pierwszych [math]\displaystyle{ p \geqslant 5 }[/math] nie może być identyczny modulo [math]\displaystyle{ p }[/math] ze zbiorem [math]\displaystyle{ \{ 1, 2, 3, \ldots, p - 1 \} }[/math].

Ilość generatorów modulo [math]\displaystyle{ p }[/math] dla liczby pierwszej [math]\displaystyle{ p = 2 q + 1 }[/math] jest równa

[math]\displaystyle{ \varphi (p - 1) = \varphi (2 q) = q - 1 = {\small\frac{p - 1}{2}} - 1 }[/math]

Ponieważ istnieje [math]\displaystyle{ {\small\frac{p - 1}{2}} }[/math] liczb niekwadratowych modulo [math]\displaystyle{ p }[/math] (zobacz J30), to liczb niekwadratowych modulo [math]\displaystyle{ p }[/math], różnych od [math]\displaystyle{ - 1 }[/math], jest [math]\displaystyle{ {\small\frac{p - 1}{2}} - 1 }[/math], czyli tyle samo, co generatorów modulo [math]\displaystyle{ p }[/math], a żadna z pozostałych liczb (kwadratowych modulo [math]\displaystyle{ p }[/math]) nie może być generatorem modulo [math]\displaystyle{ p }[/math]. Co kończy dowód.
□

Uwaga Q5
Jeśli nie potrzebujemy wyliczyć najmniejszego generatora modulo [math]\displaystyle{ p = 2 q + 1 }[/math], to z twierdzenia Q4 można łatwo pokazać, że liczba [math]\displaystyle{ - 4 }[/math] jest generatorem dla wszystkich liczb pierwszych [math]\displaystyle{ p = 2 q + 1 \geqslant 7 }[/math], a liczba [math]\displaystyle{ - 3 }[/math] dla wszystkich liczb pierwszych [math]\displaystyle{ p = 2 q + 1 \geqslant 11 }[/math]. Ponieważ [math]\displaystyle{ q = 2 k + 1 }[/math], to [math]\displaystyle{ p = 4 k + 3 }[/math].

1. Pokażemy, że [math]\displaystyle{ - 4 }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math]. Liczba [math]\displaystyle{ k }[/math] może być postaci [math]\displaystyle{ 2 j }[/math] lub [math]\displaystyle{ 2 j + 1 }[/math], co daje odpowiednio [math]\displaystyle{ p = 8 j + 3 }[/math] lub [math]\displaystyle{ p = 8 j + 7 }[/math]. Zatem

[math]\displaystyle{ \left( {\small\frac{- 4}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{2}{p}} \right)_{\small{\!\! J}}^{\! 2} = (- 1) \cdot (\pm 1)^2 = - 1 }[/math]

Zobacz twierdzenie J42 p.6.

2. Pokażemy, że [math]\displaystyle{ - 3 }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math]. Liczba [math]\displaystyle{ k }[/math] może być postaci [math]\displaystyle{ 3 j, 3 j + 1, 3 j + 2 }[/math], co daje odpowiednio

[math]\displaystyle{ k = 3 j \qquad \qquad \;\!\!\! p = 12 j + 3 \qquad \;\; q = 6 j + 1 }[/math]

[math]\displaystyle{ k = 3 j + 1 \qquad p = 12 j + 7 \qquad \;\; q = 6 j + 3 }[/math]

[math]\displaystyle{ k = 3 j + 2 \qquad p = 12 j + 11 \qquad q = 6 j + 5 }[/math]

Pierwsza i druga postać liczby [math]\displaystyle{ k }[/math] nie jest możliwa, bo albo liczba [math]\displaystyle{ p }[/math], albo liczba [math]\displaystyle{ q }[/math] byłyby liczbami złożonymi. Zatem

[math]\displaystyle{ \left( {\small\frac{- 3}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = (- 1) \cdot (+ 1) = - 1 }[/math]

Zobacz twierdzenie J42 p.6 i zadanie J47.

Uwaga Q6
O ile w ogólnym przypadku liczb pierwszych [math]\displaystyle{ p }[/math] liczących setki cyfr znalezienie najmniejszego generatora modulo [math]\displaystyle{ p }[/math] może trwać godzinami, to w przypadku liczb pierwszych [math]\displaystyle{ p = 2 q + 1 }[/math], gdzie [math]\displaystyle{ q }[/math] jest również liczbą pierwszą, wystarczy znaleźć liczbę niekwadratową modulo [math]\displaystyle{ p }[/math], a obliczenie symbolu Jacobiego trwa bardzo krótko, zaś wyszukanie liczb pierwszych postaci [math]\displaystyle{ p = 2 q + 1 }[/math] też jest zaskakująco szybkie. Dlatego napisaliśmy w PARI/GP prosty program, który wyszukuje w zadanym przedziale [math]\displaystyle{ [m, n] }[/math] liczbę pierwszą [math]\displaystyle{ p }[/math] taką, że [math]\displaystyle{ p = 2 q + 1 }[/math] i zwraca [math]\displaystyle{ p }[/math] oraz najmniejszy generator modulo [math]\displaystyle{ p }[/math].

Należy zwrócić uwagę, że funkcje ispseudoprime() i randomprime() sprawdzają pierwszość liczby na tym samym poziomie – wykonywany jest test Millera-Rabina. Dlatego używamy ich łącznie, co przyspiesza wyszukanie odpowiedniej liczby pierwszej. Następnie, już silniejszym testem, potwierdzamy pierwszość obydwu liczb: [math]\displaystyle{ p }[/math] i [math]\displaystyle{ (p - 1) / 2 }[/math].

Pokaż kod

SafePrime(m, n) = 
\\ zwraca wektor [p, g], gdzie p i (p-1)/2 są liczbami pierwszymi, a g jest generatorem modulo p
{
local(g, p);
setrand(getwalltime());  \\ ustawiamy ziarno (ang. seed) generatora liczb losowych
while( 1,
       p = 9;
       while( !ispseudoprime( (p - 1)/2 ), p = randomprime([m, n]) );
       if( isprime(p) && isprime( (p-1)/2 ), break() );
     );
g = 2;
while( jacobi(g, p) > -1, g++ );
return([p, g]);
}

Uwaga Q7
Jak dalece bezpieczna jest opisana wyżej metoda? Aby znaleźć klucz trzeba oprócz (jawnych) liczb [math]\displaystyle{ p, g, X, Y }[/math] znać jedną z liczb [math]\displaystyle{ a }[/math] lub [math]\displaystyle{ b }[/math]. Liczba [math]\displaystyle{ a }[/math] spełnia kongruencję

[math]\displaystyle{ g^a \equiv X \!\! \pmod{p} }[/math]

ale nie istnieje żadna metoda szybkiego znalezienia wykładnika [math]\displaystyle{ a }[/math]. Oczywiście zawsze pozostaje możliwość kolejnego wyliczania [math]\displaystyle{ g^n }[/math] modulo [math]\displaystyle{ p }[/math] z nadzieją trafienia na [math]\displaystyle{ X }[/math] lub [math]\displaystyle{ Y }[/math]. Dla naszych danych mielibyśmy modulo [math]\displaystyle{ 541 }[/math]

[math]\displaystyle{ 2^1 \equiv 2, \quad 2^2 \equiv 4, \; \ldots , \; 2^{17} \equiv 150, \quad 2^{18} \equiv 300 }[/math]

czyli wystarczyło jedynie 18 prób! Ale dla dwustucyfrowej liczby pierwszej [math]\displaystyle{ p }[/math] i trochę lepiej wybranych liczb [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] ilość prób będzie liczbą rzędu [math]\displaystyle{ 10^{50} }[/math]. Nawet dla najszybszych komputerów stanowi to barierę nie do pokonania.

Uwaga Q8
Realne zagrożenie pojawia się jedynie wtedy, gdy Agencja i Bolek nie sprawdzą autentyczności liczb [math]\displaystyle{ X }[/math] i [math]\displaystyle{ Y }[/math]. Przykładowo Agencja może zapytać o [math]\displaystyle{ 7 }[/math], [math]\displaystyle{ 23 }[/math], [math]\displaystyle{ 101 }[/math] itd. cyfrę liczby [math]\displaystyle{ X }[/math], którą otrzymał Bolek. Dlaczego jest to ważne? Jeżeli korespondencja (maile, listy) Agencji i Bolka jest kontrolowana przez Wywiad, to Wywiad może przechwycić liczby [math]\displaystyle{ X = R_p (g^a) }[/math] oraz [math]\displaystyle{ Y = R_p (g^b) }[/math] i wysłać im swoją liczbę [math]\displaystyle{ Z = R_p (g^c) }[/math]. Od tej pory korespondencja Agencji będzie przechwytywana, odszyfrowywana przez Wywiad kluczem [math]\displaystyle{ k_1 = R_p (g^{a c}) }[/math], czytana, ewentualnie zmieniana, ponownie szyfrowana kluczem [math]\displaystyle{ k_2 = R_p (g^{b c}) }[/math] i wysyłana do Bolka.

Analogicznie będzie kontrolowana korespondencja Bolka wysyłana do Agencji.

Szyfrowanie RSA

Uwaga Q9
Rozpoczniemy od dowodu kilku prostych twierdzeń. Łatwość ich sformułowania i dowodu zaskakuje, jeśli weźmiemy pod uwagę fakt, że stanowią one podstawę niezwykle ważnej metody szyfrowania.

Twierdzenie Q10
Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą, to dla dowolnego [math]\displaystyle{ a \in \mathbb{Z} }[/math] i każdego [math]\displaystyle{ k \geqslant 0 }[/math] jest

[math]\displaystyle{ a^{(p - 1) k + 1} \equiv a \!\! \pmod{p} }[/math]

Dowód

Jeżeli [math]\displaystyle{ p \mid a }[/math], to dowodzona kongruencja jest prawdziwa. Jeżeli [math]\displaystyle{ p \nmid a }[/math], to modulo [math]\displaystyle{ p }[/math] mamy

[math]\displaystyle{ a^{(p - 1) k + 1} = a \cdot (a^{p - 1})^k \equiv a \!\! \pmod{p} }[/math]

gdzie skorzystaliśmy z twierdzenia Fermata (J22).
□

Twierdzenie Q11
Jeżeli [math]\displaystyle{ p }[/math] i [math]\displaystyle{ q }[/math] są różnymi liczbami pierwszymi, to dla dowolnego [math]\displaystyle{ a \in \mathbb{Z} }[/math] i każdego [math]\displaystyle{ k \geqslant 0 }[/math] jest

[math]\displaystyle{ a^{k (p - 1) (q - 1) + 1} \equiv a \!\! \pmod{p q} }[/math]

Dowód

Z twierdzenia Q10 wiemy, że dla dowolnych liczb [math]\displaystyle{ i, j \geqslant 0 }[/math] prawdziwe są kongruencje

[math]\displaystyle{ a^{(p - 1) i + 1} \equiv a \!\! \pmod{p} }[/math]

[math]\displaystyle{ a^{(q - 1) j + 1} \equiv a \!\! \pmod{q} }[/math]

Dla dowolnego, ale ustalonego [math]\displaystyle{ k \geqslant 0 }[/math] wybierzmy liczby [math]\displaystyle{ i, j }[/math] następująco: [math]\displaystyle{ i = k (q - 1) }[/math] oraz [math]\displaystyle{ j = k (p - 1) }[/math]. Otrzymujemy

[math]\displaystyle{ a^{k (p - 1) (q - 1) + 1} \equiv a \!\! \pmod{p} }[/math]

[math]\displaystyle{ a^{k (p - 1) (q - 1) + 1} \equiv a \!\! \pmod{q} }[/math]

Z twierdzenia J1 wiemy, że powyższy układ kongruencji może być zapisany w sposób równoważny

[math]\displaystyle{ a^{k (p - 1) (q - 1) + 1} \equiv a \!\! \pmod{p q} }[/math]

Co należało pokazać.
□

Uwaga Q12 (metoda szyfrowania RSA)
RSA to akronim od nazwisk twórców tej metody: Rona Rivesta, Adiego Shamira i Leonarda Adlemana. Rozpoczniemy od wypisania używanych oznaczeń, co znakomicie ułatwi zrozumienie opisu metody.

1. [math]\displaystyle{ p, q }[/math] – dwie duże liczby pierwsze o zbliżonych wartościach
   • często przyjmuje się, że [math]\displaystyle{ p \lt q \lt 2 p }[/math]; można też przyjąć, że [math]\displaystyle{ q \sim 2 p }[/math]
2. [math]\displaystyle{ m = p q }[/math]
3. [math]\displaystyle{ \Phi = (p - 1) (q - 1) }[/math]
   • oznaczenie nawiązuje do funkcji Eulera [math]\displaystyle{ \varphi }[/math], bo [math]\displaystyle{ \varphi (m) = \varphi (p q) = (p - 1) (q - 1) }[/math]
4. [math]\displaystyle{ e }[/math] (ang. encryption) – wykładnik służący do szyfrowania (publiczny)
5. [math]\displaystyle{ d }[/math] (ang. decryption) – wykładnik służący do odszyfrowania (tajny)
6. [math]\displaystyle{ B }[/math] (ang. block of digits) – wiadomość w postaci liczby (ciągu cyfr) przeznaczona do zaszyfrowania
7. [math]\displaystyle{ C }[/math] (ang. coded block of digits) – zaszyfrowana wiadomość, czyli liczba powstała w wyniku szyfrowania liczby [math]\displaystyle{ B }[/math]

Opis metody

1. Wybierzmy liczbę [math]\displaystyle{ e }[/math] tak, aby spełniała warunki [math]\displaystyle{ \gcd (e, \Phi) = 1 }[/math] i [math]\displaystyle{ 2 \lt e \lt \Phi }[/math]
   • zaleca się, aby [math]\displaystyle{ e \geqslant 65537 }[/math]
2. Z lematu Bézouta (zobacz C73) istnieją takie liczby całkowite [math]\displaystyle{ d }[/math] i [math]\displaystyle{ k }[/math], że [math]\displaystyle{ d e + k \Phi = 1 }[/math]. Liczbę [math]\displaystyle{ d }[/math] wyliczamy ze wzoru [math]\displaystyle{ d = d_0 + \Phi t }[/math], gdzie [math]\displaystyle{ d_0 }[/math] (oraz [math]\displaystyle{ k_0 }[/math]) otrzymujemy, wykorzystując w PARI/GP funkcję gcdext(e, Φ) (zobacz C78)
   • [math]\displaystyle{ d }[/math] wybieramy tak, aby była liczbą dodatnią, wtedy [math]\displaystyle{ k }[/math] musi być liczbą ujemną
   • [math]\displaystyle{ d }[/math] nie może być zbyt małą liczbą; pokazano, że powinno być [math]\displaystyle{ d \gt m^{0.292} }[/math]
3. Metoda szyfrowania RSA wymaga trzech liczb: [math]\displaystyle{ m }[/math], [math]\displaystyle{ e }[/math], [math]\displaystyle{ d }[/math]. Liczba [math]\displaystyle{ d }[/math] jest tajna. Podobnie tajne są liczby [math]\displaystyle{ p }[/math], [math]\displaystyle{ q }[/math], [math]\displaystyle{ \Phi }[/math], ale te liczby można po prostu skasować po wyliczeniu [math]\displaystyle{ d }[/math]
4. Szyfrowaną wiadomość przekształcamy w ciąg cyfr. W przypadku długich wiadomości może być konieczny podział ciągu cyfr na bloki. Tworzymy w ten sposób liczbę [math]\displaystyle{ B }[/math]. Zakładamy, że [math]\displaystyle{ B \lt m }[/math]
5. Szyfrowanie. Zakodowany tekst jest wynikiem operacji: [math]\displaystyle{ C = R_m (B^e) }[/math], gdzie [math]\displaystyle{ R_m (B^e) }[/math] oznacza resztę z dzielenia liczby [math]\displaystyle{ B^e }[/math] przez [math]\displaystyle{ m }[/math]
   • zauważmy, że: [math]\displaystyle{ C \equiv B^e \!\! \pmod{m} }[/math]
6. Odszyfrowanie. Odkodowany tekst otrzymujemy, obliczając: [math]\displaystyle{ B = R_m (C^d) }[/math]
7. Dowód poprawności metody wynika z twierdzenia Q12
   • [math]\displaystyle{ R_m (C^d) \equiv C^d \equiv (B^e)^d \equiv B^{e d} \equiv B^{- k \Phi + 1} \equiv B^{- k (p - 1) (q - 1) + 1} \equiv B \!\! \pmod{m} }[/math]
   • ponieważ [math]\displaystyle{ k \lt 0 }[/math], to [math]\displaystyle{ - k }[/math] jest liczbą dodatnią i możemy zastosować twierdzenie Q12
   • ponieważ [math]\displaystyle{ B \lt m }[/math], to [math]\displaystyle{ R_m (C^d) = B }[/math]
8. Para liczb [math]\displaystyle{ (m, e) }[/math] jest nazywana kluczem publicznym – służy do szyfrowania i może być dostępna dla każdego.
9. Para liczb [math]\displaystyle{ (m, d) }[/math] jest nazywana kluczem prywatnym – służy do odszyfrowania. Liczba [math]\displaystyle{ d }[/math] jest tajna – osoba, która ją wykradnie, będzie mogła odczytywać wysyłane do nas wiadomości

Przykład Q13
Prosty przykład: niech wysyłaną wiadomością będzie słowo [math]\displaystyle{ \text{YES} }[/math]. Zamianę liter na ciąg cyfr dokonamy, przypisując każdej literze jej numer w alfabecie np.: [math]\displaystyle{ A \longrightarrow 01 }[/math], [math]\displaystyle{ B \longrightarrow 02 }[/math], ... , [math]\displaystyle{ Z \longrightarrow 26 }[/math], czyli [math]\displaystyle{ \text{YES}\longrightarrow 250519 }[/math], zatem musimy zaszyfrować liczbę [math]\displaystyle{ 250519 }[/math].

Niech [math]\displaystyle{ p = 1009 }[/math], [math]\displaystyle{ q = 1013 }[/math], [math]\displaystyle{ e = 1019 }[/math]. Znajdujemy [math]\displaystyle{ m = p q = 1022117 }[/math], [math]\displaystyle{ \Phi = (p - 1) (q - 1) = 1020096 }[/math], [math]\displaystyle{ d = 397427 }[/math]. Klucz publiczny [math]\displaystyle{ (m, e) }[/math], klucz prywatny [math]\displaystyle{ (m, d) }[/math]. Zaszyfrowana wiadomość to [math]\displaystyle{ R_m (250519^e) = 560222 }[/math]. Odszyfrowując, otrzymujemy [math]\displaystyle{ R_m (560222^d) = 250519 }[/math]. Tak, jak być powinno.

Uwaga Q14
Bezpieczeństwo metody polega na wyborze tak dużych liczb pierwszych [math]\displaystyle{ p }[/math] i [math]\displaystyle{ q }[/math], aby faktoryzacja ich iloczynu [math]\displaystyle{ m }[/math] leżała poza możliwościami współczesnych komputerów i stosowanych algorytmów. Choć klucz publiczny [math]\displaystyle{ (m, e) }[/math] służący do szyfrowania nie jest tajny i może być udostępniany wszystkim, to poznanie klucza prywatnego, czyli liczby [math]\displaystyle{ d }[/math], jest praktycznie niemożliwe.

Liczba [math]\displaystyle{ d }[/math] wynika z rozwiązania równania [math]\displaystyle{ d e + k \Phi = 1 }[/math], ale aby obliczyć [math]\displaystyle{ \Phi = (p - 1) (q - 1) }[/math] musimy znać rozkład liczby [math]\displaystyle{ m }[/math] na czynniki pierwsze. Obecnie nie istnieją dostatecznie szybkie sposoby znajdowania rozkładu dużych liczb na czynniki pierwsze. Możemy łatwo sprawdzić, czy liczba [math]\displaystyle{ m = p q }[/math] jest liczbą złożoną, ale jeśli tak jest, to poznanie jej czynników jest dla dostatecznie dużych [math]\displaystyle{ m }[/math] niemożliwe.

Uwaga Q15 (generowanie liczb [math]\displaystyle{ m, e, d }[/math])
Przyjmując proste założenia co do liczb pierwszych [math]\displaystyle{ p, q }[/math] (przyjęliśmy, że [math]\displaystyle{ 1.8 p \lt q \lt 2.2 p }[/math]) oraz zakładając, że [math]\displaystyle{ d \gt m^{2 / 3} }[/math] napisaliśmy prosty program do generowania klucza publicznego i prywatnego. Parametr w określa, ile cyfr w układzie dziesiętnym będą miały liczby [math]\displaystyle{ p, q }[/math]. Wybór w > 500 gwarantuje wygenerowanie liczby [math]\displaystyle{ m }[/math], której rozkład na czynniki pierwsze nie powinien być możliwy przez wiele lat. Ostatnie (znane) osiągnięcie faktoryzacji, to rozkład 250-cyfrowej liczby [math]\displaystyle{ m = p q }[/math] na czynniki pierwsze.

Pokaż kod

RSAkeys(w) = 
\\ parametr w > 1 określa, ile cyfr w układzie dziesiętnym będą miały liczby p, q
{
local(d, e, m, p, Phi, q);
setrand(getwalltime());  \\ ustawiamy ziarno (ang. seed) generatora liczb losowych
p = 1;
q = 0;
while( !isprime(p)  ||  !isprime(q),
       while( q < 1.8 * p  ||  q > 2.2 * p, 
              p = randomprime( [10^(w - 1), 10^w] ); 
              q = randomprime( [10^(w - 1), 10^w] );
            );
     );
m = p * q;
Phi = (p - 1) * (q - 1);
d = -1;
while( d < m^(2/3), 
       e = randomprime( [10^10, 10^15] );
       if( gcd(e, Phi) > 1, next() );
       d = gcdext(e, Phi)[1];
     );
return([m, e, d]);
}

PrintRSAkeys(w) = 
{
local(V);
V = RSAkeys(w);
print("m = ", V[1]);
print("e = ", V[2]);
print("d = ", V[3]);
}

Uwaga Q16 (zamiana tekstu na liczbę i odwrotnie)
W przypadku profesjonalnych programów szyfrujących wykorzystujących metodę RSA szyfrowany jest cały plik, który jest przecież ciągiem zer i jedynek. Oprogramowanie dzieli taki plik na odpowiednich rozmiarów bloki [math]\displaystyle{ B_j }[/math] i każdy jest szyfrowany kluczem publicznym [math]\displaystyle{ (m, e) }[/math]. Możemy w ten sposób szyfrować zdjęcia, filmy, tekst w dowolnym języku itd.

Ponieważ napisanie takiego oprogramowania wykraczałoby poza potrzeby tego omówienia, ale z drugiej strony chcemy udostępnić Czytelnikowi przykłady bardziej skomplikowane niż szyfrowanie słowa [math]\displaystyle{ \text{YES} }[/math], to postanowiliśmy ograniczyć się do szyfrowania tekstu, który zawiera jedynie znaki ASCII.

Aby efektywnie korzystać z szyfrowania RSA potrzebne będą nam programy, które przetworzą taki tekst na liczbę i odwrotnie. Poniżej przedstawiamy dwie bardzo proste funkcje: pierwsza funkcja zamienia znaki ASCII od 32 do 126 na liczbę (każdemu znakowi przypisywane są dwie cyfry), a druga funkcja zamienia wygenerowaną przez pierwszą funkcję liczbę na odpowiadający tej liczbie tekst.

Założenie, że nasza wiadomość zawiera tylko znaki ASCII od 32 do 126, jest bardzo ważne. Oznacza to, że taki tekst przetworzony przez funkcję TextToNumber() na liczbę, zostanie odtworzony przez funkcję NumberToText() w niezmienionej postaci. Nie będzie tak, jeśli wystąpią inne znaki: każdy z takich znaków zostanie zamieniony na spacje (np. każda polska litera zostanie zamieniona na dwie spacje). Nie oznacza to, że nie można korzystać z tych funkcji, ale jeśli szyfrujemy podpisaną wiadomość, to zgodność tekstów ma zasadnicze znaczenie.

Pokaż kod

TextToNumber( s ) = 
\\ zamienia znaki ASCII od 32 do 126 na liczbę
{
local(a, b, k, len, txt, V);
V = Vecsmall(s);
len = length(V);
txt = "";
k = 0;
while( k++ <= len,
       a = V[k];
       b = "01";  \\ spacja – wstawiamy jeżeli a jest poza zakresem
       if( a >= 32  &&  a <= 40, b = Str("0", a - 31) );
       if( a >= 41  &&  a <= 126, b = Str(a - 31) );
       txt = Str(txt, b);
     );
return( eval(txt) );
}

NumberToText( n ) = 
{
local(a, k, len, txt, V);
len = length(Str(n));
if( len % 2 == 1, len++ ); \\ "zgubione" zero na początku
len = len / 2;
V = vector(len);
k = len + 1;
while( k-- >= 1,
       a = n % 100;
       n = floor(n / 100);
       V[k] = a + 31;
     );
txt = strchr(V);
return(txt);
}

Uwaga Q17
Jeżeli mamy już funkcje zamieniające tekst na liczbę i odwrotnie, to napisanie w PARI/GP programów do szyfrowania i deszyfrowania metodą RSA jest bardzo proste.

Pokaż kod

RSAencode(m, e, s) = 
\\ szyfrujemy string s
{
local(B, C);
B = TextToNumber(s);
C = lift( Mod(B, m)^e );
print(C);
}

RSAdecode(m, d, C) = 
\\ deszyfrujemy liczbę C
{
local(B, s);
B = lift( Mod(C, m)^d );
s = NumberToText(B);
print(s);
}

Przykład Q18
Kładąc w = 50 w funkcji RSAkeys(w) otrzymaliśmy

m = 2173471545652309346779542101680852446325835148920429701148920590128959176663355134192839060494750117
e = 3675359337253
d = 308186586218659991253427464678921309369969889382350078327142348395702895999753492453847408362677933

Liczba m ma 100 cyfr. Podamy teraz prosty przykład z polskimi literami. Zakodujemy i odkodujemy tekst (35 znaków)

Lepszy na wolności kęsek lada jaki.

Zamieniając tekst na liczbę – funkcją TextToNumber(s) – otrzymujemy liczbę 74-cyfrową

B = 45708184919001796601888077798001016874017601018470760177666966017566767415

Jest tak, bo każdy znak tekstu został zamieniony na dwie cyfry, ale każda z polskich liter "ś" i "ę" została zamieniona na dwie spacje i każdej z tych liter odpowiadają cztery cyfry "0101". Zauważmy, że B < m tak, jak być powinno.

Korzystając z funkcji RSAencode(m, e, s), dostajemy od razu zakodowany tekst

C = 1883258467778511884133977054466089742750188942420326552221154007622797635139655819975338109849673552

Po odkodowaniu funkcją RSAdecode(m, d, C), otrzymujemy

Lepszy na wolno  ci k  sek lada jaki.

Polskie litery zostały zastąpione przez dwie spacje.

Czytelnikowi pozostawiamy odszyfrowanie podanej niżej zakodowanej wiadomości. Ze względu na rozmiar musieliśmy podzielić tekst i otrzymaliśmy trzy zakodowane bloki.

C₁ = 1228411078235780067165277802337600665865387220034514894292654793454492777859429937501850347835450261
C₂ = 1212270919532485597119464911345613794658433495925582794819870422454753698249874400827689168074862675
C₃ = 1407997868763350498310642273976637553443290951270357250985396471705600151258961305510222246198960667

Uwaga Q19
Omówiliśmy dokładnie metodę szyfrowania RSA i Czytelnik powinien mieć już jasność, że metodą tą możemy szyfrować tylko liczby. Jeśli chcemy zaszyfrować tekst, to musi najpierw zostać zapisany w postaci liczby (ciągu cyfr). Podaliśmy też dwie proste metody takiej zamiany (zobacz Q13 i Q16).

W dalszej części artykułu pisząc o szyfrowaniu metodą RSA, będziemy mieli najczęściej na myśli dwie czynności wykonywanie łącznie: zamianę tekstu na liczbę (ustaloną wcześniej metodą) i właściwą operację szyfrowania. Podobnie pisząc o odszyfrowaniu, też zazwyczaj będziemy mieli myśli dwie czynności: właściwą operację odszyfrowywania i zamianę otrzymanej liczby na tekst.

Uwaga Q20
Zwróćmy uwagę na to, że w przypadku pomyłki i zaszyfrowania wiadomości naszym kluczem prywatnym [math]\displaystyle{ (m, d) }[/math] możliwe będzie jej odczytanie przez każdą osobę, która zna nasz klucz publiczny [math]\displaystyle{ (m, e) }[/math]. Istotnie, niech [math]\displaystyle{ C = R_m (B^d) }[/math]. Łatwo pokażemy, że [math]\displaystyle{ B = R_m (C^e) }[/math].

[math]\displaystyle{ R_m (C^e) \equiv C^e \equiv (B^d)^e \equiv B^{e d} \equiv B^{- k \Phi + 1} \equiv B^{- k (p - 1) (q - 1) + 1} \equiv B \!\! \pmod{m} }[/math]

Fakt ten wykorzystamy do stworzenia podpisu wiadomości.

Kryptograficzne funkcje haszujące

Definicja Q21
Funkcja haszująca przypisuje każdemu ciągowi bitów o dowolnej (ale skończonej) długości ciąg bitów o stałej długości.

Przykład Q22
Bardzo prosta funkcja haszująca przypisuje każdemu ciągowi osiem pierwszych bitów tego ciągu (w przypadku, gdy ciąg jest za krótki, wystarczy powtórzyć go odpowiednią liczbę razy). Tak określona funkcja nie jest dobrą funkcją haszującą i ze wszystkich wymagań (które wymienimy niżej) spełnia tylko jeden: możemy szybko obliczyć wynik.

Innym przykładem funkcji haszującej może być funkcja, która oblicza sumę kodów ASCII kolejnych znaków modulo [math]\displaystyle{ 256 }[/math]. Ta funkcja, podobnie jak poprzednia, jedynie szybko oblicza wynik.

Druga funkcja jest lepsza od pierwszej, bo każdy znak tekstu wpływa na uzyskany wynik. Co prawda ciągi znaków, których suma kodów ASCII wynosi 256 (np. "8dd") możemy dodawać bezkarnie, jednak uwzględniając, że wiadomość nie jest ciągiem przypadkowych znaków, modyfikacja wiadomości tak, aby hasz pozostał niezmieniony, będzie wymagała pewnego wysiłku.

Uwaga Q23
Od dobrej funkcji haszującej oczekujemy, że będzie spełniała następujące warunki

• będzie szybko obliczać wynik
• (jednokierunkowość) dla zadanej wartości hasza [math]\displaystyle{ h }[/math] znalezienie jakiegokolwiek ciągu bitów [math]\displaystyle{ m }[/math] takiego, że [math]\displaystyle{ h = \mathop{\text{hash}}(m) }[/math] powinno być bardzo trudne
• (słaba odporność na kolizje) dla zadanego ciągu bitów [math]\displaystyle{ m_1 }[/math] znalezienie jakiegokolwiek ciągu bitów [math]\displaystyle{ m_2 \neq m_1 }[/math] takiego, że [math]\displaystyle{ \mathop{\text{hash}}(m_2) = \mathop{\text{hash}}(m_1) }[/math] powinno być bardzo trudne
• (silna odporność na kolizje) znalezienie jakichkolwiek dwóch ciągów bitów [math]\displaystyle{ m_1 }[/math] i [math]\displaystyle{ m_2 }[/math] takich, że [math]\displaystyle{ \mathop{\text{hash}}(m_1) = \mathop{\text{hash}}(m_2) }[/math] powinno być bardzo trudne

W praktyce oznacza to, że jeżeli dwa łańcuchy mają taki sam hasz, to są one identyczne. To właśnie ta własność decyduje o przydatności funkcji haszującej dla podpisu elektronicznego i innych zastosowań.

Przykład Q24 (zastosowanie funkcji haszujących)
Jeśli chcemy upewnić się, czy przesłana mailem wiadomość nie zastała zmieniona, to wystarczy, że telefonicznie podamy odbiorcy hasz wiadomości.

Hasło podawane przy logowaniu powinno być haszowane, a system powinien przechowywać jedynie hasz hasła tak, aby samo hasło pozostawało nikomu nieznane.

Udostępniając do pobrania plik, możemy udostępnić również jego hasz. Umożliwi to łatwe sprawdzenie użytkownikowi, czy pobrany plik nie został uszkodzony.

Uwaga Q25 (przykłady funkcji haszujących)
Istnieje wiele wykorzystywanych w praktyce funkcji haszujących. Najbardziej znane to: CRC, MD5, SHA-1 oraz funkcje ze standardu SHA-2: SHA-224, SHA-256, SHA-384, SHA-512

Linux udostępnia wypisane wyżej funkcje jako cksum (CRC), md5sum, sha1sum, sha224sum, sha256sum, sha384sum, sha512sum.

Na stronie GitHub – Online Tools znajdziemy wiele funkcji haszujących. Możemy policzyć wartości wybranej funkcji dla dowolnego tekstu i dla plików. Zauważmy, że wiele edytorów tekstu automatycznie dodaje znak końca linii (LF) o kodzie ASCII równym 10 (szesnastkowo 0a) na końcu pliku. Może to powodować różnice przy obliczaniu hasza dla tekstu i dla pliku tekstowego zawierającego ten sam tekst.

Przykład Q26
Dla przykładu rozważmy, często używaną, funkcję haszującą SHA-256. Generuje ona 256-bitowy hasz, który zapisujemy, podając 64 cyfry w zapisie szesnastkowym. Każdą cyfrę w układzie szesnastkowym można zapisać w postaci 4 zer i jedynek w układzie dwójkowym (czterech bitów).

[math]\displaystyle{ 0 = 0000, \ldots, 9 = 1001, a = 1010, \ldots, f = 1111 }[/math]

Dla tekstu

Polskie litery i cyfry: ąćęłńóśźżĄĆĘŁŃÓŚŹŻ 0123456789

otrzymujemy hasz

5a86397d5e16611466e82376cc9f4d367ecbcd4af6d4418a5d3a130e8ad9d98d

Czytelnik powinien zwrócić uwagę, że nawet niewielka zmiana tekstu (np. zmiana lub dodanie jednego znaku) spowoduje wygenerowanie zupełnie innego hasza.

Podpisywanie dokumentów jawnych

Uwaga Q27
Zauważmy, że przekazywanie wiadomości (jawnych lub nie) wymaga wcześniejszego ustalenia sposobu komunikowania się. Może to być konto mailowe (jawne lub używane tylko do kontaktów tajnych), umówiona skrytka itd. Wynika stąd, że odbiorca zawsze zna nadawcę (wie, od kogo otrzymał przesyłkę).

Ponieważ musimy liczyć się z tym, że ustalony kanał łączności może zostać przejęty, a przekaz zmieniony, to stosujemy różnego rodzaju zabezpieczenia, których celem jest ochrona integralności przekazu.

Uwaga Q28
Powiedzmy, że Bolek chce przekazać ważny dokument do Urzędu. Jednak Urząd chce mieć pewność, że tak ważny dokument rzeczywiście sporządził Bolek, a nie ktoś inny, kto tylko pod Bolka się podszywa. Oczywiście można taki dokument przekazać osobiście, ale co zrobić w sytuacji, gdy jest to niemożliwe, a dostępny jest internet?

Jeśli Bolek potrafi szyfrować wiadomości metodą RSA i udostępnił swój klucz publiczny [math]\displaystyle{ (m, e) }[/math] Urzędowi, to może postąpić następująco

1. sporządzić ów ważny dokument (powiedzmy DokB) w postaci pliku (ewentualnie papierowy dokument zeskanować)
2. obliczyć hasz pliku DokB: [math]\displaystyle{ \; h_B = \mathop{\text{SHA256}}( \text{DokB} ) }[/math]
3. zaszyfrować hasz [math]\displaystyle{ h_B }[/math] swoim kluczem prywatnym [math]\displaystyle{ (m, d) }[/math] (zobacz Q20)
   • zaszyfrowany hasz [math]\displaystyle{ h_B }[/math] jest podpisem Bolka (co za chwilę stanie się jasne)
4. tak zaszyfrowany hasz wpisać w treści maila i załączyć plik DokB

Jak przebiega weryfikacja odebranej wiadomości?

1. Urząd odbiera mail od Bolka i pobiera załącznik (nazwijmy go DokU, bo nie wiemy, czy nie został zmieniony)
2. Urząd oblicza hasz załączonego pliku DokU: [math]\displaystyle{ \; h_U = \mathop{\text{SHA256}}( \text{DokU} ) }[/math]
3. kluczem publicznym Bolka Urząd odszyfrowuje otrzymany w mailu zaszyfrowany hasz [math]\displaystyle{ h_B }[/math] (zobacz Q20)
4. z równości [math]\displaystyle{ h_B = h_U }[/math] wynika, że dokumenty DokB i DokU są identyczne (zobacz Q23)

Jest tak, ponieważ z równości [math]\displaystyle{ h_B = h_U }[/math] wynika, że zaszyfrowany hasz [math]\displaystyle{ h_B }[/math] musiał pochodzić od Bolka, bo został zaszyfrowany jego kluczem prywatnym, do którego nikt, poza nim, nie ma dostępu. Dlatego zaszyfrowany kluczem prywatnym Bolka hasz [math]\displaystyle{ h_B }[/math] jest tym samym, co jego podpis i potwierdza to, że plik DokB (którego hasz jest równy [math]\displaystyle{ h_B }[/math]) został sporządzony przez Bolka.

Ujmując inaczej, każdy może przedstawić się w mailu jako Bolek, dołączyć spreparowany plik, policzyć hasz tego pliku, ale nie będzie w stanie zaszyfrować tego hasza kluczem prywatnym Bolka, bo klucz ten jest tajny i niedostępny dla nikogo poza Bolkiem.

Podpisywanie dokumentów tajnych

Uwaga Q29
Powiedzmy, że Bolek ma ważną informację i chce ją przekazać do Agencji. Oczywiście informacji nie może przeczytać nikt inny, a Agencja musi mieć pewność, że źródłem tej ważnej informacji jest rzeczywiście Bolek, a nie ktoś inny, kto tylko pod Bolka się podszywa. Tym razem Bolek na pewno potrafi szyfrować wiadomości metodą RSA, a jego klucz publiczny [math]\displaystyle{ (m, e) }[/math] jest z pewnością znany Agencji. Co więcej, Bolek zna klucz publiczny Agencji [math]\displaystyle{ (M, E) }[/math], którego ma używać do komunikowania się z Agencją. W tym przypadku Bolek postępuje następująco

1. oblicza hasz wiadomości [math]\displaystyle{ h_B = \mathop{\text{SHA256}}( \text{tekst} ) }[/math]
2. szyfruje hasz [math]\displaystyle{ h_B }[/math] swoim kluczem prywatnym [math]\displaystyle{ (m, d) }[/math]
3. umieszcza zaszyfrowany hasz [math]\displaystyle{ h_B }[/math] jako ostatnią linię tekstu wiadomości
4. szyfruje całość (tekst wiadomości + zaszyfrowany hasz [math]\displaystyle{ h_B }[/math]) kluczem publicznym Agencji [math]\displaystyle{ (M, E) }[/math]
5. umieszcza cały zaszyfrowany tekst w pliku i wysyła jako załącznik maila do Agencji

Agencja

1. pobiera załącznik
2. tekst z załącznika odszyfrowuje kluczem prywatnym Agencji [math]\displaystyle{ (M, D) }[/math]
3. z ostatniej linii pliku odczytuje zaszyfrowany hasz [math]\displaystyle{ h_A }[/math] tekstu otrzymanej wiadomości
4. deszyfruje hasz [math]\displaystyle{ h_A }[/math] wiadomości kluczem publicznym Bolka [math]\displaystyle{ (m, e) }[/math]
5. oblicza hasz [math]\displaystyle{ h_B }[/math] wiadomości od Bolka
6. równość [math]\displaystyle{ h_B = h_A }[/math] potwierdza, że wiadomość nie została zmieniona i przekazał ją do Agencji Bolek

Zauważmy, że klucz publiczny Agencji może być wiedzą poufną, ale z pewnością nie jest tak dobrze strzeżony, jak klucze prywatne. Agencja nie może zakładać, że zaszyfrowany jej kluczem publicznym plik nie został spreparowany. Dopiero po odszyfrowaniu pliku, obliczeniu hasza wiadomości i potwierdzenia zgodności tego hasza z haszem zapisanym w ostatniej linii pliku (który został zaszyfrowany kluczem prywatnym Bolka) Agencja ma pewność, że plik stworzył i wysłał Bolek.

Uwaga Q30
Zwróćmy uwagę, że jeżeli korzystamy z funkcji TextToNumber() i NumberToText() (zobacz Q16), a jednocześnie chcemy podpisywać szyfrowane wiadomości, to wiadomości nie mogą zawierać znaków innych niż znaki ASCII od 32 do 126.

Jest tak dlatego, że funkcja TextToNumber() zgubi informację o innych znakach w wiadomości, a funkcja NumberToText() już tej informacji nie odtworzy. Zatem hasz wysyłanej wiadomości i hasz otrzymanej wiadomości (po odszyfrowaniu) nigdy nie będą identyczne w przypadku użycia znaków innych niż znaki ASCII od 32 do 126.