Assume that Alice uses Bob’s ElGamal public key ( = 2, Yb = 8) to send two messages $M = 17$ and $M' = 37$ using the same random integer $k = 9$. Eve intercepts the ciphertext and somehow she finds the value of $M = 17$. Show how Eve can use a known-plaintext attack to find the value of $M’$.

  • 1
    $\begingroup$ What are your thoughts? What have you tried? Sounds like an exercise. We're not here to do your exercise for you; this is not a site where you can paste your exercise and we'll solve it for you. Instead, we expect you to make a serious effort, to show us what you tried in the question, and to formulate a specific question about a specific aspect of the problem or your approach. $\endgroup$ – D.W. Jul 28 '14 at 22:58

Your parameters that you provide are incomplete (in what group are you working?).

Anyways, lets assume that you work in $\mathbb{Z}_p^*$, your have a generator $g$ and your public key is $y=g^x$.

Then, if two ciphertexts share the same randomness $k$, they will look like $(c_1,c_2)=(g^k,m\cdot y^k)$ and $(c_1',c_2')=(g^k,m'\cdot y^k)$ for your two messages $m$ and $m'$. So as you know that let say for the first ciphertext the message is $m$, then you can compute the inverse $m^{-1}$ of the message $m$ in $\mathbb{Z}_p^*$ and can find $y^k=c_2\cdot m^{-1}$. Now, as you have $y^k$ (which you can clearly also invert in $\mathbb{Z}_p^*$) and both ciphertexts share the same randomness $k$, you can easily obtain $m'$ from $c_2'$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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