Impossible ElGamal signatures

Question

From the following problem, I think it is not possible:

" You find two signatures made by Alice. You know that she is using the ElGamal signature scheme over $\mathbb{F}_{2027}$. The cyclic group $\mathbb{G}$ she is using is a (multiplicative) subgroup of order 1013. The signatures are on hash values $h(m_1) = 345$ and $h(m_2) = 567$ and are given by $(r_1, s_1) = (365, 448)$ and $(r_2, s_2) = (365, 969)$. Compute (a candidate for) Alice’s secret key $x$ based on these signatures, i.e. break the system. "

By the following equations, this is why I think these combinations are not possible:

$\begin{cases} (365, 448) = (g^k \mod 2027 , (345-365x)k^{-1} \mod 2026) \\ (365, 969) = (g^k \mod 2027, (567-365x)k^{-1} \mod 2026) \end{cases}$

The difference of the $y$-coordinate is $969-448 = 521\mod 2026$ from the left side, and $(567-345)k^{-1}=222k^{-1} \mod 2026$ from the right side. So the left side is odd and the right side is even while there are equal.

Do I do something wrong, or do you agree?

Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2\cdot 8$ in that ring. — Henno Brandsma, Nov 16 '18 at 09:05
Ok, but here we work with $\mod (p-1)$ and $p-1$ is even. Hence $521 \equiv 222k \mod (p-1)$ is meaningless — Rocco van Vreumingen, Nov 16 '18 at 09:08
If $k$ works so does $k+1013$, as we work in a smaller group than the full $Z^\ast_p$. One $k$ can be even, the other odd. — Henno Brandsma, Nov 16 '18 at 09:59
If $521 = 222k \mod 1013$ then I agree. But we work in $\mod p-1$ here, also the $k$ from $222k$ is in $\mod p-1$, so does this mean that $p-1 = 1013$? — Rocco van Vreumingen, Nov 16 '18 at 10:04
No, the $k$ is chosen in ${1,\ldots,p-1}$ such that $\gcd(k,p-1)=1$ (so the inverse exists). In particular $k$ is odd. — Henno Brandsma, Nov 16 '18 at 10:07
I think I would better read the theory again. Once done, I will come back to this. — Rocco van Vreumingen, Nov 16 '18 at 10:11
E.g. if $g=3$ we get a group of order $1013$, and both $k=587$ and $k=1599$ work to get $r=g^k = 365$. — Henno Brandsma, Nov 16 '18 at 10:11
It is clear that Alice works with a subgroup. But still $521$ cannot be $222k$ plus a multiple of $p-1$. Because $222k + m(p-1)$ ($m\in\mathbb{Z}$) is even (whether $k$ is even or odd) and $521$ is odd. — Rocco van Vreumingen, Nov 16 '18 at 10:28
Maybe the $k$ are different, but yield the same $r$. Then one $k$ can be substituted with $k+1012$ and we get different numbers. We only know the $r$ are the same, not the $k$. — Henno Brandsma, Nov 16 '18 at 11:38

Henno Brandsma · Answer 1 · 2018-11-16T10:32:26.543

1

The verifying equations are

$$H(m) = xr + ks \bmod{(p-1)}\tag{1}$$

and

$$H(m') = xr + ks' \bmod{(p-1)}\tag{2}$$

and as we have a common $k$ and $r$, there are two unknowns $x$ and $k$.

Solve these equations by standard techniques, $H(m), H(m')$ are known and find $x$ (and $k$ too, but that's not very useful).

I did and found an $x$ that works. If $k$ works so does $k+1012$ as $g$ has order $1012$, and so these give the same $r$.

edited Nov 16 '18 at 10:32

answered Nov 16 '18 at 07:31

Henno Brandsma

242,131

Yes, so $H(m) - H(m') \equiv k(s-s')\mod (p-1)$, but this yields $-521 \equiv 222k \mod (p-1)$, or equivalently $-521 - 222k \equiv 0 \mod (p-1)$. But since $-521-222k$ is odd and $p-1$ is even, is cannot be equal to a multiple of $p-1$. So it surprises me that you have found an $x$ and $k$. – Rocco van Vreumingen Nov 16 '18 at 09:04
@RoccovanVreumingen I only computed the $x$ not the $k$. – Henno Brandsma Nov 16 '18 at 09:09
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$. – Henno Brandsma Nov 16 '18 at 09:10
It is clear how you found an $x$, but I still don't see what was wrong in my calculation. – Rocco van Vreumingen Nov 16 '18 at 09:26
@RoccovanVreumingen the $k$ is determined mod 1013 only. – Henno Brandsma Nov 16 '18 at 09:29

Impossible ElGamal signatures

1 Answers1