Maths IA · Algebra and functions · topic 15 of 97
RSA: why can nobody read your messages? · IB Maths IA idea: guide, sample graph and step-by-step plan
easy one way, hard the otherYou can publish a number on the open internet that lets anyone lock a message to you, and still be the only person who can unlock it. Why can't they just work it out?
- ✓ you like proofs where every step is a small, checkable fact
- ✓ you want to know why a lock can be public while the key stays private
- ✓ you are happy to learn some number theory from scratch and explain it in your own words
The big idea
RSA rests on two facts. Multiplying two large primes is quick; recovering them from the product seems very slow. And a piece of modular arithmetic, Euler's theorem, makes encrypting and decrypting exact opposites. Your exploration can prove the second fact, step by step from Fermat's little theorem, and then measure the first: how fast the work of factoring grows with the number of digits. You also need primes of the right size, so ask how many there are. All of this is beyond both IB courses. That is your chance to show real understanding: define every term, prove each claim, test it with small numbers, and say honestly where you rely on a result you quote.
Make it yours: pick one twist
Copying a classic won't show your choices. Pick one of these (or invent your own) and your IA becomes yours.
Swipe for more twists →
Show that (m^e)^d ≡ m (mod n) when e·d ≡ 1 (mod φ(n)), starting from Fermat's little theorem for each prime.
→ A complete proof with a gap to close: you must handle the case where p divides m.Use the extended Euclidean algorithm to solve e·d ≡ 1 (mod φ) for small primes, then for larger ones in code.
→ An algorithm you can prove terminates and works. Count its steps against the size of the numbers.Compare computing m^e by repeated multiplication with repeated squaring, and count the steps for different exponents.
→ Linear work against logarithmic work. Show with logarithms why 2048-bit exponents are still feasible.Factor semiprimes of 6, 8, 10 and 12 digits by trial division and time it. Fit a model of work against digits.
→ Data and a model. Explain what an exponential fit says and why your trial-division model cannot be pushed to real key sizes.Count primes up to x exactly and compare with x / ln x. Estimate how many primes have a given number of digits.
→ A numerical test of a quoted theorem. Measure the error and say how the estimate is used to choose keys.Show how RSA fails if p and q are too close together, or if the same prime is reused in two keys.
→ The maths of security becomes the maths of attack. Give a proof, not a demonstration only.Your Maths IA research question: run the check
prove it or measure it?Write your own question first. Then make sure it ticks every box:
- Names the specific result you will prove or measure: correctness, the cost of factoring or the density of primes.
- Says which results from number theory you prove and which you quote, with sources.
- Includes small examples worked by hand and checked in code.
- Has a question with an answer you could be wrong about, so there is a real test.
- States what you leave out: real padding schemes, side-channel attacks and quantum computers.
The model
Two secret primes, one public product, and a lock that uses it. Draw your own flow with your own small primes, and mark which steps are easy and which are hard.
How your Maths IA could be laid out
The usual order for a topic like this, what each part needs to show, and roughly how much of your 12 to 20 pages it takes. The words are all yours.
What public-key encryption has to achieve, and what you will prove or measure.
Congruence defined, its rules proved, and small examples. Every term your reader needs, in your own words.
Fermat's little theorem, then the proof that (m^e)^d returns m. Worked through a small example by hand.
Choosing primes, computing n and φ, finding d with the extended Euclidean algorithm, and fast powering.
The cost of factoring against digits, your timings, and what the prime counting estimate says about choosing p and q.
Back to your aim: what you proved, what you measured and how the two fit together.
Where you relied on quoted results, why trial division is a weak model of attack, and what a real system adds. Say which limitation matters most.
Where every theorem and algorithm came from.
What your Maths IA graph could look like
try a log axis!Made-up timings to show the form of a strong graph, not the answer: time to factor a product of two primes against its number of digits, on axes that show the growth. example only
- Data and model on one set of axes, so the fit can be judged.
- Axis labels give units: digits are a count, time is in seconds.
- A log scale on the time axis turns an exponential model into a straight line.
- Say which machine and program produced the timings.
- Another graph to consider: primes counted exactly against x / ln x.
The maths in action
worked through, not sketched!The graph above was a sketch with made-up numbers. This figure works the idea through from the model itself, so you can see what a finished figure looks like. The source line under it says where every number comes from.
How crowded are the primes?
What share of numbers up to 10^k is prime? Count them yourself with a sieve and compare with 1 / ln of the size.
Your game plan
Tick steps off as you go. We'll remember on this device.
0 of 10 done
- Read and predictFind out how RSA works, using a number theory text rather than a summary. Before any proofs, guess which part of the scheme is the weak point.
- Learn the arithmeticDefine congruence and prove its basic rules. Work small examples by hand until you are fluent with remainders.
- Fermat's little theoremState it and prove it, or state it and say where you got a proof. Check it for several small primes in code.
- Trial run (1 lesson)Make a key from p = 11 and q = 13 by hand, encrypt a small message and decrypt it. Fix any mismatch now: the order of the steps, φ(n), the inverse.
- Prove decryption worksProve that (m^e)^d ≡ m (mod n), covering the case where a prime divides m. Cite your proof of each step.
- Build a larger keyUse fast powering and the extended Euclidean algorithm in code, and count how many steps each uses.
- Measure the hard partTime factoring for several sizes of n and fit a model. Compare your model with exact counts of primes to see how many keys exist.
- Go further, with a reasonProve why two close primes are a weakness, or test a quoted theorem numerically. HL: every step in your argument must be justified.
- Reflect as you goAfter every result, write one line on what it means and what you took on trust. These lines become your evaluation.
- Cut, check, then sendCheck every term is defined once, every claim is proved or sourced, and the conclusion answers your aim. Then send your teacher one draft.
The maths you'll use
- Congruences and modular arithmetic – Define , prove it respects addition and multiplication, and compute powers modulo .
- Fermat's little theorem and Euler's theorem – Prove and use it to show .
- Proof techniques – Use contradiction (infinitely many primes, uniqueness of ) and induction (the repeated-squaring count) with each step justified.
- Euclid's algorithm – Find with by back-substitution and count the steps.
- Growth of work and logarithms – Fit to factoring times, linearise with , and compare with against .
Key equations
Syllabus links
- 1.6Simple deductive proof
- 1.7Rational exponents and laws of logarithms
- 1.9Binomial theorem
- 1.15Proof by induction, contradiction and counterexampleHL
- 2.9Exponential and logarithmic functions
- 1.5Exponents and an introduction to logarithms
- 1.6Approximation, bounds and percentage error
Read up first
- Proof (AA HL) →
- Proof by induction (AA HL) →
- Exponentials and logarithms (AA HL) →
- Counting principles (AA HL) →
Data and sources to start from
Timings of a factoring program you write for semiprimes of increasing size, and an exact prime count from a sieve.
References to cite
- Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.
- Hardy, G. H., & Wright, E. M. (2008). An introduction to the theory of numbers (6th ed.). Oxford University Press.
Cite what you actually use, in your own format, and say where each number came from.
Traps to avoid in this Maths IA
quote or prove? say which- Describing RSA step by step without proving anything. A summary of a known method does not show mathematical understanding.
- Using Euler's or Fermat's theorem without stating the condition on the numbers, or without proving or sourcing it.
- Forgetting the case where p divides the message. The proof still has to work.
- Claiming that factoring is 'impossible'. No fast method is known for ordinary computers, and that is all you can say.
- Drawing a conclusion about real-world security from trial-division timings alone.
- Using real passwords, keys or card numbers as examples. Choose small made-up primes.
More Maths IA ideas like this
Elliptic curves: the maths inside a crypto wallet●●●
The birthday problem: how safe are hash codes?●●○
Check digits: how do barcodes catch mistakes?●●○
Repeating decimals: what is the pattern in the digits?●●●
This guide shows how a topic like this is usually approached. It is not an IA. Your question, choices, data, analysis and words must be your own: change something, tell your teacher where the idea came from, and follow your school's rules on outside help.