W szyfrowaniu RSA ważne są liczby pierwsze, ponieważ algorytm opiera się na faktoryzacji dużych liczb. W celu dobrania liczb do algorytmu RSA wybiera się dwie liczby pierwsze p i q.
Przykładowe liczby:
Funkcja Eulera $\phi$ to funkcja matematyczna, która dla każdej liczby całkowitej n zwraca liczbę liczb całkowitych dodatnich mniejszych od n, które są względnie pierwsze z n (tj. mają największy wspólny dzielnik równy 1). Funkcja ta jest użyteczna w teorii liczb, szczególnie w kontekście kryptografii, zwłaszcza w algorytmie RSA.
Dla liczby n będącej iloczynem dwóch różnych liczb pierwszych p i q:
$\phi(n)=(p−1)(q−1)$
$$ p = 51 \\ q = 71 \\ \phi = (p-1)(q-1) \\ \phi = (53-1)(71-1) = 52 * 40 = 3640 \\ $$
RSA to jedna z najpopularniejszych metod kryptografii asymetrycznej, która wykorzystuje parę kluczy: publiczny do szyfrowania i prywatny do deszyfrowania.
Aby wygenerować klucz RSA, wykonujemy następujące kroki:
Wybór dwóch dużych liczb pierwszych:
Obliczenie n:
Obliczenie funkcji Eulera $\phi(n)$:
Wybór wykładnika publicznego $e$:
Można sprawdzić tutaj: https://www.calculatorsoup.com/calculators/math/gcf.php
Obliczenie wykładnika prywatnego $d$:
Aby zaszyfrować wiadomość $m$, używamy klucza publicznego $(e,n)$:
* Obliczenie szyfrogramu $c: c=m^e \mod n$
Na przykład, jeśli $m = 123$:
$c = 12317 \mod 3233$
Obliczenia prowadzą do $c=855$ (po pełnych wyliczeniach).
Aby odszyfrować szyfrogram $c$, używamy klucza prywatnego $(d,n)$:
Dla $c = 855$:
$m = 8552753 \mod 3233$
Obliczenia prowadzą do $m=123$.