7
$\begingroup$

I have implemented a key pair generation scheme for RSA algorithm. I have taken the length of private key exponent as RSA key size, but then I've got to know that RSA key size is the size of the modulus $n$. Is it wrong to take RSA key size as the size of the private key exponent?

To generate a private key of 1024 bits, I increase the size of private key exponent regardless the modulus $n$.

$\endgroup$
1
  • $\begingroup$ Note that I've seen many issues with regard to this, I've seen private key exponents that are two or even three bytes less than the size of the modulus (let alone bits) so please don't rely on the private exponent (or the secret S in ECC keys, as in your other question). $\endgroup$
    – Maarten Bodewes
    Commented Jun 2, 2014 at 19:47

2 Answers 2

11
$\begingroup$

No, the RSA key size is not the size of the private key exponent. It is customarily the number of bits in the public modulus (which is known as $N$). In other words, the key size is the integer $k$ such that $2^{k-1}\le N<2^k$.

In most implementations (and all implementations conforming to PKCS#1), a private exponent $d$ has size in bits at most the key size $k$, and typically is few bits smaller. Notice that the private exponent is not uniquely defined.

The smallest private exponent is $d=e^{-1}\bmod\lambda(N)$. It is always less than $\lambda(N)$, where $\lambda()$ is Carmichael's function, with $\lambda(N)=\operatorname{lcm}(p-1,q-1)$ when $N=p\cdot q$ with $p$ and $q$ distinct primes. The smallest private exponent always has size in bits strictly less than the key size $k$, and typically is a few bits smaller.

Sometime, a private exponent is computed as $d=e^{-1}\bmod\varphi(N)$, where $\varphi()$ is Euler's function, with $\varphi(N)=(p-1)\cdot(q-1)$ when $N=p\cdot q$ with $p$ and $q$ distinct primes. That particular $d$ has size in bits at most the key size $k$, often is a few bits smaller, and often is a few bits larger than the smallest private exponent.

Yet other methods to define a private exponent give no maximum for $d$, and only require that $d\equiv e^{-1}\pmod{\lambda(N)}$ (which is the necessary and sufficient condition for $d$ to work), or $d\equiv e^{-1}\pmod{\varphi(N)}$.

$\endgroup$
5
$\begingroup$

In addition to fgrieu's correct answer, I believe I want to emphasize something: increasing the size of the private exponent beyond the size of the modulus does absolutely nothing to improve security. If you want to increase the strength of the RSA key, you must increase the size of the moduus.

As fgrieu mentioned, for any $e$ there is a minimal $d = e^{-1} \bmod \lambda(N)$; there is nothing preventing you from using a larger $d$; that means extra work on your part, but any operation you do is precisely equivalent to the smaller $d$, and hence the extra work buys you absolutely nothing.

In addition, we commonly use the Chinese Remainder Thereom to optimize the RSA private operations; when doing this, we actually compute:

$$C_p = (P \bmod p) ^ {d\ \bmod\ p-1} \bmod p$$

$$C_q = (P \bmod q) ^ {d\ \bmod\ q-1} \bmod q$$

(and then combine $C_p$ and $C_q$ to form the actual ciphertext)

We work with $d\ \bmod\ p-1$ and $d\ \bmod\ q-1$; it turns out these values are identical for any "equivalent" private exponent, and so a larger-than-necessary private exponent doesn't actually do anything (either good or bad)

$\endgroup$
2
  • $\begingroup$ does increasing size of the prime numbers p and q increase the size of the modulus n? how can I generate a RSA key with key size of 15 360? $\endgroup$ Commented Jun 2, 2014 at 6:09
  • $\begingroup$ @user2934766: since $n = p \times q$, then increasing $p$ and $q$ will, of course, increase $n$. To pick an $n$ of 15360 bits, you need to select primes $p$ and $q$ of 7680 bits. That said, if you think you need a public key system that difficult to solve, you probably should look at an Elliptic Curve system $\endgroup$
    – poncho
    Commented Jun 2, 2014 at 12:21

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.