1
$\begingroup$

Suppose Alice encrypts a number π‘₯ which indicates her bid on a contract, using textbook ElGamal encryption (malleable). This encryption of π‘₯ produces a ciphertext pair 𝑐1 and 𝑐2.

How can Eve modify 𝑐1 and 𝑐2 to make it a modified value of π‘₯2 which is an arbitrary value of π‘₯? (eg. 1% more than x)

For a modified message two times of π‘₯, I know that the modified ciphertext pair would be (𝑐1, 2 * 𝑐2). As seen here in this lecture.

But what about arbitrary values?

$\endgroup$
6
  • $\begingroup$ So you have an example of how to modify the ciphertext to double the plaintext. Do you know why that works? $\endgroup$
    – Mikero
    Commented Feb 18, 2022 at 18:34
  • $\begingroup$ What made you think your approach will not work? If you apply the decryption operation to your ciphertext $(c_1, 10 \cdot c_2)$, what plaintext will you get? $\endgroup$
    – Morrolan
    Commented Feb 18, 2022 at 19:14
  • 1
    $\begingroup$ You forgot the reduction modulo the prime. $10 * 6 = 60 \equiv 2 \pmod{29}$. As ElGamal operates over a finite group $\mathbb{Z}_p$, one has to take care to stay within the confines of this group. $\endgroup$
    – Morrolan
    Commented Feb 18, 2022 at 20:06
  • 1
    $\begingroup$ Exactly. In this case there's only 28 possible plaintexts and ciphertexts, which we would commonly associate with the numbers $\{1, 2, \ldots, 28\}$ $\endgroup$
    – Morrolan
    Commented Feb 18, 2022 at 20:27
  • 1
    $\begingroup$ With straight ElGamal in $\mathbb Z_p^*$, knowing the public key and parameters, and a ciphertext for $x$, and under the assumption $x$ is a multiple of $100$ and sizably less than the public modulus, there is a simple method to build a ciphertext which when deciphered yields $x'$ equal to 1% more than $x$. Hint: express the ratio $x'/x$. $\endgroup$
    – fgrieu
    Commented Feb 21, 2022 at 18:33

1 Answer 1

0
$\begingroup$

If you have $c=E(r_1, m)$ you can multiply it with $E(r_2, 1)$ and then you have : $$c' = E(r_1, m)E(r_2, 1)=(g^{r_1}, my^{r_1})(g^{r_2}, y^{r_2}) = (g^{r_1+r_2},my^{r_1+r_2}) = E(r_1+r_2,m)$$ So you just got an ecryption $c'$ of the very same message $m$ but with different secret key $r_1+r_2$ without even knowing the initial secret key $r_1$

$\endgroup$

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.