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

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

• Comments are not for extended discussion; this (interesting) conversation has been moved to chat.
– fgrieu
Jan 5, 2021 at 16:38

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.