0
$\begingroup$

I'm currently trying to create a lua script that can handle encrypting and decrypting using RSA, but when decrypting, the program takes an extremely long time, whilst when encrypting, the program is done within a matter of milliseconds.

Currently, I'm wondering:

  • How many bits should p and q be?
  • How big should pq be?
  • How big should the decryption exponent be?
  • How big should the decryption exponent be in comparison to the encryption exponent?

I can't seem to find any sources on the internet that give a simple, easy-to-understand answer as to the relations between encryption and decryption exponents.

Improve this question
$\endgroup$
5
  • $\begingroup$ In general $e = {3, 5, 17, 257,\text{ or }65537}$ is selected since it takes small amount of time to compute. The private key, however, on average has $bitsof(n)-1$ bits. That makes the difference. For the exact answer about $p$ and $q$, could you define the target security? Classic, Quantum, or classic combined quantum. $\endgroup$
    – kelalaka
    Mar 11, 2021 at 16:37
  • $\begingroup$ I think those answer your basic questions; Why should the RSA private exponent have the same size as the modulus?, RSA with small exponents? $\endgroup$
    – kelalaka
    Mar 11, 2021 at 16:42
  • 2
    $\begingroup$ Execution time of RSA should be roughly proportional to the bit size of $e$ for encryption, and of $d$ for decryption. If it gets proportional to $d$ (rather than to it's bit size), the implementation is overly naive, see this for a simple method without such deficiency. I recommend studying RSA with real-size numbers, thus a programming environment that can handle arbitrarily large integers natively. Python qualifies, but not any lua I used. Don't try to implement RSA for actual use. $\endgroup$
    – fgrieu ♦
    Mar 11, 2021 at 20:58
  • $\begingroup$ Also why are you using RSA encryption and decryption? If it's for learning about RSA in theory that's fine, but for learning about RSA in practical use consider studying signing and verification instead. They're vaguely related operations with one shared substep (modular exponentiation with the modulus being the product of two large primes). $\endgroup$
    – SAI Peregrinus
    Mar 11, 2021 at 21:07
  • $\begingroup$ Are you using modular exponentiation by squaring when decrypting? Even with very large primes, it should take only milliseconds to decrypt. If it is taking an extremely long time, your implementation of RSA is probably the culprit. $\endgroup$
    – John Coleman
    Mar 14, 2021 at 12:53

2 Answers 2

Reset to default
1
$\begingroup$

How many bits should p and q be?

Half (or near half) the size of the desired key size, which in turn depends on the security in bits that you try to achieve. You could look at the Lenstra equations, but non-mathematicians generally prefer keylength.com

How big should pq be?

p and q multiplied together is the modulus, and the size of the modulus defines the key size. It's of course the size of p and q added together, and p and q need to have near identical sizes (they are precisely half the size in practice).

How big should the decryption exponent be?

The security of RSA (only) requires the public exponent to be relatively prime with the modulus, so it is often pre-set to a smallish known prime, usually 0x010001 or the fifth prime of Fermat (also known as F4). This makes public key operations fast and makes recalculation of the modulus unlikely. However, it may have any size, from 2 bits (for value 3 usually) to the size of the modulus.

How big should the decryption exponent be in comparison to the encryption exponent?

They are largely unrelated, but both are practically bounded by the size of the modulus.

I can't seem to find any sources on the internet that give a simple, easy-to-understand answer as to the relations between encryption and decryption exponents.

That should make more sense now.

Improve this answer
$\endgroup$
1
$\begingroup$
  1. It depends on the level of security your application need. If the size of the modulus $n$ is $2048$ bits ($617$ decimal digits) then $p$ is a prime of $2048 / 2 = 1024$ bits and $q$ is a prime with almost the same size. Usually $q$ is slightly smaller than $p$ to avoid the Fermat factorization attack [1].
  2. Again, it depends on the level of security needed. A common modulus size is $2048$ bits.
  3. Big. The decrypt exponent $d$ has the same bit size of the modulus $n = pq$.
  4. Big. Typically the public exponent $e = 65537 = 2^{16} + 1$ for efficiency.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.