How does RSA encryption work, and how long would it take to break a small key?

AA HLAA SL Ambitious Also in: Networks & graphs

Research question

Why does RSA decryption recover the original message, and how does the time taken to factorise n = pq by trial division grow with the number of digits?

Adapt it: change the place, the data or the comparison until the question is yours.

Why it makes a good exploration

RSA protects online payments using modular arithmetic. Explaining why it works, encrypting a message by hand, and timing factorisation of growing keys shows exactly why large primes keep secrets safe.

The mathematics you'll need

Modular arithmetic (explain)
Euler's totient and Fermat's little theorem
Modular inverses via the Euclidean algorithm
Growth of computation time — exponential in digits

Course labels show where a technique sits; using maths from outside your course is fine if you explain it clearly and say it is new to you.

Where the data comes from

Use small primes for worked examples; time a trial-division program for increasing key sizes.

OEIS (On-Line Encyclopedia of Integer Sequences) — Check a sequence you have found and read its known formulas and references.

Cite every source in a footnote where you use it and in your bibliography. Check the licence of any dataset you download.

A possible outline

Explain modular arithmetic with examples.
Generate keys with small primes.
Encrypt and decrypt a short message.
Prove why decryption works.
Time factorisation and model how time grows with digits.

Pitfalls that cost marks

Only describing the algorithm without proof.
Arithmetic errors — check every step with technology.
Claiming real keys can be broken by your method.

Showing personal engagement

Encrypt a message to a friend and have them decrypt it.
Predict the time to factor a 50-digit n from your model.
Discuss quantum computing's threat accurately.

See Criterion C: personal engagement for what examiners look for.

Taking it further

Prove Fermat's little theorem by induction or counting.

Turn this idea into your IA

Plan this IAOpens the planner with this question, the maths and data sources filled in. Desmos workspacePlot your data, fit models and keep your graphs with your plan. AI feedback on a draftCriterion-by-criterion feedback with evidence from your own text. Coaching, not rewriting. Examiner reviewPete, a practising IA examiner, reads your draft and talks it through with you (€100).