Let's assume we have an RSA 2048 that was produced by two primes multiplication. What is the digit's difference in those 2 factors? For example one prime is 1024 digits and second one 1024 or, one is 900 and second one 1148? Are there any limits for primes that could be used in RSA or it could be "1" and a 2048 bit prime?

  • 3
    $\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 Feb 17 '15 at 7:35
  • 2
    $\begingroup$ Good luck implementing RSA with $p =1$... $\endgroup$ – user4686 Feb 17 '15 at 7:54
  • $\begingroup$ what is estimated primes quantity of 1024 bits are there? $\endgroup$ – user23124 Feb 22 '15 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 Mar 19 '15 at 15:59
  • $\begingroup$ In order to get an answer to this, head there. $\endgroup$ – fgrieu Mar 22 '15 at 10:41

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.


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.


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.