5
$\begingroup$

My guess is:

  1. Known attack algorithms only work on 2 primes factorization, they don't work on 3+ RSA primes.
  2. More than 3 primes is cpu waste time, better is to increase key length. So 3 primes will be the optimal number.

Example of my program (open source) generating a 30k bits RSA key.:

  • Enter rsa NUMBER of primes: 3
  • Enter rsa (3 primes) key length in bits (0 = defaut = 4096): 30000
  • RSA (N primes) GMP Encrypt/Decrypt OK- bits size: 30000 - Elapsed Time: 517.589 sec
  • key saved as: MY_RSA3KEY_30000_2023-04-08_15:24:55 in .../rsa_my_private.db
$\endgroup$
1

2 Answers 2

10
$\begingroup$
  1. It is not true that existing factoring methods do not work on 3+ prime RSA. Pretty much all of them do. Most of the methods do not improve when the number of factors increases; in particular the number field sieve's complexity does not decrease when we increase the number of prime factors (the GNFS is the best known classical factoring algorithm and is used to estimate key sizes). A notable exception is the elliptic curve method, whose complexity rests on the size of the second largest prime factor of the modulus.

  2. There are some modest efficiencies in terms of key generation and decryption when we use more than two prime factors, though these hit diminishing returns quite quickly. For most applications, it's not considered that big of a benefit (though the benefits do increase with the number of prime factors).

If one assumes that the current known factoring methods are the best and one is determined to maximise the number of prime factors for a given level of security, we can balance the cost of the NFS with the ECM to optimise the size of primes: $$\sqrt{2\log p\log\log p}\approx\root3\of{\frac {64}9\log N(\log\log N)^2}$$ which tells us to take $$\log p\approx 1.849(\log N)^{2/3}(\log\log N)^{1/3}.$$ This would give an approximate optimum number of prime factors $$\frac{\log N}{\log p}\approx0.541\left(\frac{\log N}{\log\log N}\right)^{1/3}.$$ It's not advisable to directly use log-asymptotic estimates such as this, but it suggests that 3 prime factors might be a reasonable choice for moduli of 2048-4096 bits.

ETA: For your example for a 30,000-bit number (which feels extreme -- this is even worse bandwidth than Kyber-1024 and almost as bad as a Dilithium-5 signature) it seems that roughly 6 primes would be appropriate.

$\endgroup$
3
  • 4
    $\begingroup$ Except that we need larger key size, not much has changed since 1996: RSA Moduli Should Have 3 Prime Factors, by Captain Nemo alias Richard Schroeppel. The idea was known well before in some circles. It remains open who first published that fact. $\endgroup$
    – fgrieu
    Apr 9, 2023 at 7:13
  • 1
    $\begingroup$ @fgrieu I was not familiar with that paper, but broadly agree with it. Schroeppel recommends 4 primes for moduli of 3200-bits, which I think is also plausible. $\endgroup$
    – Daniel S
    Apr 9, 2023 at 7:20
  • 1
    $\begingroup$ It's not surprising you did not know this paper: it was not published AFAIK. I only recently managed to buy a copy from USPTO. Then things accelerated and Samuel Neves found the true author. $\endgroup$
    – fgrieu
    Apr 9, 2023 at 7:32
2
$\begingroup$

When designing a crypto system we want the legitimate user to have a huge advantage over the attacker. We can increase key size as much as we want but we want legitimate users to be efficient.

In RSA the public key operation ia typically fast due to small $e$ and takes time proportional to the size of $n$.

private key operations are slower, but by using CRT we can do operations on each prime separately.

There are several possible attacks on RSA some require time proportional to smallest factor but the current best attack is NFS which though lacks rigorous analysis requires sub exponential time based on total key length.

If we focus on this attack, multi prime RSA could give us a slightly better trade off between time for running NFS and time for legitimate user to use private key.

With quantom attacks there is a proposal to use multi prime RSA to maintain a significant polynomial advantage over an adversary with a quantom computer.

As to your guess: Multi prime RSA is well known, not as well as regular RSA but plenty. Most attacks work fine against it amd specifically NFS.

I see no reason to prefer 3 primes. The number of primes does not directly make things more or less efficient as I describe cost of operations above. There is an advantage to as few primes as possible to increase the size smallest factor relative to key size. There are advantages to many primes to speed up operations with private key relative to key size.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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