Szyfrowanie RSA: krok 2

Rozwiązanie znalazł inny brytyjski matematyk i kryptograf, Clifford Cocks. Musiał opracować specjalny rodzaj funkcji jednokierunkowej, tzw. jednokierunkową funkcję zapadkową. To funkcja, którą łatwo obliczyć w jednym kierunku, ale trudno odwrócić, chyba że ma się specjalną informację zwaną zapadką. W tym celu skorzystał z potęgowania modularnego, które wprowadziliśmy przy omawianiu protokołu Diffiego-Hellmana. Wybierzcie liczbę, podnieście ją do którejś potęgi, podzielcie przez moduł, a reszta będzie stanowić wynik. Można to wykorzystać do zaszyfrowania wiadomości: wyobraźcie sobie, że Bob ma wiadomość, którą zamienia na liczbę, m. Mnoży tę liczbę przez siebie samą e razy, gdzie e jest publicznym wykładnikiem, a potem dzieli wynik przez losową liczbę N. I wynikiem jest reszta z dzielenia. Ten wynik to liczba c. Łatwo to obliczymy, jednak jeśli znamy tylko c, e i N, znacznie trudniej będzie nam określić, którego m użyto. Musielibyśmy zastosować metodę prób i błędów. To funkcja jednokierunkowa, którą możemy zastosować do m. Łatwo wykonać, trudno odwrócić. To nasz matematyczny zamek. A co z kluczem? Jest zapadką, informacją, która ułatwia deszyfrowanie. Musimy podnieść c do innej potęgi, powiedzmy, d, która odwróci pierwszą operację zastosowaną do m i przywróci oryginalną wiadomość m. Obie operacje razem sprowadzają się do tego, co m do potęgi e i wszystko razem do potęgi d. A to przecież to samo, co m do potęgi e razy d. Liczba e odpowiada szyfrowaniu, zaś d – deszyfrowaniu. Alicja potrzebuje sposobu, żeby zbudować e oraz d, trudne do wyznaczenia dla wszystkich innych osób. Wymaga to drugiej funkcji jednokierunkowej, używanej do wygenerowania d. Cocks zwrócił się ku Euklidesowi.