1
$\begingroup$

Is there a known algorithm to recover the sender's messages in ElGamal $\mathbb{F}_p^*$ if the ephemeral key is held constant in two or more transmissions, assuming the messages are always distinct?

Say Alice picks a prime $p$ between $2^{1000}$ and $2^{1001}$ and chooses a $g \in \mathbb{F}_p^*$ with large prime order. $L$ is her public key. Doug the doofus sends Alice two or more transmissions $(c_1, c_i), c_1 = g^k (mod\,p), c_i = m_{i}L^k (mod\,p) i = 1,2,...,n$ with $k$ held constant. Can Eve the eavesdropper recover Doug's messages?

IOW, why does the ephemeral key need to be ephemeral?

$\endgroup$
1
  • $\begingroup$ If $m_1 = m_2$ then the two ciphertexts will be identical, which Eve can certainly see. Even if not, Eve can compute $m_2/m_1$ or similar combinations. It doesn't directly leak $m_1$, but if Eve ever sees $m_2$ later on then she can recover $m_1$ from the quotient. $\endgroup$
    – user2552
    Commented Jul 27, 2015 at 14:50

1 Answer 1

2
$\begingroup$

One thing Eve can do is compute the modular division of any two messages.

That is, she is given both $c_2 = mL^k$ and $c'_2 = m'L^k$; she can then compute the value $c_2\cdot c'^{-1}_2 = m\cdot m'^{-1}$.

Whether this, in itself, is sufficient to recover the messages depends rather on the distribution of Doug's messages. However, what this means (independent of the distribution) is that if Eve has a guess for the plaintext for any of the messages, she can immediately deduce the plaintext for all the other messages.

Note that this similar system IES doesn't share this problem; if Doug repeats all the parameters, well, it will leak if he resends identical plaintexts; however it will still be secure otherwise.

$\endgroup$

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.