I'm trying to set up an ECDSA with Elliptic Curves over $\operatorname{GF}(2^m)$ with an example of toy with the following values:
Using the Weierstrass equation on binary finite fields. $$E: y^2 + x*y - [x^3 + a x^2 + b]$$
Let $E$ be defined over the field $\operatorname{GF}(2^7)$ ($m = 7$) with the equation
$$E: y^2 + x*y - [x^3 + 0*x^2 + 1]$$ where $a = 0$ and $b = 1$, using the irreducible polynomial $P(z) = z^7 + z + 1 \bmod 2$
The points are in decimal which has a polynomial representation. Example; $(z^2 + z; z^2 + z + 1) = (0110; 0111)$ in its binary representation and $(6, 7)$ in its decimal representation.I am using wolframcloud software to validate operations.
- $d = 17$
- generator $G = (124, 68) = (z^6 + z^5 + z^4 + z^3 + z^2, z^6 + z^2)$, a point that lives on the curve
- $Q = [d]G = (40, 19)$, a point that lives on the curve too.
- $k = 13$
- $P = [k]G = (82, 100)$
- $r = x(P) = 82$
- $e = SHA(m) = 19$
- $k^{-1} = 79$
- $S = k^{-1} (e + d*r) \pmod{P(z)}$
- $S = 79 (19 + 17*82) \pmod{P(z)}$
- $S = 11$
Finally I obtained the value r and S that is the signature of the message: $(r, S) = (82, 11)$
Verification, and then suppose that the second entity know the same parameters over the curve without know d nor k. The second entity will carry out:
$P = [(S^{-1} * e) * G] + [(S^{-1} * r) * Q] \pmod{P(z)}\\
S^{-1} = 74\\
P = (74 * 19) * G + (74 * 82) * Q \pmod{P(z)}\\
P = 102 * G + 67 * Q \pmod{P(z)}\\
P = (80, 87) + (38, 35) \pmod{P(z)}\\
P = (30, 92) \pmod{P(z)}\\
P.x = 30$
which is different from $r=82$: $P.x$ should be equal to $r$, but, it's NOT.
Now, We suppose that the second entity knows $d$ such that $Q = d * G$ then:
$P = (102 * G) + (67 * 17 * G) \pmod{P(z)}\\
P = (102 * G) + (107 * G) \pmod{P(z)}\\
P = (102 + 107) * G \pmod{P(z)}\\
P = 13 * G\pmod{P(z)}\\
P = 13 * (124, 68)\\
P = (82, 100)\\
P.x = 82 = r$
which is correct but the second entity doesn't know $d$.
Could someone help me, please and tell me how I can solve this problem?
Annex code in Wolfram language: To perform scalar multiplication through sum of points and doubling of a point I am using the following code with ; or just Try It Online!
(* Input example GF(2^7): *)
m=7;
k="10001"; (*BinaQy representation 10001 = 17 in decimal *)
lim = StringLength [k] + 1 ;
a=0;
Gx=z^6 + z^5 + z^4 + z^3 + z^2; (* Gx = 124 *)
Gy=z^6 + z^2; (* Gy = 68 *)
IrreduciblePolynomialCCE= z^7 + z + 1;
Qx=Gx;
Qy=Gy;
For [i=2, i<lim , i++,
c=StringTake [k ,{i}];
(*Dubling*)
{d, {inv, u}}=PolynomialMod[PolynomialExtendedGCD[Qx, IrreduciblePolynomialCCE],2];
Lamda=PolynomialMod[(Qx + Qy*inv ), {IrreduciblePolynomialCCE, 2}] ;
X3=PolynomialMod[(Lamda^2 + Lamda + a ), {IrreduciblePolynomialCCE, 2}] ;
Y3=PolynomialMod [ (Qx^2 + Lamda*X3 + X3) , {IrreduciblePolynomialCCE, 2}] ;
Qx = X3;
Qy = Y3;
If [c=="1",{
(*Sum*)
{d, {inv2, u}}=PolynomialMod[ PolynomialExtendedGCD[Gx + Qx, IrreduciblePolynomialCCE],2];
Lamda2=PolynomialMod[(Gy + Qy) * inv2 , {IrreduciblePolynomialCCE, 2}] ;
XX3=PolynomialMod [(Lamda2^2 + Lamda2 + Gx + Qx + a) , {IrreduciblePolynomialCCE, 2}] ;
YY3=PolynomialMod [Lamda2*(Gx + XX3) + XX3 + Gy, {IrreduciblePolynomialCCE, 2}] ;
Qx = XX3;
Qy = YY3;
},{0}
]
]
Print [Qx]
Print [Qy]
The result $Q = (z^5 + z^3, z^4 + z + 1) = (40, 19)$