RSA Encryption Principle and Example

RSA is the most widely used public-key (asymmetric) cryptographic algorithm. It uses a pair of keys (public and private) for encryption and decryption, and its security relies on the difficulty of factoring large numbers (prime factorization).

1. Key Generation Steps

The security of RSA begins with finding two very large prime numbers $p$ and $q$.

Example: Key Generation

Select Two Prime Numbers $p$ and $q$ $$p = 5$$ $$q = 11$$
Calculate the Modulus $n$ $$n = p \times q = 5 \times 11 = 55$$ (n is part of both keys and is made public.)
Calculate Euler's Totient Function $\phi(n)$ $$\phi(n) = (p-1) \times (q-1) = (5-1) \times (11-1) = 4 \times 10 = 40$$ ($\phi(n)$ is used only for key generation and kept secret.)
Select the Public Exponent $e$ Choose an integer $e$ such that $1 < e < \phi(n)$ and $e$ is coprime to $\phi(n)$. (We use $e=3$ for simplicity; typically $e=65537$). $$e = 3$$ (Public Key: $(e, n) = (3, 55)$)
Calculate the Private Exponent $d$ $d$ is the multiplicative inverse of $e$ modulo $\phi(n)$: $e \times d \equiv 1 \pmod{\phi(n)}$. $$3 \times d \equiv 1 \pmod{40}$$ $$d = 27$$ (Because $3 \times 27 = 81$, and $81 \div 40$ leaves a remainder of $1$.) (Private Key: $(d, n) = (27, 55)$)

Result: The Public Key $(3, 55)$ is shared publicly, and the Private Key $(27, 55)$ is kept secret by the owner.

2. Encryption and Decryption Process

① Encryption - Using the Public Key

Plaintext $M$: Must satisfy $M < n$. (Example: $\mathbf{M = 12}$)
Public Key $(e, n) = (3, 55)$

Ciphertext $C$ Calculation: $$C \equiv M^e \pmod{n}$$ $$C \equiv 12^3 \pmod{55}$$ $$12^3 = 1728$$ $$1728 \div 55 = 31 \text{ remainder } 23$$ $$\mathbf{C = 23}$$

② Decryption - Using the Private Key

Ciphertext $C = 23$
Private Key $(d, n) = (27, 55)$