Search code examples
securityencryptioncryptographyrsapublic-key-encryption

Computing private key of a user from his RSA public key


I know that we will give (N,e) as our public key to every one and N is product of two prime numbers P and Q. But I know that product of two prime numbers has only 4 divisors (1, itself, P, Q) and using a simple while loop hackers can easily get P and Q and compute phi also. And since they already know E they can easily determine D by using E-1 mod phi(N) formula. So what am I missing?


Solution

  • That's the thing. If p and q are big, factoring n (calculating p and q out of it) is hard. It's also called the RSA problem. It is so hard that such a naive algorithm, as you've described it, would take many many years on an cluster to compute the private key out of the public key. Today, good starting values of n are typically 2048 or 4096-bit in size.

    Let's take for example an n of 2048-bit. You need to check somewhere between 21021 and 21023 numbers on average to see if they are a factor. To do that you need to do at least one division per number with division being the costliest operation. Let's say you can do 250 (this is already too optimistic) divisions per second. So it would take 21021 * 2-50 = 2971 seconds to brute force it naively. Or that many years:

    632876810481582893092457100785400357073646391563754928178128882051373633900610117258040958109029585581349076244353277284364674653853879268372390854352115493505836400606001292655231393152068425666747005563338382798494041874404131909211331579289714661817326517908344762063152744555537801

    A better algorithm than what you described is the general number field sieve. There are quantum algorithms that are supposed to run even faster.