1. Bierze swój klucz prywatny KLo=(n, d).
2. Oblicza K=(SZ)^d mod n.
3. Czyta K, wiedząc, że Kłapouchy na pewno nie ma do tego dostępu.

1. FI(n)=(p-1)*(q-1) jest to liczba liczb względnie pierwszych z n=p*q i mniejszych od tej liczby.
2. Obliczony przez Puchatka komunikat to (K^e mod n)^d mod n, czyli po prostu K^e*d mod n.
3. Korzystając z tego, że e*d=1 mod FI(n), otrzymujemy, że wynik Puchatka to (K^FI(n))^a*K mod n.
4. Twierdzenie Eulera mówi, że jeżeli K jest względnie pierwsze z n, to K^FI(n)=1 mod n.
5. Jeżeli K było względnie pierwsze z n, to z twierdzenia Eulera mamy taki wynik Puchatka: K mod n, czyli po prostu K (zawsze zakładamy, że K < n), zatem jest OK.
6. Jeżeli K nie jest względnie pierwsze z n, to albo K dzieli p, albo K dzieli q.
7. Rozważmy przypadek K=b*p (b jest względnie pierwsze z q). Drugi przypadek jest analogiczny.
8. Chcemy udowodnić, że (b*p)^e*d=b*p mod p*q, czyli: b^e*d*p^e*d-1=b mod q.
9. Po skróceniu przez b dostajemy: (b*p)^{a*(p-1)*(q-1)}=1 mod q (to pozostaje do udowodnienia).
10. Twierdzenie Fermata mówi: jeżeli q jest pierwsze, a x jest względnie pierwsze z q, to zachodzi równość x^q-1=1 mod q (wniosek z twierdzenia Eulera)
11. W twierdzeniu Fermata używamy x=b*p (to jest względnie pierwsze z q). Otrzymujemy 1^a*(p-1)=1 mod q, co jest niewątpliwie prawdą.
12. Zatem w obu (właściwie trzech) przypadkach Puchatek dostaje od Prosiaczka poprawny komunikat.

Inne szyfry z kluczem publicznym
       Inaczej niż RSA wygląda metoda zaproponowana przez Diffiego i Hellmana. Służy ona do uzgodnienia wspólnego tajnego klucza. Opiera się ona na tym, że obliczenie dyskretnego logarytmu jest zapewne bardzo trudne. Wygląda to następująco:

1. Korzysta się z dwóch publicznych wartości: n i g. Będziemy liczyć modulo n, więc g należy do Z_n.
2. Prosiaczek wybiera losową liczbą a należącą do Z_n.
3. Puchatek wybiera losową liczbą b należącą do Z_n.
4. Liczby a i b są tajne.
5. Prosiaczek oblicza A=g^a mod n i wysyła A do Puchatka.
6. Puchatek oblicza B=g^b mod n i wysyła B do Prosiaczka.
7. Prosiaczek oblicza C=B^a mod n.
8. Puchatek oblicza C=A^b mod n.
9. Zarówno Puchatek, jak i Prosiaczek, otrzymują tę samą liczbę C. Ta liczba jest uzgodnionym tajnym kluczem.
10. Osoba podsłuchująca nie jest w stanie wydobyć wartości C, o ile nie umie obliczyć dyskretnego logarytmu. Uznaje się, że ten problem jest wystarczająco trudny.

Łamanie szyfrów z kluczem tajnym
       Zanim opiszę bardziej szczegółowo metody szyfrowania z kluczem tajnym, przedstawię możliwe rodzaje ataków na te szyfry. Im lepszy szyfr, tym trudniej będzie wykonać na niego atak i osiągnąć sukces. Ataki mogą być m.in. następujących rodzajów:

• Napastnik wybiera sobie tekst i czyta jego zaszyfrowaną wersję. Jest to najtrudniejszy od odparcia rodzaj ataku. Dość trudno go jednak wykonać w praktyce (trzeba zmusić szyfrującego do zaszyfrowania naszego tekstu).
• Napastnik zna tekst i jego zaszyfrowaną wersję, ale nie może sobie sam tekstu wybrać. Oznacza to, że ma on do dyspozycji jakąś próbkę tekstów i szyfrogramów, której nie może sobie wybrać.
• Napastnik zna tylko szyfrogram. Odgadnięcie oryginału z szyfrogramu wymaga w sposób konieczny jakiejś wiedzy o typie oryginału - w jakim jest języku itp. Takie ataki są bardzo trudne do wykonania.

DES
       Najpopularniejszym szyfrem stosowanym obecnie jest szyfr DES (Data Encryption Standard), który jest oficjalnym standardem szyfrowania przyjętym przez rząd USA. Jest to szyfr z kluczem tajnym (klucz nadawcy=klucz odbiorcy), który łączy się często z RSA (tzn. klucz przekazuje się za pomocą RSA).
       DES jest szyfrem typu Feistela. Wykonuje się w 16 kolejkach, korzystając z 56-bitowego klucza. W każdej kolejce używa się innego 48-bitowego klucza wyliczonego z głównego klucza 56-bitowego. Oryginał jest dzielony na bloki wielkości 64 bitów. Jak dotychczas jedyna udana próba złamania DES polegała na "nakarmieniu" go 2⁴³ oryginałami i analizie pochodzących stąd szyfrogramów. Kosztowało to 50 dni pracy 12 stacji roboczych HP 9735. Wykonanie takiego ataku w praktyce wydaje się niemożliwe. DES jest powszechnie uważany za bezpieczny, choć dużo mówi się o konieczności zwiększenia rozmiaru klucza (w obawie przed atakiem "na chama").
Istnieje kilka trybów działania DES:

• EBC (Electronic Codebook) - każdy 64-bitowy blok koduje się osobno,
• CBC (Cipher Block Chaining) - przed zakodowaniem kolejnego 64-bitowego bloku wykonuje się XOR tego bloku z wynikiem kodowania poprzedniego,
• CFB (Cipher Feedback) - używany do kodowania tekstów z inną wielkością bloku niż 64 bity.
• OFB (Output Feedback) - kolejna modyfikacja - błędy w czasie transmisji nie uniemożliwiają odczytania tekstu.

Funkcje mieszające - wstęp
       Kryptograficzną funkcją mieszającą nazywamy taką funkcję H, że:

• Dziedziną H jest zbiór wszystkich możliwych tekstów (dowolnej długości)
• H(x) jest zawsze tej samej długości
• H(x) jest proste do wyliczenia na komputerze
• H jest funkcją "w jedną stronę"
• H jest funkcją "bezkolizyjną"

• z wartości funkcji na tekście nie da się w żadnym wypadku odzyskać informacji o tekście
• nie da się znaleźć tekstu, który dawałby zamówioną z góry wartość mieszającą

Weryfikacja tożsamości
       Funkcje mieszające wraz z szyframi typu RSA pozwalają na elektronicznę kontrolę tożsamości nadawcy komunikatu. Przypuśćmy, że Puchatek chce wysłać do Prosiaczka komunikat K (niezaszyfrowany), ale nie jest pewien, czy Prosiaczek uwierzy, że to on napisał. Żeby udowodnić swoją tożsamość skorzysta z wersji RSA. Zachowujemy wszystkie oznaczenia z opisu algorytmu RSA - (n, e) to klucz publiczny, (n, d) to klucz prywatny (oba należą do Prosiaczka). Kontrola tożsamości wygląda następująco:

1. Prosiaczek wysyła K do Puchatka
2. Prosiaczek oblicza H(K), a następnie P=(H(K))^d mod n i wysyła P jako swój podpis do Puchatka
3. Puchatek odbiera K i P
4. Puchatek rówmież oblicza H(K), a następnie sprawdza, czy P=(H(K))^d mod n. Jeżeli ta zależność jest spełniona, to K zostanie uznany za komunikat od Prosiaczka

Funkcje mieszające - cd
      Funkcje mieszające buduje się zwykle na fundamencie tzw. funkcji kompresujących. Funkcja kompresująca pobiera dane ustalonej długości i jakoś je skraca. Funkcję mieszającą tworzy się przez iterowane obliczanie funkcji kompresujących, tzn. H(a1,...,an)=C(C(..(C(s,a1),a2)..),an), gdzie C jest funkcją kompresującą dwukrotnie, a s jest wektorem startowym. Jeżeli funkcja C ma kolizje, to nazywamy je pseudokolizjami. Istnienie pseudokolizji nie jest uważane za dowód bezużyteczności funkcji, np. funkcja MD5 (opisana dalej), ma odkryte pseudokolizje, a mimo to jest uważana za bezpieczną.
      Najpopularniejsze obecnie funkcje mieszające to MD4, MD5 oraz SHA i SHA-1. Spośród nich MD4 nie jest uważana za bezpieczną, a SHA-1, która jest modyfikacją SHA (Secure Hash Algorithm), jest uważana za najbezpieczniejszą z nich (choć jest nieco wolniejsza niż MD5).