Cryptography

RSA algorithm

Let P and Q be two prime numbers, and compute N = P Q and N' = (P-1)(Q-1). Let E be a number coprime to N' and D such that D E = 1 mod(N'). D can be easily computed by using the extended Euclid's algorithm. The pair (E,N) is the public key, the pair (D,N) is the secret key. Of course the lagorithm is broken if the number N can be easily factored so that the two factors P and Q are known.

In order to encode a message M we must have M < N. To encode the message compute ME mod(N). To do this write the binary representation of E = e0e1...en. Then we must compute M to the power Sumi ei2i that is the product of the n factors Mei2i. The n powers Mi = M2i can be computed recursively: M0 = M, and each subsequent number is the square of the preceeding one. Finally the encoded message M' = ME is obtained from the product Prodi Miei.

To decode the message, simply compute the D power of M', ( mod(N) ). This is equivalent to computing MD E = Mk N' + 1 and by Fermat's little theorem this is congruent to M modulo N. By the Chinese Remainder Theorem any number congruent to M modulo N differ from M by a multiple of N. Therefore MD E = M mod(N).


Marco Corvi - 2003