9

My private key (~/.ssh/id_rsa) is a 1766-byte file, but my public key (~/.ssh/id_rsa.pub) is only 396 bytes in length. Why the massive difference? Is it because the private key is encrypted using AES? Isn't AES ciphertext usually around the same length as the plaintext?

2 Answers 2

18

Your private key has more information than your public key does. Whereas the public key only conveys the encryption exponent (e) and the modulus (n), the private key additionally includes a decryption exponent (d) and the two prime factors (p and q) of the modulus. The private key essentially has a public key inside it.

[Encryption: ciphertext = message^e (mod n); Decryption: message = ciphertext^d (mod n)]

To see all of the data in your private key file:

$ openssl rsa -in id_rsa -text -noout

Edit: The private key file apparently doesn't have the encryption exponent, but it has exponents d_1 and d_2, where d_1 = d (mod p-1) and d_2 = d (mod q-1). These are used to speed up decryption -- you can split your decryption exponentiation into smaller parallel exponentiation calls, which ends up being faster than one big m=c^d (mod n) for big d and big n.

2

Unfortunately you did not specify in which format the keys are stored. I guess you're referring to OpenSSH key encoding. In this format the keys are stored in base64-encoded data blocks. Depending on the encoding when encrypting there is usually some sort of padding involved when encrypting data. So the resulting data is a multiple of the encryption block size.

OpenSSH keys can also include some sort of comments and additional properties inserted between the ---- BEGIN SSH2 [PUBLIC|PRIVATE] KEY ---- and -----END RSA [PUBLIC|PRIVATE] KEY----- markers. See RFC4716.

Moreover for the public key the modulus and public exponent are saved while for the private key the private exponent is saved. See RSA key-generation on Wikipedia for details on the mathematical base. There are many places on the web which describe the mathematical connection between these keys. Not sure if you need a copy of these explanation here.

Theoretically it's possible to calculate the private key from public key information but doing this is mathematically much more difficult than the other way around. Just regard the private key as the "source" which includes all variables and the public key as being a result of the calculation. It's easy to perform the calculation over and over again if you know all variables but knowing just the result it's difficult to get all source variables. This is the reason as well why it's sufficient for you to save the private key in a safe place. You can always use the private key to re-calculate the public key. But not the other way around - well, theoretically you can do this but depending on key length this might take many years ;).

2
  • Calculating the private key from the public key requires fast efficient factorisation - the lack of which is what the security of public key encryption (at least RSA) relies on.
    – Andrew
    May 8, 2011 at 23:07
  • This is correct. Find a fast factorization algorithm and basically you break the security of RSA encryption. Alternatively one could go for ECC (Elliptic Curve Cryptography) which is based on the concept of difficulties walking discrete logarithms. However if somebody finds an efficient solution to this problem...
    – SkyBeam
    May 9, 2011 at 7:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .