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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.