Why aren't 4096-bit RSA PGP key blocks $\lceil\frac{4096}{6}\rceil=683$ base64 characters long?

If a 4096-bit RSA PGP key is considered sufficiently long for most purposes, why are so many key blocks around 3000 base64 characters in length? Why aren't $\lceil\frac{4096}{6}\rceil=683$ base64 characters enough?

• Are you talking about public or private keys? – CodesInChaos Apr 26 '18 at 18:36
• See RFC 4880 for the details of what they hold. It's not a particularly difficult read. – Squeamish Ossifrage Apr 26 '18 at 18:38

The key size is the same as the modulus size. By doing some very tricky calculations called the Lenstra equations you can retrieve the key strength from the key size.

However, the key size therefore is not the size of an encoded key. A private key will probably also store the private exponent, the CRT parameters (needed to speed up the RSA calculations) and likely also the public exponent. The private exponent is the same size of the modulus (or slightly smaller). The CRT parameters are generally about half the size of the modulus each.

However, you are likely referring to a public key, as those are the ones that need to be distributed. The public key itself only contains the modulus and the public exponent, which is generally just three bytes. However, as you can see in this answer there is a lot of information stored with the public key: PGP version, creation time, user ID and subkeys to name just a few.

The PGP public key structure can therefore be better compared to a certificate (without the signature or issuer information due to the different way that public keys are trusted) than just a public key.

Your base 64 calculations are about correct, but the input is not just the modulus.

• PGP privatekey format for RSA stores n,e,d,p,q and $p^{-1}\mod q-1$ (the dual of PKCS1's $q^{-1}\mod p-1$) but NOT $d\mod p-1$ and $d\mod q-1$ which must be (and easily can be) recalculated for CRT. (Mathjax in comments sure looks ugly, at least in my browser.) – dave_thompson_085 Apr 27 '18 at 2:56

Base64 uses $64=2^6$ characters, and hence can encode at most 6 bits per character. Hence, the correct calculation would be at least $\frac{4096}{6} = 682 \frac{2}{3}$ characters (or 683, we really can't have fractional characters)

As far as why PGP keys are longer than that, well, that's because they're carrying around a lot more information than just the raw RSA key.

• Thanks for this correction. I will amend the question accordingly. What other information do they carry? – user58355 Apr 26 '18 at 18:06