3
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ 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? $\endgroup$
    – poncho
    Commented Feb 19, 2017 at 18:00
  • $\begingroup$ 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. $\endgroup$
    – KevinJ
    Commented Feb 20, 2017 at 11:31
  • $\begingroup$ "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? $\endgroup$
    – poncho
    Commented Feb 20, 2017 at 13:13
  • $\begingroup$ 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. $\endgroup$
    – KevinJ
    Commented Feb 20, 2017 at 18:45
  • $\begingroup$ 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...) $\endgroup$
    – poncho
    Commented Feb 20, 2017 at 20:40

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\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.