3
$\begingroup$

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)

$\endgroup$
3
$\begingroup$

First note that this is essentially the same problem as if you just generated the curve parameters and now wanted to find out the order, so we can use the same strategies as for that case here:

  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).
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.