Score:0

Crypto

ElGamal same private and random key attack

Public IP

8/29/23, 11:40 PM

I'm having difficulty understanding this.

Consider two messages are encrypted using the same cyclic group order $q$, generator $g$, private key $x$, and random parameter $y$. The attacker knows a plaintext $m_1$ and its corresponding ciphertext $c_1=\left(r_1,s_1\right)$.

I was told that, under these circumstances, if an attacker also knows the ciphertext $c_2=\left(r_2,s_2\right)$ of another message $m_2$, they can recover $m_2$.

How is this possible? Wouldn't the attacker need to know $q$ and $g$?

0 + 0

elgamal-encryption

elgamal-signature

Score:0

Crypto

meshcollider

8/30/23, 12:15 AM

$q$ and $g$ are usually assumed to be public knowledge - they are known as public parameters (or are part of the users' public keys).

If the same random value $y$ is used for both messages, then $r_1 = r_2 = g^y$.

Then we know that $s_1 = (r_1^x) \cdot m_1$ and $s_2 = (r_1^x) \cdot m_2$.

Thus the attacker can compute $$m_2 = \frac{s_2}{s_1}m_1$$ in the group.

0 + 0

Public IP

8/30/23, 12:18 AM

Ah thanks. If I had understood that *q* and *g* are considered public knowledge, this is exactly what I would have done.

Public IP

8/30/23, 12:25 AM

What if we were to introduce modulo?

meshcollider

8/30/23, 12:27 AM

"In the group" means modulo the order of the group. E.g. the inversion of $s_1$ is done modulo $q$

Public IP

8/30/23, 12:36 AM

I guess I'm not understanding. For example $m_1=s_1\times\left({r_1}^x\right)^{-1}\mod q$. How did you get $s_1=r_1\times m_1$ from that?

meshcollider

8/30/23, 1:36 AM

Sorry, I just forgot to write the power of $x$. Fixed :)

Public IP

8/30/23, 3:16 PM

What about the inverse?

meshcollider

8/30/23, 6:54 PM

What do you mean?

Public IP

9/1/23, 12:42 AM

$\left(r_1^x\right)^{-1}$

meshcollider

9/1/23, 3:57 AM

Yes, what about it? It's the same as what I wrote, but inverted. I'd encourage you to expand out the details if you're not sure, and see that it all cancels.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: ElGamal same private and random key attack

TH: ElGamal การโจมตีด้วยคีย์ส่วนตัวและสุ่มแบบเดียวกัน

RO: ElGamal același atac cu cheie privată și aleatorie

RU: ElGamal та же атака с закрытым и случайным ключом

VI: ElGamal cùng một cuộc tấn công khóa riêng và ngẫu nhiên

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.