How RSA Encryption Works
A comprehensive mathematical exploration of the RSA cryptosystem
Introduction to RSA
RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission. Named after its inventors Ron Rivest, Adi Shamir, and Leonard Adleman (1977), RSA's security relies on the practical difficulty of factoring the product of two large prime numbers.
- Public Key (e, n) — Used for encryption, can be shared openly
- Private Key (d, n) — Used for decryption, must be kept secret
Step 1: Key Generation
The key generation process involves several mathematical steps:
Step 1.1: Choose Two Large Primes
Select two distinct large prime numbers p and q.
Example: p = 61, q = 53
Step 1.2: Compute n (Modulus)
Calculate the modulus:
Example: n = 61 × 53 = 3233
Step 1.3: Compute Euler's Totient φ(n)
Calculate Euler's totient function:
Example: φ(3233) = 60 × 52 = 3120
Step 1.4: Choose Public Exponent e
Select e such that:
- 1 < e < φ(n)
- gcd(e, φ(n)) = 1
Common choice: e = 65537 (216 + 1)
Example: e = 17
Step 1.5: Compute Private Exponent d
Find d such that d is the modular multiplicative inverse of e modulo φ(n):
Equivalently: d × e ≡ 1 (mod φ(n))
Example: d = 2753 (since 17 × 2753 = 46801 = 15 × 3120 + 1)
Final Keys:
- Public Key: (e, n) = (17, 3233)
- Private Key: (d, n) = (2753, 3233)