Join Log in
Score:1
avatar Crypto

Sending encrypted message without public key from recipient (elgamal)

hk flag
Reideler

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.

52
0 + 0
kelalaka avatar
in flag
kelalaka
Welcome to [cryptography.se] Is this HW question? Please indicate...
0
Reply
Score:1
knaccc avatar Crypto
es flag
knaccc

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.

0 + 0
hk flag
Reideler
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:
0
Reply
hk flag
Reideler
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)
0
Reply
hk flag
Reideler
(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?
0
Reply
knaccc avatar
es flag
knaccc
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?
0
Reply
hk flag
Reideler
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?
0
Reply
knaccc avatar
es flag
knaccc
When Bob sends to Alice, $y$ is not Bob's static/permanent public key. It's Alice's static public key.
0
Reply
hk flag
Reideler
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?
0
Reply
knaccc avatar
es flag
knaccc
@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.
0
Reply
knaccc avatar
es flag
knaccc
@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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.