43

I'm having a problem understanding the size of an RSA public key and its private key pair.

I saw different key sizes for RSA algorithm (512, 1024,... for example), but is this the length of public key or the length of private key or are both equal in length?

I already searched for it, but:

  1. In this question it is mentioned that both private and public keys for RSA algorithm have equal length. But:
  2. In this question it is mentioned that they have different lengths!

Both answers are accepted. Are they equal or not in length?

Moreover my Java Card applet that generate RSA key pairs, always return pubic key and private key of equal length. The online tools for generating RSA key pairs have different length output!

Examples:

Online tool 1:

enter image description here

Online tool 2:

enter image description here

TheGoodUser
  • 799
  • 1
  • 6
  • 13
  • With RSA, the pubkey is usually a lot shorter. See this answer: https://stackoverflow.com/questions/19343022/can-a-public-key-have-a-different-length-encryption-than-the-private-key#answer-19345083 – StackzOfZtuff May 27 '15 at 10:02
  • 1
    @StackzOfZtuff Thank you. I was added that link to my question already! did you read the question carefully? :) – TheGoodUser May 27 '15 at 10:09
  • Oh sorry. I meant to link to CodesInChaos' answer there. – StackzOfZtuff May 27 '15 at 10:33

2 Answers2

39

> I saw different key sizes for RSA algorithm (512, 1024,... [bits] for example) but, is this the length of public key or the length of private key or both are equal in length?

It's the length of the modulus used to compute the RSA key pair. The public key is made of modulus and public exponent, while the private key is made of modulus and private exponent.

> but the online tools for generating RSA key pairs have different lengths output!

The first picture shows public and private key in PEM format, encoded in Base64 (and not modulus and exponents of the key, which instead are shown in the second picture).

The content of the RSA private key is as follows:

-----BEGIN RSA PRIVATE KEY-----
RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}
-----END RSA PRIVATE KEY-----

while a RSA public key contains only the following data:

-----BEGIN RSA PUBLIC KEY-----
RSAPublicKey ::= SEQUENCE {
    modulus           INTEGER,  -- n
    publicExponent    INTEGER   -- e
}
-----END RSA PUBLIC KEY-----

and this explains why the private key block is larger.

Now, why does the private key contain so much data? After all, only the modulus n and the private exponent d are needed. The reason all the other stuff is precomputed and included in the private key block is to speed up decryption using the Chinese Remainder Algorithm. (Kudos to @dbernard for pointing this out in the comments.)

Note that a more standard format for non-RSA public keys is

-----BEGIN PUBLIC KEY-----
PublicKeyInfo ::= SEQUENCE {
  algorithm       AlgorithmIdentifier,
  PublicKey       BIT STRING
}
AlgorithmIdentifier ::= SEQUENCE {
  algorithm       OBJECT IDENTIFIER,
  parameters      ANY DEFINED BY algorithm OPTIONAL
}
-----END PUBLIC KEY-----

More info here.

BTW, since you just posted a screenshot of the private key I strongly hope it was just for tests :)

dr_
  • 5,060
  • 4
  • 19
  • 30
  • Those are two different test RSA pairs. I didn't compare screen shots with each other, I compare each private key with its public key in the same screen shot. As you see for the hex form one,both seems have equal length, while for the base64 form, the private key is larger than its public key. – TheGoodUser May 27 '15 at 12:11
  • Ah ok, I see. Sorry for the misunderstanding. I corrected my answer and added more info. – dr_ May 27 '15 at 13:43
  • 8
    For people (like me) wondering why the private key has a lot more stuff than public key even though only the **modulus** and **privateExponent** are needed, that's because they are used to **speed up** decryption using the [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm) – dbernard May 15 '18 at 13:08
  • usually, how long is public and private keys? – Govinda Sakhare Apr 11 '20 at 08:22
17

A RSA public key consists in several (big) integer values, and a RSA private key consists in also some integer values. Though the contents differ, a RSA public key and the corresponding RSA private key share a common mathematical structure, and, in particular, both include a specific value called the modulus. The public and private key of a given pair necessarily work over the same modulus value, otherwise RSA does not work (what it encrypted with a public key must be decrypted with the corresponding private key).

Traditionally, the "length" of a RSA key is the length, in bits, of the modulus. When a RSA key is said to have length "2048", it really means that the modulus value lies between 22047 and 22048. Since the public and private key of a given pair share the same modulus, they also have, by definition, the same "length".

However, both the public and private key contain other values, besides to modulus. So when you encode a public or private key into bytes (so that they may be stored in a file), you will need more than just the bytes for the modulus. A 2048-bit modulus can theoretically fit over exactly 256 bytes (since 256*8 = 2048) but you need more bytes to encode the other values.

Also, a RSA public key consists in the modulus and another value called the "public exponent", which is usually quite short. So, a public key will need relatively few extra bytes for encoding; the modulus is the biggest chunk in the public key. This is not so for the private key, which includes the modulus and the public exponent (like the public key) but also the "private exponent" (a number roughly as big as the modulus) and five other values whose size is roughly half of that of the modulus. The consequence is that an encoded private key is expected to be about five times larger (when counted in bytes) than the corresponding encoded public key.

These are just encoding considerations; the "RSA key length" (as in "a 2048-bit key") relates to the numerical value of the modulus, not the encoded length of the whole paraphernalia of factors and reduced exponents and CRT coefficients.

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949