3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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$. $\endgroup$
    – fgrieu
    Commented May 18, 2023 at 14:50

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you. I will check my implementation. $\endgroup$
    – user109426
    Commented May 19, 2023 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.