What if A and B want to send many messages to each other. For example, Alice wants to send several messages to B? Turns out that they need a separate secret key for each sent message. Otherwise, Eve can decipher messages at least partially. Now this is what actually happened in practice. There was a so-called Project Venona by the US and due to this project, the US deciphered thousands of Soviet Union secret messages that they sent during the World War II in 1941 to 1945. Why that happened? Because, of course, the Soviets knew that they need to cipher their messages and they used what we've just described, called One Time Pad, to cipher those messages. But, the process of creating a random key and exchanging it with another party was pretty laborious. And the demand for sending secret messages during the war exploded and so, they just didn't catch up with a lot, and so, some of the keys were re-used. So, what was meant as a One Time Pad, just one key to encode one message, was actually used as a many-time pad. And then, if you used the same key to encode several messages in plaintext Russian or in plaintext English, it turns out that the eavesdropper can decipher at least part of it. Let's see how that happens. So, let's just assume that instead of using the same key once, we use it just two times. And so, what will Eve see during these two communications? First, she will see the ciphertext, c1, which is message m1 encoded with a key, k. Then, she will see the ciphertext, c2, which is the message m2 encoded with the same key, k. What she can compute then is the XOR of c1 and c2 which is equal to m1 XOR_k, XOR_k, XOR_m2. And you notice that I've changed places of m2 and k in this operation, but obviously, XOR operation is symmetric so this doesn't change anything. And in the middle, we get k_XOR_k which is zero. And you can just remove zero because nothing changes when you XOR something with zero. So, in the end what Eve will get is the XOR of the initial two messages, m1 and m2. And it turns out that if m1 and m2 are, for example, plain English, it is possible to at least partially decipher both given just m1_XOR_m2 because there is some redundancy in the encoding of English language. So, for example, if we know the XOR of m1 and m2 and somehow, we know the ith character of m1, character and position i, of course, we can already decipher the corresponding ith character of m2 because we know the m-prime which is equal to m1_XOR_m2. And this m-prime consists of corresponding source of bits on each position, the first position, second position, and up to Nth position. And on the ith position, m-prime_i is the XOR of m1i and m2i. So, to compute m2i, we can XOR back the known bit m-prime_i and the known bit m1i. So if we just know the XOR of two messages and some bit in one of them, we immediately know the same bit in another one. How does this help? How do we learn even one bit of one message? Well, it turns out that, for example, plain English messages contain lots of spaces of this. So, they contain some letters, maybe some punctuation marks, some numbers and lots, lots of spaces between words. Typically, computers store messages of plaintext in the so-called ASCII code. And it turns out that exclusive OR of any English letter with a space in this ASCII code is always different from exclusive OR of any two letters. So, if at some position, one of the messages contains a letter and another one contains an space, then you will be always able to distinguish this situation from the situation when there are two letters on this position, and of course, from this situation, when there are two spaces in this position, because, why? Well, because if you XOR two spaces, you just get zero, and this is different from what you get if you XOR two different characters being spaces or letters or anything. So, you can try to find positions of spaces in both messages, and using the XOR of the two messages, you will know what are the positions where there is a space in one message and a letter in another one. And then, you just have two possibilities of where is the space and what is here in another message. And doing that, you will decode the letters and the corresponding positions. And another thing, you can actually use is, that plaintext English messages are probably going to also contain some very common words, like the word "the" in the English language is the most frequent word. And it is very likely that one of the messages will contain "space the space" in some place, and another message will contain some other words, probably some letters, in these positions, and you will be able to guess that again. These five subsequent positions, we got space, the, and space. And this way, you will be able to gradually decode some, or at least some, of the positions in both of the messages. Even better, if you have not just two messages encoded with the same key, but many, like 10, and you'll actually do this yourself as an exercise. So to conclude, the One Time Pad using XOR enables secure communication. And B, to do that, must share some secret key, k, and use the XOR to encode plaintext message, m, with secret key, k, and to get ciphertext, c. And, they need to use each key to encode only one message, otherwise, the One Time Pad becomes two-time pad or many-time pad and it becomes possible to decipher at least part of the message. And, if they use the key just once, and this key is really random, then Eve cannot tell anything new about the message being sent apart from what she already knew about this message before it was sent. But the question is, in the end, how to efficiently establish a common secret key in the first place? Because A and B have to communicate somehow to do that, and Eve will be able to eavesdrop on everything they do within. So, in the next lecture, we're going to study an algorithm called RSA, which allows you to do exactly that even though Eve is listening.
