Some high "s" values in ECDSA signature not detected due to error in floating point arithmetic

[salmonberry7]

In the functions such as sigencode_strings_canonize, sigencode_string_canonize, and sigencode_der_canonize
where canonicalization of the "s" value in an ECDSA signature is performed with the code :

if s > order / 2:
	s = order - s

which uses the Python 3 "true division" operator / producing a floating point type irrespective of the type of the operands (eg. as described in [1] p146), high "s" values in at least the range [N // 2 + 1, N // 2 + 2**127] are not detected, where // is the Python 3 "floor division" operator which discards the remainder and performs exact integer arithmetic for integer operands of arbitrary size (eg. see [1] p135)). (N = order of the elliptic curve).

This is because the exact value of N / 2, which should be N // 2 + 0.5, is considerably larger than this due to the floating point error:

>>> N/2 > N//2 + 2**127
True
>>> N/2 > N//2 + 2**128
False

(testing with Python interpreter v3.8.10).

In the test below in Python interpreter v3.8.10 we can see how s = (N // 2) + 2**127 is not detected as high, whereas s = (N // 2) + 2**128 is detected as high :

N = order of secp256k1 generator point G =
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

N // 2 = 
7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0        (exact)

>>> N / 2
5.78960446186581e+76            (approximate)

>>> s = (N // 2) + 2**127
>>> s > N / 2
False

>>> s = (N // 2) + 2**128
>>> s > N / 2
True

The fix is to simply use the exact integer floor division operator // instead of / :

if s > order // 2:
	s = order - s

and this will detect any s from the "midpoint" of odd prime N upwards, ie. the "high" values of s.

This problem is also discussed in this question on Bitcoin Stack Exchange.

[1] Mark Lutz (2013), Learning Python 5th Edition, O'Reilly

[tomato42]

Good find, yes, those changes look good. Could you prepare a PR fixing them?