RSA Theory

This is our proof of the RSA algorithm. There are probably more elegant and succinct ways of doing this. We have tried to explain every step in terms of elementary number theory and avoid the `clearly it follows...' technique favoured by many text books.

Document formats available

rsa_theory.pdf (93 kB)
rsa_theory.ps (160 kB)
rsa_theory.pdf (zipped) (82 kB)
rsa_theory.ps (zipped) (79 kB)
rsa_theory.dvi (zipped (7 kB)

The document was written with LaTex (source: rsa_theory.tex) and generated on a Windows system using the wonderful TeXniCenter.

Hints

You may find these useful...

RSA Encryption scheme

Encryption: ciphertext, c = RsaPublic(m) = m^e mod n
Decryption: plaintext, m = RsaPrivate(c) = c^d mod n
Inverse transformation: m = RsaPrivate(RsaPublic(m))

RSA Signature scheme

Signing: signature, s = RsaPrivate(m) = m^d mod n
Verification: check, v = RsaPublic(s) = s^e mod n
Inverse transformation: m = RsaPublic(RsaPrivate(m))

Bibliography

R.P. Burn, A Pathway into Number Theory, Cambridge University Press, 1996, ISBN 0521575400.
Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, The MIT Press, 2001, ISBN 0262531968.
H. Davenport, The Higher Arithmetic: An Introduction to the Theory of Numbers, Cambridge University Press, 1999, ISBN 0521634466.
Graham, Knuth, Patashnik, Concrete Mathematics: a foundation for computer science, 2nd ed, Addison-Wesley, 1994, ISBN 0201558025.
M381 Mathematics and Computing: A Third Level Course, Number Theory Handbook, The Open University, 1996.

Thanks to Chris Arrettines and Jonathan Covington for pointing out the typo in Fermat's Little Theorem.

Revision History

5 May 2007: minor re-wording of text; corrected typo in Fermat's Little Theorem.
10 October 2006: fixed error with explanation of phi(12): 9 is not coprime to 12!
2 October 2006: re-written and published in LaTex format.
18 September 2004: updated HTML format.
April 2002: first published in HTML format.

Feedback

Feedback or questions: Contact Us. To comment on this page, see below.

This page last updated 3 January 2010