Elliptic Curve Digital Signature algorithm fails

Question

I would like to monitor step by step running of ECDSA.

Parameters I am working on:

• The elliptic curve satisfies the equation: $y^2 = x^3 + x + 1$.
• I picked up the base point $G$ as: $(0, 1)$
• Finally, the modulo $p$ is $977$

My private key is $19$. Thereby, my public key is equal to $19\times G$ and its coordinates are $(396, 650)$. Suppose that my hash is equal to $14$.

Then, I picked up a random key. It would be $17$. So, random point would be $17\times G$ and it is equal to $(699, 739)$.

My signature is pair of $r$ and $s$, where $r$ is $x$ coordinate of my random point, and $s$ can be calculated as: $$\begin{align} r &= 699\\ s &= ((\text{random key})^{-1} \bmod p)\cdot(\text{hash} + r \cdot (\text{my private key}))\\ &= (17^{-1}\bmod 977)\cdot(14 + 699\cdot19)\bmod 977\\ &= (115\cdot13295)\bmod977\\ &= 1528925\bmod977\\ &= 897 \end{align}$$ So, my signature is $(699, 897)$.

Let's verify the signature $$\begin{align} w &= s^{-1}\bmod p\\ &= 897^{-1}\bmod 977\\ &= 403\\ u_1 &= \text{hash} \cdot w \bmod p\\ &= 14 \cdot 403 \bmod 977\\ &= 5642 \bmod 977\\ &= 757\\ u_2 &= r \cdot w \bmod p\\ &= 7699 \cdot 403 \bmod 977\\ &= 281697 \bmod977\\ &= 321 \end{align}$$

Now, I calculate the checkpoint $$\begin{align} \text{checkpoint}&=u_1\times G + u_2\times(\text{public key})\\ &= 757\times(0, 1) + 321\times(396, 650)\\ &=(707, 48) \end{align}$$

Finally, I need to compare the $x$ coordinate of checkpoint and $r$ value of signature. But $x$ coordinate of checkpoint is $707$ whereas $r$ value was $699$. They are not same. This means that signature is invalid. But they should be equal! Anyone can help where I am wrong?

Answer 1

In the question, $p$ designates the modulus of the base field $\mathbb Z_p$, as confirmed by the fact that for $p=977$ and the curve $y^2\equiv x^3+x+1\pmod p$, it holds that $19\times(0,1)=(396,650)$ and $17\times(0,1)=(699,739)$.

Problem is, in other steps, the question reduces $r$, $s$ and related quantities modulo that same $p$, rather than modulo the order $n$ of the group generated by $G$. That's more than enough to cause the observed failure.

As an aside, the ECDSA specification requires that $n$ is prime . In the question, the curve and $G$ is such that $n=987=3\cdot7\cdot47$ is composite. One consequence is that nearly half the choices of $\text{random key}$ are invalid, and I'm uncertain about if it otherwise makes some signature unverifiable. We do not care about the possible security implications since $p$ is so small as to make the whole thing insecure anyway.

I suggest $p=1033$, which will give a prime $n=1061$.

Answer 2

Ok, I understand the problem and fix it.

I worked on F977. This means that point addition calculations will be realized on mod 977. Let's express this modulo as p (p = 977).

I added based point (0, 1) recurrently and this reveals that there are 986 point this finite field.

P: (0, 1)

2P: (733, 121)

3P: (72, 611)

...

985P: (733, 856)

986P: (0, 976)

987P fails because it requires to divide something to 0.

That's why order of the group is equal to 987 because of the existing 986 points and additional infinite point. Let's say this as order (order = 987)

I would use mod p which is 977 to calculate public key and random point. This values remain same as in my previous post.

public key: (396, 650)

random point: (699, 739)

But I would use mod order which is 987 instead of mod p when calculation r and s.

r = x coordinate of random point mod order

s = [(hash + r * private key) * ((random key)^-1 mod order)] mod order

Herein, pair of r and s would be like that:

(r, s) = (699, 724)

Pair of r and s are our signature

Let's monitor the verification process...

w = s^-1 mod order

u1 and u2 calculations would be interesting because they contain both mod p and mod order.

u1 = (base point) x (hash * w mod order) mod p = (492, 698)

u2 = (public key) x (r * w mor order) mod p = (780, 58)

checkpoint = u1 + u2 mod p = (699, 739)

Finally, x coordinate of checkpoint and r would be compared. They are both 699. This means that our signature is valid.

To sum up, my problem was based on discarding order of the group.