CNS - 43 - Elliptic Curve Crypto II

When we want to sign a message \(m\) the following steps have to be taken:

1. We first generate a random \(k\) in the \((1, q)\), which is the first half of the group.

2. We then compute \(r = (g^k \mod p)\), but since this value might be greater than \(q\) we also chop it using \(\mod q\). At the end thus we have the following value

   \[r = (g^k \mod p) \mod q\]

3. We also compute the following

   \[s = k^{-1} \cdot (H(m) + d \cdot r) \mod q\]

4. The final signature is \((r, s)\).

When instead we want to verify the signature \((r, s)\) of a given message \(m\) we do the following:

1. We first invert \(s\) and compute

   \[u_1 = s^{-1}H(m) \mod q = \frac{k}{H(m) + dr} \cdot H(m) \mod q = \frac{k H(m)}{H(m) + dr} \mod q\]

2. Then we compute

   \[u_2 = s^{-1}r \mod q = \frac{k}{H(m) + dr} \cdot r \mod q = \frac{kr}{H(m) + dr} \mod q\]

3. Finally, we verify that

   \[((g^{u_1} \cdot y^{u_2} \mod p) \mod q) = r\]

   This check makes sense since

   \[\begin{split} ((g^{u_1} \cdot y^{u_2} \mod p) \mod q) &= \bigg(g^{\frac{k H(m)}{H(m) + dr}} \cdot (g^{d})^{\frac{kr}{H(m) + dr}} \mod p \bigg) \mod q \\ &= \Bigg(g^{\frac{k H(m)}{H(m) + dr} + \frac{krd}{H(m) + dr}} \mod p\Bigg) \mod q \\ &= \Bigg(g^{\frac{k(H(m) + dr)}{H(m) + dr}} \mod p\Bigg) \mod q \\ &= \Bigg(g^{k} \mod p\Bigg) \mod q \\ &= r \\ \end{split}\]

When we want to sign a message \(m\) using ECDSA the following steps have to be taken:

1. We generate a random integer \(K \in (1, \ldots, n-1)\).

2. We compute the point \(kP = (x_1, y_1)\) using our elliptic curve group we have previously defined.

3. We compute \(r = x_1 \mod n\)

4. We compute \(k^{-1} \mod n\)

5. We compute \(s = k^{-1} \cdot(H(m) + dr)\)

6. The final signature is then given by \((r, s)\).

Note that the only operation regarding elliptic curves is when we compute the point \(kP\). Since this operation can be computationally expensive, it might get optimized. Doing so however might break the signature.

Also note that the integer \(k\) must be unique per signature and unpredictable. If these requirements are not met, then the signature might be broken.

When instead we want to verify the signature \((r, s)\) of a given message \(m\) we do the following:

1. From the message \(m\) we compute the hash \(H(m)\).

2. From \(s\) we compute

   \[w = s^{-1} \mod n = \frac{k}{H(m) + dr} \mod n\]

3. We then compute \(u_1\), \(u_2\) as follows

   \[\begin{split} u_1 &= H(m) w &\mod n &= \frac{H(m) k}{H(m) + dr} \mod n \\ u_2 &= r w &\mod n &= \frac{r k}{H(m) + dr} \mod n \\ \end{split}\]

4. Then we compute the elliptic point

   \[\begin{split} u_1 P + u_2 Q &= u_1 P + u_2 (d P) \\ &= \frac{H(m) k}{H(m) + dr} P + \frac{r k d}{H(m) + dr} P \\ &= \frac{k(H(m) + rd)}{H(m) + dr} P \\ &= (x_0, y_0) \\ \end{split}\]

5. Finally, we check that given \(v = x_0 \mod n\) we have that

   \[v = r\]

Notice that if \(k\) is predicted, then the knowledge of the longterm private key would be disclosed. Indeed, consider a signature \((r, s)\) and assume we know \(k\), then we know that

\[s = k^{-1}(H(m) + rd) \mod n\]

but notice that this gives us an equation in which the only unknown is \(d\). By solving for \(d\) we get

\[d = (sk - H(m))r^{-1} \mod n\]

and thus \(d\) is easily computed.

Assume now that \(k\) is repeated. That is, assume we have two signatures \((r, s_1)\) and \((r, s_2)\). Notice that the \(r\) value is the same in both signature because we assume that the underlying \(k\) vale is also teh same. But then we have that

\[\begin{cases} s_1 = k^{-1}(H(m_1) + rd) \mod n \\ s_2 = k^{-1}(H(m_2) + rd) \mod n \\ \end{cases} \implies \begin{cases} k = s_1^{-1} (H(m_1) + rd) \mod n \\ k = s_2^{-1} (H(m_1) + rd) \mod n \\ \end{cases}\]

which means that we have two equations in two unknowns \(k\) and \(d\). We can solve it to find

\[d = (s_1 H(m_2) - s_2 H(m_1))r^{-1}(s_2 - s_1)^{-1} \mod n\]

to once again compute \(d\).

Observation: This type of attacked happend for real in \(2010\), and the target was Sony's Playsation 3 signature.