2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this (interesting) conversation has been moved to chat. $\endgroup$ – fgrieu Jan 5 at 16:38
0
$\begingroup$

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.

$\endgroup$

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.