Let the curve $$y^2 = x^3 + 3x+ 5$$ be defined on $Z_{19}$ .

  1. If my private key is $d=4$ what is my public key for $P=(9,1)$ .

  2. If $H(M)=4$, find your ECDSA signature for message. Randomize the parameter $k$ (For example $k=2$).

  3. Verify the signature.

My steps :

  1. $Q = d \cdot P \pmod n$

    $Q = 4 \cdot (9,1) \pmod {17}$

    $Q = (8,11) \pmod {17}$

My public key is $Q = (8,11)$.

  1. $H(M) = 4$

    I choose $k = 2$.

    $k^{-1} \pmod n = 2^{-1} \pmod {17} => 2^{-1}=10 \pmod {17}$

    $kP = (x_1,x_2) => 2P = (15,9)$

    $r = x_1 \pmod n => r = 15 \pmod {17}=> r = 15$

    $s = k^{-1}(H(M) + d \cdot r) \pmod n => 2^{-1}(4+4\cdot 15) \pmod {17}=> s=15$

    $\therefore (r,s) = (15,15)$

  2. $w = s^{-1} \pmod n => 15^{-1} \pmod {17}=> w = 8$

    $u_1 = H(M) \cdot w \pmod n => u_1 = 4 \cdot 8 \pmod {17}=> u_1 = 15$

    $u_2 = r \cdot w \pmod n => u_2 = 15 \cdot 8 \pmod {17}=> u_2 = 1$

    $\therefore v = u_1 \cdot p+u_2 \cdot q \pmod n => v = 15 \cdot (9,1)+1 \cdot (8,11) \pmod {17}$

    $\therefore v = (15,8)$

    $\therefore x_v = 15 = r$

  • 2
    $\begingroup$ Welcome to crypto-SE! Hint1: ECDSA with prime field (as $\mathbb Z_{19}$ is) tends to be used on curves of prime order, and I'm not seeing that. So I'd double check the givens $\mathbb Z_{19}$ and $y^2=x^3+3x+5$. They are not necessarily false, but they do seem unusual. Hint2: You use $P=(9,1)$ for the base point. I suggest to check how you get from this to the $\pmod{17}$ used in the rest of the question. That modulus must be the order of the base point in the Elliptic Curve group (thus a divisor of the whole group's order), and I'm not seeing that. $\endgroup$
    – fgrieu
    May 28 '21 at 5:14
  • $\begingroup$ Because $Z_{17}$ subgroup of $Z_{19}$ $\endgroup$
    – Tez
    May 28 '21 at 14:03
  • $\begingroup$ $\mathbb Z_{17}$ is not a subgroup of $\mathbb Z_{19}$. Proof: the order of a subgroup of a finite group always divides the order of that group. $n$ is the order of the subgroup generated by $P$ in the Elliptic Curve group. For very small fields, you can obtain the group order by counting the solutions $(x,y)$ to the curve's equation (with $x$ and $y$ in the field), and adding one for the group's neutral. Again, that's a prime for most standard ECDSA curves on a prime field (as $\mathbb Z_{19}$ is). $\endgroup$
    – fgrieu
    May 28 '21 at 16:16
  • $\begingroup$ I understand. Do you have an answer for this question? Can you help me? $\endgroup$
    – Tez
    May 28 '21 at 17:28
  • $\begingroup$ Read our policy on homework. Assuming the (unusual) givens $\mathbb Z_{19}$ and $y^2=x^3+3x+5$ are OK, and $P=(9,1)$: your $Q=(8,11)\pmod {17}$ is no match, drops from nowhere, and also uses an unusual $Q=d\cdot P\pmod n$ notation. First step for (1.) is applying point doubling to get $4\cdot P$ (you got that part right), by doubling $P$, then doubling it again; show that result for (1.). First step for (2.) is finding the order $n$ of $P$. $\endgroup$
    – fgrieu
    May 29 '21 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.