RSA & modular exponentiation in cryptography
RSA picks two primes p and q, sets n = pq and φ(n) = (p−1)(q−1), chooses e coprime to φ(n), and computes d with ed ≡ 1 (mod φ(n)). Encryption is c = m^e mod n and decryption m = c^d mod n; they invert each other by Euler’s theorem. The security rests on factoring n being hard while multiplying p and q is easy.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Generate the modulusn = pq for primes p and q. Compute φ(n) = (p−1)(q−1) — this needs the factorisation, which is what stays secret.
- Choose e and compute de must satisfy gcd(e, φ(n)) = 1. Then d is the inverse of e mod φ(n), from the extended Euclidean algorithm.
- Encrypt and decrypt by exponentiationc = m^e mod n and m = c^d mod n, both computed by repeated squaring.
- Verify on a small exampleRound-tripping a message end to end catches every arithmetic error.
Worked example
With p = 3, q = 11 and e = 7, find d and encrypt the message m = 5.
- n = 33 and φ(n) = 2 × 10 = 20.
- Find d with 7d ≡ 1 (mod 20): 7 × 3 = 21 ≡ 1, so d = 3.
- Encrypt: c = 5⁷ mod 33. 5² = 25, 5⁴ = 625 ≡ 625 − 18·33 = 31 ≡ −2 (mod 33).
- 5⁷ = 5⁴·5²·5 ≡ (−2)(25)(5) = −250 ≡ −250 + 264 = 14 (mod 33).
Answer. d = 3 and the ciphertext is 14. Decrypting: 14³ = 2744 = 83·33 + 5, recovering m = 5 ✓.
Where marks get dropped
These are the specific errors that cost credit on rsa & modular exponentiation in cryptography questions — QED's rubric penalises each of them separately.
- Reducing the exponent modulo n instead of modulo φ(n). Exponents live mod φ(n); bases live mod n.
- Choosing e sharing a factor with φ(n), so no inverse d exists.
- Encrypting a message m ≥ n. The message must be reduced or split into blocks below n, or decryption cannot be unique.
Practise this until it is automatic
Unlimited fresh questions
QED generates new rsa & modular exponentiation in cryptography problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Number Theory mastery is tracked so you know when this is exam-ready.
RSA & modular exponentiation in cryptography — frequently asked questions
Why is RSA secure?
Because recovering d requires φ(n), which requires factoring n. Multiplying two 1024-bit primes is instant; factoring the product is not currently feasible.
Why is textbook RSA not used directly?
It is deterministic and malleable, so identical messages give identical ciphertexts. Real implementations add randomised padding such as OAEP.
What breaks RSA?
A large fault-tolerant quantum computer running Shor’s algorithm factors in polynomial time, which is why post-quantum schemes are being standardised.
The rest of Number Theory
Divisibility, primes, gcd, modular arithmetic. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Divisibility & the division algorithm
- 2Primes & unique factorisation
- 3gcd, lcm & the Euclidean algorithm
- 4Modular arithmetic & congruences
- 5Solving linear congruences
- 6Fermat’s little theorem
- 7The Chinese remainder theorem
- 8Modular inverses & fast exponentiation
- 9Euler’s totient φ(n) & Euler’s theorem
- 10Base-b representations & digit arguments
- 11RSA & modular exponentiation in cryptography
- 12Wilson’s theorem & primality testing
- 13Linear Diophantine equations ax + by = c
Ready to make rsa & modular exponentiation in cryptography exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →