[MUSIC] Hi. In this lesson, we're going to study the attacks against RSA. Although RSA is a secure crypto system, there are lot of subtle details in the implementation and if used incorrectly, it is actually possible to break the cipher. And you should listen carefully because you're going to actually decipher some cyber text yourself as an exercise. I think these are pretty cool problems but to solve them, you need to really understand what's going on and the like. We'll start with some simple attacks. First case is Alice wants to secretly transmit a message to Bob. So Alice and Bob are secret agents or Alice is a secret agent and Bob is sitting in the center, and Alice needs to either transmit that the center should attack or don't attack, to Bob. So she can convert the message attack to message m = 1 and don't attack to message m = 0 and then use RSA to encrypt m with sum public key and send the ciphertext c so that the center can decrypt it using its private key. So all in all we're using only the secure algorithms, everything should be okay, right? Well actually it's not, because unfortunately it's really easy to break this particular cipher. Just try to include both m = 0 and m = 1 with RSA, the same way, and then check which one of them results in the ciphertext c. And the one which coincides with ciphertext that Alice is going to send to Bob, this is what was initially encoded. So the algorithm RSA is publicly known, the public exponent is publicly known. So anyone can take both messages 0 and 1 and include them to get the cipher text and then compare the cipher text to the ones that was actually sent. And this works with any small set of possible messages. If you have not 2 messages but let's say 100, still an attacker can just try to encrypt all of them, see which of the ciphertext coincides with the ciphertext that you send and then he can decrypt your message. So this is really a practical situation. Of course, not often you need to send just one of two messages. But it is very often that you will want to send one of a very limited set of messages, and it is pretty fine. So what to do to solve this problem? The solution is to use randomness. So for example, you can always use the first 128 bits for the message itself and then you also append some 128 more just random bits before encryption. So, for Bob to look like he'll be able to read the first 128 bits in plain English or other language, and then the other 128 bits he won't just use, he won't look at them, they are meaningless. But this simple attack already won't work because to try all possible messages they would have to not only try the first 128 bits filled with one of the pre defined messages, but they would actually have to go through all possible combinations of the second half with 128 bits and that's already 2 to the power of 128 possible messages which is basically impossible to try all of them out. So at least this simple attack won't work if you use some randomness before sending the ciphertext. Another way to attack the RSA is for example Bob generates two random primes p and q and then he publishes the public key. But what if one of those primes p turns out to be less than 1 million? Then Eve which is eavesdropping, can try all primes up to 1 million as the potential divisors of the publicly published key n and she will get the factorization of n, p times q. And then she will be able to do the same thing that Bob does to decrypt any message that is being sent. So, if one of the primes is small, we can actually solve the factorization problem and that is why we can decipher the ciphertext. So, one typical solution to this is to generate random primes for the secret key uniformly among very large numbers. For example, you only generate primes which have 2048 bits, then these primes would be guaranteed to be big enough so that no one can go through all possible values of these primes. So these were two pretty simple attacks and we're going to discus some more advance attacks in the next videos. [SOUND]