Public-key cryptography
Objective. Explain RSA structure and assumptions.
- 1. Learn
- 2. Worked example
- 3. Practice
- 4. Feedback
- 5. Continue
Learn: the key idea
Public-key cryptography uses a mathematically linked pair of keys, public and private, so that encryption with one can only be undone by the other, enabling secure communication without a shared secret. RSA builds this on the difficulty of factorising large composite numbers: choosing primes p and q, computing n = pq and φ(n) = (p−1)(q−1), then selecting e coprime to φ(n) and its inverse d modulo φ(n) as the private exponent. Encryption raises a message to the power e modulo n; decryption raises the ciphertext to the power d modulo n, recovering the message by Euler's theorem. For example, with small primes p=3, q=11, n=33, φ(n)=20, choosing e=3 gives d=7 since 3×7=21≡1 (mod 20).
Worked example
In an RSA public-key cryptography scheme with p = 5, q = 11, compute n and φ(n).
- 1n = p×q = 5×11 = 55
- 2φ(n) = (p−1)(q−1)
- 3φ(n) = 4×10
- 4Compute: φ(n) = 40, so n = 55
Answer: n = 55, φ(n) = 40
Concept mastery
Based on your past attempts at this lesson — the question types to practise again come first.
Complete a practice set to see your concept breakdown here.
Practice
Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.
Start practisingCommon mistake. Students assume public-key cryptography is secure simply because two different keys are used; security actually depends entirely on the computational hardness of factorising n, so small or poorly chosen primes make RSA breakable despite the key pair structure.
Your progress
Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.
0 of 5 steps complete
Your place saves automatically as you read.