Score:1

# 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.se] Is this HW question? Please indicate...
Score:1

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.

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:
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)
(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?
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?
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?
When Bob sends to Alice, \$y\$ is not Bob's static/permanent public key. It's Alice's static public key.
Yes in the classical Elgamal setting Bob would use Alices public key \$y\$ and his private ephemeral key \$x_b\$ to get the shared value \$K\$ (as in \$K = y^{x_b} \: mod\: p\$. But in this special case Alice can actually choose if Bob uses his Elgamal key Parameters \$p,\ g,\ y \$ or Alices \$p,\ g,\ y \$. She can switch between these two cases and send and receive messages that way. So assume a case where Bob then uses his static public key \$y\$. Can Alice extract it from \$c_2\$? Or somehow send a correctly encrypted message to Bob in this setting by switching between his or her public key parameters?
@Reideler but then if Bob uses his own \$y_b\$ instead of Alice's \$y_a\$, then Alice can't decrypt the message without knowledge of Bob's private key \$x_b\$. Even if Bob did this, knowing Alice would not be able to decrypt the message, Alice could still not learn \$y_b\$ from it.
@Reideler it might help if you were to consider that El Gamal encryption works because there is a Diffie-Hellman exchange going on inside it. If Bob does the DH with himself, the shared secret will be with himself and not with Alice.