Placeholder Image

字幕表 動画を再生する

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