Illustration of the RSA algorithm

Math 126 Number theory

Illustration of the RSA algorithm

Illustration of the RSA algorithm with p = 11, q = 13, and e = 7. Then n = pq = 143, and phi(n) = 120. The value of e = 7 is okay since 7 is relatively prime to 120. The inverse of e moduldo 120 is d = 103 since 7 times 103 is congruent to 1 modulo 120. The following table gives the encoding and decoding functions for each number a from 0 through n – 1. To encode a message a, raise it to the power e modulo n. To decode a message b, raise it to the power d modulo n. This table was produced by a computer program. Note that a^ed is congruent to a for each value of a.

a	a^e	a^d	a^ed
0	0	0	0
1	1	1	1
2	128	63	2
3	42	16	3
4	82	108	4
5	47	125	5
6	85	7	6
7	6	123	7
8	57	83	8
9	48	113	9
10	10	10	10
11	132	132	11
12	12	12	12
13	117	52	13
14	53	27	14
15	115	141	15
16	3	81	16
17	30	95	17
18	138	112	18
19	46	72	19
20	136	58	20
21	109	109	21
22	22	22	22
23	23	23	23
24	106	41	24
25	64	38	25
26	104	130	26
27	14	92	27
28	63	128	28
29	94	68	29
30	134	17	30
31	125	47	31
32	98	98	32
33	110	110	33
34	122	122	34
35	139	74	35
36	75	49	36
37	93	119	37
38	25	103	38
39	52	117	39
40	105	79	40
41	24	50	41
42	81	3	42
43	43	43	43
44	99	99	44
45	111	111	45
46	84	19	46
47	31	5	47
48	126	9	48
49	36	114	49
50	41	106	50
51	116	90	51
52	13	39	52
53	92	14	53
54	76	76	54
55	55	55	55
56	56	56	56
57	73	8	57
58	20	137	58
59	71	97	59
60	135	70	60
61	74	139	61
62	127	101	62
63	2	28	63
64	103	25	64
65	65	65	65
66	66	66	66
67	89	89	67
68	29	107	68
69	108	82	69
70	60	86	70
71	124	59	71
72	19	84	72
73	83	57	73
74	35	61	74
75	114	36	75
76	54	54	76
77	77	77	77
78	78	78	78
79	40	118	79
80	141	115	80
81	16	42	81
82	69	4	82
83	8	73	83
84	72	46	84
85	123	6	85
86	70	135	86
87	87	87	87
88	88	88	88
89	67	67	89
90	51	129	90
91	130	104	91
92	27	53	92
93	102	37	93
94	107	29	94
95	17	134	95
96	112	138	96
97	59	124	97
98	32	32	98
99	44	44	99
100	100	100	100
101	62	140	101
102	119	93	102
103	38	64	103
104	91	26	104
105	118	40	105
106	50	24	106
107	68	94	107
108	4	69	108
109	21	21	109
110	33	33	110
111	45	45	111
112	18	96	112
113	9	126	113
114	49	75	114
115	80	15	115
116	129	51	116
117	39	13	117
118	79	105	118
119	37	102	119
120	120	120	120
121	121	121	121
122	34	34	122
123	7	85	123
124	97	71	124
125	5	31	125
126	113	48	126
127	140	62	127
128	28	2	128
129	90	116	129
130	26	91	130
131	131	131	131
132	11	11	132
133	133	133	133
134	95	30	134
135	86	60	135
136	137	20	136
137	58	136	137
138	96	18	138
139	61	35	139
140	101	127	140
141	15	80	141
142	142	142	142

a	a^e	a^d	a^ed
0	0	0	0
1	1	1	1
2	128	63	2
3	42	16	3
4	82	108	4
5	47	125	5
6	85	7	6
7	6	123	7
8	57	83	8
9	48	113	9
10	10	10	10
11	132	132	11
12	12	12	12
13	117	52	13
14	53	27	14
15	115	141	15
16	3	81	16
17	30	95	17
18	138	112	18
19	46	72	19
20	136	58	20
21	109	109	21
22	22	22	22
23	23	23	23
24	106	41	24
25	64	38	25
26	104	130	26
27	14	92	27
28	63	128	28
29	94	68	29
30	134	17	30
31	125	47	31
32	98	98	32
33	110	110	33
34	122	122	34
35	139	74	35
36	75	49	36
37	93	119	37
38	25	103	38
39	52	117	39
40	105	79	40
41	24	50	41
42	81	3	42
43	43	43	43
44	99	99	44
45	111	111	45
46	84	19	46
47	31	5	47
48	126	9	48
49	36	114	49
50	41	106	50
51	116	90	51
52	13	39	52
53	92	14	53
54	76	76	54
55	55	55	55
56	56	56	56
57	73	8	57
58	20	137	58
59	71	97	59
60	135	70	60
61	74	139	61
62	127	101	62
63	2	28	63
64	103	25	64
65	65	65	65
66	66	66	66
67	89	89	67
68	29	107	68
69	108	82	69
70	60	86	70
71	124	59	71
72	19	84	72
73	83	57	73
74	35	61	74
75	114	36	75
76	54	54	76
77	77	77	77
78	78	78	78
79	40	118	79
80	141	115	80
81	16	42	81
82	69	4	82
83	8	73	83
84	72	46	84
85	123	6	85
86	70	135	86
87	87	87	87
88	88	88	88
89	67	67	89
90	51	129	90
91	130	104	91
92	27	53	92
93	102	37	93
94	107	29	94
95	17	134	95
96	112	138	96
97	59	124	97
98	32	32	98
99	44	44	99
100	100	100	100
101	62	140	101
102	119	93	102
103	38	64	103
104	91	26	104
105	118	40	105
106	50	24	106
107	68	94	107
108	4	69	108
109	21	21	109
110	33	33	110
111	45	45	111
112	18	96	112
113	9	126	113
114	49	75	114
115	80	15	115
116	129	51	116
117	39	13	117
118	79	105	118
119	37	102	119
120	120	120	120
121	121	121	121
122	34	34	122
123	7	85	123
124	97	71	124
125	5	31	125
126	113	48	126
127	140	62	127
128	28	2	128
129	90	116	129
130	26	91	130
131	131	131	131
132	11	11	132
133	133	133	133
134	95	30	134
135	86	60	135
136	137	20	136
137	58	136	137
138	96	18	138
139	61	35	139
140	101	127	140
141	15	80	141
142	142	142	142

a	a^e	a^d	a^ed
0	0	0	0
1	1	1	1
2	128	63	2
3	42	16	3
4	82	108	4
5	47	125	5
6	85	7	6
7	6	123	7
8	57	83	8
9	48	113	9
10	10	10	10
11	132	132	11
12	12	12	12
13	117	52	13
14	53	27	14
15	115	141	15
16	3	81	16
17	30	95	17
18	138	112	18
19	46	72	19
20	136	58	20
21	109	109	21
22	22	22	22
23	23	23	23
24	106	41	24
25	64	38	25
26	104	130	26
27	14	92	27
28	63	128	28
29	94	68	29
30	134	17	30
31	125	47	31
32	98	98	32
33	110	110	33
34	122	122	34
35	139	74	35
36	75	49	36
37	93	119	37
38	25	103	38
39	52	117	39
40	105	79	40
41	24	50	41
42	81	3	42
43	43	43	43
44	99	99	44
45	111	111	45
46	84	19	46
47	31	5	47
48	126	9	48
49	36	114	49
50	41	106	50
51	116	90	51
52	13	39	52
53	92	14	53
54	76	76	54
55	55	55	55
56	56	56	56
57	73	8	57
58	20	137	58
59	71	97	59
60	135	70	60
61	74	139	61
62	127	101	62
63	2	28	63
64	103	25	64
65	65	65	65
66	66	66	66
67	89	89	67
68	29	107	68
69	108	82	69
70	60	86	70
71	124	59	71
72	19	84	72
73	83	57	73
74	35	61	74
75	114	36	75
76	54	54	76
77	77	77	77
78	78	78	78
79	40	118	79
80	141	115	80
81	16	42	81
82	69	4	82
83	8	73	83
84	72	46	84
85	123	6	85
86	70	135	86
87	87	87	87
88	88	88	88
89	67	67	89
90	51	129	90
91	130	104	91
92	27	53	92
93	102	37	93
94	107	29	94
95	17	134	95
96	112	138	96
97	59	124	97
98	32	32	98
99	44	44	99
100	100	100	100
101	62	140	101
102	119	93	102
103	38	64	103
104	91	26	104
105	118	40	105
106	50	24	106
107	68	94	107
108	4	69	108
109	21	21	109
110	33	33	110
111	45	45	111
112	18	96	112
113	9	126	113
114	49	75	114
115	80	15	115
116	129	51	116
117	39	13	117
118	79	105	118
119	37	102	119
120	120	120	120
121	121	121	121
122	34	34	122
123	7	85	123
124	97	71	124
125	5	31	125
126	113	48	126
127	140	62	127
128	28	2	128
129	90	116	129
130	26	91	130
131	131	131	131
132	11	11	132
133	133	133	133
134	95	30	134
135	86	60	135
136	137	20	136
137	58	136	137
138	96	18	138
139	61	35	139
140	101	127	140
141	15	80	141
142	142	142	142

a	a^e	a^d	a^ed
0	0	0	0
1	1	1	1
2	128	63	2
3	42	16	3
4	82	108	4
5	47	125	5
6	85	7	6
7	6	123	7
8	57	83	8
9	48	113	9
10	10	10	10
11	132	132	11
12	12	12	12
13	117	52	13
14	53	27	14
15	115	141	15
16	3	81	16
17	30	95	17
18	138	112	18
19	46	72	19
20	136	58	20
21	109	109	21
22	22	22	22
23	23	23	23
24	106	41	24
25	64	38	25
26	104	130	26
27	14	92	27
28	63	128	28
29	94	68	29
30	134	17	30
31	125	47	31
32	98	98	32
33	110	110	33
34	122	122	34
35	139	74	35
36	75	49	36
37	93	119	37
38	25	103	38
39	52	117	39
40	105	79	40
41	24	50	41
42	81	3	42
43	43	43	43
44	99	99	44
45	111	111	45
46	84	19	46
47	31	5	47
48	126	9	48
49	36	114	49
50	41	106	50
51	116	90	51
52	13	39	52
53	92	14	53
54	76	76	54
55	55	55	55
56	56	56	56
57	73	8	57
58	20	137	58
59	71	97	59
60	135	70	60
61	74	139	61
62	127	101	62
63	2	28	63
64	103	25	64
65	65	65	65
66	66	66	66
67	89	89	67
68	29	107	68
69	108	82	69
70	60	86	70
71	124	59	71
72	19	84	72
73	83	57	73
74	35	61	74
75	114	36	75
76	54	54	76
77	77	77	77
78	78	78	78
79	40	118	79
80	141	115	80
81	16	42	81
82	69	4	82
83	8	73	83
84	72	46	84
85	123	6	85
86	70	135	86
87	87	87	87
88	88	88	88
89	67	67	89
90	51	129	90
91	130	104	91
92	27	53	92
93	102	37	93
94	107	29	94
95	17	134	95
96	112	138	96
97	59	124	97
98	32	32	98
99	44	44	99
100	100	100	100
101	62	140	101
102	119	93	102
103	38	64	103
104	91	26	104
105	118	40	105
106	50	24	106
107	68	94	107
108	4	69	108
109	21	21	109
110	33	33	110
111	45	45	111
112	18	96	112
113	9	126	113
114	49	75	114
115	80	15	115
116	129	51	116
117	39	13	117
118	79	105	118
119	37	102	119
120	120	120	120
121	121	121	121
122	34	34	122
123	7	85	123
124	97	71	124
125	5	31	125
126	113	48	126
127	140	62	127
128	28	2	128
129	90	116	129
130	26	91	130
131	131	131	131
132	11	11	132
133	133	133	133
134	95	30	134
135	86	60	135
136	137	20	136
137	58	136	137
138	96	18	138
139	61	35	139
140	101	127	140
141	15	80	141
142	142	142	142