Difficulty: Intermediate | Prerequisites: Basic modular arithmetic, prime numbers
RSA is a public-key cryptosystem: one key encrypts, a different key decrypts, and the two are mathematically linked but practically impossible to derive from each other. The whole scheme rests on the fact that multiplying two large primes is easy, but factoring the product back into those primes is computationally infeasible. You generate a key pair (public and private), encrypt with the public key, and decrypt with the private key.
Public key (N, e)
The pair of numbers shared openly. Anyone can use it to encrypt a message to you. Think of it as your open letterbox slot: anyone can drop a message in.
Private key (d)
The secret number only the recipient knows. Used to decrypt messages encrypted with the matching public key. Think of it as the key to the letterbox that only you hold.
Prime numbers (p and q)
Two large prime numbers chosen at random during key generation. Their product forms the modulus N. Once N is published, p and q are discarded or kept secret, because recovering them from N is the hard problem RSA depends on.
Modulus (N)
The product of the two primes, N = p × q. It appears in both the public and private keys and defines the number space all encryption and decryption arithmetic operates within.
Euler's totient, φ(N)
The count of integers from 1 to N that share no common factor with N. For RSA, φ(N) = (p − 1)(q − 1). In simple terms, it measures how many numbers below N are coprime to N, and it is the value that ties the encryption exponent e to the decryption exponent d.
Encryption exponent (e)
A small odd integer (commonly 7, 17, or 65537) chosen so that gcd(e, φ(N)) = 1. Part of the public key. Think of it as the "locking" operation applied to a message.
Decryption exponent (d)
The multiplicative inverse of e modulo φ(N), meaning (e × d) mod φ(N) = 1. This is the private key. Think of it as the unique "unlocking" operation that reverses what e did.
Ciphertext (c)
The encrypted form of a message, produced by c = m^e mod N. It looks like a meaningless number and can only be turned back into the original message using d.
Plaintext (m)
The original, readable message, represented as a number (or sequence of numbers) smaller than N. After decryption, m = c^d mod N.
Modular inverse
b is the inverse of a modulo N if (a × b) mod N = 1. In simple terms, it is the number that "undoes" multiplication by a within the modular number system.
Key generation produces everything both parties need. One person (conventionally called Bob) runs all five steps; the result is a public key he shares and a private key he keeps.
Step 1: Choose two large primes, p and q
These must be distinct and chosen at random.
Worked example: p = 31, q = 59.
Step 2: Compute the modulus N = p × q
N = 31 × 59 = 1829.
N is public. Its size (in bits) is what people mean by "RSA-2048" or "RSA-4096."
Step 3: Compute Euler's totient φ(N) = (p − 1)(q − 1)
φ(1829) = 30 × 58 = 1740.
φ(N) is never published. It is used only during key generation and then discarded.
Step 4: Choose the encryption exponent e
e must satisfy 1 < e < φ(N) and gcd(e, φ(N)) = 1 (i.e., e and φ(N) share no common factor other than 1).
Worked example: e = 7, since gcd(7, 1740) = 1.
Step 5: Compute the decryption exponent d
d is the multiplicative inverse of e modulo φ(N): (e × d) mod φ(N) = 1.
Found using the extended Euclidean algorithm.
Worked example: d = 1243, because (7 × 1243) mod 1740 = 8701 mod 1740 = 1.
Output:
Public key: (N, e) = (1829, 7)
Private key: d = 1243
Alice wants to send a message to Bob. She looks up Bob's public key (N, e) and computes the ciphertext.
Formula: c = m^e mod N
Worked example:
Message m = 1211
Public key: e = 7, N = 1829
c = 1211^7 mod 1829 = 1027
Alice sends c = 1027 to Bob. Anyone intercepting it sees only 1027, which is useless without d.
Encoding text as numbers
Letters are mapped to two-digit numbers (A = 01, B = 02, ... Z = 26, or using position values like S = 19, T = 20). Letters are concatenated into blocks that are smaller than N.
Example with public key (2537, 13) and the message "STOP":
S = 19, T = 20, O = 15, P = 16
Block the digits into groups smaller than N: m₁ = 1819, m₂ = 1415 (note: some sources pair as 1920 and 1516; this example pairs as ST = 1819 and OP = 1415, following the source convention).
c₁ = 1819^13 mod 2537 = 2081
c₂ = 1415^13 mod 2537 = 2182
Encrypted message: (2081, 2182)
Bob receives the ciphertext c and uses his private key d to recover the plaintext.
Formula: m = c^d mod N
Worked example (continuing from above):
Ciphertext c = 1027
Private key: d = 1243, N = 1829
m = 1027^1243 mod 1829 = 1211
Bob recovers the original message m = 1211.
Decrypting the "STOP" example:
c₁ = 2081, c₂ = 2182, private key d = 937, N = 2537
m₁ = 2081^937 mod 2537 = 1819
m₂ = 2182^937 mod 2537 = 1415
Convert back: 18 19 14 15 → S T O P
Decrypted message: "STOP"
Step | Formula | Purpose |
|---|---|---|
Modulus | N = p × q | Public; defines the number space |
Totient | φ(N) = (p − 1)(q − 1) | Secret; used only to find d |
Encryption | c = m^e mod N | Turns plaintext into ciphertext |
Decryption | m = c^d mod N | Recovers plaintext from ciphertext |
Key relationship | (e × d) mod φ(N) = 1 | Links public and private keys |
Modular inverse | b × a ≡ 1 (mod N) | b is the inverse of a mod N |
Fermat's Little Theorem | m^(p−1) ≡ 1 (mod p) | Holds when p is prime and p does not divide m |
RSA is the algorithm behind most HTTPS connections you use daily: when your browser shows a padlock, RSA (or a related scheme) was likely involved in the initial key exchange. It is also the basis of digital signatures, where the private key signs a document and anyone with the public key can verify the signature is authentic.
Students often think the public key can decrypt messages. It cannot. The public key encrypts; only the private key decrypts. The maths is not symmetric in that direction.
Students sometimes confuse N with φ(N). N is public and used in every encryption/decryption operation. φ(N) is secret, used only during key generation to compute d, and then discarded.
A common error is choosing e that shares a factor with φ(N). If gcd(e, φ(N)) ≠ 1, the modular inverse d does not exist and the system breaks.
Students occasionally assume small example primes (like 31 and 59) are realistic. In practice, RSA primes are hundreds of digits long. The small numbers in coursework exist only to make the arithmetic manageable by hand.
⚠️ You will almost certainly be asked to perform a full RSA key generation from two given primes. Practise the five steps until they are automatic.
⚠️ Encryption and decryption calculations with small numbers are a staple exam question. Be comfortable computing m^e mod N by hand or with modular exponentiation.
⚠️ Expect a question requiring you to compute a modular inverse, either as a standalone problem or as part of key generation (finding d).
⚠️ The relationship (e × d) mod φ(N) = 1 is frequently tested. Know why it must hold and what breaks if it does not.
True or false: The public key is used for decryption. (False. The public key encrypts; the private key decrypts.)
Fill in the blank: φ(N) = ()() when N = p × q. ((p − 1)(q − 1))
True or false: If gcd(e, φ(N)) = 3, then e is a valid encryption exponent. (False. gcd must equal 1.)
Fill in the blank: The decryption exponent d satisfies (e × d) mod ___ = 1. (φ(N))
True or false: Knowing N alone is sufficient to compute d. (False. You need φ(N), which requires knowing p and q.)
Q: Given p = 5 and q = 11, compute N and φ(N).
A: N = 5 × 11 = 55. φ(N) = (5 − 1)(11 − 1) = 4 × 10 = 40.
Q: With N = 55 and φ(N) = 40, verify that e = 3 is a valid encryption exponent.
A: gcd(3, 40) = 1, so yes, e = 3 is valid.
Q: Find d for e = 3 and φ(N) = 40.
A: We need (3 × d) mod 40 = 1. Testing: 3 × 27 = 81, and 81 mod 40 = 1. So d = 27.
Q: Encrypt the message m = 13 using public key (55, 3).
A: c = 13^3 mod 55 = 2197 mod 55 = 2197 − 39 × 55 = 2197 − 2145 = 52. Ciphertext c = 52.
Q: Decrypt c = 52 using private key d = 27, N = 55.
A: m = 52^27 mod 55. Using repeated squaring (or a calculator), the result is 13. The original message is recovered.
Q: Why can an attacker who knows N and e not simply compute d?
A: Computing d requires φ(N), which requires knowing p and q. Factoring N into p and q is computationally infeasible for large N, so d remains secret.
RSA builds directly on modular arithmetic and number theory, so comfort with modular operations is a prerequisite. Euler's totient and Fermat's Little Theorem (covered in the companion study notes on RSA Mathematical Foundations) provide the proof that decryption actually recovers the original message. RSA also connects to the broader topic of computational complexity: the security guarantee is that no known polynomial-time algorithm can factor large integers, which ties into P vs NP discussions.
RSA, RSA cryptosystem, RSA algorithm, public-key cryptography, asymmetric encryption, key generation RSA, RSA encryption, RSA decryption, modulus N, Euler's totient function, phi of N, encryption exponent e, decryption exponent d, modular inverse, extended Euclidean algorithm, ciphertext, plaintext, Rivest Shamir Adleman, CS 182, Foundations of Computer Science, Purdue