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.

  • $\begingroup$ 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? $\endgroup$ – fgrieu Jan 24 at 15:40
  • $\begingroup$ @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. $\endgroup$ – Paris Jan 24 at 15:46
  • $\begingroup$ "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. $\endgroup$ – fgrieu Jan 24 at 18:38
  • $\begingroup$ Oh I see, so for total break it suffices to find a way to sign messages of your choice without knowing the private key? $\endgroup$ – Paris Jan 24 at 18:40
  • 1
    $\begingroup$ @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? $\endgroup$ – Paris Jan 24 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.


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.