The Working of RSA

For Paul to send a message to me, first I choose two large prime numbers. Large in this case generally nowadays means over 10¹⁵⁰. These are known as p and q. I can then multiply p and q together to get N. Now I also choose another number, E (so that E is prime in relation to p and q).

I know	Paul knows	The rest of the world know
p
q
N	N	N
E	E	E

The message is encrypted using the formula: C = M^E (mod N). C is the cyphertext and M is the message Paul is sending me (converted first into numbers using ASCII). Paul calculates M using my values of N and E, which he finds published in the equivalent of a phone book. He then sends me C (which any eavesdropped can collect also).

I know	Paul knows	The rest of the world know
p
q
N	N	N
E	E	E
	M
C	C	C

Since the modular function has been used, it is practically impossible for the rest of the world to find M from C - so they can't just reverse the process that Paul used to encrypt the message.

Back at home, I calculate another value, D (quite hard, but relatively simple using Euclid's Algorithm):

E × D = 1 (mod (p-1)(q-1) ).

To find M, I use this equation:

M = C^D (mod N)

I know	Paul knows	The rest of the world know
p
q
N	N	N
E	E	E
M	M
C	C	C
D

Since I never tell anyone the values of p and q, only I can work out D and by doing so, then go on to decipher C into the original message M. Even Paul, once he has encoded the message, cannot decipher it. The only way he or anyone else can work out the message is to factor N into its prime factors, p and q. This is very hard to do as long as p and q are both very big.

One other use of the asymmetry is that for the receiver to verify that they sent a certain value of N and E (rather than an imposter giving false values and therefore being able to decode messages with the false p and q), the receiver can code a verification message with their secret p and q, so that the sender can check to see if he can decode this using the public key. If he can he knows the receiver is no imposter.

Continue