I'm trying to figure out how it is composed the RSA key. Follow what I know :

  • For a RSA 2048, 2048 is the bit length of the module.

  • The public key is composed by $(e,M)$ when $e$ is the public exponent and $M$ is the module.

  • The private key is composed by $(d,M)$ when $d$ is the private exponent and $M$ is the module.

Now, I tryed to find info about the standard bit lentght of the exponent without lack. Does anyone have info ? I need to define the max value that $d$ and $e$ can reach. I think that it useless to have the same exponent bit lenght of the module. Is it right ?

  • $\begingroup$ It should be noted that, if an arbitrary message of size of n bits is to be processed by RSA, the modulus M must be chosen to be greater than 2**n. $\endgroup$ – Mok-Kong Shen Feb 24 '15 at 11:30
  • $\begingroup$ Well, I think that I could also divide the message to get more than one crypted messages. $\endgroup$ – haster8558 Feb 24 '15 at 11:40
  • $\begingroup$ @Mok-Kong Shen: $2^n<M$ where $n$ is the message size in bits, and $M$ the public modulus, applies to Textbook RSA, which is insecure in many use cases, and in good practice mostly used for largely random messages. It does NOT apply to secure versions of RSA used in practice, like RSAES-PKCS1-V1_5 or RSAES-OAEP, which have a significantly smaller message capacity $n$ for a given modulus $M$. And that does not apply to hybrid encryption (as used in practice for any sizable message), where the message size $n$ is practically unconstrained. $\endgroup$ – fgrieu Feb 24 '15 at 11:43
  • $\begingroup$ @haster8558: No, you should not "divide the message to get more than one crypted messages", see e.g. this. Use hybrid encryption. $\endgroup$ – fgrieu Feb 24 '15 at 11:45
  • 1
    $\begingroup$ @fgrieu I know that, for example, ssh work with hybrid encryption, RSA for key exchange and AES for communication. But actually I don't need to encrypt/decrypt more than plain/cypher message. I need only a system to authenticate ( I could use HMAC, but it doesn't like to my supervisors ), so there isn't the need to use a hybrid encryption. Thanks for the help $\endgroup$ – haster8558 Feb 24 '15 at 11:54

Generally speaking, the bit length of the exponents are the same as the modulus. Depending on the implementation, there may also be some extra data in the public/private key structure.

Here is a good discussion on the concept of key length as it relates to the public/private values: Private key length bytes

  • $\begingroup$ @Haster8558: Beware, this answer is wrong in practice: in most actual use of RSA, the public exponent is small; most often $65537$, or $3$, $5$, $17$, or within some limit; I have seen such limits of $2^{32}$, $2^{64}$, $2^{128}$, $2^{256}$. In particular the later limit is enforced in FIPS 186-4, thus many HSMs. $\endgroup$ – fgrieu Feb 24 '15 at 11:32
  • 1
    $\begingroup$ Ok, the public exponent is usually small, but I need to decrypt too, so I need that exponent of my VHDL module is big enough ( same core for decrypt and encrypt ). $\endgroup$ – haster8558 Feb 24 '15 at 11:38
  • $\begingroup$ @haster8558: Right for private key in $(M,d)$ form. But if you care for speed or power, you'll want to support RSA with CRT when doing the part (use of private key) that requires large exponents; the potential savings approaches a factor of 4 with common RSA keys (the aforementioned FIPS 186-4). $\;$ If you care for security, you'll have to study if your threat model requires protection against at least fault attacks, timing attacks, power analysis and other variants of side-channel attacks. $\endgroup$ – fgrieu Feb 24 '15 at 11:49
  • 1
    $\begingroup$ @fgrieu The only problem with Chinese reminder algo is that I have to save also $p$ and $q$ and at the end I need to perform an addition. I don't know the effect on area occupation. I need to check the free area in FPGA $\endgroup$ – haster8558 Feb 24 '15 at 12:05
  • 1
    $\begingroup$ @haster8558: In many hardware implementations of RSA using CRT, the recombination after exponentiation is performed in software, and still does not dominate the execution time. CRT may actually significantly reduce silicon requirement for a given public modulus size, since all quantities manipulated in the time-critical part are only half as wide as in regular RSA (assuming balanced primes as in FIPS 186-4); that will be the case if there's hardware to make modular multiplication over the full modulus width. $\;$ Another design choice will be using Montgomery arithmetic, or regular one. $\endgroup$ – fgrieu Feb 24 '15 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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