RSA Encryption

If we know e < X  and we know that e and X are relatively prime meaning that GCF (e,X) is 1.  How do we find d < X so that ed % X = 1.

As an example, we take X = 100, and e = 3.

A	B 	Q	R	AF 	BF	ABR
100	3	33	1	0	1	0 - 33*1  (AF-Q*BF) = -33

3	1			1	-33

We stop because B is 1.  So, let's look at the B Factor.  -33.  (-33)%100 = (100-33)%100 = (67%100) = 67.  (Mod the Factor by X, make it nonnegative.

67*3 = 201.  201%100 = 1, so we've found it.

(3*67) %100 = 1.

X = 100,  e = 21.

A	B	Q	R	AF	BF	ABR
100	21	4	16	0	1	0 - 4*1 = -4
21	16	1	5	1	-4	1-(-4*1) = 5
16	5	3	1	-4	5	-4-(3*5) = -19
5	1			5	-19

B is 1 so we're done.  Our BF is -19.  (-19)%100 = 81.

(81)(21) =     1600+20+80+1 = 1701.  1701%100 = 1.

(21)(81)%100 = 1.



For RSA.

1.  Find two very large prime numbers, p,q.
2.  Compute n = pq,  and phi(n) which is (p-1)(q-1).
3.  Find some number e < phi(n) which is relatively prime to phi(n).
4.  Compute d (using above algorithm) so that ed%phi(n) = 1.
5.  Publicize n and e.  PUBLIC KEY.
6.  DO NOT MAKE PUBLIC p, q, or d.



p = 5  q = 11, so n is 55  and phi(n) is what?  40

Pick an e < phi(n) relatively prime to phi(n)

A	B	Q	R	AF	BF	ABR
40	37	1	3	0	1	0-1*1 = -1
37	3	12	1	1	-1	1-(12*-1)=13
3	1			-1	13
B is 1 so we're done.

13%40 = 13.

(13)(37)  = 300+90+70+21 = 460+21 = 481.  481%40 = 1.

e = 37.

d = 13.

So, our message is an integer < n (and n is 55).

M =43.  Compute 43^37  %55


43		37		43

34		18		43

1		9		43*1=43

1		4		43

1		2		43

1		1		43*1=43
Our message 43 encodes as 43.


43		13		43

34		6		43

1		3		43*1=43

1		1		43*1=43