Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In ElGamal scheme we have message $M$; $p$, $g$ and $y=g^x \bmod p$ as public key where $x$ is unknown private key.
Encrypted message $(c,d)$, where $c=g^k \bmod p$ and $d=M \cdot y^k \bmod p$.
Signature $(r,s)$, where $r=g^k \bmod p$ and $s=(M - xr)\cdot k^{-1} \bmod p-1$
If $c=r$ then message encrypted and signed with the same $k$.
Is there a possibility to obtain private key $x$?
Is there a possibility to obtain private key $x$?
No; here's the proof.
Suppose we had a black box that, given $c = g^k, d = M \cdot y^k, r = g^k$ and $s = (M - xr) \cdot k^{-1} \bmod p-1$ (and we'll throw in $M$, and $z : y = g^z$), is able to give us $x$.
Then, here's how we can find the private key given an ElGamal signature.
We have $M, r = g^k$ and $s = (M - xr) \cdot k^{-1} \bmod p-1$ (as that's the ElGamal signature and message being signed).
That also gives us $c$. To get $d$, we select a random $z$ and compute $d = M \cdot c^z = M \cdot y^k$.
We now have everything the Oracle expects; we pass in everything, and we recover $x$.
As we believe that deriving the ElGamal private key from a signature is infeasible, we believe there cannot be such a black box.
