I'm a newbie to encryption. If I create a number 'n' as a product of two prime numbers 'p' and 'q' with the following specifications:

'p' is a fully random prime with 300 decimal digits in length. 'q' is a fully random prime with 400 decimal digits in length.

My question is: If I make 'n' public, will anyone be able to get 'p' and 'q' within a month? Tanks in advance!

  • 2
    $\begingroup$ That's about 2300 bits modulus length, which is what is widely used (unbroken) on the internet. $\endgroup$ – SEJPM Jun 25 '16 at 11:54
  • $\begingroup$ Thank you for your quick answer. So what would be the minimum number of decimal digits nowadays to get 'p' and 'q' from 'n'? $\endgroup$ – Jan Lonner Jun 25 '16 at 11:58
  • 1
    $\begingroup$ @JanLonner: this answer could help. The number of bits (used in cryptography) is $\log_2(10)\approx3.322$ times the number of decimal digits. $\endgroup$ – fgrieu Jun 25 '16 at 12:05
  • 1
    $\begingroup$ someone could guess it on the first try, but that's exceedingly unlikely $\endgroup$ – dandavis Jun 26 '16 at 9:10

No an attacker will not be able to factor your $n$ (e.g. break it).

Your $n$ is of size 700 decimal digits which is $\frac{700}{\log_{10}(2)}\approx2325$ bits. Now 2048-bit moduli is the most widespread size used on the internet and hasn't seen a failure yet (without exploiting bad random number generators), so you are secure with that modulus size.

As for the largest known-broken modulus size, this would be a 768-bit modulus and it is conjectured that nation-state attackers are able to factor 1024-bit moduli using their ressources.

You have chosen 400 digits and 300 digits. While this is safe in this instance, this is unusual to do, because too much unbalancedness can help the attacker as he can apply attacks that find small factors first (by trial division or ECM). The standard way of approaching this is to generate two equally large primes (in terms of digits) and ensuring that $|p-q|>2^{k/3}$ (where k is your modulus bitlength), which will hold anyways with overwhelming probability if you choose both primes independently at random.

| improve this answer | |
  • $\begingroup$ What is the ideal difference between 'p' and 'q'? I mean: is it right to keep the length of 'p' in the range of 43%-48% of the length of 'n'? $\endgroup$ – Jan Lonner Jun 25 '16 at 12:42
  • 1
    $\begingroup$ @JanLonner Ideally you'd use the same bit length for all factors. But in your example the asymmetry is not big enough to make elliptic-curve factoring more efficient than GNFS, so it doesn't really matter. $\endgroup$ – CodesInChaos Jun 25 '16 at 12:54
  • $\begingroup$ @JanLonner Usually the primes are chosen to be of equal length (in base 2), which will imply that the largest prime divided by the smallest prime will be less than 2. A pair of primes of 300 and 400 digits differ by a lot more than that. Given the performance characteristics of currently published algorithms for factoring it may be that the optimal number of primes is more than two. For instance it might be advantageous to use three primes of 250 digits each rather than the two primes you are currently using. $\endgroup$ – kasperd Jun 25 '16 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.