3
$\begingroup$

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?

$\endgroup$
0
6
$\begingroup$

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$.

$\endgroup$
2
  • 1
    $\begingroup$ slight correction: while it's common that $n < p$, there are standard curves for which $n$ is greater than $p$, secp160r1 is one curves like this $\endgroup$ – Hubert Kario Dec 12 '20 at 13:42
  • $\begingroup$ @Hubert Kario: Thanks, didn't knew that fact some recommended curves use $n>p$. Fixed. $\endgroup$ – fgrieu Dec 12 '20 at 15:34
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Yes. However, you really want to pick $p$ so that the order $n$ is prime, if only so that most $r$ will do. See my answer. $\endgroup$ – fgrieu Feb 2 '18 at 7:50
  • $\begingroup$ not only selection of $p$ has impact on primality of $n$, selection of $a$ and $b$ does too (where $y^2=x^3+ax+b\text{ mod }p$), so if you want a particular prime, you can just keep changing $a$ and $b$ until you get an $n$ that's prime too. For example, with $p=977$, $a=432$ and $b=520$, $G=(3, 572)$ has order $n=991$ $\endgroup$ – Hubert Kario Dec 12 '20 at 13:53

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.