1
00:00:00,500 --> 00:00:02,660
The following content is
provided under a Creative
2
00:00:02,660 --> 00:00:04,180
Commons license.
3
00:00:04,180 --> 00:00:06,520
Your support will help
MIT OpenCourseWare
4
00:00:06,520 --> 00:00:10,880
continue to offer high quality
educational resources for free.
5
00:00:10,880 --> 00:00:13,500
To make a donation or
view additional materials
6
00:00:13,500 --> 00:00:17,396
from hundreds of MIT courses,
visit MIT OpenCourseWare
7
00:00:17,396 --> 00:00:18,021
at ocw.mit.edu.
8
00:00:23,120 --> 00:00:26,280
PROFESSOR: So let's get ready.
9
00:00:26,280 --> 00:00:29,000
If good, you should
receive some handouts.
10
00:00:29,000 --> 00:00:36,767
So the TAs are walking around,
so you should slowly get those.
11
00:00:36,767 --> 00:00:38,600
This is the second
lecture on number theory,
12
00:00:38,600 --> 00:00:40,990
and we're going to cover
for a lot of stuff.
13
00:00:40,990 --> 00:00:42,510
And actually, we're
going to start
14
00:00:42,510 --> 00:00:48,540
with encryption, which is an
application of number theory.
15
00:00:48,540 --> 00:00:51,914
And we'll take that as a theme
throughout the whole lecture.
16
00:00:51,914 --> 00:00:54,455
And so, in this way, you can
see how useful number theory is.
17
00:00:58,410 --> 00:01:02,040
Now, encryption--
yeah, what is it?
18
00:01:02,040 --> 00:01:04,680
So let's first talk
about it a little bit.
19
00:01:04,680 --> 00:01:06,820
Maybe some of you
have heard about it.
20
00:01:06,820 --> 00:01:11,100
Cryptology in general is the
art of hiding information.
21
00:01:11,100 --> 00:01:13,660
And encryption is
a very useful tool.
22
00:01:13,660 --> 00:01:15,420
I'll only give a very
high level overview.
23
00:01:15,420 --> 00:01:17,544
I mean, if you really want
to know more about this,
24
00:01:17,544 --> 00:01:22,401
you should do a class in
crypto, or practical security.
25
00:01:22,401 --> 00:01:23,275
So what's encryption?
26
00:01:29,520 --> 00:01:32,970
The idea is usually
that, beforehand, we're
27
00:01:32,970 --> 00:01:39,490
going to share a
whole bunch of keys.
28
00:01:39,490 --> 00:01:47,370
So keys are exchanged between
a receiver and a sender.
29
00:01:47,370 --> 00:01:51,140
And the whole idea is that
if I want to transmit, like,
30
00:01:51,140 --> 00:01:54,380
a message to one
of you, well, there
31
00:01:54,380 --> 00:01:56,820
could be someone
in the middle who
32
00:01:56,820 --> 00:01:59,560
wants to intercept
my message, and wants
33
00:01:59,560 --> 00:02:01,060
to find out what I'm saying.
34
00:02:01,060 --> 00:02:02,690
So I do not like this.
35
00:02:02,690 --> 00:02:07,560
And in order to avoid it,
I will use encryption,
36
00:02:07,560 --> 00:02:13,600
which is some kind of algorithm
that actually transforms
37
00:02:13,600 --> 00:02:17,790
my message m-- my plain
message-- by using
38
00:02:17,790 --> 00:02:21,800
some kind of algorithm, E.
Some encryption algorithm--
39
00:02:21,800 --> 00:02:26,760
it can be a function as
well-- that uses the keys
40
00:02:26,760 --> 00:02:32,040
in order to transform this
into an encryption, which
41
00:02:32,040 --> 00:02:33,850
we call m prime here.
42
00:02:33,850 --> 00:02:38,370
So the plain text is, in the
clear, all the information
43
00:02:38,370 --> 00:02:41,260
that I want to convey to
one of you, for example.
44
00:02:41,260 --> 00:02:48,480
And m prime is somehow
a complete-- well,
45
00:02:48,480 --> 00:02:52,190
a mixture of bits,
out of which I'm not
46
00:02:52,190 --> 00:02:55,240
able to distill any information
about the plain text.
47
00:02:55,240 --> 00:02:58,080
So encryption to a very
special kind of thing.
48
00:02:58,080 --> 00:03:01,420
We're not going to talk about
the precise definitions here,
49
00:03:01,420 --> 00:03:05,650
but we just take the
ID into this lecture.
50
00:03:05,650 --> 00:03:10,810
Now, decryption is transforming
the cypher text back
51
00:03:10,810 --> 00:03:11,830
into the plain text.
52
00:03:11,830 --> 00:03:17,190
So we will start with
the encryption, m prime,
53
00:03:17,190 --> 00:03:19,820
and we have some kind
of decryption algorithm.
54
00:03:19,820 --> 00:03:24,050
And again, we can make use
of the keys we exchanged.
55
00:03:24,050 --> 00:03:27,910
And we transform it back
into the plain message.
56
00:03:27,910 --> 00:03:30,340
So only if I know the
keys, I can actually
57
00:03:30,340 --> 00:03:35,060
transform back the encrypted
version into the plain version.
58
00:03:35,060 --> 00:03:38,980
So in encryption schemes we
like both these algorithms
59
00:03:38,980 --> 00:03:41,430
to be is really efficient.
60
00:03:41,430 --> 00:03:45,680
And the security of such a
scheme-- well, the first kind
61
00:03:45,680 --> 00:03:48,780
of intuition that
we can get is well,
62
00:03:48,780 --> 00:03:51,800
if I'm a man in the
middle somewhere,
63
00:03:51,800 --> 00:03:55,740
intercepting an encrypted
message-- m prime--
64
00:03:55,740 --> 00:03:58,840
I should not be able to
get any information about m
65
00:03:58,840 --> 00:04:02,400
if I have no knowledge
about those keys.
66
00:04:02,400 --> 00:04:05,552
So this is the
example that we're
67
00:04:05,552 --> 00:04:10,160
going to take throughout
this whole lecture.
68
00:04:10,160 --> 00:04:17,440
So let's start with a
first possible scheme.
69
00:04:17,440 --> 00:04:25,380
Turing, who lived around
1936-- he was 24 years old--
70
00:04:25,380 --> 00:04:29,760
and he lived to
about-- actually,
71
00:04:29,760 --> 00:04:32,780
I think he was about
54 when he died.
72
00:04:32,780 --> 00:04:37,600
In any case, Turing was the one
who first originally proposed
73
00:04:37,600 --> 00:04:40,350
to use number theory
in cryptography.
74
00:04:40,350 --> 00:04:44,280
And before he joined the British
army, before the Second World
75
00:04:44,280 --> 00:04:49,270
War, he actually
proposed a scheme,
76
00:04:49,270 --> 00:04:50,700
but it got never published.
77
00:04:50,700 --> 00:04:52,480
So here in this
class, we are going
78
00:04:52,480 --> 00:04:56,000
to try to think about what
he could have thought about.
79
00:04:56,000 --> 00:04:59,540
So we will have a
first scheme, which
80
00:04:59,540 --> 00:05:04,510
we will call Turing's
code, version number one.
81
00:05:04,510 --> 00:05:07,490
And the whole idea
is that we're going
82
00:05:07,490 --> 00:05:11,520
to translate a message first
of all into a prime number,
83
00:05:11,520 --> 00:05:13,430
because we want to use numbers.
84
00:05:13,430 --> 00:05:14,930
We're here in
number theory class,
85
00:05:14,930 --> 00:05:17,230
so we want to use some
tricks with numbers in order
86
00:05:17,230 --> 00:05:18,810
to encrypt it.
87
00:05:18,810 --> 00:05:19,800
So let's do this.
88
00:05:24,620 --> 00:05:27,780
So for example, let's
take the word victory.
89
00:05:30,460 --> 00:05:33,270
We can map this into an integer.
90
00:05:33,270 --> 00:05:38,850
For example, we could
say, well, m is 22,
91
00:05:38,850 --> 00:05:42,250
where I map V to--
because I know
92
00:05:42,250 --> 00:05:46,600
V is the 22nd letter in the
alphabet, I just start with 22.
93
00:05:46,600 --> 00:05:52,890
I is the ninth letter in the
alphabet, so I append 09.
94
00:05:52,890 --> 00:05:57,470
C is the third letter in the
alphabet, I append 3-- 03.
95
00:05:57,470 --> 00:06:02,820
I continue like this
and in end, over here
96
00:06:02,820 --> 00:06:06,240
I've mapped Y to
the 25th letter.
97
00:06:06,240 --> 00:06:09,820
Because it's the 25th letter
of alphabet, I write 25.
98
00:06:09,820 --> 00:06:12,520
It turns out, I can just
add a couple of digits
99
00:06:12,520 --> 00:06:15,030
more, if I specially
compute those.
100
00:06:15,030 --> 00:06:18,630
In this case, I could
add 13, and then it
101
00:06:18,630 --> 00:06:20,250
changes into a prime number.
102
00:06:23,990 --> 00:06:26,000
Now we are not going to
talk about why this is,
103
00:06:26,000 --> 00:06:27,810
and how this can
be done, and so on.
104
00:06:27,810 --> 00:06:31,350
But it turns out that the
prime numbers are densely
105
00:06:31,350 --> 00:06:35,090
distributed over the integers,
and it's really possible to,
106
00:06:35,090 --> 00:06:39,110
just with a few extra
digits-- by selecting them
107
00:06:39,110 --> 00:06:41,820
in a smart way-- to actually
create a prime number.
108
00:06:41,820 --> 00:06:45,100
And also verify that it is a
prime number very efficiently.
109
00:06:45,100 --> 00:06:49,880
So it's very easy to compute--
to translate such a word
110
00:06:49,880 --> 00:06:51,490
into a prime number.
111
00:06:51,490 --> 00:06:53,600
So this is how it all starts.
112
00:06:53,600 --> 00:06:56,950
And just like in an
encryption scheme,
113
00:06:56,950 --> 00:07:04,490
beforehand we are going
to exchange a key.
114
00:07:04,490 --> 00:07:13,730
So we exchange the secret
prime in this example,
115
00:07:13,730 --> 00:07:15,790
which we call k.
116
00:07:15,790 --> 00:07:20,030
And the encryption
is very simple.
117
00:07:20,030 --> 00:07:24,210
We are just going to
multiply m with k.
118
00:07:24,210 --> 00:07:27,050
Now, you may wonder why this
is such a fantastic idea.
119
00:07:27,050 --> 00:07:29,750
But let's just bear with me.
120
00:07:29,750 --> 00:07:33,970
So m is this first prime
number, and we multiply it
121
00:07:33,970 --> 00:07:35,480
by a second prime
number, and that's
122
00:07:35,480 --> 00:07:38,810
going to be our encryption.
123
00:07:38,810 --> 00:07:40,132
Now how do we decrypt?
124
00:07:40,132 --> 00:07:42,090
That seems to be pretty
straightforward, right?
125
00:07:42,090 --> 00:07:44,560
How do we do it?
126
00:07:44,560 --> 00:07:47,350
We start off with m prime.
127
00:07:47,350 --> 00:07:50,490
I know we have exchanged
this secret prime k,
128
00:07:50,490 --> 00:07:54,110
so if I receive from
you this message--
129
00:07:54,110 --> 00:07:57,050
this encrypted message--
well, I know the key, k.
130
00:07:57,050 --> 00:07:59,820
So I just divide it by k.
131
00:07:59,820 --> 00:08:05,030
Well, which is m k
divided k, and I get m.
132
00:08:05,030 --> 00:08:07,730
So that's pretty
straightforward.
133
00:08:07,730 --> 00:08:10,880
Now, as it turns out actually--
and I'll write it up here,
134
00:08:10,880 --> 00:08:16,900
because we need it later-- that
it's not so trivial to actually
135
00:08:16,900 --> 00:08:23,020
just give an m prime to
figure out what m is, or k.
136
00:08:23,020 --> 00:08:26,450
m prime is a product of two
very large prime numbers,
137
00:08:26,450 --> 00:08:28,996
and that turns out to be
a really hard problem.
138
00:08:28,996 --> 00:08:30,370
Up to now, nobody
has really been
139
00:08:30,370 --> 00:08:34,159
able to get a really efficient
algorithm to solve that.
140
00:08:34,159 --> 00:08:36,610
So we may think this is secure.
141
00:08:36,610 --> 00:08:45,630
So let me write it down
It's hard to factor
142
00:08:45,630 --> 00:08:48,460
a product of two large primes.
143
00:08:57,850 --> 00:08:59,830
You will actually
need this also,
144
00:08:59,830 --> 00:09:02,970
when we come to the final
encryption scheme-- RSA
145
00:09:02,970 --> 00:09:05,580
that we will discuss,
which is widely used.
146
00:09:13,241 --> 00:09:14,740
But something is
wrong here, though.
147
00:09:14,740 --> 00:09:16,510
This seems to be
too simple, right?
148
00:09:16,510 --> 00:09:19,040
So what can we do if
we have like, say,
149
00:09:19,040 --> 00:09:22,970
suppose I intercept
two encrypted messages.
150
00:09:22,970 --> 00:09:23,680
What can I do?
151
00:09:31,800 --> 00:09:35,900
So suppose I have
a first message, m
152
00:09:35,900 --> 00:09:39,920
prime 1, which is the product
of a first plain message
153
00:09:39,920 --> 00:09:41,800
times the key, k.
154
00:09:41,800 --> 00:09:44,490
And I have a second
message that is
155
00:09:44,490 --> 00:09:49,480
encrypted by using the same
key, which is m 2 times k.
156
00:09:49,480 --> 00:09:51,730
Does anybody have an idea
what I could do here?
157
00:09:51,730 --> 00:09:55,400
AUDIENCE: Find the GCD and
that would give you the key.
158
00:09:55,400 --> 00:09:58,680
PROFESSOR: Yeah, you
could find the GCD
159
00:09:58,680 --> 00:10:04,000
of m 1 prime and m 2 prime.
160
00:10:04,000 --> 00:10:05,720
I've intercepted those two.
161
00:10:05,720 --> 00:10:08,220
Now, m 1 is a prime number.
162
00:10:08,220 --> 00:10:10,160
k is prime number, and
2 is a prime number.
163
00:10:10,160 --> 00:10:11,970
k is a prime number
here, also, right?
164
00:10:11,970 --> 00:10:16,690
So they're all relatively
prime towards one another.
165
00:10:16,690 --> 00:10:23,080
The GCD of these two-- well, the
greatest common divisor is k.
166
00:10:23,080 --> 00:10:27,390
So just by calculating the GCD
of the two encrypted messages,
167
00:10:27,390 --> 00:10:33,070
I'll be able to figure
out what k is-- the key.
168
00:10:33,070 --> 00:10:35,800
Well, if I know
the key, then I can
169
00:10:35,800 --> 00:10:38,440
do the decryption
of any cypher text,
170
00:10:38,440 --> 00:10:42,360
any encryption of a message
that I can intercept.
171
00:10:42,360 --> 00:10:44,730
So this is not secure.
172
00:10:44,730 --> 00:10:47,030
So how can we change this?
173
00:10:47,030 --> 00:10:53,870
Can we create a different
kind of encryption scheme?
174
00:10:53,870 --> 00:10:56,710
Let's do something
much more difficult,
175
00:10:56,710 --> 00:11:01,550
and then we will get into
modular arithmetic and things
176
00:11:01,550 --> 00:11:02,387
like that.
177
00:11:02,387 --> 00:11:03,095
So let's do this.
178
00:11:08,290 --> 00:11:11,950
So Turing's code,
version number two--
179
00:11:11,950 --> 00:11:15,420
we try to do something much
more complicated than just
180
00:11:15,420 --> 00:11:17,050
multiplying by prime.
181
00:11:17,050 --> 00:11:19,230
So let's do the following.
182
00:11:19,230 --> 00:11:27,270
So beforehand, we're
going to exchange not only
183
00:11:27,270 --> 00:11:33,890
a secret prime k, but we will
also exchange a public prime.
184
00:11:33,890 --> 00:11:39,430
So we exchange-- by public
we mean that anybody
185
00:11:39,430 --> 00:11:40,630
can see this prime.
186
00:11:40,630 --> 00:11:42,790
It's common knowledge.
187
00:11:42,790 --> 00:11:54,240
A public prime p, and
also a secret prime k.
188
00:11:54,240 --> 00:11:57,780
Let's see whether
this would work.
189
00:11:57,780 --> 00:11:58,595
We have encryption.
190
00:12:01,490 --> 00:12:04,680
Well, we're going to start
out exactly the same way.
191
00:12:07,870 --> 00:12:11,450
First of all, I should tell you
how a message is represented.
192
00:12:11,450 --> 00:12:19,360
The message is going to be
represented as a number, m,
193
00:12:19,360 --> 00:12:25,270
in the range from 0, 1,
all the way to p minus 1.
194
00:12:25,270 --> 00:12:31,988
And we will compute the
encryption as follows.
195
00:12:31,988 --> 00:12:38,970
m is going to be the
remainder of m times k,
196
00:12:38,970 --> 00:12:42,930
after dividing out as many
multiples of p as possible.
197
00:12:42,930 --> 00:12:45,560
So notice we do kind
of the same thing.
198
00:12:45,560 --> 00:12:47,830
We just multiply
by k, but now we
199
00:12:47,830 --> 00:12:51,730
just take the remainder
after taking out
200
00:12:51,730 --> 00:12:55,080
as many multiples of p.
201
00:12:55,080 --> 00:12:58,650
Well, let's see whether
we can do the decryption.
202
00:12:58,650 --> 00:13:01,950
It seems to be, like, a
next level of complexity.
203
00:13:01,950 --> 00:13:04,900
So maybe that'll
help us here, right?
204
00:13:04,900 --> 00:13:06,750
So how will we do decryption?
205
00:13:06,750 --> 00:13:09,630
Well, somehow we would
like to divide by k.
206
00:13:09,630 --> 00:13:11,940
But we cannot really
do that, right?
207
00:13:11,940 --> 00:13:15,570
This does not make any sense.
208
00:13:15,570 --> 00:13:17,990
So the decryption-- we
have no idea at this point
209
00:13:17,990 --> 00:13:19,410
how to do this.
210
00:13:19,410 --> 00:13:23,070
And now we can get into
modular arithmetic,
211
00:13:23,070 --> 00:13:26,220
because it turns out that
we can sort of divide by k.
212
00:13:26,220 --> 00:13:29,790
There exists what we call
multiplicative inverse
213
00:13:29,790 --> 00:13:31,720
of k modulo p.
214
00:13:31,720 --> 00:13:34,580
And I will explain all
those terminologies to you.
215
00:13:34,580 --> 00:13:39,260
And then we will be
able to take m prime,
216
00:13:39,260 --> 00:13:42,320
and transform it back to m.
217
00:13:42,320 --> 00:13:48,160
So we will be able to get a
lot of this machinery going.
218
00:13:48,160 --> 00:13:52,250
So let's find out
how this works.
219
00:13:52,250 --> 00:13:58,510
So first of all, last time we
saw that we defined a and b
220
00:13:58,510 --> 00:13:59,870
to be relatively prime.
221
00:13:59,870 --> 00:14:03,030
So let me repeat that.
222
00:14:03,030 --> 00:14:07,400
So a and b are relatively
prime if and only
223
00:14:07,400 --> 00:14:13,190
if-- that's how we define
it-- if the GCD of a and b
224
00:14:13,190 --> 00:14:13,810
is equal to 1.
225
00:14:13,810 --> 00:14:17,610
And in last lecture
and in the recitation,
226
00:14:17,610 --> 00:14:19,860
you got a different
proof, I think.
227
00:14:19,860 --> 00:14:25,300
And we proved that,
actually, the GCD of a and b
228
00:14:25,300 --> 00:14:28,560
is equal to the smallest
positive linear combination
229
00:14:28,560 --> 00:14:30,780
of a and b.
230
00:14:30,780 --> 00:14:32,880
So that means that
one, in particular,
231
00:14:32,880 --> 00:14:34,500
is a linear
combination of a and b.
232
00:14:34,500 --> 00:14:39,010
So there exists
integers-- s and t--
233
00:14:39,010 --> 00:14:44,041
such that s times a,
plus t times b equals 1.
234
00:14:44,041 --> 00:14:46,290
It turns out that it can
also go the other way around,
235
00:14:46,290 --> 00:14:51,930
because if I can write one as
a linear combination of a b,
236
00:14:51,930 --> 00:14:54,060
well I cannot get much
lower than that, right?
237
00:14:54,060 --> 00:14:56,730
So that's really the smallest
possible that I can achieve.
238
00:14:56,730 --> 00:15:00,080
So the GCD must be equal to 1.
239
00:15:00,080 --> 00:15:01,940
So this is a property
that we will be using.
240
00:15:06,130 --> 00:15:09,910
And from this property,
we can already figure out
241
00:15:09,910 --> 00:15:10,940
an interesting property.
242
00:15:10,940 --> 00:15:13,500
So suppose we have a
linear combination that
243
00:15:13,500 --> 00:15:15,100
looks like this.
244
00:15:15,100 --> 00:15:17,720
Then you can imagine
that, sort of,
245
00:15:17,720 --> 00:15:22,260
that s times a is equal
to 1, plus or minus
246
00:15:22,260 --> 00:15:26,300
some linear multiple of b.
247
00:15:26,300 --> 00:15:30,200
So it's sort of-- s times
a is sort of equal to 1,
248
00:15:30,200 --> 00:15:33,480
you can say, up to
a multiple of b.
249
00:15:33,480 --> 00:15:39,000
So you can see a sort
of as an inverse of s.
250
00:15:39,000 --> 00:15:42,380
Because s times a is
equal to one, sort of.
251
00:15:42,380 --> 00:15:45,660
So this is what we're going
to use-- this kind of feeling.
252
00:15:45,660 --> 00:15:50,745
And in order to do that, we
are going to define congruency.
253
00:15:55,230 --> 00:15:58,300
So that's the first
definition for this lecture.
254
00:15:58,300 --> 00:16:10,940
We say x is congruent
to y modulo n,
255
00:16:10,940 --> 00:16:18,160
if-- which we denote as
follows-- x with three bars,
256
00:16:18,160 --> 00:16:22,460
y in between brackets, mod n.
257
00:16:22,460 --> 00:16:31,330
And we say that this is
the case if n divides
258
00:16:31,330 --> 00:16:34,150
the difference between x and y.
259
00:16:34,150 --> 00:16:36,845
So let's have a look
at some examples.
260
00:16:44,580 --> 00:16:49,130
So let's take 31,
and I would like
261
00:16:49,130 --> 00:16:53,250
to show to you that
this is congruent to 16
262
00:16:53,250 --> 00:16:57,570
modulo, between brackets, 5.
263
00:16:57,570 --> 00:16:58,550
Why is this?
264
00:16:58,550 --> 00:17:02,910
Well, I take the difference
between 31 and 16, which is 15,
265
00:17:02,910 --> 00:17:08,700
and I know that 15 is 3 times
5, so 5 divides this difference.
266
00:17:08,700 --> 00:17:12,210
And then by definition,
we can write it like this.
267
00:17:12,210 --> 00:17:14,390
And we say-- that's
the definition--
268
00:17:14,390 --> 00:17:17,730
31 is congruent to 16 modulo 5.
269
00:17:17,730 --> 00:17:24,290
Another example is-- no, we
will stick with this example.
270
00:17:24,290 --> 00:17:26,569
It's pretty clear.
271
00:17:26,569 --> 00:17:31,920
So once we have defined this,
we can continue and talk
272
00:17:31,920 --> 00:17:34,310
about this inverse that
I was talking about.
273
00:17:34,310 --> 00:17:39,020
So we like to, sort of, explain
in this encryption scheme
274
00:17:39,020 --> 00:17:42,540
how we can divide by k.
275
00:17:42,540 --> 00:17:46,310
Actually, we would like to
multiply by an inverse of k.
276
00:17:46,310 --> 00:17:50,420
And we're going to
use this framework.
277
00:17:50,420 --> 00:17:54,140
So we'll have a
new definition that
278
00:17:54,140 --> 00:17:56,950
talks about the
multiplicative inverse.
279
00:17:56,950 --> 00:17:59,180
So it's a new concept.
280
00:17:59,180 --> 00:18:01,780
And you'll give a
couple of examples.
281
00:18:01,780 --> 00:18:15,350
So the multiplicative
inverse of x modulo n
282
00:18:15,350 --> 00:18:24,240
is a number, which we
denote by x and then minus 1
283
00:18:24,240 --> 00:18:27,290
on top of here.
284
00:18:27,290 --> 00:18:34,960
It's a number in the interval 0,
1, all the way up to n minus 1.
285
00:18:34,960 --> 00:18:41,800
Such that x times
x inverse-- so x
286
00:18:41,800 --> 00:18:44,190
times its
multiplicative inverse--
287
00:18:44,190 --> 00:18:49,440
is congruent to 1 modulo n.
288
00:18:49,440 --> 00:18:52,810
So this is the definition
for a multiplicative inverse.
289
00:18:52,810 --> 00:18:55,180
So let's have some examples.
290
00:19:00,440 --> 00:19:02,890
So let's do that over here.
291
00:19:02,890 --> 00:19:10,690
For example, we have that 2
times 3-- which equals 6--
292
00:19:10,690 --> 00:19:15,900
is equal to 1 modulo 5.
293
00:19:15,900 --> 00:19:16,680
Why is this?
294
00:19:16,680 --> 00:19:20,310
Well, 6 minus 1
is divisible by 5,
295
00:19:20,310 --> 00:19:24,720
so I know is congruent
to 1 modulo 5.
296
00:19:24,720 --> 00:19:27,130
So what does this mean?
297
00:19:27,130 --> 00:19:29,160
Well, we can say
that two is actually
298
00:19:29,160 --> 00:19:36,460
equal to the multiplicative
inverse of 3 modulo 5.
299
00:19:36,460 --> 00:19:42,060
We can also say that write 3
is the multiplicative inverse
300
00:19:42,060 --> 00:19:45,450
of 2 modulo 5.
301
00:19:45,450 --> 00:19:48,800
Let's have another example, just
to make it a little bit more
302
00:19:48,800 --> 00:19:51,150
clear.
303
00:19:51,150 --> 00:19:54,370
We know that 5
times 5 equals 25,
304
00:19:54,370 --> 00:19:57,370
and this is
congruent to 1 modulo
305
00:19:57,370 --> 00:20:03,150
6, because 25 is
1 plus 4 times 6.
306
00:20:03,150 --> 00:20:05,040
So now we see something
funny happening,
307
00:20:05,040 --> 00:20:11,030
because 5 is actually equal to
its own multiplicative inverse
308
00:20:11,030 --> 00:20:11,720
modulo 6.
309
00:20:18,470 --> 00:20:21,310
So are there any questions
about these concepts?
310
00:20:21,310 --> 00:20:24,630
Because these are really
basic for the whole lecture,
311
00:20:24,630 --> 00:20:27,073
and this is what you really
need to understand if you do
312
00:20:27,073 --> 00:20:29,990
all the problem sets as well.
313
00:20:29,990 --> 00:20:32,160
Are there any questions?
314
00:20:32,160 --> 00:20:36,910
So now we can
actually start talking
315
00:20:36,910 --> 00:20:44,670
about this second version of the
Turing code that we invented.
316
00:20:44,670 --> 00:20:46,450
Let's have a look
at this remainder.
317
00:20:46,450 --> 00:20:48,430
So let's write it out again.
318
00:20:48,430 --> 00:20:53,750
The remainder of m times
k, after dividing out
319
00:20:53,750 --> 00:20:56,230
as many multiples of p.
320
00:20:56,230 --> 00:21:02,030
Well, we know that this is
congruent to m times k modulo
321
00:21:02,030 --> 00:21:03,990
p.
322
00:21:03,990 --> 00:21:06,020
So why is this?
323
00:21:06,020 --> 00:21:08,562
Well, we just apply the
definition over here.
324
00:21:08,562 --> 00:21:10,270
We take the difference
between those two.
325
00:21:10,270 --> 00:21:14,810
So here we have the
remainder of m times k,
326
00:21:14,810 --> 00:21:18,930
after dividing out as
many multiples of p.
327
00:21:18,930 --> 00:21:22,470
And if you subtract
that from m times k,
328
00:21:22,470 --> 00:21:26,350
well then we have something
that is a multiple of p,
329
00:21:26,350 --> 00:21:28,560
because that's what
we divided out.
330
00:21:28,560 --> 00:21:32,570
So the difference
is a multiple of p,
331
00:21:32,570 --> 00:21:34,810
so that means that p
divides the difference.
332
00:21:34,810 --> 00:21:37,950
And that's the definition of
saying that this remainder is
333
00:21:37,950 --> 00:21:40,540
congruent m k modulo p.
334
00:21:40,540 --> 00:21:44,750
So this is kind of
interesting, because now we
335
00:21:44,750 --> 00:21:48,570
can rewrite over there--
well, not really rewrite,
336
00:21:48,570 --> 00:21:53,240
but we can use this to analyze
the encryption over here.
337
00:21:53,240 --> 00:21:58,640
So m prime is equal
to this remainder.
338
00:21:58,640 --> 00:22:00,070
And we get a
beautifully equation.
339
00:22:00,070 --> 00:22:04,260
We see that the encryption is
congruent to the plain message,
340
00:22:04,260 --> 00:22:06,930
times the key modulo p.
341
00:22:06,930 --> 00:22:09,140
So how do I do decryption?
342
00:22:09,140 --> 00:22:12,330
I can use the multiplicative
inverse of k, right?
343
00:22:12,330 --> 00:22:15,510
So then I can divide k out.
344
00:22:18,770 --> 00:22:20,640
So let's write this out as well.
345
00:22:20,640 --> 00:22:25,410
So suppose I have a
multiplicative inverse--
346
00:22:25,410 --> 00:22:33,230
k to the power minus 1-- that
is congruent to 1 modulo p.
347
00:22:33,230 --> 00:22:34,710
Why do I do this?
348
00:22:34,710 --> 00:22:36,870
Why am I writing this out?
349
00:22:36,870 --> 00:22:39,950
Because you will see
that it is not always
350
00:22:39,950 --> 00:22:42,840
possible to have a
multiplicative inverse.
351
00:22:42,840 --> 00:22:45,170
That's going to be
really a big problem.
352
00:22:45,170 --> 00:22:50,380
And that's where all
these other functions
353
00:22:50,380 --> 00:22:53,330
come in-- the Euler totient
function and Euler's theorem,
354
00:22:53,330 --> 00:22:55,020
and so on.
355
00:22:55,020 --> 00:22:56,910
So it's not really
always the case.
356
00:22:56,910 --> 00:22:58,410
We'll give an
example in a moment.
357
00:22:58,410 --> 00:23:02,610
But suppose that we have a
multiplicative inverse-- modulo
358
00:23:02,610 --> 00:23:08,130
p-- well, then I'm
able to easily compute.
359
00:23:08,130 --> 00:23:13,810
I take m prime, I multiply
it with k inverse.
360
00:23:13,810 --> 00:23:21,630
Well, I'm substituting for
m prime, m times k-- times
361
00:23:21,630 --> 00:23:22,600
k inverse.
362
00:23:22,600 --> 00:23:24,500
I still have this left.
363
00:23:24,500 --> 00:23:29,690
Now I can say that this
is equal to 1 modulo p.
364
00:23:32,220 --> 00:23:39,030
So this is equal, or is
congruent, to m modulo p.
365
00:23:39,030 --> 00:23:41,440
So now we see how we
can do decryption.
366
00:23:41,440 --> 00:23:45,090
We simply use the
multiplicative inverse of k.
367
00:23:45,090 --> 00:23:48,700
And as in the first
Turing code, we
368
00:23:48,700 --> 00:23:51,710
are able to somehow
divide out-- so where
369
00:23:51,710 --> 00:23:54,346
did I have it-- to divide out k.
370
00:23:54,346 --> 00:23:56,470
I did it very differently--
I have a very different
371
00:23:56,470 --> 00:24:01,090
mathematical structure-- but the
idea is, essentially, the same.
372
00:24:01,090 --> 00:24:04,720
I have a multiplicative
inverse of k,
373
00:24:04,720 --> 00:24:07,710
and if I multiply this
with the encryption,
374
00:24:07,710 --> 00:24:10,920
I will get the plain
message, modulo p.
375
00:24:10,920 --> 00:24:13,660
So, am I finished
now is the question.
376
00:24:13,660 --> 00:24:21,150
Well, I know that m is in the
range of 0, 1, all the way up
377
00:24:21,150 --> 00:24:23,480
to p minus 1.
378
00:24:23,480 --> 00:24:29,150
So this means that I
can also rewrite m as--
379
00:24:29,150 --> 00:24:32,300
and I use a similar trick
as what I did over here--
380
00:24:32,300 --> 00:24:39,090
I can rewrite m as they
remainder of m prime times k
381
00:24:39,090 --> 00:24:45,210
inverse, after dividing out as
many copies of p as possible.
382
00:24:45,210 --> 00:24:48,590
So what we did here
is to first prove
383
00:24:48,590 --> 00:24:53,290
that the difference between
those two is a multiple of p.
384
00:24:53,290 --> 00:24:56,730
That's essentially
what congruent modulo p
385
00:24:56,730 --> 00:24:59,350
means-- that's the definition.
386
00:24:59,350 --> 00:25:02,890
So now that I know that the
difference is a multiple of p,
387
00:25:02,890 --> 00:25:09,350
and if I know that m is actually
in this range up to p minus 1,
388
00:25:09,350 --> 00:25:12,460
I can use what we
learned last lecture--
389
00:25:12,460 --> 00:25:16,230
and what the book was talking
about-- that the definition
390
00:25:16,230 --> 00:25:20,400
of the remainder of m prime
times k inverse-- this thing--
391
00:25:20,400 --> 00:25:22,350
after finding out
as many copies of p,
392
00:25:22,350 --> 00:25:25,440
is exactly this plain message m.
393
00:25:25,440 --> 00:25:27,234
OK, so now we the decryption.
394
00:25:27,234 --> 00:25:28,150
So this is decryption.
395
00:25:30,870 --> 00:25:35,040
And that sounds great.
396
00:25:35,040 --> 00:25:38,520
So now, of course, we
are wondering, well,
397
00:25:38,520 --> 00:25:43,170
if we can do this, can we also
attack this scheme, right?
398
00:25:43,170 --> 00:25:46,920
Can we do something bad with it?
399
00:25:46,920 --> 00:25:49,380
Well, it can be used
to break this code,
400
00:25:49,380 --> 00:25:52,730
but in a slightly
more complicated way.
401
00:25:55,700 --> 00:25:59,750
So let's see where I put that.
402
00:25:59,750 --> 00:26:04,290
Right, so what we are
going to use, now-- so when
403
00:26:04,290 --> 00:26:06,700
we talk about
security, and so on,
404
00:26:06,700 --> 00:26:08,560
you can think of
all kinds of ways
405
00:26:08,560 --> 00:26:10,940
to break an encryption scheme.
406
00:26:10,940 --> 00:26:14,620
So we started out with,
in the first version,
407
00:26:14,620 --> 00:26:17,140
well, what if I just
know the encryption?
408
00:26:17,140 --> 00:26:21,940
And then, well, I cannot know
anything about the plain text,
409
00:26:21,940 --> 00:26:25,720
simply because I know that it's
very hard to factor a product
410
00:26:25,720 --> 00:26:27,080
of two large primes.
411
00:26:27,080 --> 00:26:29,920
Then I said, but suppose
I know a little bit more
412
00:26:29,920 --> 00:26:30,660
as an adversary.
413
00:26:30,660 --> 00:26:33,580
Suppose I have a
plain message together
414
00:26:33,580 --> 00:26:37,430
with an encrypted message.
415
00:26:37,430 --> 00:26:39,600
Well, then I could
do this GCD trick
416
00:26:39,600 --> 00:26:43,000
and figure out and
break the scheme.
417
00:26:43,000 --> 00:26:45,310
And now we're going to
do something similar.
418
00:26:45,310 --> 00:26:52,290
And we say, well, suppose that
I do not know two encryptions,
419
00:26:52,290 --> 00:26:55,470
but I know a plain message.
420
00:26:55,470 --> 00:26:59,000
And in corresponding,
encrypted message.
421
00:26:59,000 --> 00:27:03,170
So if I know such a pair,
which is-- I mean, in practice,
422
00:27:03,170 --> 00:27:06,220
such type of information
will be leaked.
423
00:27:06,220 --> 00:27:07,740
Then in this case,
I can break it.
424
00:27:07,740 --> 00:27:12,700
So we call this the known
the plain text attack.
425
00:27:12,700 --> 00:27:21,760
And it assumes that we
know-- as an adversary,
426
00:27:21,760 --> 00:27:31,010
I know a message-- a plain
message, m-- and also
427
00:27:31,010 --> 00:27:40,330
an encryption of this
message, m prime.
428
00:27:40,330 --> 00:27:42,300
And m prime, according
to this scheme,
429
00:27:42,300 --> 00:27:47,590
is the remainder of m times
k, after the dividing out
430
00:27:47,590 --> 00:27:51,480
as many multiples
of p as possible.
431
00:27:51,480 --> 00:27:54,330
Now, we saw-- now,
suppose I know these two.
432
00:27:54,330 --> 00:27:56,550
I'm going to show
you how to break it.
433
00:27:56,550 --> 00:27:59,750
So let's have a look.
434
00:27:59,750 --> 00:28:04,860
The encryption, m prime, is
congruent to m times k modulo
435
00:28:04,860 --> 00:28:06,160
p.
436
00:28:06,160 --> 00:28:09,100
We just proved it over here.
437
00:28:09,100 --> 00:28:11,740
And what do we know?
438
00:28:11,740 --> 00:28:14,400
We know that p is
a public prime.
439
00:28:14,400 --> 00:28:16,590
I know p.
440
00:28:16,590 --> 00:28:24,290
Since it's a prime, I know that
the GCD of m and p equals 1.
441
00:28:24,290 --> 00:28:26,630
So these two are
relatively prime.
442
00:28:26,630 --> 00:28:29,500
So now if they are
relatively prime--
443
00:28:29,500 --> 00:28:31,620
and that's what
we wrote up here--
444
00:28:31,620 --> 00:28:35,080
we know that there exists
this linear combination
445
00:28:35,080 --> 00:28:43,310
of, in this case, m and
p that is equal to 1.
446
00:28:43,310 --> 00:28:45,740
And this way we
can figure out how
447
00:28:45,740 --> 00:28:51,590
to compute the inverse-- the
multiplicative inverse of m.
448
00:28:51,590 --> 00:28:54,020
So that's what
we're going to do.
449
00:28:54,020 --> 00:29:01,870
So we can compute and the
multiplicative inverse, such
450
00:29:01,870 --> 00:29:09,250
that m times m inverse is
congruent to 1 modulo p.
451
00:29:12,040 --> 00:29:15,190
So now we can do the next step.
452
00:29:15,190 --> 00:29:17,780
So what could I do next?
453
00:29:17,780 --> 00:29:21,890
So let's see, if I
have such an inverse,
454
00:29:21,890 --> 00:29:25,530
then I can take my
encrypted message
455
00:29:25,530 --> 00:29:30,330
that I have as an
attacker, which is m prime.
456
00:29:30,330 --> 00:29:33,310
I know m, and
since p was public,
457
00:29:33,310 --> 00:29:36,150
I can compute this
multiplicative inverse.
458
00:29:36,150 --> 00:29:40,370
So I could just
compute this product,
459
00:29:40,370 --> 00:29:46,350
and I know that this is actually
equal to, well, k times m times
460
00:29:46,350 --> 00:29:47,580
m inverse.
461
00:29:47,580 --> 00:29:51,370
This is again equal to--
congruent to 1 modulo p.
462
00:29:51,370 --> 00:29:55,700
So this is equal to k modulo p.
463
00:29:55,700 --> 00:29:59,080
So now, all of a sudden,
I know k modulo p,
464
00:29:59,080 --> 00:30:01,060
because I know those two.
465
00:30:01,060 --> 00:30:06,990
So if I know k, I can compute
its multiplicative inverse.
466
00:30:06,990 --> 00:30:13,230
So I can compute k
inverse modulo p.
467
00:30:13,230 --> 00:30:15,930
And if I know k
inverse, again, I
468
00:30:15,930 --> 00:30:20,690
can use it to decrypt any
other encrypted message
469
00:30:20,690 --> 00:30:22,290
that I receive.
470
00:30:22,290 --> 00:30:25,220
So for all future
encrypted messages,
471
00:30:25,220 --> 00:30:28,460
I do not need anymore
the plain messages.
472
00:30:28,460 --> 00:30:32,990
I've already used-- just
by using one plain message
473
00:30:32,990 --> 00:30:37,280
encryption pair, I have been
able to compute the secret key,
474
00:30:37,280 --> 00:30:39,990
and the whole scheme is broken.
475
00:30:39,990 --> 00:30:46,890
So security is kind of
an interesting science.
476
00:30:46,890 --> 00:30:49,040
We can always think
of more tricks
477
00:30:49,040 --> 00:30:53,480
to break schemes, or
other assumptions,
478
00:30:53,480 --> 00:30:56,070
that we haven't
thought about before.
479
00:30:56,070 --> 00:31:02,120
And so now, let's talk about--
so what did we do here?
480
00:31:04,750 --> 00:31:10,900
We have been talking about
encryption-- these two schemes.
481
00:31:10,900 --> 00:31:14,050
We talked about
modular arithmetic.
482
00:31:14,050 --> 00:31:16,060
We talked about
congruence, and also
483
00:31:16,060 --> 00:31:18,060
the multiplicative inverse.
484
00:31:18,060 --> 00:31:22,490
And we showed how to use that
to break Turing's code, version
485
00:31:22,490 --> 00:31:24,080
number two.
486
00:31:24,080 --> 00:31:26,910
So we need something
much more fundamental
487
00:31:26,910 --> 00:31:30,300
in order to create a scheme
that is really secure.
488
00:31:30,300 --> 00:31:32,070
And that's what we're
going to do now.
489
00:31:32,070 --> 00:31:35,820
We're going to start off with
Euler's totient function,
490
00:31:35,820 --> 00:31:38,780
and improve a related theorem.
491
00:31:38,780 --> 00:31:43,070
And with that we will be
able to actually explain
492
00:31:43,070 --> 00:31:46,490
RSA algorithm, which is a
famous algorithm invented here
493
00:31:46,490 --> 00:31:52,760
at MIT in 1977, by Rivest,
Shamir, and Adleman.
494
00:31:52,760 --> 00:31:55,820
And they actually also
got the Turing Award
495
00:31:55,820 --> 00:31:58,600
for this a few years ago.
496
00:31:58,600 --> 00:32:03,200
And it's widely
used in practice.
497
00:32:03,200 --> 00:32:05,070
But we will be able
to actually explain
498
00:32:05,070 --> 00:32:08,770
this algorithm with just this
fundamental piece of number
499
00:32:08,770 --> 00:32:09,490
theory.
500
00:32:09,490 --> 00:32:10,962
So that's really exciting.
501
00:32:10,962 --> 00:32:11,670
So let's do this.
502
00:32:16,390 --> 00:32:20,425
So we're going to first define
Euler's totient function.
503
00:32:31,290 --> 00:32:33,580
And it's related to this
multiplicative inverse.
504
00:32:48,510 --> 00:32:52,890
This function is
denoted phi of n,
505
00:32:52,890 --> 00:33:10,350
and it denote the
number of the integers
506
00:33:10,350 --> 00:33:16,460
in 1, 2, 3-- all the way
up to n minus 1, that
507
00:33:16,460 --> 00:33:29,400
are relatively prime to n.
508
00:33:29,400 --> 00:33:35,280
So this just drops out of
the air, you may think.
509
00:33:35,280 --> 00:33:40,830
But this is a
fundamental quantity,
510
00:33:40,830 --> 00:33:43,830
and Euler's theorem is what
we will try to prove next.
511
00:33:43,830 --> 00:33:45,750
But let's give a
couple of examples
512
00:33:45,750 --> 00:33:50,350
about this, just to
see how it works.
513
00:33:53,430 --> 00:33:58,070
So for example, let's
take n to be equal to 12.
514
00:33:58,070 --> 00:34:02,270
What would be the value of
Euler's totient function,
515
00:34:02,270 --> 00:34:05,150
evaluated for 12?
516
00:34:05,150 --> 00:34:15,010
So if you take 12, we have the
following numbers to consider.
517
00:34:15,010 --> 00:34:23,480
1, 2, 3, 4, 5, 6, 7,
8, 9, 10,11, and 12.
518
00:34:23,480 --> 00:34:24,900
So now, let's have a look.
519
00:34:27,996 --> 00:34:29,729
You want to count
the integers that
520
00:34:29,729 --> 00:34:31,850
are relatively prime to 12.
521
00:34:34,429 --> 00:34:37,230
Well, 1 is relatively
prime to 12.
522
00:34:37,230 --> 00:34:38,179
Why is that?
523
00:34:38,179 --> 00:34:42,570
Because to GCD of 12
and 1 is equal to 1,
524
00:34:42,570 --> 00:34:44,770
and that's the definition
of being relatively prime.
525
00:34:44,770 --> 00:34:47,510
So this is a good number.
526
00:34:47,510 --> 00:34:52,730
The GCD of 12 and 2, well
both are divisible by 2.
527
00:34:52,730 --> 00:34:55,685
So they're not relatively
prime, because the GCD
528
00:34:55,685 --> 00:34:56,909
is at least two.
529
00:34:56,909 --> 00:34:59,120
In this case, equal to 2.
530
00:34:59,120 --> 00:35:01,388
3 also divides 12.
531
00:35:01,388 --> 00:35:03,410
4 divides 12.
532
00:35:03,410 --> 00:35:07,020
5 is relatively prime
with respect to 12.
533
00:35:07,020 --> 00:35:11,500
6 actually is
dividing 12 as well.
534
00:35:11,500 --> 00:35:16,680
7 is relatively prime,
and 11 over here as well.
535
00:35:16,680 --> 00:35:19,510
And all the others have
a greatest common divisor
536
00:35:19,510 --> 00:35:21,390
that's larger than 1.
537
00:35:21,390 --> 00:35:26,010
So here we see that the Euler's
totient function evaluated
538
00:35:26,010 --> 00:35:28,100
in 12 is equal to 4.
539
00:35:28,100 --> 00:35:31,720
There are one, two,
three, four integers
540
00:35:31,720 --> 00:35:34,250
that are relatively prime.
541
00:35:34,250 --> 00:35:36,800
OK, so let's have
a different one.
542
00:35:36,800 --> 00:35:39,200
Say, n equals 15.
543
00:35:39,200 --> 00:35:42,040
It's little bit different,
because here you
544
00:35:42,040 --> 00:35:45,013
may think this is kind
of coincidental that 1,
545
00:35:45,013 --> 00:35:48,870
5, 7, and 11 are
actually, also, primes.
546
00:35:48,870 --> 00:35:50,780
But for 15 it looks a
little bit different.
547
00:35:55,300 --> 00:36:01,150
So let's write out
all the numbers.
548
00:36:01,150 --> 00:36:02,590
Again, let's have a look.
549
00:36:02,590 --> 00:36:04,750
Well, one is the
greatest common divisor
550
00:36:04,750 --> 00:36:08,290
equal to 1, with respect to 15.
551
00:36:08,290 --> 00:36:13,240
2 is also relatively
prime, with respect to 15.
552
00:36:13,240 --> 00:36:14,416
3 is dividing 15.
553
00:36:14,416 --> 00:36:20,200
4-- yeah, 4 and 15 have greatest
common divisor equal to 1.
554
00:36:20,200 --> 00:36:23,400
So that's relatively prime.
555
00:36:23,400 --> 00:36:25,200
5 is not.
556
00:36:25,200 --> 00:36:25,930
6 is not.
557
00:36:25,930 --> 00:36:27,540
7 is relatively prime.
558
00:36:27,540 --> 00:36:31,260
8-- again, this is only
divisible by power of 2,
559
00:36:31,260 --> 00:36:35,780
and this has no
power of 2 in it.
560
00:36:35,780 --> 00:36:41,750
9, 10 are-- this one is
divisible by 5, divisible by 3.
561
00:36:41,750 --> 00:36:44,520
11 is, again, relatively prime.
562
00:36:44,520 --> 00:36:48,100
And then we have 13 is
relatively prime as well.
563
00:36:48,100 --> 00:36:50,460
And 14 as well, because
this is 2 times 7,
564
00:36:50,460 --> 00:36:52,240
and this is 3 times 5.
565
00:36:52,240 --> 00:36:53,880
So how many do we see now?
566
00:36:53,880 --> 00:36:57,722
1, 2, 3, 4, 5, 6, 7, 8.
567
00:37:01,660 --> 00:37:04,570
So the Euler's totient
function evaluated in 15
568
00:37:04,570 --> 00:37:05,540
is actually equal to 8.
569
00:37:05,540 --> 00:37:10,240
Now, it turns out
that this function has
570
00:37:10,240 --> 00:37:13,560
really nice properties,
and you can easily
571
00:37:13,560 --> 00:37:18,610
calculate-- if you know
the decomposition of n
572
00:37:18,610 --> 00:37:21,340
into its primes, and
powers of primes--
573
00:37:21,340 --> 00:37:28,190
you can easily compute
this number, phi of n.
574
00:37:28,190 --> 00:37:30,300
Now, you will be able to
find this in the book.
575
00:37:30,300 --> 00:37:31,160
You should read it.
576
00:37:31,160 --> 00:37:35,340
And also, problem
set talks about this.
577
00:37:35,340 --> 00:37:38,820
But for now, let's
just talk about this
578
00:37:38,820 --> 00:37:40,950
is an abstract notion,
because that's all
579
00:37:40,950 --> 00:37:43,370
that we will use
in this lecture.
580
00:37:43,370 --> 00:37:44,940
But you will have
a few exercises
581
00:37:44,940 --> 00:37:48,170
to talk about computing
this kind of stuff.
582
00:37:48,170 --> 00:37:58,410
OK, so let's talk about Euler's
totient function and Euler's
583
00:37:58,410 --> 00:37:59,140
theorem.
584
00:37:59,140 --> 00:38:04,325
So let me use this blackboard.
585
00:38:14,260 --> 00:38:17,800
Now, this is really
an exciting theorem.
586
00:38:17,800 --> 00:38:20,110
And it's a little
bit hard to prove.
587
00:38:20,110 --> 00:38:24,810
So why we'll need a little
bit more time to do this.
588
00:38:24,810 --> 00:38:27,430
Euler's theorem
says the following.
589
00:38:27,430 --> 00:38:34,750
If the GCD of n and
k is equal to 1,
590
00:38:34,750 --> 00:38:42,520
then k to the power [INAUDIBLE]
the Euler's totient function
591
00:38:42,520 --> 00:38:50,280
evaluated in n is actually
congruent to 1 modulo n.
592
00:38:50,280 --> 00:38:52,340
So this is what we're
going to prove here.
593
00:38:52,340 --> 00:38:54,920
So why is this so interesting?
594
00:38:54,920 --> 00:38:57,760
Well, we'll talk about
an application which
595
00:38:57,760 --> 00:39:00,160
is a direct consequence of
this theorem, which we'll
596
00:39:00,160 --> 00:39:02,550
call Fermat's little theorem.
597
00:39:02,550 --> 00:39:07,430
And that, in turn, we will use
to explain the RSA algorithm,
598
00:39:07,430 --> 00:39:11,480
and show how the decryption
works, and so on.
599
00:39:11,480 --> 00:39:13,000
So how can we prove this?
600
00:39:21,450 --> 00:39:37,570
It will start with
a first lemma,
601
00:39:37,570 --> 00:39:41,310
and then we're going to do a few
tricks-- mathematical tricks,
602
00:39:41,310 --> 00:39:42,510
you will see it.
603
00:39:42,510 --> 00:39:48,960
So the first lemma
is that if I know
604
00:39:48,960 --> 00:39:52,120
that the GCD-- which is
what we are assuming,
605
00:39:52,120 --> 00:39:55,646
the statement of the theorum--
if I know that the GCD of n
606
00:39:55,646 --> 00:40:04,480
and k equals 1, then I
know that and a times k--
607
00:40:04,480 --> 00:40:12,720
if a times k is congruent
to b times k modulo n,
608
00:40:12,720 --> 00:40:17,890
then this applies that a
is congruent to b modulo n.
609
00:40:17,890 --> 00:40:21,435
All this seems to be kind
of a straightforward lemma.
610
00:40:21,435 --> 00:40:24,180
I will only talk
about its proof.
611
00:40:24,180 --> 00:40:25,550
So how do we do it?
612
00:40:25,550 --> 00:40:29,790
Well, first of all, I know that
the GCD of n and k equals 1.
613
00:40:29,790 --> 00:40:36,440
So that means that I can create
a multiplicative inverse,
614
00:40:36,440 --> 00:40:41,970
because I know that there's
such a linear combination that
615
00:40:41,970 --> 00:40:46,240
will ends up to 1.
616
00:40:46,240 --> 00:40:50,140
So I have the
multiplicative inverse.
617
00:40:50,140 --> 00:40:55,330
I multiply both sides with
this, and then I will end up to,
618
00:40:55,330 --> 00:40:57,230
a is congruent to b modulo n.
619
00:40:57,230 --> 00:40:59,300
And actually, you can
use some of the facts
620
00:40:59,300 --> 00:41:02,670
on your sheet to prove this.
621
00:41:02,670 --> 00:41:05,280
And in the problem
set, you probably
622
00:41:05,280 --> 00:41:09,020
have seen that there
are a number of problems
623
00:41:09,020 --> 00:41:09,875
related to this.
624
00:41:13,080 --> 00:41:15,610
So you will recognize this,
and prove a few of these things
625
00:41:15,610 --> 00:41:17,410
yourself.
626
00:41:17,410 --> 00:41:24,570
OK, so this is-- so let me see.
627
00:41:29,380 --> 00:41:31,960
So let me see what
we have done here.
628
00:41:34,610 --> 00:41:37,680
Actually, I noticed that
I've missed one statement
629
00:41:37,680 --> 00:41:40,600
that I would like to
explicitly mention.
630
00:41:40,600 --> 00:41:43,510
I mean, I've used
it a few times.
631
00:41:43,510 --> 00:41:45,740
Let me do that first.
632
00:41:45,740 --> 00:41:56,740
Which is that, we know that if
the GCD of n and k equals 1,
633
00:41:56,740 --> 00:42:02,460
then-- this is if, and
only if, the case-- if k
634
00:42:02,460 --> 00:42:09,780
has a multiplicative inverse--
I've not yet explicitly stated
635
00:42:09,780 --> 00:42:16,400
it-- and we can
easily see this--
636
00:42:16,400 --> 00:42:21,000
let me just give a quick
proof to show how this works.
637
00:42:23,960 --> 00:42:31,050
Well, if the GCD is
equal to 1, then we
638
00:42:31,050 --> 00:42:34,090
use the statement up there.
639
00:42:34,090 --> 00:42:37,530
So this is if,
and only if, there
640
00:42:37,530 --> 00:42:40,470
exists a linear combination.
641
00:42:40,470 --> 00:42:46,250
So an s and a t, such that
n times s plus k times t
642
00:42:46,250 --> 00:42:48,170
equals 1.
643
00:42:48,170 --> 00:42:56,450
Well, then I also know that
there exists a t such that,
644
00:42:56,450 --> 00:43:01,280
actually, the difference
between 1 and k times t
645
00:43:01,280 --> 00:43:03,740
is divisible by n.
646
00:43:03,740 --> 00:43:10,716
So n divides the difference
of k times t minus 1.
647
00:43:10,716 --> 00:43:12,080
So why is that?
648
00:43:12,080 --> 00:43:14,570
Well, if I look at the
difference between k times
649
00:43:14,570 --> 00:43:17,580
t and 1, the difference
is n times s.
650
00:43:17,580 --> 00:43:20,640
And n times s is divisible by n.
651
00:43:20,640 --> 00:43:24,480
So now, by the
definition of congruence,
652
00:43:24,480 --> 00:43:26,710
I just apply the
definition over here.
653
00:43:26,710 --> 00:43:28,390
We have written it out here.
654
00:43:28,390 --> 00:43:37,470
We can say that k times t
is congruent to 1 modulo n.
655
00:43:37,470 --> 00:43:41,970
And this is the definition of
the multiplication inverse.
656
00:43:41,970 --> 00:43:46,000
So we have essentially
shown that if the greatest
657
00:43:46,000 --> 00:43:48,650
common divisors in
any case equal to 1,
658
00:43:48,650 --> 00:43:52,380
then it has a
multiplicative inverse.
659
00:43:52,380 --> 00:43:58,300
OK, we have been using
this property over
660
00:43:58,300 --> 00:44:02,990
here because we assume that
the greatest common divisor is
661
00:44:02,990 --> 00:44:03,860
equal to 1.
662
00:44:03,860 --> 00:44:08,720
So we now know that there exists
a multiplicative inverse of k.
663
00:44:08,720 --> 00:44:13,440
We use that one to
multiply away, essentially,
664
00:44:13,440 --> 00:44:15,870
the k out of this
equation, and get
665
00:44:15,870 --> 00:44:19,320
a is congruent to b modulo n.
666
00:44:19,320 --> 00:44:24,160
Also note that we use
the property over here.
667
00:44:24,160 --> 00:44:32,520
We said that we wanted to
compute, what was it again?
668
00:44:32,520 --> 00:44:37,480
Over here-- we started off
with the GCD of m and p
669
00:44:37,480 --> 00:44:40,280
to be equal to 1, and I know p.
670
00:44:40,280 --> 00:44:43,920
And now I can compute the
multiplicative inverse of m.
671
00:44:43,920 --> 00:44:46,930
And I should have
said why it exists.
672
00:44:46,930 --> 00:44:49,950
And it exists
because of that lemma
673
00:44:49,950 --> 00:44:53,140
that I just mentioned up here.
674
00:44:53,140 --> 00:44:55,395
OK, so now let's go
back to Euler's theorem.
675
00:44:58,030 --> 00:45:01,070
This first lemma we are going
to use to prove a second lemma,
676
00:45:01,070 --> 00:45:03,030
and that second
lemma we can finally
677
00:45:03,030 --> 00:45:04,850
use to prove the theorem.
678
00:45:07,610 --> 00:45:15,570
All right, so this lemma I
will put on a separate board,
679
00:45:15,570 --> 00:45:18,205
because it contains quite
a number of steps to prove.
680
00:45:26,400 --> 00:45:38,430
So the lemma states that, if we
suppose that the GCD of n and k
681
00:45:38,430 --> 00:45:44,090
equals 1-- so it's the same
assumptions as before-- if it
682
00:45:44,090 --> 00:45:53,580
lets k1 all the way up to k r to
be those integers in the range
683
00:45:53,580 --> 00:45:59,970
1, 2, 3, and so
on, to n minus 1,
684
00:45:59,970 --> 00:46:05,000
that are relatively
prime-- so these denote
685
00:46:05,000 --> 00:46:15,640
the integers relatively
prime to n-- then
686
00:46:15,640 --> 00:46:18,555
we can prove a very
interesting property.
687
00:46:21,270 --> 00:46:24,690
Now, notice by the
way, that r in here
688
00:46:24,690 --> 00:46:28,780
is equal to this value of
the Euler's totient function
689
00:46:28,780 --> 00:46:30,380
evaluated in n.
690
00:46:30,380 --> 00:46:33,080
Because this counts
the total number
691
00:46:33,080 --> 00:46:40,390
of numbers that are relatively
prime with respect to n.
692
00:46:40,390 --> 00:46:44,200
So now we can prove
something really spectacular.
693
00:46:44,200 --> 00:46:48,830
We can show that the
set that contains
694
00:46:48,830 --> 00:46:54,350
all of these remainders--
the remainder of k 1 times k,
695
00:46:54,350 --> 00:46:57,170
after dividing out this
many multiples of n
696
00:46:57,170 --> 00:47:06,840
as possible, all the way to
the remainder off k r times k,
697
00:47:06,840 --> 00:47:12,590
after dividing out as many
multiples of n as possible,
698
00:47:12,590 --> 00:47:18,810
this set is actually equal
to the set k 1 up to k r.
699
00:47:18,810 --> 00:47:20,910
So this is what
we're going to prove.
700
00:47:20,910 --> 00:47:23,280
And we'll do it in two steps.
701
00:47:23,280 --> 00:47:29,630
We first show that this
set has exactly r numbers.
702
00:47:29,630 --> 00:47:32,570
So the cardinality of
that set is equal to r.
703
00:47:32,570 --> 00:47:36,150
So that will be our
first step in the proof.
704
00:47:36,150 --> 00:47:42,400
And over here we will show that
every remainder is actually
705
00:47:42,400 --> 00:47:46,420
relatively prime to n, so
it must be part of this set.
706
00:47:46,420 --> 00:47:49,580
So we will show that this
is a subset of this set
707
00:47:49,580 --> 00:47:51,770
in a second part of the proof.
708
00:47:51,770 --> 00:47:55,450
And combining those two, we
are able to prove equality.
709
00:47:55,450 --> 00:47:56,435
Why's that?
710
00:47:56,435 --> 00:48:00,680
Well I have r distinct
elements in this set,
711
00:48:00,680 --> 00:48:04,290
I have r distinct elements
in this set, this one
712
00:48:04,290 --> 00:48:05,450
is a subset of this.
713
00:48:05,450 --> 00:48:08,890
So that can only happen
if they are equal.
714
00:48:08,890 --> 00:48:12,910
So this is the
method for the proof.
715
00:48:16,030 --> 00:48:31,290
I should-- so we'll start
with the first part.
716
00:48:34,180 --> 00:48:40,470
And the way to do that is to
see whether it is possible
717
00:48:40,470 --> 00:48:47,840
that any two remainders
in that set, can they
718
00:48:47,840 --> 00:48:48,860
be equal to one another?
719
00:48:48,860 --> 00:48:50,870
We will show that
that's not possible.
720
00:48:50,870 --> 00:48:54,490
So if it's not possible,
then all these remainders
721
00:48:54,490 --> 00:48:55,470
must be different.
722
00:48:55,470 --> 00:48:57,790
And we have exactly r of those.
723
00:48:57,790 --> 00:48:59,650
So let's do this.
724
00:48:59,650 --> 00:49:04,690
So the proof for
1 is as follows.
725
00:49:04,690 --> 00:49:07,550
Let's assume that we
he have to remainders.
726
00:49:07,550 --> 00:49:17,330
Say, k i times k, and a
remainder k j times k,
727
00:49:17,330 --> 00:49:19,210
after dividing out as
many multiples of n.
728
00:49:19,210 --> 00:49:22,000
And supposed that they
are equal to one another.
729
00:49:22,000 --> 00:49:25,120
We're going to show
that this can only
730
00:49:25,120 --> 00:49:29,120
happen if k i is equal to k j.
731
00:49:29,120 --> 00:49:31,867
And if you can see
that, well then
732
00:49:31,867 --> 00:49:34,200
we know that all these different
remainders are actually
733
00:49:34,200 --> 00:49:35,500
different from one another.
734
00:49:35,500 --> 00:49:37,880
And if they're all
different from one another,
735
00:49:37,880 --> 00:49:39,870
then we must have exactly r.
736
00:49:39,870 --> 00:49:44,140
Because we have k 1
up to k r in here.
737
00:49:44,140 --> 00:49:48,610
OK let's see where
we can do this.
738
00:49:48,610 --> 00:49:52,210
Well, if you know that
these two remainders are
739
00:49:52,210 --> 00:49:56,280
equal to one another, we can
look at them with respect
740
00:49:56,280 --> 00:49:58,940
to these definitions over here.
741
00:49:58,940 --> 00:50:05,110
And we can show that k
i times k is actually
742
00:50:05,110 --> 00:50:10,640
congruent to k j
times k modulo n.
743
00:50:10,640 --> 00:50:12,170
So why is this?
744
00:50:12,170 --> 00:50:15,620
Well, these two
remainders are the same.
745
00:50:15,620 --> 00:50:19,370
And k i times k is
equal to this remainder,
746
00:50:19,370 --> 00:50:21,270
plus a multiple of n.
747
00:50:21,270 --> 00:50:25,650
This k j times k is equal
to this remainder plus,
748
00:50:25,650 --> 00:50:27,350
a multiple of n.
749
00:50:27,350 --> 00:50:32,179
So the difference between those
two is also a multiple of n.
750
00:50:32,179 --> 00:50:33,845
And that's the
definition of congruence.
751
00:50:36,880 --> 00:50:42,510
So now we can use
our first lemma,
752
00:50:42,510 --> 00:50:46,040
which is stated over here.
753
00:50:46,040 --> 00:50:48,800
We know that we assumed
in Euler's theorem
754
00:50:48,800 --> 00:50:52,570
that the GCD of n
and k is equal to 1.
755
00:50:52,570 --> 00:50:57,170
If a times k is congruent
to b times k modulo n,
756
00:50:57,170 --> 00:50:59,910
then we know that's a is
congruent to b modulo n.
757
00:50:59,910 --> 00:51:03,420
So let's apply it over
here, and take for a k
758
00:51:03,420 --> 00:51:07,270
i, and for b we can take k j.
759
00:51:07,270 --> 00:51:16,010
So now we see that key k i
is congruent to k j modulo n.
760
00:51:16,010 --> 00:51:19,300
And from this we will
conclude-- and that
761
00:51:19,300 --> 00:51:23,900
takes an extra step-- that k
i is actually equal to k j.
762
00:51:23,900 --> 00:51:25,950
So how can we do this?
763
00:51:25,950 --> 00:51:30,870
Well, we know that k i and k
j are both in the range from 1
764
00:51:30,870 --> 00:51:33,810
all the way up to n minus 1.
765
00:51:33,810 --> 00:51:38,000
So if I look at the
difference between those
766
00:51:38,000 --> 00:51:39,950
two-- so by definition
of congruence
767
00:51:39,950 --> 00:51:46,780
I know that n divides
k i minus k j.
768
00:51:46,780 --> 00:51:52,790
I know that this one is in the
range from 0 up to n minus 1.
769
00:51:52,790 --> 00:51:55,850
This one is in the range
of 0 up to n minus 1.
770
00:51:55,850 --> 00:52:00,510
The only way how a difference
of two numbers in this range
771
00:52:00,510 --> 00:52:05,250
can be divisible by n, is if
this thing is equal to zero.
772
00:52:05,250 --> 00:52:09,170
And that means that
k i equals k j.
773
00:52:09,170 --> 00:52:11,200
So now we are done
with the first part,
774
00:52:11,200 --> 00:52:14,040
because we have shown
that if I take any two
775
00:52:14,040 --> 00:52:18,990
remainders over here it
must be that they can only
776
00:52:18,990 --> 00:52:21,425
be equal to one another
if, actually, the k i is
777
00:52:21,425 --> 00:52:22,300
equal to the k j.
778
00:52:22,300 --> 00:52:24,570
So actually we're looking
at the same remainder.
779
00:52:24,570 --> 00:52:27,950
So they remainders in this
set are all different,
780
00:52:27,950 --> 00:52:30,680
and there are
exactly r of those.
781
00:52:30,680 --> 00:52:32,690
So now we go to the
second part of the proof.
782
00:52:49,520 --> 00:52:52,370
And notice that we
are-- so far we've only
783
00:52:52,370 --> 00:52:54,470
been proving the second
lemma, and we still
784
00:52:54,470 --> 00:52:56,990
need to go to Euler's
theorem as well.
785
00:52:56,990 --> 00:52:58,375
So it still takes a few steps.
786
00:53:02,560 --> 00:53:05,430
So how do we do the second part?
787
00:53:05,430 --> 00:53:09,200
Well, we saw in last
lecture that we were
788
00:53:09,200 --> 00:53:14,640
explaining Euclid's algorithm.
789
00:53:14,640 --> 00:53:18,650
And we used, essentially,
this property.
790
00:53:18,650 --> 00:53:22,080
We said that the greatest
common divisor between n
791
00:53:22,080 --> 00:53:28,460
and the remainder of
say, k i times k and n,
792
00:53:28,460 --> 00:53:33,750
is actually equal to the
greatest common divisor of n
793
00:53:33,750 --> 00:53:36,265
and k i times k.
794
00:53:39,090 --> 00:53:40,340
So why is this, again?
795
00:53:40,340 --> 00:53:46,320
Well, the remaining is
actually equal to k i times k,
796
00:53:46,320 --> 00:53:48,680
minus a multiple of n, right?
797
00:53:48,680 --> 00:53:53,080
So the greatest common
divisor is therefore--
798
00:53:53,080 --> 00:53:55,720
between n and this-- is the same
as the greatest common divisor
799
00:53:55,720 --> 00:53:57,840
between n and k i times k.
800
00:53:57,840 --> 00:54:00,210
So you should have to
look at last lecture.
801
00:54:00,210 --> 00:54:04,250
And now we are pretty much done.
802
00:54:04,250 --> 00:54:04,790
Why is this?
803
00:54:04,790 --> 00:54:07,800
Because we have assumed that
the greatest common divisor
804
00:54:07,800 --> 00:54:11,631
between n and k is equal to 1.
805
00:54:11,631 --> 00:54:15,150
And k i, in the
statement of the lemma,
806
00:54:15,150 --> 00:54:17,180
is relatively prime to n.
807
00:54:17,180 --> 00:54:20,770
And that means, according to
the definition over there,
808
00:54:20,770 --> 00:54:23,830
that the greatest common
divisor between k i and n
809
00:54:23,830 --> 00:54:25,330
is also equal to 1.
810
00:54:25,330 --> 00:54:35,450
So we know that both
these greatest common
811
00:54:35,450 --> 00:54:39,220
divisors are equal to 1.
812
00:54:39,220 --> 00:54:43,592
So that means that there is
no common divisor between n
813
00:54:43,592 --> 00:54:47,600
and these, except 1 of course.
814
00:54:47,600 --> 00:54:49,320
So what does this say?
815
00:54:49,320 --> 00:54:52,470
Well, this means that
this remainder, according
816
00:54:52,470 --> 00:54:55,830
to our definition, is
relatively prime to n,
817
00:54:55,830 --> 00:54:59,171
because this greatest common
divisor is equal to 1.
818
00:54:59,171 --> 00:55:05,420
So if it is an integer
relatively prime to n,
819
00:55:05,420 --> 00:55:08,460
then it must be one
of those k i's, k j's
820
00:55:08,460 --> 00:55:11,820
in this set that is
stated in the lemma.
821
00:55:11,820 --> 00:55:16,290
So this shows that it must be
part of this set over here.
822
00:55:16,290 --> 00:55:20,160
So if proven, the fact
[? is ?] that the set of all
823
00:55:20,160 --> 00:55:25,350
the remainders is a subset
of the set k 1 of the k r.
824
00:55:25,350 --> 00:55:28,260
So now we're done.
825
00:55:28,260 --> 00:55:34,730
So now that we have shown
this particular lemma,
826
00:55:34,730 --> 00:55:40,420
we can continue and
prove Euler's theorem.
827
00:55:40,420 --> 00:55:43,460
And I'll probably need
to wipe out some of this.
828
00:55:52,750 --> 00:55:56,360
So let's use this lemma
to prove this theorem.
829
00:55:56,360 --> 00:55:57,920
So this is really a neat trick.
830
00:56:02,350 --> 00:56:09,510
So the proof of Euler's
theorem is as follows.
831
00:56:09,510 --> 00:56:14,130
We're going to take the product
of all those k i's over there,
832
00:56:14,130 --> 00:56:17,670
and see where we can
find a nice relationship.
833
00:56:17,670 --> 00:56:23,540
So we take k 1 times k
2, all the way times k r.
834
00:56:23,540 --> 00:56:27,290
And we know, because those two
sets are actually the same,
835
00:56:27,290 --> 00:56:30,310
that this is equal
to the remainder--
836
00:56:30,310 --> 00:56:37,230
the first remainder--
k 1 times k,
837
00:56:37,230 --> 00:56:39,520
after dividing out as
many multiples of n.
838
00:56:39,520 --> 00:56:42,340
And we go all the way
up to the final one,
839
00:56:42,340 --> 00:56:47,980
the remainder of k r
times k, dividing out
840
00:56:47,980 --> 00:56:50,280
as many multiples of n.
841
00:56:50,280 --> 00:56:55,800
So now we can see that--
well, we've already
842
00:56:55,800 --> 00:56:59,480
shown that each of
those remainders
843
00:56:59,480 --> 00:57:01,650
is congruent to, in
this case, this one
844
00:57:01,650 --> 00:57:05,210
is congruent to k
1 times k modulo n.
845
00:57:05,210 --> 00:57:08,190
And this one is congruent
to k r times k modulo n.
846
00:57:08,190 --> 00:57:09,650
So let's write it out.
847
00:57:09,650 --> 00:57:12,430
So it's k 1 times k.
848
00:57:12,430 --> 00:57:16,140
And then we have k 2 times k.
849
00:57:16,140 --> 00:57:23,890
And finally we have
k r times k modulo n.
850
00:57:23,890 --> 00:57:26,910
So let's regroup those.
851
00:57:26,910 --> 00:57:30,580
We see k 1, k 2, all the
way up to k r reappearing.
852
00:57:35,660 --> 00:57:39,770
And we have a k here,
a k here, and we
853
00:57:39,770 --> 00:57:42,630
have that r times--
so we have times
854
00:57:42,630 --> 00:57:47,990
k to the power r modulo n.
855
00:57:47,990 --> 00:57:52,250
So now we are able to, again,
use this particular lemma
856
00:57:52,250 --> 00:57:53,990
over here.
857
00:57:53,990 --> 00:57:55,560
So what do we do?
858
00:57:55,560 --> 00:58:01,115
Well, we know that k 1
is relatively prime to n.
859
00:58:01,115 --> 00:58:04,590
And k 2 is as well,
all the way up to k r.
860
00:58:04,590 --> 00:58:08,450
So this whole product is also
relatively prime, with respect
861
00:58:08,450 --> 00:58:09,979
to n.
862
00:58:09,979 --> 00:58:11,770
That means that the
greatest common divisor
863
00:58:11,770 --> 00:58:17,060
of this whole product
with n is equal to 1.
864
00:58:17,060 --> 00:58:21,920
So that means that I can
divide out this whole product.
865
00:58:21,920 --> 00:58:25,190
We have-- so let's do this.
866
00:58:25,190 --> 00:58:28,300
We have 1 times this product.
867
00:58:28,300 --> 00:58:33,960
We take this for a,
and we take this for b.
868
00:58:33,960 --> 00:58:38,770
And then we can divide
this whole thing out
869
00:58:38,770 --> 00:58:40,600
according to this
particular lemma,
870
00:58:40,600 --> 00:58:44,760
by using the multiplicative
inverse of that product.
871
00:58:44,760 --> 00:58:49,690
So now we see that the 1 is
equal to k to the power r
872
00:58:49,690 --> 00:58:51,720
modulo n.
873
00:58:51,720 --> 00:58:56,010
And remember, in our
theorem, r over here
874
00:58:56,010 --> 00:59:02,500
in this lemma-- r is
actually equal to the Euler's
875
00:59:02,500 --> 00:59:04,740
totient function in n.
876
00:59:04,740 --> 00:59:09,780
So now this equation
proves the whole theorem.
877
00:59:09,780 --> 00:59:15,890
OK, so now I'm going
to talk about RSA,
878
00:59:15,890 --> 00:59:17,890
which is the last part here.
879
00:59:17,890 --> 00:59:20,080
So maybe you all
would like to have
880
00:59:20,080 --> 00:59:24,430
a little break of a couple of
minutes, just to relax a bit.
881
00:59:24,430 --> 00:59:26,540
And then-- and shake
hands with your neighbors,
882
00:59:26,540 --> 00:59:30,150
and jump up in the
air if you'd like to.
883
00:59:30,150 --> 00:59:33,590
All right let's start
with the RSA algorithm.
884
00:59:33,590 --> 00:59:37,480
So we have done everything
up to this point.
885
00:59:37,480 --> 00:59:42,150
And we are actually-- we have
done these two over here.
886
00:59:42,150 --> 00:59:45,300
We still have to talk about
Fermat's little theorem.
887
00:59:45,300 --> 00:59:48,990
But then we can go for RSA,
and it uses this consequence
888
00:59:48,990 --> 00:59:52,470
of Euler's theorem.
889
00:59:52,470 --> 01:00:04,130
So Fermat's little
theorem is actually
890
01:00:04,130 --> 01:00:08,154
talking about what happens
if n is a prime number.
891
01:00:11,640 --> 01:00:14,340
It says, well,
suppose p is a prime.
892
01:00:19,830 --> 01:00:25,100
And if you have k in the
range 1, 2, all the way up
893
01:00:25,100 --> 01:00:32,010
to p minus 1, then we
can conclude that k
894
01:00:32,010 --> 01:00:37,770
to the power of p minus 1
is congruent to 1 modulo n.
895
01:00:37,770 --> 01:00:44,150
And we can directly prove
this by using Euler's theorem.
896
01:00:44,150 --> 01:00:46,340
So how do we do this?
897
01:00:46,340 --> 01:00:49,300
Well, we know that p is prime.
898
01:00:49,300 --> 01:00:57,380
So the numbers 1, 2, all
the way up to p minus 1,
899
01:00:57,380 --> 01:01:01,880
are actually
relatively prime to p.
900
01:01:05,000 --> 01:01:05,710
So why is that?
901
01:01:05,710 --> 01:01:06,920
Well, p is prime.
902
01:01:06,920 --> 01:01:10,257
So the greatest common divisor
between any of those with p
903
01:01:10,257 --> 01:01:10,840
is equal to 1.
904
01:01:10,840 --> 01:01:14,640
That's the definition
of relatively prime.
905
01:01:14,640 --> 01:01:21,070
And we know that
we can now apply
906
01:01:21,070 --> 01:01:23,370
Euler's theorem
over here, and see
907
01:01:23,370 --> 01:01:31,640
that k to the power phi of
p is, of course, congruent
908
01:01:31,640 --> 01:01:34,390
to 1 modulo p.
909
01:01:34,390 --> 01:01:36,430
That's Euler's theorem.
910
01:01:36,430 --> 01:01:39,510
But now, since we know that
these are the exact ones that
911
01:01:39,510 --> 01:01:42,930
are relatively prime,
we can explicitly
912
01:01:42,930 --> 01:01:46,290
compute the Euler's
totient function of p.
913
01:01:46,290 --> 01:01:48,250
Because there are p
minus 1 numbers that
914
01:01:48,250 --> 01:01:50,480
are relatively prime to p.
915
01:01:50,480 --> 01:01:53,530
So that's the
definition over here.
916
01:01:53,530 --> 01:01:57,870
So the number of integers in
the range 1 up to p minus 1--
917
01:01:57,870 --> 01:02:00,040
they're all relatively prime.
918
01:02:00,040 --> 01:02:09,060
So we know that 5 p
is equal to p minus 1.
919
01:02:09,060 --> 01:02:14,140
So now we have shown that
k to the power of p minus 1
920
01:02:14,140 --> 01:02:18,320
is congruent to 1 modulo k.
921
01:02:18,320 --> 01:02:22,260
This is kind of interesting
because we can use this theorem
922
01:02:22,260 --> 01:02:26,170
also to compute the
multiplicative inverse of k,
923
01:02:26,170 --> 01:02:27,830
in this particular case.
924
01:02:27,830 --> 01:02:31,430
So how do we do this?
925
01:02:31,430 --> 01:02:35,250
We just take k,
and we look at what
926
01:02:35,250 --> 01:02:41,690
happens if you multiply k with
k to the power of p minus 2.
927
01:02:41,690 --> 01:02:46,340
Well, this is equal to k to
the power p minus 1, which
928
01:02:46,340 --> 01:02:56,047
is congruent to 1 modulo p
according to Fermat's theorem.
929
01:02:56,047 --> 01:02:57,630
So now, when we look
at the definition
930
01:02:57,630 --> 01:03:01,220
of multiplicative
inverse over here,
931
01:03:01,220 --> 01:03:05,240
we see that k to
the power p minus 2
932
01:03:05,240 --> 01:03:07,755
is actually the
multiplicative inverse of k.
933
01:03:10,350 --> 01:03:15,240
So k inverse is actually
equal to k to the power
934
01:03:15,240 --> 01:03:22,340
p minus 2 modulo k.
935
01:03:22,340 --> 01:03:25,180
All right, so this theorem
we're going to use now
936
01:03:25,180 --> 01:03:26,290
in the description of RSA.
937
01:03:29,850 --> 01:03:36,440
As I said, it was only
decades later, after Turing,
938
01:03:36,440 --> 01:03:40,480
Rivest, Shamir, and Adleman
were the first to really show
939
01:03:40,480 --> 01:03:42,430
how number theory
could be applied so
940
01:03:42,430 --> 01:03:44,900
successfully in cryptography.
941
01:03:44,900 --> 01:03:48,850
And they essentially showed
the first public key encryption
942
01:03:48,850 --> 01:03:52,130
scheme in which a sender and
receiver do not necessarily
943
01:03:52,130 --> 01:03:54,250
have to exchange a secret key.
944
01:03:54,250 --> 01:03:55,460
That's not necessary.
945
01:03:55,460 --> 01:03:59,140
So they had a public key method.
946
01:03:59,140 --> 01:04:04,880
And that's still used today,
and it's a great inventions.
947
01:04:04,880 --> 01:04:07,820
So how does the RSA work?
948
01:04:07,820 --> 01:04:10,300
Again, we have to talk
with an encryption scheme
949
01:04:10,300 --> 01:04:12,830
about what happens beforehand.
950
01:04:12,830 --> 01:04:17,320
So beforehand, we need to
generate this public key
951
01:04:17,320 --> 01:04:19,660
and a secret key.
952
01:04:19,660 --> 01:04:32,320
So the idea is that the receiver
creates a public key, and also
953
01:04:32,320 --> 01:04:33,250
a secret key.
954
01:04:36,910 --> 01:04:39,020
He will publish the public
key, and he will keep
955
01:04:39,020 --> 01:04:40,760
the secret key for himself.
956
01:04:40,760 --> 01:04:43,750
And now anybody can
use the public key
957
01:04:43,750 --> 01:04:46,680
to encrypt a message.
958
01:04:46,680 --> 01:04:49,690
The encrypted message
is sent to the receiver,
959
01:04:49,690 --> 01:04:52,930
and he's going to use his
secret key to get back
960
01:04:52,930 --> 01:04:55,890
to the plain message.
961
01:04:55,890 --> 01:04:57,880
So how is he going to do this?
962
01:04:57,880 --> 01:05:00,860
Well in the first
step, the idea is
963
01:05:00,860 --> 01:05:05,730
to generate two distinct primes.
964
01:05:05,730 --> 01:05:10,190
Turns out that this can be
done in a very efficient way.
965
01:05:10,190 --> 01:05:14,020
There are lots of primes
among the integers.
966
01:05:14,020 --> 01:05:15,710
So you just sample.
967
01:05:15,710 --> 01:05:21,150
And it turns out that
you can test primality
968
01:05:21,150 --> 01:05:23,756
with a pretty high
probability, very efficiently.
969
01:05:23,756 --> 01:05:25,130
And recently,
actually, there has
970
01:05:25,130 --> 01:05:29,094
been a deterministic
algorithm that is polynomial.
971
01:05:29,094 --> 01:05:30,510
And a number of
bits of the primes
972
01:05:30,510 --> 01:05:33,710
that can actually tell you
whether you have a prime
973
01:05:33,710 --> 01:05:34,220
or not.
974
01:05:34,220 --> 01:05:35,050
So you can do this.
975
01:05:37,700 --> 01:05:41,760
Two, we're going to create
the product of these two
976
01:05:41,760 --> 01:05:42,790
distinct primes.
977
01:05:42,790 --> 01:05:47,000
And that's where our
assumption is going to help us.
978
01:05:47,000 --> 01:05:51,470
That it is hard to factor a
product of two large primes.
979
01:05:51,470 --> 01:05:54,740
That's going to be the
underlying hardness assumption
980
01:05:54,740 --> 01:05:57,110
of the RSA encryption scheme.
981
01:05:59,660 --> 01:06:02,840
So let n be this.
982
01:06:02,840 --> 01:06:11,790
Three, we are going to
select an integer e,
983
01:06:11,790 --> 01:06:16,960
such that the greatest
common divisor of e
984
01:06:16,960 --> 01:06:22,060
with the product p
minus 1 times q minus 1
985
01:06:22,060 --> 01:06:25,850
is actually equal to 1.
986
01:06:25,850 --> 01:06:30,470
And the public-- and once
we have created this,
987
01:06:30,470 --> 01:06:40,270
the public key is going
to be a pair that consists
988
01:06:40,270 --> 01:06:44,650
of e itself together with n.
989
01:06:44,650 --> 01:06:46,670
So that's the public key.
990
01:06:46,670 --> 01:06:51,800
And the secret key is going
to be computed as follows,
991
01:06:51,800 --> 01:06:54,315
in step four.
992
01:06:54,315 --> 01:06:55,315
We are going to compute.
993
01:06:58,750 --> 01:07:09,290
d, such that d times e
is congruent to 1 modulo
994
01:07:09,290 --> 01:07:16,010
that product of p minus
1 times q minus 1.
995
01:07:16,010 --> 01:07:17,260
Can we do this?
996
01:07:17,260 --> 01:07:21,180
Yeah, because the greatest
common divisor between e
997
01:07:21,180 --> 01:07:23,860
and that product is equal to 1.
998
01:07:23,860 --> 01:07:26,770
And we have shown over
here that, therefore, it
999
01:07:26,770 --> 01:07:28,790
has a multiplicative inverse.
1000
01:07:28,790 --> 01:07:32,820
And first of all, we know
that the solution d exists,
1001
01:07:32,820 --> 01:07:36,070
and we can also
efficiently compute it.
1002
01:07:36,070 --> 01:07:48,030
So the secret key is
going to be the pair that
1003
01:07:48,030 --> 01:07:51,730
consists of d and also n.
1004
01:07:51,730 --> 01:07:53,530
So how does it work?
1005
01:07:53,530 --> 01:07:58,720
The sender knows the
public key, e and n,
1006
01:07:58,720 --> 01:08:00,690
and uses those to
encrypt a message.
1007
01:08:00,690 --> 01:08:02,340
I will explain it in a moment.
1008
01:08:02,340 --> 01:08:07,510
And then the receiver knows
the secret key, d and n,
1009
01:08:07,510 --> 01:08:10,130
and then is able to decrypt.
1010
01:08:10,130 --> 01:08:15,050
OK, so let's see how
encryption works.
1011
01:08:15,050 --> 01:08:18,170
And then we will have to
do a lot of mathematics
1012
01:08:18,170 --> 01:08:21,060
to get the decryption going.
1013
01:08:21,060 --> 01:08:27,330
So m prime, which is computed--
so the encrypted plain text is
1014
01:08:27,330 --> 01:08:31,410
computed as the remainder
of m to the power e--
1015
01:08:31,410 --> 01:08:33,870
which is part of
the public key--
1016
01:08:33,870 --> 01:08:38,850
and then dividing out as many
multiples of n as possible.
1017
01:08:38,850 --> 01:08:43,859
It turns out-- and we are going
to prove this-- that decryption
1018
01:08:43,859 --> 01:08:46,720
works as follows.
1019
01:08:46,720 --> 01:08:50,760
We can compute m
by using m prime.
1020
01:08:50,760 --> 01:08:52,880
So we receive m prime.
1021
01:08:52,880 --> 01:08:54,100
What do we do?
1022
01:08:54,100 --> 01:08:58,000
We're going to take m prime,
raise it to the power d-- which
1023
01:08:58,000 --> 01:09:01,710
is part of the secret
key-- and then dividing out
1024
01:09:01,710 --> 01:09:04,890
as many multiples of n.
1025
01:09:04,890 --> 01:09:08,200
Now, why would that work?
1026
01:09:08,200 --> 01:09:09,240
Why would this work?
1027
01:09:09,240 --> 01:09:12,979
So let's prove this
step over here.
1028
01:09:15,590 --> 01:09:20,439
Well, it turns out that they
can apply Fermat's theorem,
1029
01:09:20,439 --> 01:09:23,430
and the idea is as follows.
1030
01:09:23,430 --> 01:09:24,790
So let's have a look.
1031
01:09:24,790 --> 01:09:31,100
We know that m prime is equal
to the remainder of m raised
1032
01:09:31,100 --> 01:09:35,450
to the power e, which
is congruent to m
1033
01:09:35,450 --> 01:09:39,029
to the power e, modulo n.
1034
01:09:39,029 --> 01:09:42,200
We've seen this now a
number of times, right?
1035
01:09:42,200 --> 01:09:45,310
So what does this imply?
1036
01:09:45,310 --> 01:09:52,939
This implies that m prime to
the power d is actually equal--
1037
01:09:52,939 --> 01:09:57,900
is congruent to m to the
power e, to the power d.
1038
01:09:57,900 --> 01:10:00,390
So I just raised this
side to the power d,
1039
01:10:00,390 --> 01:10:03,030
and I raised this
side to the power d.
1040
01:10:03,030 --> 01:10:08,390
And I still-- and
I know, now, that m
1041
01:10:08,390 --> 01:10:11,540
prime to the power d is
equal to m to the power e d--
1042
01:10:11,540 --> 01:10:15,420
congruent to m to the
power e d modulo n.
1043
01:10:15,420 --> 01:10:19,970
So now we know that there
exists an integer r.
1044
01:10:19,970 --> 01:10:23,450
We are going to use the
fact that we have that e
1045
01:10:23,450 --> 01:10:26,280
and p minus 1 times q
minus 1 as a greatest
1046
01:10:26,280 --> 01:10:28,020
common divisor over 1.
1047
01:10:28,020 --> 01:10:35,290
So we know that e times
d is actually equal to 1,
1048
01:10:35,290 --> 01:10:40,320
plus r times p minus
1, times q minus 1.
1049
01:10:40,320 --> 01:10:46,310
Actually, what I use here is
the fact-- is this over here.
1050
01:10:46,310 --> 01:10:48,710
By definition of
congruency, I know
1051
01:10:48,710 --> 01:10:51,390
that the difference
between those two-- d times
1052
01:10:51,390 --> 01:10:55,430
e and 1-- is divisible
by this product.
1053
01:10:55,430 --> 01:10:57,590
So I know that there
exists an integer such
1054
01:10:57,590 --> 01:11:02,070
that e times d equals 1, plus
a multiple of that product.
1055
01:11:02,070 --> 01:11:04,860
That's how it works.
1056
01:11:04,860 --> 01:11:08,800
So we know that m
prime to the power
1057
01:11:08,800 --> 01:11:14,670
d-- we already saw that it is
equal to m to the power e d,
1058
01:11:14,670 --> 01:11:17,410
which is congruent
to-- well, we just
1059
01:11:17,410 --> 01:11:20,960
replace e d by 1 plus
r times this multiple.
1060
01:11:20,960 --> 01:11:25,220
So we have m to the
power 1, times m
1061
01:11:25,220 --> 01:11:31,026
to the power-- this part--
r p minus 1, q minus 1.
1062
01:11:35,220 --> 01:11:45,450
So now we're finally going
get to Fermat's theorem.
1063
01:11:45,450 --> 01:11:48,820
We know that n is the
products of p and q,
1064
01:11:48,820 --> 01:11:52,260
and I'm not actually
sure I do this here.
1065
01:11:55,130 --> 01:12:00,870
So let's apply Fermat's theorem
and see how we can use this.
1066
01:12:00,870 --> 01:12:08,320
So if m is not
congruent to 0 modulo p,
1067
01:12:08,320 --> 01:12:11,580
well then we can apply
Fermat's theorem.
1068
01:12:11,580 --> 01:12:12,080
Where is it?
1069
01:12:12,080 --> 01:12:14,480
It's over here.
1070
01:12:14,480 --> 01:12:18,830
We can only apply this if
k is in the range from 1
1071
01:12:18,830 --> 01:12:21,640
to p minus 1 is
not equal to zero.
1072
01:12:21,640 --> 01:12:27,020
So if m is not equal to 0--
not congruent to 0 modulo p--
1073
01:12:27,020 --> 01:12:30,700
then we can apply
the theorem and state
1074
01:12:30,700 --> 01:12:37,960
that m to the power p minus
1 is congruent to 1 modulo p.
1075
01:12:37,960 --> 01:12:42,440
And in the same way,
we can do this for q.
1076
01:12:42,440 --> 01:12:48,880
So if this is not
true-- modulo q-- then m
1077
01:12:48,880 --> 01:12:54,120
to the power q minus 1 is
congruent to 1 modulo q.
1078
01:12:54,120 --> 01:12:56,840
So here we have used
Fermat's theorem twice.
1079
01:12:59,890 --> 01:13:04,330
Now we can apply what
we have learned before,
1080
01:13:04,330 --> 01:13:07,990
which is what we
wrote down over here.
1081
01:13:07,990 --> 01:13:13,110
And prime to the power d is
congruent to this modulo n.
1082
01:13:13,110 --> 01:13:17,890
Now n is p times q, so let's
have a look at what that means.
1083
01:13:17,890 --> 01:13:23,140
It means that since n
is a product of p and q,
1084
01:13:23,140 --> 01:13:27,730
we can also look at
this congruent modulo p.
1085
01:13:27,730 --> 01:13:32,170
So in particular, we know
that m prime to the power
1086
01:13:32,170 --> 01:13:39,190
d is congruent to m times
m r p minus 1 times q minus
1087
01:13:39,190 --> 01:13:42,280
1 modulo p.
1088
01:13:42,280 --> 01:13:43,540
Why is that?
1089
01:13:43,540 --> 01:13:46,670
Well, we know that n
divides this difference
1090
01:13:46,670 --> 01:13:49,270
by the definition of congruency.
1091
01:13:49,270 --> 01:13:52,450
n is equal to p times q.
1092
01:13:52,450 --> 01:13:56,270
So if n is dividing
this difference,
1093
01:13:56,270 --> 01:13:58,770
also p is dividing
this difference.
1094
01:13:58,770 --> 01:14:01,140
So that's why we can write
it m prime to the power d
1095
01:14:01,140 --> 01:14:05,380
is congruent to this
thing, modulo p.
1096
01:14:05,380 --> 01:14:08,560
And of course, we can
repeat this for q.
1097
01:14:11,100 --> 01:14:12,940
So let me write
this out as well.
1098
01:14:17,930 --> 01:14:18,890
So there it is.
1099
01:14:21,600 --> 01:14:28,400
So now we can there use what
we have figured out over here.
1100
01:14:28,400 --> 01:14:33,560
So we know that if
m is not equal to 0,
1101
01:14:33,560 --> 01:14:38,180
then this thing over
here cancels out.
1102
01:14:38,180 --> 01:14:43,000
Because m to the power p
minus 1 is congruent to 1.
1103
01:14:43,000 --> 01:14:47,690
So we have that m
prime to the power
1104
01:14:47,690 --> 01:14:55,490
d is congruent to m
modulo p, if m is not
1105
01:14:55,490 --> 01:14:57,460
congruent to 0 modulo p, right?
1106
01:14:57,460 --> 01:14:59,550
Because if m is not
congruent to zero,
1107
01:14:59,550 --> 01:15:01,150
we have this
particular equation.
1108
01:15:01,150 --> 01:15:04,100
We plug it in over
here, this all cancels,
1109
01:15:04,100 --> 01:15:06,840
and we just are left with m.
1110
01:15:06,840 --> 01:15:12,080
Now, if m is equal-- is
congruent-- to 0 modulo p,
1111
01:15:12,080 --> 01:15:16,050
then we can see that
it is equal to 0.
1112
01:15:16,050 --> 01:15:18,210
So it's equal to 0.
1113
01:15:18,210 --> 01:15:21,600
So this actually
holds for any case.
1114
01:15:21,600 --> 01:15:27,680
Now we can do the same for
q-- the same argument--
1115
01:15:27,680 --> 01:15:30,680
and show that this must hold.
1116
01:15:30,680 --> 01:15:35,110
So now we know that p
divides the difference
1117
01:15:35,110 --> 01:15:38,225
of m prime d minus m.
1118
01:15:38,225 --> 01:15:43,190
q is another prime that
divides this difference.
1119
01:15:43,190 --> 01:15:49,280
And the only way that's possible
is if the product of p and q
1120
01:15:49,280 --> 01:15:55,130
is dividing this particular
number-- this difference.
1121
01:15:55,130 --> 01:15:58,230
And we have two different
primes dividing the same number,
1122
01:15:58,230 --> 01:16:00,290
so the product
must [? divided. ?]
1123
01:16:00,290 --> 01:16:08,770
So p times q divides
m prime d minus m.
1124
01:16:08,770 --> 01:16:12,040
Oh, but p times q is equal to n.
1125
01:16:12,040 --> 01:16:14,230
So now we're almost
done, because now we
1126
01:16:14,230 --> 01:16:18,010
can state-- by the
definition of congruency--
1127
01:16:18,010 --> 01:16:26,350
that m prime to the power d
is congruent to m modulo n.
1128
01:16:26,350 --> 01:16:32,200
Now, since m is a message that's
in the range of-- so I did not
1129
01:16:32,200 --> 01:16:35,030
write it down here--
so m is a message
1130
01:16:35,030 --> 01:16:40,440
which is in the range of 0
all the way up to n minus 1.
1131
01:16:40,440 --> 01:16:43,440
We know, and we have seen it
before with Turing's code,
1132
01:16:43,440 --> 01:16:47,200
that we can rewrite this
and say that m equals
1133
01:16:47,200 --> 01:16:50,960
the remainder of m
prime to the power
1134
01:16:50,960 --> 01:16:57,100
d, after multiplying out as
many multiples of n as possible.
1135
01:16:57,100 --> 01:16:58,060
So here you go.
1136
01:16:58,060 --> 01:17:02,180
So this is the decryption
rule, and it works.
1137
01:17:02,180 --> 01:17:06,640
We have shown that this
equation truly holds.
1138
01:17:06,640 --> 01:17:10,250
So RSA has really
withstood the test of time.
1139
01:17:10,250 --> 01:17:13,250
It's already out there
for many decades,
1140
01:17:13,250 --> 01:17:15,322
and it's still widely used.
1141
01:17:15,322 --> 01:17:17,030
I wanted to talk a
little bit about this,
1142
01:17:17,030 --> 01:17:19,580
but there seemed not
to be enough time.
1143
01:17:19,580 --> 01:17:26,570
But I'd just like to mention
that only 2009 Craig Gentry
1144
01:17:26,570 --> 01:17:32,250
proved a beautiful theorem,
and was able to evaluate
1145
01:17:32,250 --> 01:17:33,250
Boolean circuits.
1146
01:17:33,250 --> 01:17:37,650
Or, say, certain types of
programs under encryption.
1147
01:17:37,650 --> 01:17:41,040
So you can sort of add
and multiply cypher text
1148
01:17:41,040 --> 01:17:45,310
encryptions together, and it
is as if you multiply them
1149
01:17:45,310 --> 01:17:46,700
at the plain text level.
1150
01:17:46,700 --> 01:17:50,720
That was a fantastic-- that
was an enormous open problem.
1151
01:17:50,720 --> 01:17:52,030
And he solved it.
1152
01:17:52,030 --> 01:17:55,850
And only a few months
earlier, in 2010,
1153
01:17:55,850 --> 01:17:59,810
in joint work with Craig and
some other colleagues at IBM,
1154
01:17:59,810 --> 01:18:02,570
we showed it with
very simple arithmetic
1155
01:18:02,570 --> 01:18:07,120
that just uses modulo p and
modulo 2 kind of things.
1156
01:18:07,120 --> 01:18:11,450
We could show a
construction this
1157
01:18:11,450 --> 01:18:13,490
has such a property--
such an encryption
1158
01:18:13,490 --> 01:18:15,100
scheme of the integers.
1159
01:18:15,100 --> 01:18:18,130
So there's still a lot of
stuff going on in this area.
1160
01:18:18,130 --> 01:18:21,780
And really, we use this
type of very basic stuff.
1161
01:18:21,780 --> 01:18:25,450
The problem in cryptography
is to show that it is secure.
1162
01:18:25,450 --> 01:18:28,330
So you have to show
that breaking the scheme
1163
01:18:28,330 --> 01:18:32,190
needs to be reduced to
some really hard problem.
1164
01:18:32,190 --> 01:18:34,920
And that is always the
really difficult part
1165
01:18:34,920 --> 01:18:37,200
of such type of research.
1166
01:18:37,200 --> 01:18:40,950
OK, well, have lots of
fun with recitation.