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$
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. And, at least customarily, $n$ is slightly less than $p$. Here, the curve and $G$ is such that $n=987=3\cdot7\cdot47$ is composite and larger than $p$. 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.

Having $n<p$ would introduce a minor complication: $r$ is an $x$ coordinate after reduction modulo $n$; but again that's customary.

I suggest $p=1051$, which will give a prime $n=1009$ slightly less than $p$ for the same $G$. Or, if we want $n>p$ so that $r$ is an $x$ coordinate in all cases, $p=1033$, which will give a prime $n=1061$.

$\endgroup$
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$
  • 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

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.