Tekst źródłowy strony Protokół Diffiego-Hellmana. Szyfrowanie RSA. Podpis cyfrowy

<div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">22.11.2023</div>

__FORCETOC__



== Protokół Diffiego-Hellmana ==

<span style="font-size: 110%; font-weight: bold;">Uwaga Q1</span><br/>
Metoda ta została opracowana przez W. Diffiego i&nbsp;M. Hellmana<ref name="DiffieHellman1"/><ref name="DiffieHellman2"/> w 1976 roku. Opisana niżej procedura nie jest metodą szyfrowania i&nbsp;z&nbsp;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&nbsp;odczytywać wiadomości wybraną metodą szyfrowania. Przedstawimy w&nbsp;punktach procedurę postępowania wraz z&nbsp;przykładowymi danymi.

::1. Agencja i&nbsp;Bolek wybierają (jawną) liczbę pierwszą <math>p = 541</math> i (jawną) liczbę <math>g = 2</math><ref name="generator1"/>

::2. Agencja ustala (tajny, znany tylko sobie) wykładnik <math>a = 2718</math>

::3. Bolek ustala (tajny, znany tylko sobie) wykładnik <math>b = 3141</math>

::4. Agencja oblicza (jawną) liczbę <math>X = R_p (g^a) = 300</math> i&nbsp;wysyła ją do Bolka

::5. Bolek oblicza (jawną) liczbę <math>Y = R_p (g^b) = 191</math> i&nbsp;wysyła ją do Agencji

::6. Agencja oblicza (tajną) liczbę <math>k_A = R_p (Y^a) = 493</math>

::7. Bolek oblicza (tajną) liczbę <math>k_B = R_p (X^b) = 493</math>

::8. Modulo <math>p</math> mamy

::::<math>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&nbsp;definicji liczby <math>k_A, k_B \in [0, p - 1]</math>, zatem <math>0 \leqslant | k_A - k_B | \leqslant p - 1</math>. Ponieważ liczby <math>k_A, k_B</math> przystają do siebie modulo <math>p</math>, to muszą być sobie równe, czyli liczba <math>k = k_A = k_B</math> jest poszukiwanym kluczem.



<span style="font-size: 110%; font-weight: bold;">Uwaga Q2</span><br/>
Liczby <math>a</math> i <math>b</math> mogą być losowo wybranymi liczbami dodatnimi nie większymi od <math>p</math>. Istotnie, jeżeli <math>a = k \cdot (p - 1) + r</math>, to

::<math>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>a = 18</math> oraz <math>b = 441</math> otrzymując te same rezultaty. W&nbsp;praktyce ten problem nie występuje, bo gdy liczba pierwsza <math>p</math> ma co najmniej sto cyfr, to trudno wybrać jeszcze większy wykładnik.



<span style="font-size: 110%; font-weight: bold;">Przykład Q3</span><br/>
Zobaczmy, jak wpłynie na protokół zmiana liczby <math>g</math>. Niech <math>p = 541</math> i <math>g = 15</math>.

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{a}</math> || <math>\boldsymbol{b}</math> || <math>\boldsymbol{R_p(g^a)}</math> || <math>\boldsymbol{R_p(g^b)}</math> || <math>\boldsymbol{R_p(g^{a b})}</math>
|-
| <math>2985</math> || <math>4683</math> || <math>411</math> || <math>129</math> || <math>1</math>
|-
| <math>4270</math> || <math>8998</math> || <math>312</math> || <math>214</math> || <math>15</math>
|-
| <math>9749</math> || <math>3921</math> || <math>225</math> || <math>411</math> || <math>129</math>
|-
| <math>8993</math> || <math>6479</math> || <math>225</math> || <math>505</math> || <math>214</math>
|-
| <math>2146</math> || <math>8663</math> || <math>312</math> || <math>352</math> || <math>225</math>
|-
| <math>9941</math> || <math>6182</math> || <math>352</math> || <math>505</math> || <math>312</math>
|-
| <math>8944</math> || <math>8120</math> || <math>214</math> || <math>225</math> || <math>352</math>
|-
| <math>2928</math> || <math>9314</math> || <math>129</math> || <math>505</math> || <math>411</math>
|-
| <math>7436</math> || <math>3172</math> || <math>225</math> || <math>312</math> || <math>505</math>
|}

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

::<math>\{ g^1, g^2, g^3, \ldots, g^{p - 1} \}</math>

rozpatrywany modulo <math>p</math> jest identyczny ze zbiorem

::<math>\{ 1, 2, 3, \ldots, p - 1 \}</math>

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

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



<span style="font-size: 110%; font-weight: bold;">Twierdzenie Q4</span><br/>
Niech <math>p = 2 q + 1</math> będzie liczbą pierwszą, gdzie <math>q \geqslant 3</math> jest również liczbą pierwszą. Jeżeli <math>g</math> jest liczbą niekwadratową modulo <math>p</math> i <math>g \not\equiv - 1 \!\! \pmod{p}</math>, to <math>g</math> jest generatorem modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Dowód jest na tyle prosty i&nbsp;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>\varphi (p - 1)</math> różnych generatorów modulo <math>p</math>, gdzie <math>\varphi</math> jest funkcją Eulera<ref name="funkcjaphi1"/>. Funkcja Eulera <math>\varphi (n)</math> jest równa ilości liczb całkowitych dodatnich nie większych od <math>n</math> i&nbsp;względnie pierwszych z <math>n</math>.

'''Komentarz 2.'''

Udowodnimy, że jeżeli <math>g</math> jest generatorem modulo <math>p</math>, to <math>g</math> jest liczbą niekwadratową modulo <math>p</math>.

Przypuśćmy, że <math>g</math> jest liczbą kwadratową modulo <math>p</math>, zatem (zobacz J31)

::<math>g^{(p - 1) / 2} \equiv 1 \!\! \pmod{p}</math>

Wynika stąd, że zbiór

::<math>S = \{ g^1, g^2, g^3, \ldots, g^{p - 1} \}</math>

::<math>\;\;\,\, = \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>p</math> ze zbiorem

::<math>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>\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>p</math> ze zbiorem <math>T = \{ 1, 2, 3, \ldots, p - 1 \}</math>, bo <math>S'</math> zawiera co najwyżej połowę elementów zbioru <math>T</math>. Uzyskana sprzeczność dowodzi, że generator musi być liczbą niekwadratową modulo <math>p</math>.

'''Komentarz 3.'''

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

'''Komentarz 4.'''

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

:* wszystkie liczby parzyste <math>2, 4, 6, \ldots, 2 p - 2</math> mają z&nbsp;liczbą <math>2 p</math> wspólny dzielnik równy <math>2</math> i&nbsp;nie mogą być względnie pierwsze z&nbsp;liczbą <math>2 p</math> 
:* wszystkie liczby nieparzyste <math>1, 3, 5, \ldots, 2 p - 1</math> (których jest <math>p</math>) są względnie pierwsze z&nbsp;liczbą <math>2 p</math>, poza liczbą nieparzystą <math>p</math>, która nie jest względnie pierwsza z&nbsp;liczbą <math>2 p</math>


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

::<math>\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>p \geqslant 5</math> liczba <math>- 1</math> nie jest generatorem modulo <math>p</math>. Ponieważ <math>(- 1)^n = \pm 1</math>, to zbiór potęg

::<math>\{ g^1, g^2, g^3, \ldots, g^{p - 1} \}</math>

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


Ilość generatorów modulo <math>p</math> dla liczby pierwszej <math>p = 2 q + 1</math> jest równa

::<math>\varphi (p - 1) = \varphi (2 q) = q - 1 = {\small\frac{p - 1}{2}} - 1</math>

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



<span style="font-size: 110%; font-weight: bold;">Uwaga Q5</span><br/>
Jeśli nie potrzebujemy wyliczyć najmniejszego generatora modulo <math>p = 2 q + 1</math>, to z&nbsp;twierdzenia Q4 można łatwo pokazać, że liczba <math>- 4</math> jest generatorem dla wszystkich liczb pierwszych <math>p = 2 q + 1 \geqslant 7</math>, a&nbsp;liczba <math>- 3</math> dla wszystkich liczb pierwszych <math>p = 2 q + 1 \geqslant 11</math>. Ponieważ <math>q = 2 k + 1</math>, to <math>p = 4 k + 3</math>.

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

::<math>\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>- 3</math> jest liczbą niekwadratową modulo <math>p</math>. Liczba <math>k</math> może być postaci <math>3 j, 3 j + 1, 3 j + 2</math>, co daje odpowiednio

::<math>k = 3 j \qquad \qquad \;\!\!\! p = 12 j + 3 \qquad \;\; q = 6 j + 1</math>

::<math>k = 3 j + 1 \qquad p = 12 j + 7 \qquad \;\; q = 6 j + 3</math>

::<math>k = 3 j + 2 \qquad p = 12 j + 11 \qquad q = 6 j + 5</math>

Pierwsza i&nbsp;druga postać liczby <math>k</math> nie jest możliwa, bo albo liczba <math>p</math>, albo liczba <math>q</math> byłyby liczbami złożonymi. Zatem

::<math>\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&nbsp;zadanie J47.



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

Należy zwrócić uwagę, że funkcje <code>ispseudoprime()</code> i <code>randomprime()</code> 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>p</math> i <math>(p - 1) / 2</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
 <span style="font-size: 90%; color:black;">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]);
 }</span>
<br/>
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga Q7</span><br/>
Jak dalece bezpieczna jest opisana wyżej metoda? Aby znaleźć klucz trzeba oprócz (jawnych) liczb <math>p, g, X, Y</math> znać jedną z&nbsp;liczb <math>a</math> lub <math>b</math>. Liczba <math>a</math> spełnia kongruencję

::<math>g^a \equiv X \!\! \pmod{p}</math>

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

::<math>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>p</math> i&nbsp;trochę lepiej wybranych liczb <math>a</math> i <math>b</math> ilość prób będzie liczbą rzędu <math>10^{50}</math>. Nawet dla najszybszych komputerów stanowi to barierę nie do pokonania.



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

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





== Szyfrowanie RSA ==

<span style="font-size: 110%; font-weight: bold;">Uwaga Q9</span><br/>
Rozpoczniemy od dowodu kilku prostych twierdzeń. Łatwość ich sformułowania i&nbsp;dowodu zaskakuje, jeśli weźmiemy pod uwagę fakt, że stanowią one podstawę niezwykle ważnej metody szyfrowania.



<span style="font-size: 110%; font-weight: bold;">Twierdzenie Q10</span><br/>
Jeżeli <math>p</math> jest liczbą pierwszą, to dla dowolnego <math>a \in \mathbb{Z}</math> i&nbsp;każdego <math>k \geqslant 0</math> jest

::<math>a^{(p - 1) k + 1} \equiv a \!\! \pmod{p}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Jeżeli <math>p \mid a</math>, to dowodzona kongruencja jest prawdziwa. Jeżeli <math>p \nmid a</math>, to modulo <math>p</math> mamy

::<math>a^{(p - 1) k + 1} = a \cdot (a^{p - 1})^k \equiv a \!\! \pmod{p}</math>

gdzie skorzystaliśmy z&nbsp;twierdzenia Fermata (J22).<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie Q11</span><br/>
Jeżeli <math>p</math> i <math>q</math> są różnymi liczbami pierwszymi, to dla dowolnego <math>a \in \mathbb{Z}</math> i&nbsp;każdego <math>k \geqslant 0</math> jest

::<math>a^{k (p - 1) (q - 1) + 1} \equiv a \!\! \pmod{p q}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z twierdzenia Q10 wiemy, że dla dowolnych liczb <math>i, j \geqslant 0</math> prawdziwe są kongruencje

::<math>a^{(p - 1) i + 1} \equiv a \!\! \pmod{p}</math>

::<math>a^{(q - 1) j + 1} \equiv a \!\! \pmod{q}</math>

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

::<math>a^{k (p - 1) (q - 1) + 1} \equiv a \!\! \pmod{p}</math>

::<math>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&nbsp;sposób równoważny

::<math>a^{k (p - 1) (q - 1) + 1} \equiv a \!\! \pmod{p q}</math>

Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga Q12 (metoda szyfrowania RSA)</span><br/>
RSA<ref name="RSA1"/><ref name="RSA2"/> to akronim od nazwisk twórców tej metody: Rona Rivesta, Adiego Shamira i&nbsp;Leonarda Adlemana. Rozpoczniemy od wypisania używanych oznaczeń, co znakomicie ułatwi zrozumienie opisu metody.

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


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



<span style="font-size: 110%; font-weight: bold;">Przykład Q13</span><br/>
Prosty przykład: niech wysyłaną wiadomością będzie słowo <math>\text{YES}</math>. Zamianę liter na ciąg cyfr dokonamy, przypisując każdej literze jej numer w&nbsp;alfabecie np.: <math>A \longrightarrow 01</math>, <math>B \longrightarrow 02</math>, ... , <math>Z \longrightarrow 26</math>, czyli <math>\text{YES}\longrightarrow 250519</math>, zatem musimy zaszyfrować liczbę <math>250519</math>.

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



<span style="font-size: 110%; font-weight: bold;">Uwaga Q14</span><br/>
Bezpieczeństwo metody polega na wyborze tak dużych liczb pierwszych <math>p</math> i <math>q</math>, aby faktoryzacja ich iloczynu <math>m</math> leżała poza możliwościami współczesnych komputerów i&nbsp;stosowanych algorytmów. Choć klucz publiczny <math>(m, e)</math> służący do szyfrowania nie jest tajny i&nbsp;może być udostępniany wszystkim, to poznanie klucza prywatnego, czyli liczby <math>d</math>, jest praktycznie niemożliwe.

Liczba <math>d</math> wynika z&nbsp;rozwiązania równania <math>d e + k \Phi = 1</math>, ale aby obliczyć <math>\Phi = (p - 1) (q - 1)</math> musimy znać rozkład liczby <math>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>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>m</math> niemożliwe.



<span style="font-size: 110%; font-weight: bold;">Uwaga Q15 (generowanie liczb <math>m, e, d</math>)</span><br/>
Przyjmując proste założenia co do liczb pierwszych <math>p, q</math> (przyjęliśmy, że <math>1.8 p < q < 2.2 p</math>) oraz zakładając, że <math>d > m^{2 / 3}</math> napisaliśmy prosty program do generowania klucza publicznego i&nbsp;prywatnego. Parametr <code>w</code> określa, ile cyfr w&nbsp;układzie dziesiętnym będą miały liczby <math>p, q</math>. Wybór <code>w > 500</code> gwarantuje wygenerowanie liczby <math>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>m = p q</math> na czynniki pierwsze<ref name="RSA250"/>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
 <span style="font-size: 90%; color:black;">RSAkeys(w) = 
 \\ parametr w > 1 określa, ile cyfr w&nbsp;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]);
 }</span>

 <span style="font-size: 90%; color:black;">PrintRSAkeys(w) = 
 {
 '''local'''(V);
 V = RSAkeys(w);
 '''print'''("m = ", V[1]);
 '''print'''("e = ", V[2]);
 '''print'''("d = ", V[3]);
 }</span>
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga Q16 (zamiana tekstu na liczbę i&nbsp;odwrotnie)</span><br/>
W przypadku profesjonalnych programów szyfrujących wykorzystujących metodę RSA szyfrowany jest cały plik, który jest przecież ciągiem zer i&nbsp;jedynek. Oprogramowanie dzieli taki plik na odpowiednich rozmiarów bloki <math>B_j</math> i&nbsp;każdy jest szyfrowany kluczem publicznym <math>(m, e)</math>. Możemy w&nbsp;ten sposób szyfrować zdjęcia, filmy, tekst w&nbsp;dowolnym języku itd.

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

Aby efektywnie korzystać z&nbsp;szyfrowania RSA potrzebne będą nam programy, które przetworzą taki tekst na liczbę i&nbsp;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&nbsp;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ę <code>TextToNumber()</code> na liczbę, zostanie odtworzony przez funkcję <code>NumberToText()</code> w&nbsp;niezmienionej postaci. Nie będzie tak, jeśli wystąpią inne znaki: każdy z&nbsp;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&nbsp;tych funkcji, ale jeśli szyfrujemy '''podpisaną''' wiadomość, to zgodność tekstów ma zasadnicze znaczenie.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
 <span style="font-size: 90%; color:black;">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) );
 }</span>

 <span style="font-size: 90%; color:black;">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);
 }</span>
<br/>
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga Q17</span><br/>
Jeżeli mamy już funkcje zamieniające tekst na liczbę i&nbsp;odwrotnie, to napisanie w&nbsp;PARI/GP programów do szyfrowania i&nbsp;deszyfrowania metodą RSA jest bardzo proste.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
 <span style="font-size: 90%; color:black;">RSAencode(m, e, s) = 
 \\ szyfrujemy string s
 {
 '''local'''(B, C);
 B = TextToNumber(s);
 C = '''lift'''( '''Mod'''(B, m)^e );
 '''print'''(C);
 }</span>

 <span style="font-size: 90%; color:black;">RSAdecode(m, d, C) = 
 \\ deszyfrujemy liczbę C
 {
 '''local'''(B, s);
 B = '''lift'''( '''Mod'''(C, m)^d );
 s = NumberToText(B);
 '''print'''(s);
 }</span>
<br/>
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Przykład Q18</span><br/>
Kładąc <code>w = 50</code> w&nbsp;funkcji <code>RSAkeys(w)</code> otrzymaliśmy

m = 2173471545652309346779542101680852446325835148920429701148920590128959176663355134192839060494750117<br/>
e = 3675359337253<br/>
d = 308186586218659991253427464678921309369969889382350078327142348395702895999753492453847408362677933<br/>

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

''Lepszy na wolności kęsek lada jaki.''

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

B = 45708184919001796601888077798001016874017601018470760177666966017566767415

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

Korzystając z&nbsp;funkcji <code>RSAencode(m, e, s)</code>, dostajemy od razu zakodowany tekst

C = 1883258467778511884133977054466089742750188942420326552221154007622797635139655819975338109849673552

Po odkodowaniu funkcją <code>RSAdecode(m, d, C)</code>, otrzymujemy

''Lepszy na wolno&nbsp;&nbsp;ci k&nbsp;&nbsp;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&nbsp;otrzymaliśmy trzy zakodowane bloki.

C<sub>1</sub> = 1228411078235780067165277802337600665865387220034514894292654793454492777859429937501850347835450261<br/>
C<sub>2</sub> = 1212270919532485597119464911345613794658433495925582794819870422454753698249874400827689168074862675<br/>
C<sub>3</sub> = 1407997868763350498310642273976637553443290951270357250985396471705600151258961305510222246198960667<br/>



<span style="font-size: 110%; font-weight: bold;">Uwaga Q19</span><br/>
Omówiliśmy dokładnie metodę szyfrowania RSA i&nbsp;Czytelnik powinien mieć już jasność, że metodą tą możemy szyfrować tylko liczby. Jeśli chcemy zaszyfrować tekst, to musi najpierw zostać zapisany w&nbsp;postaci liczby (ciągu cyfr). Podaliśmy też dwie proste metody takiej zamiany (zobacz Q13 i&nbsp;Q16).

W dalszej części artykułu pisząc o&nbsp;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&nbsp;właściwą operację szyfrowania. Podobnie pisząc o&nbsp;odszyfrowaniu, też zazwyczaj będziemy mieli myśli dwie czynności: właściwą operację odszyfrowywania i&nbsp;zamianę otrzymanej liczby na tekst.



<span style="font-size: 110%; font-weight: bold;">Uwaga Q20</span><br/>
Zwróćmy uwagę na to, że w&nbsp;przypadku pomyłki i&nbsp;zaszyfrowania wiadomości naszym kluczem prywatnym <math>(m, d)</math> możliwe będzie jej odczytanie przez każdą osobę, która zna nasz klucz publiczny <math>(m, e)</math>. Istotnie, niech <math>C = R_m (B^d)</math>. Łatwo pokażemy, że <math>B = R_m (C^e)</math>.

::<math>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 ==

<span style="font-size: 110%; font-weight: bold;">Definicja Q21</span><br/>
Funkcja haszująca<ref name="hashfunction1"/> przypisuje każdemu ciągowi bitów o&nbsp;dowolnej (ale skończonej) długości ciąg bitów o&nbsp;stałej długości.



<span style="font-size: 110%; font-weight: bold;">Przykład Q22</span><br/>
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&nbsp;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>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.



<span style="font-size: 110%; font-weight: bold;">Uwaga Q23</span><br/>
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>h</math> znalezienie jakiegokolwiek ciągu bitów <math>m</math> takiego, że <math>h = \mathop{\text{hash}}(m)</math> powinno być bardzo trudne
:* (słaba odporność na kolizje) dla zadanego ciągu bitów <math>m_1</math> znalezienie jakiegokolwiek ciągu bitów <math>m_2 \neq m_1</math> takiego, że <math>\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>m_1</math> i <math>m_2</math> takich, że <math>\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&nbsp;przydatności funkcji haszującej dla podpisu elektronicznego i&nbsp;innych zastosowań.



<span style="font-size: 110%; font-weight: bold;">Przykład Q24 (zastosowanie funkcji haszujących)</span><br/>
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&nbsp;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.



<span style="font-size: 110%; font-weight: bold;">Uwaga Q25 (przykłady funkcji haszujących)</span><br/>
Istnieje wiele wykorzystywanych w&nbsp;praktyce funkcji haszujących. Najbardziej znane to: CRC<ref name="CRC"/>, MD5<ref name="MD5"/>, SHA-1<ref name="SHA1"/> oraz funkcje ze standardu SHA-2<ref name="SHA2"/>: 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 [https://emn178.github.io/online-tools/ GitHub – Online Tools] znajdziemy wiele funkcji haszujących. Możemy policzyć wartości wybranej funkcji dla dowolnego tekstu i&nbsp;dla plików. Zauważmy, że wiele edytorów tekstu automatycznie dodaje znak końca linii<ref name="konieclinii"/> (LF) o&nbsp;kodzie ASCII równym 10 (szesnastkowo 0a) na końcu pliku. Może to powodować różnice przy obliczaniu hasza dla tekstu i&nbsp;dla pliku tekstowego zawierającego ten sam tekst.



<span style="font-size: 110%; font-weight: bold;">Przykład Q26</span><br/>
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&nbsp;zapisie szesnastkowym. Każdą cyfrę w&nbsp;układzie szesnastkowym można zapisać w&nbsp;postaci 4 zer i&nbsp;jedynek w&nbsp;układzie dwójkowym (czterech bitów).

::<math>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 ==

<span style="font-size: 110%; font-weight: bold;">Uwaga Q27</span><br/>
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&nbsp;tym, że ustalony kanał łączności może zostać przejęty, a&nbsp;przekaz zmieniony, to stosujemy różnego rodzaju zabezpieczenia, których celem jest ochrona integralności przekazu.



<span style="font-size: 110%; font-weight: bold;">Uwaga Q28</span><br/>
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&nbsp;nie ktoś inny, kto tylko pod Bolka się podszywa. Oczywiście można taki dokument przekazać osobiście, ale co zrobić w&nbsp;sytuacji, gdy jest to niemożliwe, a&nbsp;dostępny jest internet?

Jeśli Bolek potrafi szyfrować wiadomości metodą RSA i&nbsp;udostępnił swój klucz publiczny <math>(m, e)</math> Urzędowi, to może postąpić następująco

:# sporządzić ów ważny dokument (powiedzmy DokB) w&nbsp;postaci pliku (ewentualnie papierowy dokument zeskanować)
:# obliczyć hasz pliku DokB: <math>\; h_B = \mathop{\text{SHA256}}( \text{DokB} )</math>
:# zaszyfrować hasz <math>h_B</math> swoim '''kluczem prywatnym''' <math>(m, d)</math> (zobacz Q20)
:#* zaszyfrowany hasz <math>h_B</math> jest podpisem Bolka (co za chwilę stanie się jasne)
:# tak zaszyfrowany hasz wpisać w&nbsp;treści maila i&nbsp;załączyć plik DokB


Jak przebiega weryfikacja odebranej wiadomości?

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


Jest tak, ponieważ z&nbsp;równości <math>h_B = h_U</math> wynika, że zaszyfrowany hasz <math>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>h_B</math> jest tym samym, co jego podpis i&nbsp;potwierdza to, że plik DokB (którego hasz jest równy <math>h_B</math>) został sporządzony przez Bolka.

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





== Podpisywanie dokumentów tajnych ==

<span style="font-size: 110%; font-weight: bold;">Uwaga Q29</span><br/>
Powiedzmy, że Bolek ma ważną informację i&nbsp;chce ją przekazać do Agencji. Oczywiście informacji nie może przeczytać nikt inny, a&nbsp;Agencja musi mieć pewność, że źródłem tej ważnej informacji jest rzeczywiście Bolek, a&nbsp;nie ktoś inny, kto tylko pod Bolka się podszywa. Tym razem Bolek na pewno potrafi szyfrować wiadomości metodą RSA, a&nbsp;jego klucz publiczny <math>(m, e)</math> jest z&nbsp;pewnością znany Agencji. Co więcej, Bolek zna klucz publiczny Agencji <math>(M, E)</math>, którego ma używać do komunikowania się z&nbsp;Agencją. W&nbsp;tym przypadku Bolek postępuje następująco

:# oblicza hasz wiadomości <math>h_B = \mathop{\text{SHA256}}( \text{tekst} )</math>
:# szyfruje hasz <math>h_B</math> swoim '''kluczem prywatnym''' <math>(m, d)</math>
:# umieszcza zaszyfrowany hasz <math>h_B</math> jako ostatnią linię tekstu wiadomości 
:# szyfruje całość (tekst wiadomości + zaszyfrowany hasz <math>h_B</math>) kluczem publicznym Agencji <math>(M, E)</math>
:# umieszcza cały zaszyfrowany tekst w&nbsp;pliku i&nbsp;wysyła jako załącznik maila do Agencji 

Agencja

:# pobiera załącznik
:# tekst z&nbsp;załącznika odszyfrowuje kluczem prywatnym Agencji <math>(M, D)</math>
:# z&nbsp;ostatniej linii pliku odczytuje zaszyfrowany hasz <math>h_A</math> tekstu otrzymanej wiadomości
:# deszyfruje hasz <math>h_A</math> wiadomości '''kluczem publicznym''' Bolka <math>(m, e)</math>
:# oblicza hasz <math>h_B</math> wiadomości od Bolka
:# równość <math>h_B = h_A</math> potwierdza, że wiadomość nie została zmieniona i&nbsp;przekazał ją do Agencji Bolek

Zauważmy, że '''klucz publiczny''' Agencji może być wiedzą poufną, ale z&nbsp;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&nbsp;potwierdzenia zgodności tego hasza z&nbsp;haszem zapisanym w&nbsp;ostatniej linii pliku (który został zaszyfrowany '''kluczem prywatnym''' Bolka) Agencja ma pewność, że plik stworzył i&nbsp;wysłał Bolek.



<span style="font-size: 110%; font-weight: bold;">Uwaga Q30</span><br/>
Zwróćmy uwagę, że '''jeżeli korzystamy''' z&nbsp;funkcji <code>TextToNumber()</code> i <code>NumberToText()</code> (zobacz Q16), a&nbsp;jednocześnie chcemy podpisywać szyfrowane wiadomości, to wiadomości '''nie mogą''' zawierać znaków innych niż znaki ASCII od&nbsp;32 do&nbsp;126.

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














== Przypisy ==

<references>

<ref name="DiffieHellman1">Whitfield Diffie and Martin E. Hellman, ''New Directions in Cryptography'', IEEE Transactions on Information Theory, Vol.&nbsp;22, No.&nbsp;6, 1976 ([https://ee.stanford.edu/~hellman/publications/24.pdf LINK])</ref>

<ref name="DiffieHellman2">Wikipedia, ''Protokół Diffiego-Hellmana'', ([https://pl.wikipedia.org/wiki/Protok%C3%B3%C5%82_Diffiego-Hellmana Wiki-pl]), ([https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange Wiki-en])</ref>

<ref name="generator1">Liczba <math>g</math> powinna (ale nie musi) być generatorem modulo <math>p</math>. Dlaczego tak jest, wyjaśnimy w&nbsp;dalszej części tekstu.</ref>

<ref name="funkcjaphi1">Wikipedia, ''Funkcja φ'', ([https://pl.wikipedia.org/wiki/Funkcja_%CF%86 Wiki-pl]), ([https://en.wikipedia.org/wiki/Euler%27s_totient_function Wiki-en])</ref>

<ref name="RSA1">R. Rivest, A. Shamir and L. Adleman, ''A Method for Obtaining Digital Signatures and Public-Key Cryptosystems'', Communications of the ACM, Volume 21, Issue 2, Feb. 1978, pp. 120-126</ref>

<ref name="RSA2">Wikipedia, ''RSA (kryptografia)'', ([https://pl.wikipedia.org/wiki/RSA_(kryptografia) Wiki-pl]), ([https://en.wikipedia.org/wiki/RSA_(cryptosystem) Wiki-en])</ref>

<ref name="BonehDurfee1">Dan Boneh and Glenn Durfee, ''Cryptanalysis of RSA with Private Key d Less Than N<sup>0.292</sup>'', IEEE Transactions on Information Theory, Vol.&nbsp;46, No.&nbsp;4, 2000</ref>

<ref name="RSA250">Wikipedia, ''RSA numbers'', ([https://en.wikipedia.org/wiki/RSA_numbers#RSA-250 Wiki-en])</ref>

<ref name="ASCII">Wikipedia, ''ASCII'', ([https://pl.wikipedia.org/wiki/ASCII Wiki-pl]), ([https://en.wikipedia.org/wiki/ASCII Wiki-en])</ref>

<ref name="hashfunction1">Wikipedia, ''Cryptographic hash function'', ([https://en.wikipedia.org/wiki/Cryptographic_hash_function Wiki-en]), ([https://pl.wikipedia.org/wiki/Funkcja_skr%C3%B3tu#Kryptograficzne_funkcje_skr%C3%B3tu Wiki-pl])</ref>

<ref name="CRC">Wikipedia, ''Cykliczny kod nadmiarowy'', ([https://pl.wikipedia.org/wiki/Cykliczny_kod_nadmiarowy Wiki-pl]), ([https://en.wikipedia.org/wiki/Cyclic_redundancy_check Wiki-en])</ref>

<ref name="MD5">Wikipedia, ''MD5'', ([https://pl.wikipedia.org/wiki/MD5 Wiki-pl]), ([https://en.wikipedia.org/wiki/MD5 Wiki-en])</ref>

<ref name="SHA1">Wikipedia, ''SHA-1'', ([https://pl.wikipedia.org/wiki/SHA-1 Wiki-pl]), ([https://en.wikipedia.org/wiki/SHA-1 Wiki-en])</ref>

<ref name="SHA2">Wikipedia, ''SHA-2'', ([https://pl.wikipedia.org/wiki/SHA-2 Wiki-pl]), ([https://en.wikipedia.org/wiki/SHA-2 Wiki-en])</ref>

<ref name="konieclinii">Wikipedia, ''Koniec linii'', ([https://pl.wikipedia.org/wiki/Koniec_linii Wiki-pl]), ([https://en.wikipedia.org/wiki/Newline Wiki-en])</ref>

</references>








&nbsp;