RSA Encryption Algorithm in a Nut Shell
Wednesday, February 23 2011 @ 02:33 PM UTC
Contributed by: Sarad
Abstract To analyze the RSA encryption algorithm and present a working implementation in python. We discuss the mathematical results and see why the math works. The proofs of various number theoretic results subsequently discussed are available in books mentioned in the bibliography and thus omitted. Detailed discussions on big oh notation, time complexity of basic bit operations, Euclidean and extended Euclidean algorithm, time complexity of Euclidean algorithm, time complexity of extended Euclidean algorithm, linear congruences, Euler totient function, Fermats little theorem, Euler's theorem, the Miller-Rabin test are presented. With this mathematical background we then analyze the RSA algorithm followed by a simplifed example. Finally, the documented python code for the RSA algorithm is presented and is hoped to be of use for serious programmers who intend on implementing the algorithm on a workstation.