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

[salmonberry7]

In the PrivateKey.sign method the following code :

if s > N / 2:
    s = N - 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), fails to detect high "s" values in at least the range [N // 2 + 1, N // 2 + 2**127], 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)).

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 > N // 2:
    s = N - 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