3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Shouldn't it be $d = M \cdot y^k \bmod p$? $\endgroup$ – poncho Oct 24 '17 at 18:54
  • $\begingroup$ Yes, my mistake. Edited $\endgroup$ – Yevhen Vlasenko Oct 24 '17 at 19:10
  • $\begingroup$ Not really an answer to the question, but using the same key for signing and encrypting is asking for trouble. Signing and encryption keys require very different, and almost opposite, security practices. $\endgroup$ – Daffy Aug 21 '18 at 0:54
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Shouldn't the private decryption key and the private signature key be the same? That is $y=g^x$ and therefore $x = z$? $\endgroup$ – K.G. Oct 24 '17 at 19:36
  • 1
    $\begingroup$ @K.G. well, typically, if you are doing a sign-and-encrypt operation, you're signing with your own private key, and encrypting with someone else's public key. Apart from homomorphic schemes, it rarely makes sense to encrypt with your own public key; if you want something where the encryptor and decryptor are the same, there's little reason not to use symmetric crypto... $\endgroup$ – poncho Oct 24 '17 at 19:39
  • 1
    $\begingroup$ I agree 100% with your reasoning, but the question says $y=g^x$, which I should have said to begin with. $\endgroup$ – K.G. Oct 24 '17 at 19:52

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.