Codes, cryptography and algorithms · Maths EE idea · Solid
Why RSA encryption works
A research question to start from
Why does RSA decryption recover the message, and how does its security depend on the difficulty of factorising?
A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.
Why it works as a maths EE
Number theory with a working system you can build by hand and prove correct.
Mathematics you would need
- Modular arithmetic
- Euler's theorem and the totient function
- Modular inverses
- Fast exponentiation
Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.
One possible line of attack
- Prove Euler's theorem.
- Prove decryption works, including when the message shares a factor with n.
- Analyse the cost of factorising small n and discuss security.
Scope and difficulty
Solid. Solid.
Pitfalls
- Computer security essay.
- Ignoring the shared-factor case.
Where to start reading
Search a library catalogue or a university's open lecture notes for: RSA correctness proof Euler theorem; RSA message not coprime. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).
Make it your EE
Similar ideas
- Correcting errors with Hamming codesCodes & algorithmsSolid
- Check digits: which errors do they catch?Codes & algorithmsAccessible
- Sharing a secret in publicCodes & algorithmsSolid
- Breaking substitution ciphers with statisticsCodes & algorithmsAccessible
All codes, cryptography and algorithms ideas · the full ideas library