7
$\begingroup$

Let's assume we have a modulus in RSA with 2048 bits that was produced by multiplying two primes. What is the difference in digits in those two factors? For example, one prime is 1024 bits long and the second one has 1024 as well. Or one is 900 bits and the second one 1148 bits?

Are there any limits for primes that could be used in RSA or could it work with two primes where one prime consists of 1 bit and the other is a 2048-bit prime?

$\endgroup$
6
  • 4
    $\begingroup$ I very much depends on what security recommendation was followed when generating the 2048-bit modulus. If that's FIPS 186-4 (a very common choice), then the factors $p$ and $q$ must each be exactly 1024-bit (further, each factor must be at least $2^{1023.5}$). $\endgroup$
    – fgrieu
    Commented Feb 17, 2015 at 7:35
  • 3
    $\begingroup$ Good luck implementing RSA with $p =1$... $\endgroup$
    – user4686
    Commented Feb 17, 2015 at 7:54
  • $\begingroup$ what is estimated primes quantity of 1024 bits are there? $\endgroup$
    – user23124
    Commented Feb 22, 2015 at 17:41
  • 1
    $\begingroup$ A common assumption is equal length, $q<p<2q$ or at most a length difference of $1$. But that is not really a question about security, it is more about the policy for the usage of RSA. Allowing uneven factors is a potential security risk, because "small factors" can be found more easily. In general, the factoring problem scales with the smallest prime factor, not with the total length. Multiplying $2^{1000000}$ to any RSA modulus does not make it harder to factor. $\endgroup$
    – tylo
    Commented Mar 19, 2015 at 15:59
  • $\begingroup$ In order to get an answer to this, head there. $\endgroup$
    – fgrieu
    Commented Mar 22, 2015 at 10:41

3 Answers 3

7
$\begingroup$

As far as the standard (PKCS#1) is concerned, the primes need not have the same length; the smallest should not be "too small" to avoid getting in range of the ECM factorization method, but there is still a lot of margin here.

However, some implementations can be more limited. For instance, Windows' implementation of RSA (in CryptoAPI) assumes that, for a 2048-bit modulus, both primes have length exactly 1024 bits, no more. It is also commonplace in hardware-assisted implementations (think smart card) to enforce such a constraint, because they do computations modulo p and modulo q (with the Chinese Remainder Theorem) and thus need circuitry able to process numbers up to the size of the larger of the two primes -- they thus have a vested interest in making the larger prime as small as possible, leading to both primes having the same length.

RSA supports moduli that are a product of more than two primes, but, there again, it must not be overdone, and support for the encoding of private keys with more than two primes is not widespread. This does not matter when private keys are not exported. When you use the public key, you don't know, and do not have to know, the number and sizes of the prime factors.

$\endgroup$
6
$\begingroup$

When you multiply an $n$-bit integer by an $m$-bit integer, the product is an $(m+n-\epsilon)$-bit integer, with $\epsilon \leq 1$.

For RSA the security recommendations specify that secret factors of the public modulus must be of approximately the same size. If the difference in the number of bits is modest (less than a machine granularity) it could be approved.

There is also another suggestion from Shamir about generation of RSA keys for paranoid, which recommends for example a prime $p$ of say $1000$ bits and the other prime $q$ of $5000$ bits.

$\endgroup$
0
2
$\begingroup$

To get a sense for common prime lengths in RSA, you can run

openssl genpkey -algorithm RSA -out private.pem

to generate a private RSA key. Then, have a look at the primes with

openssl rsa -in private.pem -text -noout

I'm using OpenSSL 1.1.1m and both primes are 2048-bit. The public modulus has 4096 bits.

$\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.