0
$\begingroup$

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$?

$\endgroup$

1 Answer 1

0
$\begingroup$

$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.

$\endgroup$
9
  • $\begingroup$ Ah thanks. If I had understood that q and g are considered public knowledge, this is exactly what I would have done. $\endgroup$
    – Public IP
    Apr 30, 2022 at 0:18
  • $\begingroup$ What if we were to introduce modulo? $\endgroup$
    – Public IP
    Apr 30, 2022 at 0:25
  • $\begingroup$ "In the group" means modulo the order of the group. E.g. the inversion of $s_1$ is done modulo $q$ $\endgroup$ Apr 30, 2022 at 0:27
  • $\begingroup$ 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? $\endgroup$
    – Public IP
    Apr 30, 2022 at 0:36
  • $\begingroup$ Sorry, I just forgot to write the power of $x$. Fixed :) $\endgroup$ Apr 30, 2022 at 1:36

Your Answer

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

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