RSA's summmary

RSA encryption for the cluefully bereft

p a random prime number
q another random prime number (could be = p)
n = p * q
e some number (e < n ). Wiener says a usual choice is e = 2¹⁶ - 1 = 65537
d a number such that (ed-1)/(p-1) and (ed-1)/(q-1) are integers (Wiener)
or, (ed-1)/(p-1)(q-1) is an integer (RSA Labs)
or, ed mod (p-1)(q-1) = 1

Examples 1

e (<n) must be relatively prime to (p-1)(q-1) = 4 = 2²
hence e = 3, 7, or 9.

taking e = 3

ed mod (p-1)(q-1) = 1 or 3d mod 4 = 1

by looping through possible values of d that satisfy this relationsship we find

d = 3 7 11 ...

and now, c = m^e mod n. If we want to encrypt an arbitrary message, m (m <n), say 7 then

c = m^e mod n = 7³ mod 10 = 343 mod 10 = 3

To get the message back, use d as follows:

m = c^d mod n = 3³ mod 10 = 27 mod 10 = 7

If we actually apply this to all possible values of message, m, we get:

m c m
0 0 0
1 1 1
2 8 2
3 7 3
4 4 4
5 5 5
6 6 6
7 3 7
8 2 8
9 9 9

example:	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
p	2			2			2				2			3				3			3				3
q	5			7			11				13			5				7			11				13
n = pq	10			14			22				26			15				21			33				39
factors of (p-1)(q-1)	22			2 3			2 5				22 3			23				22 3			22 5				22 3
e	3	5	7	5	7	11	3	7	9	11	5	7	11	3	5	7	11	5	7	11	3	7	9	11	5	7	11
d	3	5	3	7	5	7	5	7	3	9	5	7	11	3	5	7	3	5	7	11	3	7	9	11	5	7	11

example:	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49
p	3			5			5				5			7			7			11
q	13			7			11				13			11			13			13
n = pq	39			35			55				65			77			91			143
factors of (p-1)(q-1)	22 3			23 3			22 3				24 3			22 3 5			23 32			23 3 5
e	5	7	11	5	7	11	3	7	9	11	5	7	11	7	11	13	5	7	11	7	11	13
d	5	7	11	5	7	11	27	23	9	11	29	7	35	43	11	37	29	31	59	103	11	37

arbitrarily pick m (0 £ m £ n)	7	10	18	61
c =	75 mod 9 = 4	77 mod 15 = 13	183 mod 25 = 7	617 mod 143 = 74
m =	45 mod 9 = 7	137 mod 15 = 7	711 mod 25 = 18	74103 mod 143 = 61

1. High-Speed Cryptography with the RSA Algorithm, Michael J. Wiener, Dr Dobbs Journal February 2000.
2. RSA Laboratory FAQ 4.0, Question 3.1.1 What is RSA?
3. The Code Book, Simon Singh, 1998, Appendix J.