2

As an example, I generated a 256 bit key pair. The private key (when saved to a file by puttygen) is: AAAAIGZcM73lV3Uk/psErZAYA0F+4xK78FtFoVi2fdypv92tAAAAEQDdOhyFJ6iV FSKDgjpj8+bRAAAAEQC2nAZD6DurGlj+DlPuB7tNAAAAEQCbHQFLFNR/URs4eu0o ZfPE

This is 132 ascii characters. Assuming only 6 bits per character (if the character set used is only 64 characters, that would make 132*6 = 792 bits, which is way more than the 256 bits that are supposed to be in the key.

So why the extra characters? Thanks.

2
  • You've asked the question backwards. Instead, you need to think, "how many characters does it take to represent 256 bits?" 256 log(2) = n log(10)
    – schroeder
    Jan 28, 2015 at 1:29
  • 1
    Sorry . I didnt get your answer.
    – user45475
    Jan 28, 2015 at 2:18

1 Answer 1

4

The PuTTY format for an RSA SSH2 private key blob is dlen||d||plen||p||qlen||q||ulen||iqmp. The values dlen, plen, qlen, and ulen are the length in bytes of d, p, q, and iqmp, respectively; the length is expressed as an int, so each of the four length markers itself takes up 4 bytes. The four key elements stored are respectively the decryption key d, the prime factors p and q, and the value of q^(-1) mod p -- the last 3 aren't technically needed, but they significantly speed up RSA operations.

In your key, d is 256 bits (32 bytes), p and q are each 17 bytes, and iqmp is also 17 bytes. The 17 byte lengths of p, q, and iqmp are artifacts of the somewhat odd rounding method used; to compute bitlen(p)/8 rounded up to the nearest byte, the PuTTY source computes (bitlen(p)+8)/8. If p is exactly 128 bits long, then (128+8)/8=17 is the value of plen, even though p fits just fine into 16 bytes. Likewise for q and iqmp - the values are all actually 128 bits exactly, but the odd rounding turns them into 17-byte values. There's no security consequence either way, as far as I know; it would have made more sense to add 7 bits and integer divide by 8, but they made it the way they made it, and can't change it now.

Anyway, that's the components of the blob: 4 bytes for dlen, 32 for d, 4 for plen, 17 for p, 4 for qlen, 17 for q, 4 for ulen, 17 for iqmp. Add them up, you get 99 bytes, or 792 bits. For convenience, this is then encoded with Base64, which uses a subset of 64 characters that are particularly "safe" -- "safe" here meaning that they can be processed using systems designed to process text (notably email) without any major issues -- no trouble with special characters, no trouble with programs that only support ASCII characters and don't preserve the 8th bit of the byte, etc. That's how the message goes from 792 bits to 132 characters.

0

You must log in to answer this question.

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