10
$\begingroup$

Suggested definition

A positive integer is a safe RSA modulus if, after removing all its prime factors less than 512 bits, it is composite and has size at least 2048 bits.

Discussion

I want to build the smallest-possible safe RSA modulus without a trusted party. (The use case is for an RSA-based verifiable delay function to be used on a blockchain.) The strategy is to randomly sample several random numbers $N_1, ..., N_k$ and multiply them together. Each $N_i$ has some probability $p$ of being a safe RSA modulus so the product $N_1...N_k$ has probability $1 - (1-p)^k$ of being safe.

The above strategy of multiplying randomly chosen integers was pioneered by Thomas Sanders in the context of RSA accumulators. He used a stricter definition of a safe RSA modulus which only looked at having at least two primes above a minimum bit size. The reasoning behind suggesting this less strict definition of a safe RSA modulus is to maximise the probability $p$ so as to minimise the size of the final RSA modulus.

The "512 bits" parameter was chosen (conservatively) to protect against the ECM which has found primes of size up to 273 bits. The "2048 bits" parameter was chosen (conservatively) to protect against the GNSF which factored numbers up to 768 bits.

Is the above definition of a safe RSA modulus actually safe to use in production?

$\endgroup$
2
  • 2
    $\begingroup$ A number with more than 2 prime factors is not an "RSA modulus" - in the general understanding of the term. Also, 2048 bit is not a conservative choice any more - it is the minimum of the latest BSI recommendation and it is not enough for the near-term recommendation of ECRYPT-CSA, which is 3K bit. See current recommendations on keylength.com $\endgroup$
    – tylo
    Jul 31, 2018 at 17:30
  • 7
    $\begingroup$ @tylo: actually, more than 2 prime factors is called "multiprime RSA", while not generally used, the concept is out there, and in fact, PKCS #1 has hooks for how to represent the private key in that case... $\endgroup$
    – poncho
    Jul 31, 2018 at 19:33

2 Answers 2

10
$\begingroup$

Overall I find the proposed definition and methods satisfactory in principle, barring quantum computers usable for factorization; but the 512-bit limit for factor, and to a lesser degree the 2048-bit unfactored limit, are not conservative.


Unfactored limit

As noted in comment, for long term security or/and convincing security authorities, it's probably best to up the 2048-bit size to 3072-bit, or more. France's ANSSI changed mind and went from year 2020 to 2030 for the limit beyond which 2048-bit is no longer enough, but other authorities stick to earlier dates.

Difficulty of factoring $n$ by GNFS grows with $L_n\left[\frac1 3,\sqrt[3]{\frac{64}9}\right]$ in L-notation, and (ignoring the hidden $o(1)$ term) that tells 2048-bit is roughly 40 Binary Orders of Magnitude (BOM) harder than the RSA-768 landmark of 2009. This is comfortable for now, but not huge. 3072-bit gives 62 BOM, that is huge.


Small prime limit

Difficulty of factoring by ECM grows roughly as $L_p\left[\sqrt2,\frac1 2\right]$ where $p$ is the factor pulled. Neglecting the $o(1)$, that tells a 512-bit $p$ is roughly 28 BOM harder to pull by ECM than the 273-bit record of 2013. That does not look like a comfortable margin to me: Ryan Propper's log and account mention relatively modest resources compared to the RSA-768 effort:

For this job, I did about 5,000 curves, spanning about 10 days, on the FarmShare compute cluster at Stanford. I guess this was quite the lucky find. :)

and I do not see that the latest theoretical advances (Edwards curves) have been used. Consider more effort, dedicated ASICs, Moore's law at 1 bit per year, and the 28 BOM is about gone. I would not go below 640-bit (>41 BOM) or 704-bit $p$ (>47 BOM) with 2048-bit $n$. 832-bit $p$ gives 59 BOM, that's large.

$\endgroup$
1
  • $\begingroup$ Are the $L_n\left[\frac1 3,\sqrt[3]{\frac{64}9}\right]$ and $L_p\left[\frac1 2,\sqrt2\right]$ difficulty growth rates proven lower bounds? Would you mind including sources for those? $\endgroup$
    – Randomblue
    Aug 3, 2018 at 8:23
1
$\begingroup$

Note that if somebody finds a small (less than 512-bit in your case) prime factor $p$ of your modulus, then he can decrypt any ciphertext mod $p$. So in general it is not safe but it may be ok in your scenario.

$\endgroup$
1
  • 1
    $\begingroup$ With OAEP or similar Full Domain Hashing, getting the padded ciphertext modulo $p$ is not that helpful. $\endgroup$
    – fgrieu
    Aug 3, 2018 at 15:43

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.