Problem with generating a valid ECDSA signature over a small field

[marekyggdrasil]

Hello! Thanks for writing this great library!

I am playing with it by making a toy example over a small finite field of prime order n=17 and I find that I cannot generate a valid signature. Here is an example code that reproduces the problem:

a = 0
b = 7
c = 0
n = 17

curve = CurveOverFp(a, b, c, n)

print('Points on the finite field:')
points = curve.get_points()
for j, point in enumerate(points):
    descr = ''
    if j == 3:
        descr = ' <- generator P'
    print(str(point) + descr)
print()
P = points[3]

is_contained = curve.contains(P)
print('P is on the curve?', is_contained)
print()

keypair = generate_keypair(curve, P, n)
d, Q = keypair
is_contained = curve.contains(Q)
print('Q is on the curve?', is_contained)

divides = curve.mult(Q, n).is_infinite()
print('Does Q has an order that divides p?', divides)

message = '''
Hey you, what up?!
'''

sig = sign(message, curve, P, n, keypair)
print()

valid = verify(message, curve, P, n, sig)
print()
print('is valid?', valid)

Some example outputs, in the following signature verification fails because the public key is of an order that does not divide n

y^2 = x^3 + 7x over F_17
Points on the finite field:
Inf
(0,0)
(1,5)
(1,12) <- generator P
(7,1)
(7,16)
(10,4)
(10,13)
(16,3)
(16,14)

P is on the curve? True

Priv key: d = 1
Publ key: Q = (1,12)
Q is on the curve? True
Does Q has an order that divides n? False
ECDSA sig: (Q, r, s) = ((1,12), 16, 8)

is valid? False

https://github.com/qubd/mini_ecdsa/blob/5119ff3861d56492d41d189194130774b999849f/mini_ecdsa.py#L435-L437

and in the following run the public key ended up to be an infinity point

y^2 = x^3 + 7x over F_17
Points on the finite field:
Inf
(0,0)
(1,5)
(1,12) <- generator P
(7,1)
(7,16)
(10,4)
(10,13)
(16,3)
(16,14)

P is on the curve? True

Priv key: d = 5
Publ key: Q = Inf
Q is on the curve? True
Does Q has an order that divides n? True
ECDSA sig: (Q, r, s) = (Inf, 1, 8)

is valid? False

fails at

https://github.com/qubd/mini_ecdsa/blob/5119ff3861d56492d41d189194130774b999849f/mini_ecdsa.py#L432-L434

in any case, it seems like the problem lays in the public key, but generation of the public key is really trivial, could it be because of my choice of the curve? a=0, b=7, c=7 of order n=17?

Thanks in a advance for the debugging hints!

[qubd]

The problem here is that you're using n = 17, when the subgroup generated by (1, 12) on the curve you're working with actually has order 5.

C = CurveOverFp(0, 7, 0, 17)
P = Point(1, 12)
C.generate(P)
['Inf', '(1,12)', '(16,3)', '(16,14)', '(1,5)']

You need to use n = 5 when you generate the keypair and signature.

Trying to reproduce your example myself (with a different message text), correcting this mistake actually lead to an infinite loop when generating the signature. In fact, all of the five available options for the nonce k lead to r = 1 and s = 0 in the ECDSA signature generation process.

Here we have d = 1, and for every nonce k, the resulting r is also 1, since the x-coordinate of any point in the subgroup generated by P is 1 mod 5 (except the point at infinity, whose x-coordinate I have set to zero, so if it appears as R in the signature generation process, a valid signature will not result and we will try another nonce k). The upshot of this is that the calculation of s reduces to s = k^(-1)(z+1), where z is the message hash. This means if z+1 (which depends only on the message, not the value of the nonce k) happens to be 0 mod 5, then s will be as well, and no valid ECDSA signature is possible for this choice of curve, subgroup, and message.

I've never thought about it before, but this can certainly occur by chance in small examples like this one.

[qubd]

I think your second issue brings up a problem I should fix: the public key in a key pair should not be allowed to be the identity (point at infinity), or the signature generation process will just loop forever (there is no valid signature since r = 0 for all values of the nonce k).

Update: Nevermind. It's been a while since I've looked at any of this. The nonce k is actually multiplied with the generator of the distinguished subgroup, not the public key, so generating valid signatures from a key pair whose public key is the identity should not be problem. Of course, it's a very silly choice and no one should ever actually use such a key pair.

[marekyggdrasil]

Thank you @qubd for such quick and informative reply. Here is updated example

a = 0
b = 7
c = 0
p = 17

curve = CurveOverFp(a, b, c, p)

print('Points on the finite field:')
points = curve.get_points()
for j, point in enumerate(points):
    descr = ''
    if j == 3:
        descr = ' <- generator P'
    print(str(point) + descr)
print()
P = points[3]

group = curve.generate(P)
n = len(group)
print('order of cyclic group generated by P is n =', n)

is_contained = curve.contains(P)
print('P is on the curve?', is_contained)
print()

keypair = generate_keypair(curve, P, n)
d, Q = keypair
is_contained = curve.contains(Q)
print('Q is on the curve?', is_contained)

divides = curve.mult(Q, n).is_infinite()
print('Does Q has an order that divides p?', divides)

message = '''
Hey you, what up?!
'''

sig = sign(message, curve, P, n, keypair)
print()

valid = verify(message, curve, P, n, sig)
print()
print('is valid?', valid)

and its output

y^2 = x^3 + 7x over F_17
Points on the finite field:
Inf
(0,0)
(1,5)
(1,12) <- generator P
(7,1)
(7,16)
(10,4)
(10,13)
(16,3)
(16,14)

order of cyclic group generated by P is n = 5
P is on the curve? True

Priv key: d = 4
Publ key: Q = (1,5)
Q is on the curve? True
Does Q has an order that divides p? True
ECDSA sig: (Q, r, s) = ((1,5), 1, 1)

is valid? True

it works now. I thought that the order of the cyclic group is equal to the entire finite field size and I was confusing n and p.... Thanks again!

[qubd]

No problem. I guess the hash of your message ended up resulting in a nonzero value for s, and hence a valid signature was possible.

It would be nice to have an example where the size of the distinguished prime order subgroup is a bit larger (large enough that the nonce k does affect the signature, and every message hash can result in a valid signature) but still small enough to see the entire set of points displayed in the terminal in one or two lines.

Maybe something like y^2 = x^3 + 3 over F_19. In this case, there are 13 points on the curve, and any non-identity element will generate the entire group of 13 points.

[marekyggdrasil]

Thanks for the suggestion @qubd ! I also found a problem with k, basically for such small values of k it is not always possible to calculate the modular inverse as GCD must be 1. That was also problematic.

I summarized what I did under a form of a small tutorial. I also linked to your library and this discussion (I hope you don't mind!) https://mareknarozniak.com/2021/03/16/ecdsa/

[qubd]

The value of the nonce k is taken to be a nonzero random number between 1 and n-1, where n is the order of the distinguished subgroup. As long as n is prime, the computation of the inverse of k will succeed. As is stated in the readme, the signing and verifying procedures in this package assume that requirement is met. I believe that the usual specification of the ECDSA algorithm requires this (at least the one on Wikipedia does).

Nice tutorial, and of course you can link this. It's great to see the code here is helping people learn things!