 ## 字幕表 動画を再生する

• The following content is provided under a Creative

• Your support will help MIT OpenCourseWare

• 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.

• 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.

• 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.

• 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