Why do my two ssh public keys have the same beginning?

I was updating the authorized_keys file on my server with the public key for the new laptop I got and I was surprised to discover that the two public keys began the same:

# key 1
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQ....
#
# key 2
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQ....

What's the story on AAAAB3... etc? With some searching online, I see that others keys start the same, too. Does it explain the algorithm or version or something?

Solution 1:

This is actually a header that defines what kind of key this is. If you check out the Public Key Algorithm section of RFC 4253 we can see that for RSA keys

The "ssh-rsa" key format has the following specific encoding:

 string    "ssh-rsa"
 mpint     e
 mpint     n

Here the 'e' and 'n' parameters form the signature key blob.

In fact, if you Base64 decode the string "B3NzaC1yc2E" you will see it translates into ASCII as "ssh-rsa". Presumably the "AAAA" represents some kind of header so the application can know where exactly in the data stream to start processing the key.

Solution 2:

The SSH public key format is documented in RFC 4253, and summarized somewhat here. The PEM encoded data consists of a number of (length,data) pairs, and the first pair encodes the algorithm name, which is going to be something like ssh-rsa or ssh-dsa.

This means that the initial part of the public key data for all ssh keys is going to be similar.

Solution 3:

I did an overkill deep-dive into the format after following Scott's links for funsies. TLDR:

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQ...
       |  "ssh-rsa"   |exponent|   modulus

ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIFKy...
           |   "ssh-ed25519"   |   32 byte public key

RFC4231 specifies the two data types used:

• string: Arbitrary length binary string. Strings are allowed to contain arbitrary binary data, including null characters and 8-bit characters.

• mpint: Represents multiple precision integers in two's complement format, stored as a string, 8 bits per byte, MSB first. [...]

Both datatypes start with a uint32 defining the length of data to come. Because that's usually overkill and you end up with lots of 0's (e.g. "abc" is stored as \x00\x00\x00\x03abc...), they end up as runs of As in the base64-encoded payload (...AAAAA2FiYwo)

RFC4253 sec 6.6 says the key is encoded as:

The "ssh-rsa" key format has the following specific encoding:

string    "ssh-rsa"
mpint     e
mpint     n

Here the 'e' and 'n' parameters form the signature key blob. [Ed: but the blob also seems to contain the string "ssh-rsa" as well...]

The resulting signature is encoded as follows:

string    "ssh-rsa"
string    rsa_signature_blob

The value for 'rsa_signature_blob' is encoded as a string containing s [Ed: don't know what s is.] (which is an integer, without lengths or padding, unsigned, and in network byte order).

The more modern Ed25519 and Ed448 keys are defined in RFC-8709 and have two fields:

• the constant string "ssh-ed25519" (or "ssh-ed448")
• the 32-byte (or 57-byte) public key as a string

"ssh-rsa"

The string ssh-rsa is converted to \x00\x00\x00\x07ssh-rsa, which then encodes to AAAAB3NzaC1yc2E=, so all ssh-rsa keys should start with that.

e, the public exponent

Usually something like 3, 17, 257, 65537. Those numbers get encoded as below (with the trailing offset from above)

• 3 → '\x00\x00\x00\x01\x03' → AAAABAw
• 17 → '\x00\x00\x00\x01\x11' → AAAABEQ
• 257 → '\x00\x00\x00\x02\x01\x01' → AAAACAQE
• 65537/0x10001 → '\x00\x00\x00\x03\x01\x00\x01' → AAAADAQAB

So, if you see "BAw", your exponent was 3, or "DAQAB" = 65537

n, the modulus (product of your two secret primes, factor this!)

AAABAQ after the above means that your key length is 2048 bits (and that your exponent was like DAQAB because of base64 padding). The entire rest of the base64 stuff is the exponent, there's nothing after.

Other modulus prefixes that may be common:

• AAAAg 1024 bits, e = 0x10001
• AAAQI: 2048 bits, e = 3