2
$\begingroup$

I am trying to implement the RSA cryptography algorithm using C language. I am not sure of the size that each operand should have. Let me explain:

RSA requires to generate two huge prime numbers p and q, and compute their product n = pq. Let's suppose that we want to use a key size = 2048 bits.

So we generate two 2048-bits prime numbers. Hence their product is 4096 bits-wide. But as we said, our key size is 2048 bits ! So should we use only the low-part of this product i.e the 2048 less significant bits of n ?

Or should we limit the range of p and q to 1024 bits i.e half of the key size ?

I don't know what is the impact of these two options on the safety of the system.

$\endgroup$
2
  • $\begingroup$ Note: in RSA, what's called "key size" is the number of bits of the public modulus $n$. That's the sum of the number of bits in the two (or more generally $k\ge2$) prime factors of $n$, within at most $1$ bit by default (more generally at most $k-1$ bit by default). The key itself is usually slightly larger, because it includes the public exponent $e$, and formatting. $\endgroup$
    – fgrieu
    Oct 14, 2023 at 8:20
  • $\begingroup$ Well, use GNU/GMP for your development... $\endgroup$
    – kelalaka
    Oct 15, 2023 at 20:40

1 Answer 1

2
$\begingroup$

Yes, you need two primes of half the key size, since multiplication of two $𝑛$-bit integers are $2𝑛$-bit.

It is possible to use more primes for multi-prime RSA, in which case the cumulative prime sizes make up the key size. This can speed up the algorithm in case the Chinese Remainder Theorem (CRT) is used and it will speed up the generation of the primes as well.

A number that is $p \cdot q \bmod 2^{2048}$ cannot guarantee to produce two large primes and therefore it may be easily factored, so it will break the standard assumptions of the RSA problem. As the security of RSA relies on the problem it cannot rely on the RSA problem and is not likely to be secure - if the inversion with the other key works at all.

$\endgroup$
4
  • $\begingroup$ Thank you ! For curiosity, why p.q mod 2^2048 would be easily factored if p and q are 2048-bits wide numbers instead of 1024 ? $\endgroup$
    – Wheatley
    Oct 12, 2023 at 10:00
  • $\begingroup$ Also, does the multi-prime version guarantee the same safety ? The more factors involved, the more easy is to break the encryption, right? $\endgroup$
    – Wheatley
    Oct 12, 2023 at 10:02
  • 3
    $\begingroup$ Multi prime RSA key generation. Multip-Prime RSA has a different RSA problem, though similar arguments can be made. We can say as long as one uses primes > 1024-bits and Shor's factoring algorithm is not built, it is secure. $p\cdot q \bmod2^{2048}$ is not guaranteed to be product of primes, even it may have many small primes. $\endgroup$
    – kelalaka
    Oct 12, 2023 at 10:19
  • $\begingroup$ I've removed the last part of the discussion, which is about handling large numbers in software. It is not on topic for this answer. $\endgroup$
    – Maarten Bodewes
    Oct 16, 2023 at 15:45

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.