0
$\begingroup$

Let $p$ be a large prime and $g$ a primitive root modulo $p$, and $h$ a collision-resistant hash function.

Person A chooses a random integer $1 < u< p$ and $y \equiv g^u \pmod p$ is publicly known.

The ElGamal signature scheme using exponent $k$ for a message $m$ is an ordered pair $(r,s)$ satisfying:

$r \equiv g^k \pmod p$

$h(m) \equiv ur + ks \pmod {p-1}$

Suppose now that person A chooses the exponents for the signature scheme to increase by two for every message she sends. For example if she sends messages $m_1, m_2, m_3$ then she uses exponents $k, k+2, k+4$ respectively.

Suppose that she sends a finite number of messages and such has a finite number of exponents, and that she makes her initial choice of $k$ so that all the following keys are coprime to $p-1$.

If we know that she does this, how might we be able to deduce $u$ if we intercept two consecutive signed messages?

If the messages are $m_1, m_2$ then we have signatures $(r_1,s_2),(r_2,s_2)$ such that:

$h(m_1) \equiv ur_1 + ks_1 \pmod{p-1}$

$h(m_2) \equiv ur_2 + (k+2)s_2 \pmod {p-1}$

$\Rightarrow s_1h(m_2) - s_2h(m_1) \equiv u(s_1r_2 - s_2r_1) + 2s_2s_1 \pmod {p-1}$

This is where I get stuck because I'm not sure what I can do here that is really that helpful. We don't know if $s_1r_2 - s_2r_1$ is coprime to $p-1$ so we can't immediately get $u$, but is it true that it would be coprime? If so how could you prove it? What concerns me the most is that this doesn't really seem to use the fact that the exponents used differ by $2$.

Any help would be greatly appreciated, thank you!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

We don't know if $s_1r_2−s_2r_1$ is coprime to $p−1$ so we can't immediately get $u$, but is it true that it would be coprime?

I don't believe coprimality is guarranteed, however we don't need it.

If they're not coprime, it means that there are multiple solutions to the linear equations we have; however:

  • The number of solutions are likely to be small; bounded by $\text{gcm}( s_1r_2−s_2r_1, p-1)$

  • We can list all those solutions efficiently

So, what we do is go through the list of possible $u, k$ solutions, plug each one into the $r_1 = g^k \pmod p$ relation, and see which one satisfies it; our work is done.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your response. I understand that in principle this would work but by what method are you finding possible $(u,k)$ solutions? I.e. how are you finding these candidates? $\endgroup$
    – user366818
    Apr 14, 2018 at 18:47
  • $\begingroup$ @user366818: first, let us simplify the linear equation to $au \equiv b \pmod n$, for known $a, b, n$ and which $a, n$ need not be coprime. This is equivalent to finding integer solutions to $au = b + zn$ in $\mathbb{Z}$; if we denote $g = \text{gcd}(a, n)$, then this is the same as $(a/g)u = (b/g) + z(n/g)$ (and if $b/g$ is not an integer, there are no solutions); we can find an initial solution $u_0$ (as $a/g$, $n/g$ are coprime); and the rest of the solutions are $u_0 + i (n/g)$ for $i \in \{0, 1, ..., g-1\}$ $\endgroup$
    – poncho
    Apr 14, 2018 at 19:23

Your Answer

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

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