Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
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. –  D.W. Jul 28 at 22:58

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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