RSA
The
RSA algorithm presented below was first published in [6]
Setup

Alice picks up two very large prime numbers, usually of
order 100 decimal digits. These numbers are p and q.

Calculate, M and N, such
that

M = p * q

N = (p1) * (q1)

Alice selects another number e, which is
relatively prime to N.

Now she calculates d such that e
* d = 1 (mod N).

Once p, q, M, N, e and
d are selected, she
publishes e and M. The rest of them are kept secret

(e,
M) is the public key

d is the private key
Encryption and Decryption
Suppose
Bob has a message to Alice. Regarding it, or a block of numbers in it, as
a number x in the range of 0 to M1.
Bob
calculates the ciphertext as
y = x^{e}
mod M
Now
Alice can decrypt it
x = y^{d}
mod M
Since
Alice publishes e and M, any one who wants to
send encrypted messages to Alice can do so, but these messages cannot be
decrypted without the knowledge of d. d is
kept secret and only Alice knows it, she can only decrypt messages.
Example

Choose p and q;
p =5 and q =11

Calculate M and N
M
= p * q = 5 * 11 = 55
N
= (p1) * (q1) = 4 * 10 = 40

Select e, e = 7

Calculate d
d
= e^{1} mod N = (1/7) mod 40 = 23

Let the message be x = 24

For encryption, y =
x^{e} mod M = (24 ^{7 }) mod 55 = 4586471424
mod 55 = 29.
so
the encrypted message is 29.

For decryption, x =
y^{d} mod M = (29^{23 }) mod 55 =
4316720717749415770740818372739989
mod 55 = 24
so
the decrypted message is 24, which is the initial message
