Problem with the signature of message using ECDSA over GF(2^m)

Question

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

Answer 1

First of all I would like to thank @fgrieu, @kelelaka and the moderator Maarten Bodewes for their support to solve my question.

I had an error to determine K^-1, S, y S^-1, I was also missing an important piece of information which is the order of G (n = 29)

Correcting my mistake we have:

GF(2^7), m = 7

E: y^2 + xy - [x^3 + ax^2 + b]

y^2 + xy - [x^3 + 0x^2 + 1] with a = 0 and b = 1

Irreducible polynomial P(z) = z^7 + z + 1 mod 2

d = 17

G = (124, 68) = (z^6 + z^5 + z^4 + z^3 + z^2, z^6 + z^2), Generator 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

n = order of G = 29

k^-1 = 9 (Here was my first mistake when taking modularization with P(z) instead of n)

S = k^-1 (e + d*r) mod n (Here was my second mistake when taking modularization with P(z) instead of n)

S = 9 (19 + 17 * 82) mod 29

S = 15

Finally we obtained the value r and S that is the signature of the message(r,S)=(82,15)

Verifying the signature:

P = [S^-1 * e mod n] G + [(S^-1 * r mod n)] Q

S^1 = 2

P = (2 * 19 mod 29 )G + (2 * 82 mod 29)Q

P = [9]G + [19]Q

P = 9(124, 68) + 19(40, 19)

P = (76, 50) + (98, 104)

P = (82, 100)

x(P) = r

This is how we check that the signature is valid.