I read about DER encoding and checked how IsValidSignatureEncoding is enforcing it, but I do not know why OpenSSL generates not-DER-compliant (r, s) values?
2 questions.
Are you doing the DER encoding yourself or is OpenSSL does it for you? If it is the later then it is doing it correctly.
And what do you mean by "non-DER-compliant"? DER is just an encoding, you have some data that you encode using a form of
TLV encoding scheme. This way of encoding can handle any kind of value. From 32 byte integers (r and s) to anything else like booleans, strings,...
How should I overcome this? I am thinking of something along the lines of (pseudocode):
Pair (r, s);
do
{
(r, s) = sign(hash, pvtkey);
} while (r[0] >= 128 || s[0] >= 128); // where r[0], s[0] should be the very first byte of each value
But isn't that kind of redundant? Can I give OpenSSL any flag to produce a valid DER (R, S) pair in the first place?
If OpenSSL is doing the DER-encoding then let it be like that. If you are DER-encoding yourself then first you have to understand why that initial 0 is appended to the result.
For humans when we want to represent sign we put a symbol behind the number showing its sign: -2 or +2
For computer there is no "sign" under the hood so the way it does it is with manipulating the bits (zeros and ones). The way it works for big numbers (like r and s here) is that the computer looks at the highest-order bit of the last byte (little endian order) if that is set the number is negative, if it is not set then the number is positive.
1 byte is 8 bits:
0000 0000 you look at the bold bit and if it was set then you decide about the sign.
127 =
0111 1111
128 =
1000 0000
129 =
1000 0001
...
So if the last byte (or first byte since DER encodes in big endian) is bigger than or equal to 128 and you want the number to be positive (which is the case with r and s) you append a new byte (0) to it to make the computer treat that number as positive.
So this code you posted is wrong because if the first byte of the byte array of 'r' or 's' is bigger than 128 that doesn't make them invalid that you want to try again. They can still be valid, you just have to append a first 0 byte to make it positive.
What you need to check are listed in sec1 pdf section 4.1.3 (!=0 & <N)
In bitcoin there is an additional check for s value only and that is to check if s is bigger than curve order. In which case you use s'=N-s and because of the way used arithmetic works s' is valid.
So here technically you always* end up with a value for s that is small, hence doesn't have its highest-order bit of the first byte (big endian order) set so you don't need that appended 0.
* I haven't really thought about this much but I believe it may be possible to find a smaller s (eg. 31 bytes instead of 32) and that s is lower than N/2 but can have its highest-order bit set (>=128 will fail and reject this valid s) which is another reason why the posted code is wrong.
