# Occasional failure of an attack on ElGamal signature

I am following the procedure described on p. 319 of the fourth edition of Douglas Stinson and (since that edition) Maura Paterson's Cryptography − Theory and Practice (IBSN 978-1-03-247604-9).

The context is recovery of the nonce $$k$$ in ElGamal signature in $$\mathbb Z_p^*$$, assuming nonce reuse. We have two message/signature pairs $$\bigl(x_1,(\gamma,\delta_1)\bigr)$$ and $$\bigl(x_2,(\gamma,\delta_2)\bigr)$$. It holds $$\gamma=\alpha^k\bmod p$$, $$\delta_i=(x_i-a\gamma)k^{-1}\bmod(p-1)$$ where $$\alpha$$ is a generator and $$a$$ is the private key.

We are in the sub-case of $$d=\gcd(\delta_1-\delta_2,p-1)\ne1$$. It's computed $$x'=(x_1-x_2)/d$$, $$\delta'=(\delta_1-\delta_2)/d$$, and $$p'=(p-1)/d$$.

Then the congruence $$x_1-x_2\equiv k(\delta_1-\delta_2)\pmod{p-1}$$ becomes: $$x'\equiv k\delta'\pmod{p'}.\tag{1}\label{eq1}$$ Since $$\gcd(\delta',p')=1$$, we can compute $$\epsilon=(\delta')^{-1}\bmod p'.\tag{2}\label{eq2}$$ The value of $$k$$ is determined modulo $$p'$$ to be $$k=x'\epsilon\bmod p'.\tag{3}\label{eq3}$$ This yields $$d$$ candidate values for $$k$$: $$k=x'\epsilon+ip'\bmod(p-1)\tag{4}\label{eq4}$$ for some $$i,0\le i\le d-1$$. Of these $$d$$ candidate values, the (unique) correct one can be determined by testing the condition $$\gamma=\alpha^k\pmod p.\tag{5}\label{eq5}$$

I wrote a program that does all calculations with random parameters and notice that not always can I compute $$k$$ using the formula $$\ref{eq4}$$. Nevertheless, sometimes it does work. So I wonder if I am doing something wrong, or there is an assumption on the parameters that I am missing.

For example, taking $$p=157, k = 79, a = 139, \alpha= 70, \beta = 152, x_1 = 116, x_2 = 65, \gamma = 87, \delta_1 = 113, \delta_2 =140,$$ we have $$d=3$$ and the values returned by formula $$\ref{eq4}$$ are $$0, 52, 104$$, none of which is equal to $$79$$.

• Equation $\eqref{eq3}$ is intended to be read $k\equiv x'\epsilon\pmod{p'}$, meaning $x'\epsilon-k$ is a multiple of $p'=(p-1)/d$. Equation $\eqref{eq5}$ can be read as $\gamma\equiv\alpha^k\pmod p$ or $\gamma=\alpha^k\bmod p$.
– fgrieu
Commented May 18, 2023 at 14:50

For the question's added example values we get $$x'=17$$, $$\delta'=-9$$, $$p'=52$$, $$\epsilon=23$$. Then for $$i=(0,1,2)$$ I get $$x'\epsilon+ip'\bmod(p-1)=(79,131,27)$$, and equation $$\eqref{eq5}$$ holds for $$i=0$$, as claimed by the reference.
I conclude the implementation of equation $$\eqref{eq2}$$ or $$\eqref{eq4}$$ is wrong in the program that produced $$0,52,104$$. An hypothesis is that negative $$\delta'$$ is mishandled.
I see no mistake in that part of the reference. As noted in comment I wish it used standard and unambiguous notation for modular congruence $$u\equiv v\pmod q$$ and modular reduction $$u=v\bmod q$$. Also I think it would be more useful and as easy to find $$a$$ rather than $$k$$.
For large $$d$$, it's worth noting that each step in the sequential search for the full $$k$$ or $$a$$ can be organized to cost a single modular multiplication modulo $$p$$, or further optimized to have cost proportional to $$\sqrt d$$ such operations, using baby-step/giant-step or Pollard's rho.