# ECDSA Algorithm

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

• 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.
– fgrieu
May 28 '21 at 5:14
• Because $Z_{17}$ subgroup of $Z_{19}$
– Tez
May 28 '21 at 14:03
• $\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).
– fgrieu
May 28 '21 at 16:16
• I understand. Do you have an answer for this question? Can you help me?
– Tez
May 28 '21 at 17:28
• 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$.
– fgrieu
May 29 '21 at 6:59