Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 exponenet?

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

Thank You!

share|improve this question

migrated from stackoverflow.com May 27 at 15:34

This question came from our site for professional and enthusiast programmers.

1  
This question appears to be off-topic because it is about cryptography and doesn't include a programming problem. –  Duncan May 27 at 9:54
    
Flagged for transfer to crypto. Answering this for retrieving the key size is pretty obvious. I don't see how you can increase the private exponent size without changing the modulus size during generation, but I guess the asker will have to explain. –  owlstead May 27 at 12:11
    
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). –  owlstead Jun 2 at 19:47

2 Answers 2

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 Charmichael'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)}$.

share|improve this answer

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)

share|improve this answer
    
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? –  user2934766 Jun 2 at 6:09
    
@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 –  poncho Jun 2 at 12:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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