2
$\begingroup$

I am working in a very bandwidth restricted environment where I from time to time have the need to distribute public keys. The distribution happens in bit format, so there is no need for encoding, at best I would like all my data "raw".

It is my understanding that the public key, in compressed form, takes up the space of the curve size+1, e.g. 160 bit curve gives 161 bit public key. However, the output from OpenSSL gives me a much larger key size, e.g. 904 bits for the secp160r1 curve. I reckon there must be a lot of metadata involved.

Edit: I removed the "--- Public key starts here ---" etc and that almost cut the file in half ahem. But still there are 60 bytes/480 bits, a lot more than what I would think of as necessary.

Can I somehow reduce this size, getting rid of metadata? For example extract the key components of the signature and reassemble it in a compatible format on the receiver side? I assume DER encoding also adds overhead, but hardly this much?

Here arethe commands I use, in Cygwin:

$ openssl ecparam -out private.pem -name secp160k1 -genkey
$ openssl ec -in private.pem -pubout -conv_form compressed -out public.pem
| improve this question | |
$\endgroup$
  • $\begingroup$ (These 2 comments don't help answer your question, but may be useful in your environment.) ​ This paper shows how to get short key encapsulation. ​ It may be possible to modify that and/or the signature algorithm to let you ​ ​ ​ (continued ...) ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user991 Jan 12 '16 at 9:02
  • $\begingroup$ (... continued) ​ ​ ​ use the same key-pairs for encryption and signing, although there are separate reasons why you might want to avoid that anyway. ​ It should be possible to reduce the key size by 1 more bit by dropping the y coordinate. ​ ​ ​ ​ $\endgroup$ – user991 Jan 12 '16 at 9:02
3
$\begingroup$

Asn1parse to the rescue.

Most of the overhead is from the base64 encoding and the PEM header and footer.

The raw size of the compressed form ASN1 encoding is just 44 bytes for my dummy key.

And 22 of those bytes are for the 161 bits of the actual public key.

$ openssl asn1parse -in compressed_public.pem -i -dump
    0:d=0  hl=2 l=  42 cons: SEQUENCE
    2:d=1  hl=2 l=  16 cons:  SEQUENCE
    4:d=2  hl=2 l=   7 prim:   OBJECT            :id-ecPublicKey
   13:d=2  hl=2 l=   5 prim:   OBJECT            :secp160k1
   20:d=1  hl=2 l=  22 prim:  BIT STRING
      0000 - 00 03 ca f2 7b b8 4c 3c-99 b2 7a 6f fb f3 cf 8f   ....{.L<..zo....
      0010 - 95 b8 77 61 76 dc                                 ..wav.

And if you turn the PEM encoding into raw DER encoding like so...

$ openssl ec -pubin -in compressed_public.pem -outform der -out compressed_public.der
read EC key
writing EC key

...then 44 bytes is the size of your file.

$ stat compressed_public.pem | grep Size
  Size: 113             Blocks: 1          IO Block: 65536  regular file

$ stat compressed_public.der | grep Size
  Size: 44              Blocks: 1          IO Block: 65536  regular file

And just for another look at this: using "dumpas1n", you can see exactly where those 22 non-pubkey bytes went:
(Note: dumpasn1 skips the "00" byte at the beginning of the 22 byte "BIT STRING" object and does not display it. And openssl asn1parse does not.)

$ dumpasn1  | head -n2
DumpASN1 - ASN.1 object dump/syntax check program.
Copyright Peter Gutmann 1997, 1998.  Last updated 27 July 1998.

$ dumpasn1 compressed_public.der
   0 30   42: SEQUENCE {
   2 30   16:   SEQUENCE {
   4 06    7:     OBJECT IDENTIFIER ecPublicKey (1 2 840 10045 2 1)
  13 06    5:     OBJECT IDENTIFIER '1 3 132 0 9'
            :     }
  20 03   22:   BIT STRING 0 unused bits
            :     03 CA F2 7B B8 4C 3C 99 B2 7A 6F FB F3 CF 8F 95
            :     B8 77 61 76 DC
            :   }

0 warnings, 0 errors.

So to answer your question:

Can I somehow reduce this size, getting rid of metadata?

Yes. You could cut the size down to just the 22 bytes (or 21 bytes if you exclude any leading 00 bytes).

(If you want yet another tool to look at ASN1: Here's that key in asn1js online.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ Yes. This gives constant size because the encoding uses BIT STRING rather than INTEGER. $\endgroup$ – fgrieu♦ Jan 12 '16 at 12:46
  • $\begingroup$ Great answer, thank you very much. Is it true this last comment, that this ensures also that the length of the public key is constant and stable, not even varying by one bit? $\endgroup$ – BenM Jan 12 '16 at 13:22
  • $\begingroup$ By the way, @StackzOfZtuff, I tested this on secp curves of 112, 131, 160, 256 - using your tool to read out the number of bits describing the key. They were, respectively, 120, 144, 168, 264. So the rule holds - curve size+8, except for the 131 bit curve. Do you know why? $\endgroup$ – BenM Jan 12 '16 at 13:35
  • $\begingroup$ @BendikM: Don't know. Sorry. I don't know much about EC. Maybe make that another, separate question. $\endgroup$ – StackzOfZtuff Jan 12 '16 at 13:40
  • $\begingroup$ @BendikM, an ECDSA public key is just a point on the curve. The most compressed version of such a point is just the x-coordinate along with a hint which y-coordinate (because there are two square roots) to use. The additional byte encodes a) whether you encode the point at infinity, b) a compressed point (x-coordinate only) and which y-coordinate to use or c) whether you encode an uncompressed point (i.e. x- and y-coordinate). As for the 131-bit curve, it probably rounds up to the nearest multiple of 8 (136) to encode the x and then adds the type byte. $\endgroup$ – SEJPM♦ Jan 12 '16 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.