Breaking RSA - Computerphile

If you pick the wrong prime numbers, cracking RSA becomes a cinch. Dr Mike Pound explains the findings of researcher Hanno Böck


This video was filmed and edited by Sean Riley.

[bluekeybo]

The best lecturer on Computerphile, hands down.

[JMPDev]

“A lot of thought goes into generating random primes than I am doing justice in this video” - sounds like a great topic for a future video :)

[halbronk]

I find it hilarious that for weak primes, the factoring algorithm runs faster than the primality test.

[sharkinahat]

Generating random numbers is too important to leave it up to chance.

[python-programming]

Always a good day when a Mike Pound video drops!

[elmoyou]

While not directly related to this RSA "shortcoming", this video did remind me of another (arguably more fundamental) concern regarding RSA. It is widely known that the difficulty of factorizing the product of two large and random prime numbers, is that makes RSA work. However, when just 1 of those primes isn't truly random, maybe a fixed value or in any way deterministic or part of some limited/predictable pool/rotation of seemingly random possibilities, it becomes rather trivial to break the cipher (to anyone with knowledge about what makes this prime less random).

Nothing new there. This "trick" has been used in CTF challenges. However, what has surprised me on several occasions, is that not many people appear to realize that it is this same factorization problem that makes it equally hard/impossible to detect any "weakened" key from the outside. In other words: it is nearly impossible to determine if a RSA initiated encrypted transmission is in fact secure, without access to the private key. From a set of private keys, a pattern in primes might still be spotted (although maybe not trivial). But from just public keys, this is certainly nearly impossible.

In a way, you could say that RSA is just as good at hiding compromised security, as it is at providing secure cryptography. One may ponder on whether that is a desirable property of good cryptography. One may also wonder whether that might have been just a side effect, or who knows maybe intentional.

The few times I have seen this being brought up, it was instantly discarded as irrelevant. Often in a surprisingly dismissive way. Usually with arguments along the way of: "if you don't trust who generated the keys, all bets are off anyways" or "organizations who take their security seriously, will do such a thing because of X Y Z". However, I can think of at least several scenarios in which a company may like to pretend to use very strong cryptography, while at the same time (secretively) provide a convenient way (e.g. to a 3rd party with "special interests") to eavesdrop on those "secure" transmission without much hassle.

While accusations of any such a thing actually happening remain conspiracy theory, it is the nature of this factorization difficulty in RSA that also makes that it would be almost impossible to prove such a thing taking place (unless some closely guarded secret leaks out). Considering the history of the NSA and RSA (both individually and in relationship with each other), it feels to me like this RSA concern deserves more attention than it generally appears to get. Similar concerns (although for totally different technical reason) might be raised regarding the NSA's EC cryptography.

But that's just my 2 cents.

[gloweye]

Back in school, we did some RSA by hand, generally using primes up to 13. having a p, q = 7, 13 is a bit lower than generally secure, but it illustrates the point nicely.

[johnholly]

Definitely stealing this method for CTFs. I've been using a number field sieve to factor low-bit modulo numbers. This is awesome!

[compuholic]

Just another bullet point in the long list of reasons why you should never ever implement cryptography algorithms yourself unless you really, really know what you are doing.

Unfortunately many people think that because the formulas behind cryptography algorithms are easy to find, implementing them is also easy. There is a reason why you have specialists for cryptography.

[elraviv]

7:09 an interesting point here, you need to assume that a & b are integers.
since b=(p-q)/2 a=(p+q)/2 they might be a fraction like if p=5 & q=2.
fortunately "2" is the only even prime. so we are dealing here with two odd primes, so always
(p-q) & (p+q) are even.

[anarcho.pacifist]

Also when p-1 or p+1 is B-smooth for some small value of B (approx. B <= 10^8), then the prime factor p can be found very fast using the Pollard's p-1 method, or the WIlliams' p+1 method. More generally, the Lenstra's Elliptic Curves Method can also be used.

[noir]

I have no idea what he’s talking about but I can’t stop watching

[Thats_Mr_Random_Person_to_you]

Would love more videos on the challenges of generating good primes.

As said its more complex that math.random, and this video shows that bad prime choice can destroy what is essentially an amazingly good encryption algorithm. So would love to know more!!! Its that nice mix of maths and computer science (almost like a hybrid of numberphile and computerphile!) that I think is really fascinating and resonantes with both audiences.

Dr. Mike is really great at explaining even really complex topics, so would be great for more!!!

[DedicatedAngler]

I love this channel. it's encouraged me to start a degree in computer science, I'm just starting second year and I'm really excited.

[Ormaaj]

Ah yes, been reading Hanno's blog for years. His "feisty duck" newsletter is also always a good read. How very unsurprising to see Hanno's excellent work make an appearance. :)

[gdclemo]

Interesting. I'm surprised that it finds the factors so quickly, even with so many random bits difference. You're effectively searching for the arithmetic mean ((p+q)/2) of the two factors, given the geometric mean (sqrt(pq)). I guess the 'trick' is that for numbers of similar scale, these two values are very close.

[edwardkent]

A side note - any modulo with a prime base creates a group under multiplication, which is why you mentioned finding the inverse of phi_n - I think this is an awesome example of pure maths such as group theory actually being used in action! :)

[Rchals]

Hum, so this is a glimpse of what Professor Edward Frenkel was talking about the relations between P and Q in the NSA video... it is frightening to think what math techniques and tools may be under the radar that we will never know about...

[alessioprovenzano]

Maybe you can use a factor K for N: X^2 + K*N = Y^2 and using K as an iterator.

For example: 313 * 113 = 35369 = N, if you pick K as equal 3 you get 3*35369 = K*N = 106107 so take the square root of ceil(3 * 35369) = 326;

326^2 - 3 * 35369 = 169 = 13^2

326 - 13 = 313 = P
326 + 13 = 339 = Q * 3

For example: 17 * 11 = 187, K = 1 -> ceil(sqrt(K*N)) = 14 and 14^2 - 187*1 = 3*3 -> 14 + 3 = 17, 14 - 3 = 11

[jacob_s]

13:35 pick random p, find the nearest prime
pick q such that q > [p + 2^n/2] (or you can choose whatever difference is large enough for you), and find the nearest prime above that The important part is if the q you pick doesn't match, you have to generate a completely brand new number each time.