In RSA encryption, prime numbers are important because the algorithm is based on factorisation of large numbers. In order to select numbers for the RSA algorithm, two prime numbers p and q are chosen.
Example numbers:
The Euler function $$ is a mathematical function that, for any integer n, returns the number of positive integers less than n that are relatively prime of n (i.e. have a greatest common divisor equal to 1). This function is useful in number theory, particularly in the context of cryptography, especially in the RSA algorithm. ==== Formula ==== For the number n being the product of two different prime numbers p and 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 is one of the most popular methods of asymmetric cryptography, which uses a pair of keys: public for encryption and private for decryption.
To generate an RSA key, we follow the following steps:
Selection of two large prime numbers:
Calculation of n:
Calculation of Euler's function $phi(n)$:
Selection of the public exponent $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$.