[MUSIC] Hi, in this video we're going to study a bit more subtle attack, which uses a small difference between primes and the public key. So assume that Bob generates primes p and q such that p is less than q and the difference q- p is somewhat small like 1 million. What can Eve do in this situation, what do you think? Well, we see that n = p times q and p is less than q so p should be less than square root of n and q should be bigger than square root of n for that to be true. And Eve doesn't know p or q, but she knows that this property is necessarily true, that one of the primes is less than the square root of n and another one is bigger than the square root of n. Now, we can also say that square root of n- p is less than q- p because square root of n is less than the bigger of the two primes. q- p = r, which is small. And so now, we can say that square root of n- r is less than p, okay? And then, also, we know that p, the smaller of two primes is less than square root of n. So now we have a range between square root of n- r and square root of n where necessarily, one of our prime lies. So p is lying in this range. And the life of this range, was it? Well, it's just r, which was said to be pretty small, like 1 million or something. So what we can do is we can actually for applying for Eve we can try all integers in this range between square root of n- r and square root of n as divisors of n. And necessarily we will be able to factorize n and to try just 1 million divisors is, we can do that pretty fast. So this leaves to us breaking decipher. Actually we can do this even more efficiently because if n is the product of two primes, well of course p and q will be both odd because it doesn't make any sense to use prime number two as one of those because it's small and we already know that RSA when one of the prime is small. Then both p and q are more than two and so they're both odd. So number p+ q over 2 and p minus q over 2 are integers. Now n = p times q and we can rewrite that as p = (p + q) over 2 + ( p- q) over 2 and q = (p + q) over 2- p minus q over 2. So we can rewrite as a product of these to break us and then this product is equal to difference of squares of p + q over 2 squared minus p- q over 2 squared. So n is the difference of squares and one of the squares is small because the absolute value of p minus q is given to be small. So what we can do to decipher or to factorise n, at least we can try adding the increasing squares of integers to n. Like try n plus one, try n plus four, try n plus nine and so on, and plus some small numbers squared until the number that we get becomes a perfect square. So if you get n plus some square is equal to some other square then we get that n is a difference of square. So of course we can use the formula a plus b times a minus b to factorise the difference of squares. So this is guaranteed to work, because we know that some square of a number less than, let's say 1 million, is going to work. So we will just try all these numbers, and try to, factorize that. So, this can be done probably even faster than the previous version of just going through all possible p in the range. So the solution to avoid this attack is to not just generate p and q, but if we generate the p and q and it turns out that absolute value of p- q is small, and can just regenerate and repeat until the absolute value of p- q is sufficiently large. But actually in practice if we're using a good random number generator and we're generating really big primes, like primes of size 2048 bits, then the probability that this happens is negligibly small. So we can actually even ignore this problem whatsoever and just generate primes uniformly among all big integer numbers of 2048 bits. And the probability that we'll get this problem is so small that we don't need to bother about it. The probability that someone will just go and tell our enemy our secret key is much bigger than the probability that this algorithm will actually generate two prime which are too close to each other. So although this is an interesting attack this is more of a theoretical attack which shouldn't happen in practice, and we don't have to actually defend ourselves against it. The only way we need to defend us is to really use uniform distribution on the numbers when we generate big random. [MUSIC]