The following content is provided under a Creative

Commons license.

Your support will help MIT OpenCourseWare

continue to offer high quality educational resources for free.

To make a donation or view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

at ocw.mit.edu.

PROFESSOR: So let's get ready.

If good, you should receive some handouts.

So the TAs are walking around, so you should slowly get those.

This is the second lecture on number theory,

and we're going to cover for a lot of stuff.

And actually, we're going to start

with encryption, which is an application of number theory.

And we'll take that as a theme throughout the whole lecture.

And so, in this way, you can see how useful number theory is.

Now, encryption-- yeah, what is it?

So let's first talk about it a little bit.

Maybe some of you have heard about it.

Cryptology in general is the art of hiding information.

And encryption is a very useful tool.

I'll only give a very high level overview.

I mean, if you really want to know more about this,

you should do a class in crypto, or practical security.

So what's encryption?

The idea is usually that, beforehand, we're

going to share a whole bunch of keys.

So keys are exchanged between a receiver and a sender.

And the whole idea is that if I want to transmit, like,

a message to one of you, well, there

could be someone in the middle who

wants to intercept my message, and wants

to find out what I'm saying.

So I do not like this.

And in order to avoid it, I will use encryption,

which is some kind of algorithm that actually transforms

my message m-- my plain message-- by using

some kind of algorithm, E. Some encryption algorithm--

it can be a function as well-- that uses the keys

in order to transform this into an encryption, which

we call m prime here.

So the plain text is, in the clear, all the information

that I want to convey to one of you, for example.

And m prime is somehow a complete-- well,

a mixture of bits, out of which I'm not

able to distill any information about the plain text.

So encryption to a very special kind of thing.

We're not going to talk about the precise definitions here,

but we just take the ID into this lecture.

Now, decryption is transforming the cypher text back

into the plain text.

So we will start with the encryption, m prime,

and we have some kind of decryption algorithm.

And again, we can make use of the keys we exchanged.

And we transform it back into the plain message.

So only if I know the keys, I can actually

transform back the encrypted version into the plain version.

So in encryption schemes we like both these algorithms

to be is really efficient.

And the security of such a scheme-- well, the first kind

of intuition that we can get is well,

if I'm a man in the middle somewhere,

intercepting an encrypted message-- m prime--

I should not be able to get any information about m

if I have no knowledge about those keys.

So this is the example that we're

going to take throughout this whole lecture.

So let's start with a first possible scheme.

Turing, who lived around 1936-- he was 24 years old--

and he lived to about-- actually,

I think he was about 54 when he died.

In any case, Turing was the one who first originally proposed

to use number theory in cryptography.

And before he joined the British army, before the Second World

War, he actually proposed a scheme,

but it got never published.

So here in this class, we are going

to try to think about what he could have thought about.

So we will have a first scheme, which

we will call Turing's code, version number one.

And the whole idea is that we're going

to translate a message first of all into a prime number,

because we want to use numbers.

We're here in number theory class,

so we want to use some tricks with numbers in order

to encrypt it.

So let's do this.

So for example, let's take the word victory.

We can map this into an integer.

For example, we could say, well, m is 22,

where I map V to-- because I know

V is the 22nd letter in the alphabet, I just start with 22.

I is the ninth letter in the alphabet, so I append 09.

C is the third letter in the alphabet, I append 3-- 03.

I continue like this and in end, over here

I've mapped Y to the 25th letter.

Because it's the 25th letter of alphabet, I write 25.

It turns out, I can just add a couple of digits

more, if I specially compute those.

In this case, I could add 13, and then it

changes into a prime number.

Now we are not going to talk about why this is,

and how this can be done, and so on.

But it turns out that the prime numbers are densely

distributed over the integers, and it's really possible to,

just with a few extra digits-- by selecting them

in a smart way-- to actually create a prime number.

And also verify that it is a prime number very efficiently.

So it's very easy to compute-- to translate such a word

into a prime number.

So this is how it all starts.

And just like in an encryption scheme,

beforehand we are going to exchange a key.

So we exchange the secret prime in this example,

which we call k.

And the encryption is very simple.

We are just going to multiply m with k.

Now, you may wonder why this is such a fantastic idea.

But let's just bear with me.

So m is this first prime number, and we multiply it

by a second prime number, and that's

going to be our encryption.

Now how do we decrypt?

That seems to be pretty straightforward, right?

How do we do it?

We start off with m prime.

I know we have exchanged this secret prime k,

so if I receive from you this message--

this encrypted message-- well, I know the key, k.

So I just divide it by k.

Well, which is m k divided k, and I get m.

So that's pretty straightforward.

Now, as it turns out actually-- and I'll write it up here,

because we need it later-- that it's not so trivial to actually

just give an m prime to figure out what m is, or k.

m prime is a product of two very large prime numbers,

and that turns out to be a really hard problem.

Up to now, nobody has really been

able to get a really efficient algorithm to solve that.

So we may think this is secure.

So let me write it down It's hard to factor

a product of two large primes.

You will actually need this also,

when we come to the final encryption scheme-- RSA

that we will discuss, which is widely used.

But something is wrong here, though.

This seems to be too simple, right?

So what can we do if we have like, say,

suppose I intercept two encrypted messages.

What can I do?

So suppose I have a first message, m

prime 1, which is the product of a first plain message

times the key, k.

And I have a second message that is

encrypted by using the same key, which is m 2 times k.

Does anybody have an idea what I could do here?

AUDIENCE: Find the GCD and that would give you the key.

PROFESSOR: Yeah, you could find the GCD

of m 1 prime and m 2 prime.

I've intercepted those two.

Now, m 1 is a prime number.

k is prime number, and 2 is a prime number.

k is a prime number here, also, right?

So they're all relatively prime towards one another.

The GCD of these two-- well, the greatest common divisor is k.

So just by calculating the GCD of the two encrypted messages,

I'll be able to figure out what k is-- the key.

Well, if I know the key, then I can

do the decryption of any cypher text,

any encryption of a message that I can intercept.

So this is not secure.

So how can we change this?

Can we create a different kind of encryption scheme?

Let's do something much more difficult,

and then we will get into modular arithmetic and things

like that.

So let's do this.

So Turing's code, version number two--

we try to do something much more complicated than just

multiplying by prime.

So let's do the following.

So beforehand, we're going to exchange not only

a secret prime k, but we will also exchange a public prime.

So we exchange-- by public we mean that anybody

can see this prime.

It's common knowledge.

A public prime p, and also a secret prime k.

Let's see whether this would work.

We have encryption.

Well, we're going to start out exactly the same way.

First of all, I should tell you how a message is represented.

The message is going to be represented as a number, m,

in the range from 0, 1, all the way to p minus 1.

And we will compute the encryption as follows.

m is going to be the remainder of m times k,

after dividing out as many multiples of p as possible.

So notice we do kind of the same thing.

We just multiply by k, but now we

just take the remainder after taking out

as many multiples of p.

Well, let's see whether we can do the decryption.

It seems to be, like, a next level of complexity.

So maybe that'll help us here, right?

So how will we do decryption?

Well, somehow we would like to divide by k.

But we cannot really do that, right?

This does not make any sense.

So the decryption-- we have no idea at this point

how to do this.

And now we can get into modular arithmetic,

because it turns out that we can sort of divide by k.

There exists what we call multiplicative inverse

of k modulo p.

And I will explain all those terminologies to you.

And then we will be able to take m prime,

and transform it back to m.

So we will be able to get a lot of this machinery going.

So let's find out how this works.

So first of all, last time we saw that we defined a and b

to be relatively prime.

So let me repeat that.

So a and b are relatively prime if and only

if-- that's how we define it-- if the GCD of a and b

is equal to 1.

And in last lecture and in the recitation,

you got a different proof, I think.

And we proved that, actually, the GCD of a and b

is equal to the smallest positive linear combination

of a and b.

So that means that one, in particular,

is a linear combination of a and b.

So there exists integers-- s and t--

such that s times a, plus t times b equals 1.

It turns out that it can also go the other way around,

because if I can write one as a linear combination of a b,

well I cannot get much lower than that, right?

So that's really the smallest possible that I can achieve.