Why do all SSH-RSA Keys begin with "AAAAB3NzaC1yc"? My friend and I have been generating a few SSH2 RSA keys and noticed all the public keys begin with AAAAB3NzaC1yc, with the similarity extending to AAAAB3NzaC1yc2EAAAABIwAAAQEA between two keys generated on the same machine in two successive attempts (googling AAAAB3Nz ends up getting a few hits as well).
Is this normal or are we doing something wrong while generating, such as suffering from insufficient entropy?
The public key blob doesn't consist of just the numbers that make up the public key: it begins with a header that says “this is an SSH public key”. The repeated prefix encodes this header.

RFC 4254 specifies the encoding of public key in SSH key format. 


  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.


The string is encoded as 32-bit big endian length followed by the literal string:

0,0,0,7,'s','s','h','-','r','s','a'


Encoding this sequence of bytes in Base64 gives:

AAAAB3NzaC1yc2E


The public exponent is also usually the same, so the common prefix is even longer. The bulk of the key is the public modulus, and that is completely different in different keys.