Po prostu umawiamy się, że (na przykład) zamiast litery A będziemy pisać G; zamiast B - literę H; zamiast C - literę I i tak dalej, to znaczy: zamiast -tej litery alfabetu będziemy pisać -tą literę. (Tak naprawdę -tą literę, gdyż pod koniec musimy alfabet cyklicznie zawinąć do początku.) Równie dobrze moglibyśmy alfabet przesuwać nie o 6 pozycji, a o 3 pozycje, o 17 pozycji, czy ogólnie: o pozycji.

Nieco bardziej skomplikowany jest szyfr permutacyjny. Tutaj dwie strony ustalają zawczasu permutację literek

a następnie - aby zaszyfrować tekst - przykładają tę permutację do kolejnych literek wiadomości, uzyskując szyfrogram, czyli tekst zaszyfrowany. Odszyfrowanie wygląda podobnie, tylko przykładamy kolejno permutację odwrotną do

Oba powyższe przykłady wpisują się w pewien bardzo ogólny schemat szyfrowania. Mianowicie, na początku, jeszcze przed jakimkolwiek szyfrowaniem, dwie strony (ochrzcijmy je imionami Aldona i Bogumił) muszą się spotkać i ustalić coś sekretnego, czyli tak zwany klucz kryptograficzny w naszym przykładach, odpowiednio: oraz Następnie, gdy Aldona chce przekazać Bogumiłowi wiadomość musi ona najpierw obliczyć wartość (gdzie jest specyficznym opisem wybranego szyfru) i wysłać właśnie ją do Bogumiła. Bogumił otrzymawszy szyfrogram dokonuje obliczenia gdzie oznacza funkcję deszyfrującą. Oczywiście, żeby wszystko miało ręce i nogi, musi zawsze (dla każdego wyboru ) zachodzić oraz - ze względów bezpieczeństwa - podsłuchanie szyfrogramu przez niecną Helgę nie może ujawnić właściwego komunikatu, czyli Ten ostatni wymóg nie jest wcale banalny do sformalizowania, ale my pozostaniemy przy nieformalnym określeniu - chcemy po prostu, aby dla Helgi było bardzo trudno wywnioskować cokolwiek na temat z wartości Dodatkowo w środowisku kryptologicznym przyjmuje się, że Helga zawsze wie, jakiego systemu używają Aldona z Bogumiłem - innymi słowy zna definicję a jedyne czego nie zna, to klucz (to założenie to treść tak zwanej zasady Kerckhoffsa). Więcej o samej zasadzie Kerckhoffsa oraz motywacji jej przyjęcia pisaliśmy w Migawce w Delcie 07/2018

Przez setki lat rozwój kryptologii przebiegał dokładnie według powyższego schematu. Wymyślano przeróżne szyfry, po czym próbowano się upewnić, czy aby na pewno znajomość (oraz definicji ) nic nie mówi o Okazało się dość szybko, że zarówno szyfr Cezara, jak i permutacyjny, nie są bezpiecznymi szyframi, ale za to inne współczesne szyfry, np. AES czy Triple-DES, uchodzą za bezpieczne i są stosowane powszechnie do dziś.

Wszystko pięknie, ale widać, gdzie znajduje się spora niewygoda. Żeby szyfrować, trzeba bezpiecznie ustalić wspólny tajny klucz. Zadanie to wcale nie wydaje się banalne (szczególnie, gdy Aldona i Bogumił mieszkają na różnych kontynentach, trwa wojna etc.), więc można by sformułować następujące naiwne marzycielskie pytanie:

Łatwo wykazać, że postulat powyższy nie jest możliwy do zrealizowania.

Pomimo znajomości powyższego rozumowania w roku 1976 dwóch dżentelmenów - Whitfield Diffie oraz Martin Hellman - postanowiło (w pracy New Directions in Cryptography) bezczelnie zapytać: a może jednak się da? Więcej, już rok później panowie Ron Rivest, Adi Shamir oraz Leonard Adleman (korzystając ze wskazówek z pracy D-H) wykazali, że faktycznie: da się! Czytelnik Logiczny powinien w tym momencie poczuć co najmniej niesmak. Akapit wyżej pokazaliśmy dowód, że czegoś się nie da, a dalej coś tam jeszcze dywagujemy? Haczyk - jak zwykle w matematyce - tkwi w założeniach. Diffie i Hellman nie wykazali, że powyższy dowód jest błędny. Zaproponowali tylko pewne dodatkowe założenie, przy którym ten dowód przestaje być poprawny! Konkretnie chodzi o punkt 5. tego dowodu. Jeśli założymy (jak proponują D-H), że Helga ma ograniczoną moc obliczeniową, to wcale nie jest jasne, że będzie potrafiła szybko odwrócić znaną sobie funkcję Tym tropem poszli Rivest, Shamir i Adleman, proponując swój szyfr, znany dziś jako szyfrowanie RSA.

Zanim przejdziemy do szczegółów, spróbujmy naświetlić samą esencję pomysłu. Idea opiera się na spostrzeżeniu, że (generalnie) mnożenie jest szybkie, ale już jego odwracanie (czyli rozkład na czynniki pierwsze) - bardzo trudne. Innymi słowy, chodzi o znalezienie takich funkcji oraz aby do wyliczania wystarczała znajomość ale już do szybkiego obliczania - konieczne były zarówno jak i Wówczas Bogumił może wszystkim (i Aldonie, i Heldze, i Kamili, i Markowi, i Szymonowi i każdemu, kto tylko będzie chciał) bez skrępowania ujawniać opis ALE zachowując dla siebie czynniki oraz (czyli w istocie opis ). Naprawdę jest to troszkę bardziej skomplikowane i wygląda tak.

Rzeczywiście Bogumił wybiera dwie duże (rzędu setek cyfr) liczby pierwsze i oraz oblicza ich iloczyn Następnie oblicza oraz losuje dowolną liczbę względnie pierwszą z Teraz znajduje taką liczbę że

(*)

Okazuje się, że powyższa operacja (wyznaczenie ) da się wykonać bardzo szybko (np. za pomocą rozszerzonego algorytmu Euklidesa), gdy znamy oraz natomiast wierzymy, że jest bardzo trudna, gdy znamy tylko oraz Pozostaje opisać funkcję szyfrującą i deszyfrującą :

Aby uznać szyfrowanie RSA za poprawne i bezpieczne, należy sprawdzić, że:

(a)

czyli, że Dowód tego faktu pominiemy, pozostawiając tylko uwagę, że - korzystając z kilku faktów z teorii liczb - da się go wyprowadzić wprost z równania (*).

(b)

Znajomość opisu (czyli liczb i ) nie pomoże odtworzyć funkcji gdyż - jak już wspomnieliśmy - wierzymy, że z i nie da się łatwo obliczyć które jest niezbędnym elementem opisu

Jak to wygląda w praktyce?

Szyfrowanie RSA jest niezwykle popularne i wygodne. Aby z niego korzystać, należy postąpić dokładnie tak, jak Bogumił w opisie wyżej. Następnie parę (tak zwany klucz publiczny) należy rozgłaszać wszem i wobec, ponieważ jej znajomość umożliwia światu bezpieczne wysyłanie komunikatów przeznaczonych tylko dla nas. Z drugiej strony - liczbę (osobisty klucz prywatny) oraz rozkład i należy trzymać w wielkiej tajemnicy i nigdy nikomu nie zdradzać.

Jaki to ma związek z podpisem cyfrowym?

Podpis cyfrowy Bogumiła to taka para funkcji że:

• tylko Bogumił potrafi obliczać wartości (czyli podpisywać );
• każdy potrafi obliczać wartości (czyli sprawdzać autentyczność podpisu pod dokumentem );
• funkcja zachowuje się dobrze, to znaczy oraz jeśli tylko

Powyższa definicja wydaje się zupełnie intuicyjna i nie wymaga szerszego komentarza. Wyzwaniem jest jednak znaleźć odpowiednie oraz Okazuje się, że znajomość RSA bardzo nam pomoże. Przyjmijmy bowiem:

gdzie oraz są takie same jak w RSA (w szczególności: i są publiczne, a - znane tylko Bogumiłowi).

Innymi słowy: podpis zachowuje się jak a weryfikacja podpisu dokumentu sprowadza się do sprawdzenia, czy

Teraz widać, że bezpieczeństwo takiego podpisu jest takie samo, jak bezpieczeństwo RSA. Jeśli bowiem (w RSA) tylko Bogumił mógł deszyfrować, to u nas tylko on może podpisywać. Skoro wcześniej każdy mógł szyfrować ( jest publiczna), to teraz każdy może obliczać funkcję Wreszcie - funkcja zachowuje się zgodnie z oczekiwaniami, co wynika wprost z faktu, że jest odwrotna do

Postscriptum

Na zakończenie jeszcze mała obserwacja, która na razie pewnie wyda się mało użyteczna (choć zaryzykujemy stwierdzenie, że jest elegancka i zaskakująca), ale będziemy jej potrzebować w kolejnych częściach cyklu A jednak się da. Otóż chcemy zdefiniować protokół tak zwanego ślepego podpisu. To znaczy: chcielibyśmy, aby Bogumił mógł (jeśli tylko ma taką fantazję) pozwolić Aldonie na podpisanie czegoś, czego sam nigdy nie zobaczy na oczy. Możemy zrobić to tak:

1.

Aldona wybiera dokument do podpisu oraz losową liczbę ;

2.

Aldona wysyła do Bogumiła liczbę ;

3.

Bogumił oblicza i odsyła wynik Aldonie;

4.

Aldona oblicza

Jako ćwiczenie pozostawiamy sprawdzenie, że w protokole powyżej: (1) Bogumił nie jest w stanie odtworzyć dokumentu oraz (2) liczba jest poprawnym podpisem Bogumiła pod dokumentem