RSA Encryption

A public key is a pair of generally very large numbers  (n,e) where e < phi(n), and e is relatively prime to phi(n).  (GCF (phi(n),e) is 1.)

n is the product of two distinct prime numbers p,q.

A "message" m is an integer less than n.

The world knows your public key.  When they want to send a message, they will compute m' = (m^e)%n, using the "powermod" algorithm.

*I* have a private key for decryption.  The world does not know my private key.  Only I know my private key!!!

My private key is (n,d).  I will compute m = (m'^d)%n.  This will get me my message back.  Even though the world knows n and e, they will not live long enough to compute d.

Where do e and d come from?  (We already know that n is the product of two primes.)  e and d are chosen so that (ed)%phi(n) = 1.

phi(n) = the number of positive integers less than n that are relatively prime to n.

phi(5) = 4...because 1,2,3,4 are all relatively prime to 5.
phi(10) = 4...because 1,3,7,9 are all relatively prime to 10.
phi(12) = 4...because 1,5,7,11 are all relatively to 12.
phi(9) = 6...1,2,4,5,7,8
phi(11) = 10...1,2,3,4,5,6,7,8,9,10
phi(8) = 4...1,3,5,7   (2,4,6 all have a factor in common in 8, like, maybe 2.)
phi(14) = 6...1,3,5,9,11,13
phi(15) = 8...1,2,4,7,8,11,13,14

if n = (p1^e1) x (p2^e2) x ... (pk^ek)

phi(n) = (p1-1)(p1^(e1-1)) x (p2-1)(p2^(e2-1)) x ... x (pk-1)(pk^(ek-1))

phi(100) = 2^2 x 5^2

           (1)(2^1) x 4(5^1)
            1x2x4x5 = 40
phi (100) = 40

phi (81) =

81= 3^4

    (2)(3^3) = 2x27 = 54

If n = pq.  Then phi(n) = (p-1)(q-1).

It turns out that if ed%phi(n) = 1   that (m^e %n)^d % n = m.  In other words, if ed%phi(n)=1, then e and d will decrypt each other in the encryption formula m^e % n.

So, quick example:

Two primes:  5,7.  n = 35.  phi(n) = 24

Our n is 35,  we need a number less than 24 relatively prime to 24.  How about 13?

Our public key is (35,13). Valid messages are integers from 0 to 34.

If someone wants to send us a message "10".  They will compute 10^13 %35


Base		Exponent	Running Product
10		13		10
100%35=30	6		10
900%35=25	3		10x25 = 250 = 5
625=30		1		5x30=150 % 35 = 10


To decrypt I need a d, such that 13d%24 = 1.

 24	0
-13	-1

13	1
11	-1
 2	2
1	-11

(-11)%24 = 13   (-11+24) = 13.

So, if e is 13, then d is 13.

Here's the thing.

Since I know p and q, I know n and I know phi (n).  I picked p and q first and I know them to be prime and I know that n=pq, Once I have phi(n), I can pick e such that e is relatively prime to  phi (n).  Once I know e, I can compute d.

I make n and e public.  For the world to compute d, they have to know what phi(n) is.  To compute phi(n), they need to to know the factors p and q...which I am not going to tell them.  The fastest known way to compute d is to use phi(n).  The fastest known way to compute phi(n) is to use the prime factors of n.  The fastest known way to compute the factors of n is to systematically try primes until you find the correct ones.  Thus, for the world to compute d, they have to factor n...and n is very very large.