1
$\begingroup$

assume Bob and Alice use Elgamal encryption scheme. Alice wants to send Bob a message, but does not know Bobs public key. Is there a way for Alice to find out Bobs public key by receiving multiple message pairs C1 (ephemeral key) and C2 (message) from Bob? Alice can easily decrypt Bobs messages, as from Bob to Alice the shared K is known by Alice. But Alices messages to Bob cannot be correctly decrypted by Bob, as the messages were not created by using Bobs public key but a random number.

Thanks for any help.

Improve this question
$\endgroup$
1
  • $\begingroup$ Welcome to Cryptography Is this HW question? Please indicate... $\endgroup$
    – kelalaka
    May 18, 2022 at 18:32

1 Answer 1

Reset to default
1
$\begingroup$

If Bob was using an ephemeral key pair when encrypting for Alice, then Bob would need to send his permanent public key as the message in order for Alice to receive it. There is no way Alice could learn anything about Bob's permanent public or private key if Bob did not use either of them when sending to Alice.

If Bob used his permanent key pair to encrypt for Alice, then obviously C1 in the message would be Bob's permanent public key.

If Bob keeps a record of his ephemeral keys, Alice could simply use one of Bob's C1 public keys in order to encrypt something to send back to Bob, and Bob would decrypt it using the ephemeral private key that he had retained from a prior transmission.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thank you for your answer. Bob always uses a new ephemeral public key. But Alice knows p and g used for Bobs public and private keys. Alice gets the following two ciphertexts: $\endgroup$
    – Reideler
    May 18, 2022 at 18:19
  • $\begingroup$ Sorry, hit enter too fast and comment was gone. Bob always uses a new ephemeral public key and doesn't keep a record. But Alice knows p and g used for Bobs public and private keys. I don't know if this helps any way, but Alice can control if Bob uses his key parameters $p,\ g,\ y $ or Alices $p,\ g,\ y $ to encrypt his messages to Alice ($y$ is static public key). So Alice can get the following two ciphertexts where she doesn't know Bob's secret ephemeral key $ b_x $ but all the other parameters. It's possible for the to keep $ p,\ g,\ m$ and $ y $ the same. (See next comment) $\endgroup$
    – Reideler
    May 18, 2022 at 18:35
  • $\begingroup$ (see previous comment) $$ c_1 = g^{x_b} \: mod\: p \\ c_2 = m\: y^{x_b}\: mod\: p $$ I know that DLP is the foundation of Elgamal, but is there a way to calculate $ x_b $ or is having two DLP equations no different to having one DLP? Or can Alice get Bobs static $y$ from $c_2$ somehow? $\endgroup$
    – Reideler
    May 18, 2022 at 18:36
  • $\begingroup$ What you've just written looks like how Bob will use his ephemeral private key $x_b$ to send a message to Alice using Alice's public key $y$. No, it's definitely not possible for Alice to determine $x_b$ due to the DLP. But even if she could, how does it help for Alice to know Bob's ephemeral private key? She wants to know Bob's permanent public key so she can encrypt something to send to him. If Bob needed no knowledge of his own permanent key pair in order to send to Alice, how could Alice possibly learn anything about something that Bob may not even have known? $\endgroup$
    – knaccc
    May 18, 2022 at 18:53
  • $\begingroup$ I thought maybe getting $x_b$ is easier than directly going for $y$. Because $y$ is always Bobs static key, which is what Alice is after. I summarize: Alice can get as many of those message pairs as she wants back from Bob. The parameters $ p,\ g,\ m$ and $ y $ are constant throughout all these message pairs. The $y$ in $c_2$ is Bobs static key, the necessary variable for Alice to correctly encrypt a message to Bob. $$ c_1 = g^{x_b} \: mod\: p \\ c_2 = m\: y^{x_b}\: mod\: p $$ So I'm wondering is there no way to get Bobs $y$ from these equations by having multiple pairs of them? $\endgroup$
    – Reideler
    May 18, 2022 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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