# Finding the private key for this signature scheme

Assume the signature scheme where $$x$$ is the private key and the public key $$y = g^x \pmod{p}$$. The signature works as:

• Choose $$h \in \{0, \dots, p-2 \}$$ s.t.: $$\mathcal{H}(m) + x + h \equiv 0 \pmod{p-1}$$, $$\mathcal{H}(m)$$ collision-resistant hash function.

• The signature is the triple $$(m, (x+h) \pmod{p-1},g^h \pmod{p}) = (m,a,b)$$

• Verification checks if: \begin{align} yb &\equiv g^a \pmod{p} \tag{1} \\ g^{\mathcal{H}(m)}yb &\equiv 1 \pmod{p} \tag{2} \end{align}

The objective is to achieve and forge signatures for arbitrary messages of our choice.

• Would you mind adding how the signature verification procedure works? And confirm that the goal of the exercise is finding $x$, rather than merely forging signatures?
– fgrieu
Jan 24 '21 at 15:40
• @fgrieu I added the verification. The actual question is if total break is possible, but I assumed that is equivalent to having the private key. Jan 24 '21 at 15:46
• "Total break" means ability, from public key and some example messages+signatures, to produce a signature accepted by the verification procedure for any message. Recovering the private key implies total break, but the converse does not hold.
– fgrieu
Jan 24 '21 at 18:38
• Oh I see, so for total break it suffices to find a way to sign messages of your choice without knowing the private key? Jan 24 '21 at 18:40
• @fgrieu is the triple $(m', a' , b')$ with $a' = -H(m') \pmod{p-1}$ and $b' = g^{-H(m')} \cdot y^{-1} \pmod{p}$ valid for forging signatures with $m'$ arbitrary? Jan 24 '21 at 19:13

Let $$m'$$ be an arbitrary message. Then, the triple $$(m', a', b')$$ with:
\begin{align} a' &= -\mathcal{H}(m') \pmod{p-1} \\ b' &= g^{-\mathcal{H}(m')} \cdot y^{-1} \pmod{p} \end{align}
is a valid signature on $$m'$$. Since we forged a signature on an arbitrary message, we've achieved total break for this scheme.