What is the relation between x y and r s in an ECDSA signature?

Question

I'm writing functions in C using OpenSSL and the EVP interface to interact with Intel SGX. One of those functions calculates an ECDSA (with SHA256) signature over some data.

The output of the ECDSA signature in OpenSSL is an ASN.1 structure with two integers, which I am assuming to be r and s. However, the data structure in Intel SGX that represents the signature has two values, x and y, each of fixed length 32 bytes.

#define SGX_SHA256_HASH_SIZE            32
#define SGX_ECP256_KEY_SIZE             32
#define SGX_NISTP_ECP256_KEY_SIZE       (SGX_ECP256_KEY_SIZE/sizeof(uint32_t))

typedef struct _sgx_ec256_private_t
{
    uint8_t r[SGX_ECP256_KEY_SIZE];
} sgx_ec256_private_t;

typedef struct _sgx_ec256_public_t
{
    uint8_t gx[SGX_ECP256_KEY_SIZE];
    uint8_t gy[SGX_ECP256_KEY_SIZE];
} sgx_ec256_public_t;

typedef struct _sgx_ec256_signature_t           <----- this structure
{
    uint32_t x[SGX_NISTP_ECP256_KEY_SIZE];
    uint32_t y[SGX_NISTP_ECP256_KEY_SIZE];
} sgx_ec256_signature_t;

I need to somehow convert the r and the s returned by OpenSSL's libcrypto to the x and the y used in Intel SGX. What is the relation between these parameters in the context of an ECDSA signature?

Answer 1

The ECDSA signature is the couple $(r, s)$ with $r \equiv (k\times G)_x \pmod{q}$ and $s \equiv k^{-1} (H(m) + r\,t) \pmod q$ where $G$ is a point of the elliptic curve of order $q$ and $t$ the secret key. $r$ and $s$ are thus 256 bits integers if the point used in the ECDSA algorithm is of order $q \approx 2^{256}$ which it is whith the secp256 curve.

With great probability, $x$ represents $r$ and $y$ represents $s$. You just need to convert your OpenSSL signature to the appropriate format.

The OpenSSL BN_bn2bin() might be useful.

Answer 2

Yes, those encoded values are $r$ and $s$.

The ASN.1 integers are signed big endian values while the two fixed sized values are unsigned big endian. So the value field may be identical or it may not, if:

1. the value is equal to or larger than $2^{256 - 1}$: encoding this as signed big endian value will result in an additional byte at the left set to 00 to avoid it being interpreted as a negative value;
2. the value is smaller than $2^{256 - 8 - 1}$: encoding this as signed big endian value will result in fewer bytes.

---

To convert back and forward between the ASN.1 structure you need two functions: I2OSP and OS2IP, also specified in e.g. RSA PCKS#1.

You can follow the mathematical construct of course, but basically you need to do the following (where $n$ is the minimum required size in bytes to encode the order $N$, i.e. the key size in bytes). The reason to do it this way is that you likely are handed rep(i) - the unsigned big endian encoding of i rather than the number itself.

I2OSP(i, n):

1. if len(rep(i)) is two larger or more than n then error;
2. if len(rep(i)) is one larger and the leftmost byte isn't 00 then error;
3. if len(rep(i)) is one larger and the leftmost byte is 00 then skip this byte and return the rest of rep(i) as answer;
4. if len(rep(i)) as unsigned integer is identical to n, then copy rep(i);
5. if len(rep(i)) is smaller than n then left-pad with zero's until the representation is the same size as n.

OS2IP(i)

You may want to skip initial zero bytes of rep(i) and then left-pad with one zero byte in case the result would be interpreted as negative number (i.e. the most significant bit is set, or the initial byte value is 0x80 or higher).

Usually however this kind of functionality is included in big integer libraries.

Unfortunately the BN library of OpenSSL is internalized so you may have to operate directly on the encodings like above.

---

The ASN.1 encoding is a SEQUENCE of two integers, DER encoded, as follows:

30 LC 02 LR rep(r) 02 LS rep(s)

LR and LS are the size of the following unsigned integer representation, a single byte. The value of LR and LS may differ of course.

LC is usually a single byte length encoding of everything that comes next. However, if the encoding of r and s combined is over 128 bytes then a two byte encoding needs to be used: 81 LC. This is only the case for 521 or 512 bit curves though, so you can almost ignore it :)

I'll let you have the fun to implement it. Finding a BER/DER parser/generator would be recommended though.