# Sending encrypted message without public key from recipient (elgamal)

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.

• Welcome to Cryptography Is this HW question? Please indicate... May 18 at 18:32

• 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) May 18 at 18:35
• (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? May 18 at 18:36
• 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? May 18 at 18:53
• 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? May 18 at 19:27