Encoding SSH RSA public key

[Daniel Kahn Gillmor]

On Wed 2008-08-13 10:54:02 -0400, robert wrote:

> There must be options (optional), bits, e, n and comments (optional),
> but how are these represented before encoding? Are each of these data
> encoded to base64 separately and then concatenated? What exactly is
> encoded?
>
> Could anyone describe me the algorithm for obtaining the base64 string?
> I couldn't find it anywhere.

The format for the base64-encded data (the unreadable stuff in the
middle of the line) appears to be:

A series of length-prefixed bitstrings, where the length for each
bitstring is encoded as a network-order, 32-bit unsigned integer
representing the number of bytes in the following bitstring.

The first bitstring indicates the type of the key.  This can be used
to determine the nature of the bitstrings which follow.  The type is
represented by a 7-byte string ("ssh-rsa" or "ssh-dss"), so the first
4 bytes are 0x00,0x00,0x00,0x07 (this indicates the length of the
type string).

For RSA keys, the exponent follows next as a multi-precision integer
(MPI), and then the modulus (also an MPI).

So for example, for a 2048-bit key, you can unpack it this way:

[0 dkg at squeak ~]$ < ./.example/id_rsa.pub cut -f2 -d\  | base64 -d | hd | head -n2
00000000  00 00 00 07 73 73 68 2d  72 73 61 00 00 00 03 01  |....ssh-rsa.....|
00000010  00 01 00 00 01 01 00 c4  68 99 07 36 4f d4 7a 35  |........h..6O.z5|
[0 dkg at squeak ~]$ 

the example above uses a 3-byte exponent of 0x10001 (65537), followed
by a 257(==0x101)-byte modulus, which is the rest of the key.

Be careful that your MPIs all have the first bit set to 0, though!
OpenSSH appears to treat the MPIs as a two's-complement signed
representation, so if your first bit is a 1, ssh will think you're
trying to provide a negative value.  If your calculations produce a
number with the high bit set to 1, just increase the length by another
byte and pad the beginning with 0x00 to keep it positive.  (this is
why the modulus above is 257 bytes starting with 0x00,0xc4 instead of
256 starting with 0xc4,0x68).

Hope this is helpful,

     --dkg
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 826 bytes
Desc: not available
Url : http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20080813/a28882bf/attachment-0001.bin