Join Log in
Score:0
avatar Crypto

Malleability of El Gamal encryption

cn flag
Lawrence Meigs

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 can 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, https://www.cs.umd.edu/~gasarch/COURSES/456/F18/lec25/lec25.pdf)

But what about arbitrary values?

117
0 + 0
us flag
Mikero
So you have an example of how to modify the ciphertext to double the plaintext. Do you know *why* that works?
0
Reply
Morrolan avatar
ng flag
Morrolan
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?
0
Reply
Morrolan avatar
ng flag
Morrolan
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.
1
Reply
Morrolan avatar
ng flag
Morrolan
Exactly. In this case there's only 28 possible plaintexts and ciphertexts, which we would commonly associate with the numbers $\{1, 2, \ldots, 28\}$
1
Reply
Morrolan avatar
ng flag
Morrolan
Regarding your edit: Mind that messages and ciphertexts must be group members. So it makes little sense to talk about "arbitrary values" such as "1% more than $x$", as this is not well-defined in this context. Mathematically it makes little sense as it conflates the multiplicative group operation with the multiplication over the reals, but also intuitively it is clear that e.g $1.01 \cdot 6 = 6.01$ is not a member of $\{1, 2, \ldots, 28\}$.
0
Reply
fgrieu avatar
ng flag
fgrieu
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$.
0
Reply
Score:0
tonythestark avatar Crypto
vi flag
tonythestark

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$

+ 0
ธงชาติไทย
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.