Banalny przykład kryptografii asymetrycznej to RSA.
Klucz prywatny RSA to dwie liczby -> d
oraz n
Klucz publiczny RSA to dwie liczby -> e
oraz n
n
jest iloczynem dwóch liczb pierwszych q
oraz p
, e
zwykle wynosi 65537 oraz istnieje zależność, że e*d modulo (q-1)(p-1) = 1
Nie bede to wchodził w szczegoły co z tego wynika matematycznie, ale efekt dobrania liczb jest taki ze:
(xe)d modulo n = x
Jeśli przez x
oznaczysz swoją wiadomość zamienioną na liczbę to za pomocą potęgowania modularnego xe modulo n dokonujesz szyfrowania a następnie podnosząc to do potęgi d
modulo n dokonujesz deszyfrowania.
Więc dlaczego to jest w ogóle bezpieczne? No bo przecież znamy matematyczny przepis na liczbę d
, wiec czemu jej nie policzyć? Problem jest tutaj z rozkładem liczby n
na liczby p
oraz q
. Rozkład takiej liczby na czynniki pierwsze jest cieżki obliczeniowo i dla dużych liczb jest póki co niemozliwy. Liczbę d
można łatwo uzyskać jeśli zna sie p
oraz q
.
Więc równie dobrze moglibyśmy powiedzieć że kluczem prywatnym jest para liczb p
oraz q
a kluczem publicznym jest liczba n
. Mając p
oraz q
znasz także n
bo wystarczy je pomnożyć, ale odwrotnie już nie. Operacja potęgowania modularnego do samego potęgowania wymaga jedynie liczby n
(oraz e
ale ta zwykle jest taka sama) ale odwrócenie
tego potęgowania wymaga już rozkładu liczby n
.