# ElGamal: Why is reusing the same $k$ not secure?

I have a question on the encryption process of ElGamal: $$Y = g ^ a \bmod p \\ C = g ^ k \bmod p \quad\text{(k is chosen randomly)} \\ D = m \cdot y ^ k \bmod p \\ \text{Decryption:}\qquad m = C^{(p-1-a)}\cdot D\bmod p$$

My professor told us we should know why it's bad to use the same values for the variables $a$ and $k$ more than once, but he didn't say why. I guess that if the same values for $a$ and $k$ are used several times, the attacker could calculate the unknown values if he is able to capture the traffic, but I don't know how.

How could an attacker proceed there?

• Hint: suppose that attacker captured two encrypted values with the same $k$, and he knows the corresponding plaintext to one of them; what can he determine about the plaintext of the other? Commented Feb 19, 2017 at 18:00
• Maybe I'm wrong but I don't really get the point. In ElGamal the variables (p, g and y) are public and if you send an encrypted message m you also send d and c. So you could calculate the k even if you haven't intercepted a 2nd message (to calc. k you solve g^k = c mod p). And even when you get a 2nd message encrypted with the same k, the problem you have to solve didn't get easier (it's the same mod p). The only problem by using the same k more than once is in my opinion that if the attacker had captured more messages and he get the k he could decrypt all other messages. Commented Feb 20, 2017 at 11:31
• "to calc. k you solve g^k = c mod p"; could you give a summary of how you would solve this equation, assuming p was a 2048 bit prime? Commented Feb 20, 2017 at 13:13
• With a 2048 bit prime it's nearly impossible the only possibility I see is by splitting it to the subset (p-1) and using the Chinese Remainder Theorem. But also with this it's nearly impossible. And there I don't understand the specification of not reusing the same k. Because even if you use the same k the probability of solving k doesn't change. Commented Feb 20, 2017 at 18:45
• Yes, reusing a value $k$ doesn't help the attacker learn $k$; however what if the attacker was interested in learning something other than $k$? What if he was interested in (say) the plaintext? (See my hint...) Commented Feb 20, 2017 at 20:40

In ElGamal encryption like you said for unknown $$m_1$$ and known $$m_2$$ we have:
$$m_1: C_1=g^k\ mod\ p,\ D_1=m_1.g^{a.k}$$
$$m_2: C_2=g^k\ mod\ p,\ D_2=m_2.g^{a.k}$$
$$k$$ is the same in both encryptions, by dividing $$D_1$$ and $$D_2$$ we have:
$${D_1\over D_2}={m_1\over m_2} => D_1.m_2 = D_2.m_1$$
$$m_2$$ , $$D_1$$ and $$D_2$$ and are known so now we can calculate $$m_1$$. This is how can attacker proceed and find unknown $$m_1$$.