# How to find q in a corrupted ECDSA signauture

I'm doing exam papers for a crypto exam and I've been given a corrupted ECDSA signature. I'm asked to check if the signature is valid (which I know how to do), however, the q value is corrupted and so I can't actually check the signature. Any ideas on how i'd find the value of q?

Curve, E = y^2 = x^3 + 2x + 2

Field size, p = 17

q = 1~ (where tilda stands for the corrupted value)

Base Point, P = (5, 1)

Public key, y = (0, 6)

h(M) = 26

(r, s) = (9, 17)

1. Ask a tool like sagemath: EllipticCurve(GF(17),[2,2]).cardinality() which constructs an elliptic curve over $$\mathbb F_{17}$$ with $$a=2,b=2$$ and finds out its cardinality which is $$q=19$$. This is the easisest way.
2. Calculate it yourself using Schoof's algorithm. Of course this is an $$\mathcal O(\log^5 p)$$ algorithm, so it will be quite tiresome to execute by hand, especially for small values. But for large curves it is the way to go.
3. Guess it using the Hasse-Bound. Essentially you want to solve the discrete logarithm $$q\cdot P=\mathcal O$$ (with $$\mathcal O$$ being the additive neutral element). Now you can use standard discrete-logarithm finding techniques, such as plain brute-force or BSGS to find it and also use the constrain that the Hasse-Bound gives you: $$|p+1-q|\leq 2\sqrt p$$, so $$q\in[p+1-2\sqrt p, p+1+2\sqrt p]$$ or in your concrete case: $$q\in [17+1-2\cdot 5,17+1+2\cdot 5]=[8,28]$$. So you would e.g. start with $$8P$$ and check if that's $$\mathcal O$$ and if not proceed to $$8P+P=9P$$ until you find the index that yields you $$\mathcal O$$ which is the order of $$P$$ (and in this case also the order of the curve because the curve order is prime).