The best lecturer on Computerphile, hands down.

“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 :)

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

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

Always a good day when a Mike Pound video drops!

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.

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

Really nice video. And I am playing with Sage again, after some 10 years. Mr. Euler and Mr. Fermat - it is truly amazing what you guys gave us.

the math is way over my head, but again Dr Mike made a complex subject very simple to follow, Thanks you, always look forward to these presentations.

please post more computerphile. I find my computer science classes incredibly boring, but these videos I cant stop watching. Makes me love computers!

Love these little lectures! More concepts and interesting problems please!

I watch each of these lectures. To learn but also just to relax.

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.

Not sure if anyone has mentioned this, but I love how you've repurposed continuous feed (dot matrix) paper! Also, your writing is so clean and legible, which makes it perfect for this application!

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

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.

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.

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!!!

This was so well explained, wow. Nicely done!

Very nice! A video with a practical example! Not only dry theory as most of your videos.

Any plans to have a video on quantum-resistant cryptography? Seems like a good time with the recent White House memo

Also when p-1 or p+1 is B-smooth for some small value of B (approx. B

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! :)

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.

Owh yes, dr Pound is always on point!

Interesting that you only have in the private key, all the reference implementations I've found (and the one ChatGPT spat out) all have a two-part private key, made of (, ) and also using both…

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.

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.

3:04 a Lisp developer was born that second.

Great video! What about making a video about Peter Shor's algorithm for quantum computers?

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. :)

There used to be a big problem with some hardware servers with too low entropy to generate p and q at boot. Often 2 different servers where using the same p or the same q. So there's N1=p . q1 And N2=p . q2 Taking the biggest common prime factor of 2 numbers is fast so do that on N1 and N2 to get p then you get q1 and q2 with simple division. 2 servers hacked together...

Mike pound is back ! Missed you man

This is pretty neat method to reduce search space , I will have to give it a run. I would use this against the issuing CA, not the server key. Then re-issue your own certificates. Sign your own firmware images. Some firmware signing techniques will use an intermediate certificate and leaf that are both generated at the time of signing and each time a new image is signed. It would be interesting to analyse the p q generation in such a circumstance.

Unparalleled explanation skills!

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...

Have you done a video on using quantum computing to break RSA?

Really great Lecture. Well Done.

"I'm not a genius, it just wasn't difficult". I'm using this

Six minutes in I had to check, am I on numberphile or computerphile

I’m not a programmer or coder but when Mr P speaks I listen.

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

_RSA Hate Him for This One Simple Trick_

That looks like it's a pretty handy test algorithm to make sure your encryption is properly secure.

This is exactly the reason why one must never implement cryptographic algorithms as they are explained in textbooks. They lack all these real world tweaks which are necessary to prevent very specialized attacks for specific cases. There even have been smartphone apps in the past (sorry for not remembering the names - they were short lived), where cryptographers essentially criticized exactly that: It was a textbook implementation which does not hold up against real world scenarios, resulting from specific hardware, bad random number generators, limited memory, similar user mindsets, etc...

Common factor attack: Given two private keys n1 = p * q1, n2 = p * q2, using the same p, then p = gcd(n1, n2), which is easy to compute with Euclid's algorithm, then q = n / p. This actually happened for a large number of public keys in the wild, that had been generated using a faulty prime number generator. This finding was revealed in a paper from February 2012.

isqrt(n) + 1 -- "so that's the ceiling" only given that n isn't square, otherwise it's the ceiling + 1 :)

When I started following Numberphile I couldn't understand what was all the fuss about with the primes. Then I started following computerphile and it slowly started to make sense.

RSA has been broken. It has a secret back door: correct horse battery staple

Presumably, someone could "sweep the web", looking for weak Public Keys, and then focus their attacks on those poor unfortunates.

Aahh man, ComputerPhil the expert does it again!

7:30 If we maintained a list of squares where S]x] = x^2, then ceil(sqrt(N)) = bisect.bisect_left(S, N) which can be computed in O(lgN). I'm guessing the issue is that N is so large that maintaining a sufficiently long list S would be impractical.

I love this! Even without understanding all

I wonder if you could make this work better on well chosen primes by assuming they will be well chosen. Start at root of N + the root of the root of N and start going both up and down (instead of a=a+1 you have a+g and a=g for g starts at 1 and g=g+1 each iteration.

Good stuff! Look forward to the video on selection of random primes

love this stuff, even though my maths was always garbage.

Mike makes the day

I love the way he talks

please make a cryptography playlist of Dr. Mike Pound videos

How fast could you calculate 'd' (public key) when using optimized code for QBit Processor? Even when 'p' and 'q' are "difficult" numbers?

This is brilliant.. and scary ! I would imagine not a lot the RSA libraries will pick a good far apart primes. And what makes this scary is parallelizing this is quite easy.

5:38 I'm relieved that not even Dr. Mike Pound can escape the inevitable sharpie marks on your hands.

Ahh the nightmare is back... Had to do both RSA and quadratic sieving by hand during my discrete maths exam.

It seems that your starting guess for "a" could actually be anything, and as long as your initial guess is close, this method is a (relatively) fast way to explore out from that point? Is my understanding correct that the lesson learned from this isn't "don't pick two primes that are close in size", but rather "don't pick primes that are near intuitive starting positions"? And then you have the issue that, if you tell all of the RSA algorithm providers to avoid all of the areas that are near intuitive starting positions, you've drastically, and perhaps cataclysmically, reduced the search-space of what 'acceptable' primes are in-use by RSA library providers? I feel like I'm missing something here, posting to be corrected and be a little less wrong.

I was about to wreck havoc on the internet but Mike said don't that stopped me.

The good news is since getting the weak primes out of the keys is so trivial, it's equally trivial to make a test at key creation and just reject the keys and start over.

I find that if you add phi(n) to the d key, then the new d = old d + phi(n) still works, is that new private key?

I wonder if this problem generally occurs if the attacker, for whatever reason, has a good estimate on p/q? In which case it is not so much that choosing p and q similar is inherently weak it is just that it is natural to try for p/q close to 1 and it is more natural to end up with an implementation of choosing p and q close to each other rather than specifically 20% apart. Kinda how 1234 is not a weaker number than any other 4 digit number but it is bad as a password because the human brain can more easily remember it and thus prefers to choose it.

Have any RSA client libraries implemented checks to reject certs with weak keys?

would it be possible to have an n that is the product of several sets of p and q primes and would that make it "easier" for figure out d? just thinking that having a bigger pool of primes to use might make it somewhat quicker somehow.

I think he purposefully avoids looking at the camera, at us. And I think it has a positive effect on us focusing on the subject.

plz ! i hope you make a video about chacha20/xchacha20 cipher with more details !!

The thumbnail is savage 😂

Pls do a video about yubikey or sth similar

I haven't understood how I would end-up with two close values of p and q. Because when I generate an RSA key pair, I don't choose those numbers (I'm not even aware of them). I might be asked by the keygen program to 'generate some randomness' by moving my mouse (or some such). So what's the arrangement where these values are 'badly chosen'? How could I [arrange that | rely on that | expect that] as a hacker?

Nice explanation 😄

I tried many ways, I even modified my iptables rules, firewall restrictions, and all the possible ways, but still I cant get reverse shell. Netcat doesn't listen to my reverse shell, so I stucked in the root me room for more than a week. I need help, please anyone suggest me any ideas to overcome this.

Protect this man at all costs.

Have no idea what you said but I enjoy it. Thank you sir and tha k you computerfile

thank you!

10:16 In this pythonic context, the ^ gave me small heart attack. But then I remembered it's not Python.

I was literally just thinking about how secure the factorization of RSA really is and this video pops up. Im amazed.

Geez, he got a new sweater/jumper. Times are changing.

How do we know if our RSA implementation avoids this? Could NSA sneak something in that causes this weakness?

this was scary af and also interesting!

function rsaAlgorithm(base, exponent, modulus) { return base**exponent % modulus }

brilliant

Can someone give a proper intuitive explanation for this? I just tried it myself, randomising the last 512 bits and it found the result in the first step of ceil(sqrt(n)). How can it pinpoint to the solution so easily.

You explained very well for a person that doesn't know anything about math

Is n the same as N? I didn't catch why there was a change but he did refer to N once as, "our original en." So....?

I see Mike Pound, I click. I am a simple man.

muchas gracias❤❤

11:03 Why are a and b so different in length? I thought they were similar in length? Edit: Nevermind. We are talking about p and q, and not a and b :facepalm:

So then how close is 'too close'? Once you know the threshold for 'too close' couldn't you just begin your search outside that boundary? Basically reducing your search space?

Now this is really scary... Especially in some proprietary systems where you have no access to protocols which calculates RSA...

But just where does Dr Mike get his sweaters...?

I don't understand one thing though, 1 mod anything is always 1 right? So what's the point of writing 1 mod (euler totient (n))?

This video might get a million views :)

I'm 4 minutes in and I have a 3-part question. if P and Q are Prime numbers, How many primes are in the "usable range of primes", and is that few enough that you could precalculate them into an, albeit large, rainbow-table? How large of a drive would you need to store the rainbowtable for current RSA prime sizes? I'd also like to clarify "usable range of primes", because, the generation method for primes, will not give all primes for a range, and is a much, much shorter list.

Python people, remember exponentiation operator is a double-asterisk, caret is bitwise XOR.