2
$\begingroup$

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!

$\endgroup$
4
  • 2
    $\begingroup$ That's about 2300 bits modulus length, which is what is widely used (unbroken) on the internet. $\endgroup$
    – SEJPM
    Jun 25, 2016 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, 2016 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, 2016 at 12:05
  • 1
    $\begingroup$ someone could guess it on the first try, but that's exceedingly unlikely $\endgroup$
    – dandavis
    Jun 26, 2016 at 9:10

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2016 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$ Jun 25, 2016 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, 2016 at 16:36
0
$\begingroup$

Addressing kapserd's comment:

Likely using more than the two primes we use today would not help immensely, and likely (again) would reduce the difficulty. This is, of course, subject to the point I shall end with (below).

The reason is that there is one pair of lengths completing your right triangle for every pair combination of prime factors used. So use {3,5,7} and your combinations are {3,35}, {5,21}, and {7,15} giving you hypotenuse and other side lengths of {19,16}, {13,8}, and {11,4} respectively. (The third side is their product, 105, in all three triangles.) So now the codebreaker would have three targets instead of a single target. And adding primes makes those combinations take off.

The other point addresses the idea of using similar size primes. There is a human element to all things in human life and this is no exception. If one "must" shoot for two 350 decimal digit primes or "be sub-par at his encoding" then codebreakers will start with 350 decimal digit primes and work away from the center, so to speak. Those happen to be the most numerous of the possible numbers to examine (as SEJPM says, one doesn't have to attack the LARGER prime, just the smaller prime). If one uses a 300 and a 400 decimal digit prime, the path to them would be MUCH MUCH longer than the path from 1 decimal digit up to 300. So expecting you to do the cleverest thing mathematically would hurt very badly if you do the cleverest thing "humanly."

(That point applies to kasperd's smaller primes but more of them in the sense that it is, sort of, and obtusely, a way of ending up with primes to find that are a long way from the "balanced" primes SEJPM talks about. So it maybe would get an advantage.)

$\endgroup$
1
  • $\begingroup$ Welcome to Cryptography.SE. On our site, the answers are not written for the comments. What Kasperd is talking is so-called Multi-Prime-RSA. Your answer doesn't fit to that. $\endgroup$
    – kelalaka
    Apr 25, 2021 at 18:34

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.