Can I extract R and S from an ECDSA signature in bit form, and vica versa?

Question

I have searched the forum and found related information, but not answer to this question. I am working in an extremely bandwidth-restricted environment, in need of creating as small ECDSA signatures as possible. We are, for now, using OpenSSL. Also - as the signature data must be of a predictable length - a fixed size.

I understand that the ECDSA signature consists of two integers S and R, of the bit length equal to the curve size. In addition, 6-7 bytes seem to be added when I try creating a signature, reading the size from cygwin wc -c command. I have read many places that this overhead may vary - hence we lose the predictability of the signature length.

Possible solution - extract S and R and transmit is in binary(?) form - just as a stream of bits. I am uncertain if this is possible, because I guess it loses compatibility with the OpenSSL library. So we would need to reverse the process, constructing a signature using the S and R in the encoding OpenSSL will accept.

I have noticed that there is a -binary option in OpenSSL which gave me a blank file. I assumed I was on the wrong track.

Answer 1

I know it's old, but I've spent some time trying to figure out the same question lately, so here's an answer of sorts.

Let's assume you've created a signature like so:

$ openssl dgst -sha256 -sign private_secp160k1.pem foo.txt > sign.bin

Because the curve is 160 bits, the signature is two 20 byte numbers. By default, OpenSSL will have written it in ASN.1's binary DER format. Inspecting it, we should find at least 2 * 20 bytes:

$ xxd -i < sign.bin
0x30, 0x2d, 0x02, 0x14, 0x22, 0xd0, 0x8b, 0xc1, 0x0d, 0x0b, 0x7b, 0xff,
0xe6, 0xc1, 0x77, 0xc1, 0xdc, 0xc4, 0x2f, 0x64, 0x05, 0x17, 0x71, 0xc8,
0x02, 0x15, 0x00, 0xdd, 0xf4, 0x67, 0x10, 0x39, 0x92, 0x1b, 0x13, 0xf2,
0x40, 0x20, 0xcd, 0x15, 0xe7, 0x6a, 0x63, 0x0b, 0x86, 0x07, 0xb6

In this particular DER encoded signature, there's 47 bytes. A DER or PEM encoded signature can be inspected with OpenSSL's asn1parse command to find out what the bytes are:

$ openssl asn1parse -inform DER -in sign.bin
 0:d=0  hl=2 l=  45 cons: SEQUENCE          
 2:d=1  hl=2 l=  20 prim: INTEGER  :22D08BC10D0B7BFFE6C177C1DCC42F64051771C8
24:d=1  hl=2 l=  21 prim: INTEGER  :DDF4671039921B13F24020CD15E76A630B8607B6

In short, it says:

• At byte 0, there is a DER header of length 2, indicating a there's a SEQUENCE of elements to follow, with a total combined length of 45 bytes.
• At byte 2, there is a DER header of length 2, indicating an INTEGER element of length 20, the first element of the SEQUENCE (20 bytes are then printed in hex)
• At byte 24, there is a DER header of length 2, indicating an INTEGER element of length 21, the second element of the SEQUENCE (20 bytes are then printed in hex)

(The d=N just means "depth", so the two INTEGER elements have d==1, because they are part of a sequence.)

Pretty printing the raw bytes from earlier, one can recognize the elements:

$ xxd -i < sign.bin
0x30, 0x2d, # Sequence of length 45 to follow (45 == 0x2d)

0x02, 0x14, # Integer of length 20 to follow (20 == 0x14)
# Here come the 20 bytes:
0x22, 0xd0, 0x8b, 0xc1, 0x0d, 0x0b, 0x7b, 0xff, 0xe6, 0xc1, 
0x77, 0xc1, 0xdc, 0xc4, 0x2f, 0x64, 0x05, 0x17, 0x71, 0xc8,

0x02, 0x15, # Integer of length 21 to follow (21 == 0x15)
0x00,       # The first of the 21 integer bytes (see explanation below!)
# Here come the remaining 20 bytes
0xdd, 0xf4, 0x67, 0x10, 0x39, 0x92, 0x1b, 0x13, 0xf2, 0x40, 
0x20, 0xcd, 0x15, 0xe7, 0x6a, 0x63, 0x0b, 0x86, 0x07, 0xb6

So why is the second integer 21 bytes?

Integers in DER are two's complement, so if the first byte of the 20 byte integer is >0x7F, an extra 0x00 byte is prepended, that way the first bit is always 0. In other words, while R and S are 20 bytes numbers, encoding them to DER integers may take an extra byte.

In OpenSSL, the ECDSA_SIG type contains two BIGNUMs. So once you've decoded the DER bytes with d2i_ECDSA_SIG, you can access them with yourSig->r and yourSig->s, which will be <=20 bytes (for 160 bits curves).

It's also possible that R or S need less than 20 bytes, if their first most significant digits happen to be zero. You can find the number of bytes needed for each one with BN_num_bytes, and then write them to a regular byte array with BN_bn2bin for serialiazation.

ECDSA_SIG* ecSig = d2i_ECDSA_SIG(NULL, derBuf, derBufSize);

int rBytes = BN_num_bytes(ecSig->r), // Number of bytes needed for R
    sBytes = BN_num_bytes(ecSig->s); // Number of bytes needed for S

// ...
unsigned char someBuffer[40] = {0};
BN_bn2bin( ecSig->r, someBuffer + 20 - rBytes ); // Place R first in the buffer
BN_bn2bin( ecSig->s, someBuffer + 40 - sBytes ); // Place S last in the buffer

On the receiving end, you would then simply recreate the ECDSA_SIG instance by setting its r and s members:

ECDSA_SIG* ecSig = ECDSA_SIG_new();
BN_bin2bn( someBuffer,      20, ecSig->r );
BN_bin2bn( someBuffer + 20, 20, ecSig->s );