字幕表 動画を再生する 英語字幕をプリント 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