Score:0

Crypto

Decrypting a ciphertext in ElGamal's cryptosystem

seboll13

2/25/23, 5:49 PM

I am a student in computer science currently working on a problem set in cryptography (practical problem but stuck on the math part).

Basically, suppose we receive a message that has been encrypted using ElGamal's crypto system and our goal is to decrypt and completely recover the message.

The initial plaintext is a sequence $p_1p_2\ldots p_m$. We are given a hashed version of the public key SHA256$(g^s)$ (so $s$ is the private key and $g^s$ the public one). For the encryption, it is said that an $r_1$ value is sampled uniformly at random and then for some given value $u\in\mathbb{Z}_q$, $r_i=u^{i-1}r_1$ for all the remaining $i$'s. The cipher text is then $c_i=(g^{r_i},p_ig^{r_is})_{i\in[m]}$.

Overall, we are given $p$, $q$, $g$, $u$, the hashed public key $H$ and the cipher text $c_i$ as a tuple.

The problem I have is that I don't really see what computations we have to do in order to recover the entire original sequence. One of the assistants told me to find some $p_i$'s and then use them to decrypt the cipher but I don't see where that brings me. The $r$'s are unknown and even if we know $g^{r_i}$, as we are given rather huge values, we can't compute the log.

I am a little lost here to be honest (I don't have an enormous background in algebra) so if someone has some advice on what I should do, I would truly appreciate it.

Thanks :)

146

0 + 0

elgamal-encryption

yacovm

2/25/23, 7:10 PM

But isn't the private key $s$? Can't you raise $g^{r_i}$ to the $s$ like in the regular scheme?

seboll13

2/25/23, 7:17 PM

@yacovm yes $s$ is the private key, but we don't know it so we can't do some computation with it. I guess the best solution would somehow be to find a way to know $r_1$ but I don't know how.

kelalaka

2/25/23, 9:19 PM

Could you first read https://en.wikipedia.org/wiki/ElGamal_encryption then tell us where did you fail?

yacovm

2/26/23, 7:10 AM

So you're trying to decrypt without knowing the private key? Is that the assignment?

seboll13

2/26/23, 8:20 AM

I guess I'm starting to think that we are missing some crucial elements in the problem statement (even though that's not the case). Indeed @yacovm we do not have access to the private key $s$. We only have access to a hash of $g^s$. The TA told us to guess some $p_i$'s but I don't really see how to do this.

seboll13

2/26/23, 8:22 AM

@kelalaka I guess that in our scenario we have to proceed a little differently than how the real decryption process works, that's partially why I am confused :p

fgrieu

2/26/23, 11:50 AM

What's the size of $p$, in bits or decimal digits? If that's small enough, there can be attacks. Also, is $(p-1)/2$ prime, or a composite with non-trivial factors?

seboll13

2/26/23, 2:57 PM

@fgrieu $p$ is a power of two, to be precise it is $2^{1024}$ so 309 digits. If I'm not mistaken, $(p-1)/2$ is not prime. I think that I'm close to something but computations with modulos is always quite challenging.

fgrieu

2/26/23, 2:59 PM

If $p$ is a large power of two, it's not prime, and $(p-1)/2$ can't be prime. Are you sure of this?

fgrieu

2/26/23, 3:24 PM

Ignoring what you said about $p$: I think the crux of the problem is that the $r_i$ are not random, as they should. Just to check that we got the equations right: you should be able to verify that $g^{r_i}=(g^{r_1})^{(u^{i-1})}\bmod p$ (notice that the $g^{r_i}$ are the first part of the ciphertexts). Now do something similar with the second part of the ciphertexts and you should be able to get all the $p_i/p_1\bmod p$. And then..

seboll13

2/26/23, 5:08 PM

@fgrieu I’m sure that p is not prime (that’s trivial) and pretty sure that (p-1)/2 is. I will be looking into what you say. But to clarify: $r_1$ is random, $u$ also is (uniformly random in $\mathbb{Z}_q$ and all the remaining $r_i$’s are generated based on $r_1$ and the preceding $u$. So the trick I believe is to somehow find some $r_i$ and go further from there.

Score:0

Crypto

Djagaz

2/26/23, 3:29 PM

You should try to find $r_{1}$. For this, try to see if there is a relation between $c_{i}$ and $c_{j}$, mostly between $g^{r_{i}}$ and $g^{r_{j}}$. Maybe you can find a $c$ such that $g^{c}=g^{r_{i}}/g^{r_{j}}$. Then you can compute $g^{s}$

0 + 0

seboll13

2/26/23, 5:10 PM

Thank you for your answer :) yes that was my main goal, in fact, finding a single $r_i$ is sufficient here because from there we can easily find $r_1$ and everything else. But, computations with modulos are quite tricky so I’m doing my best to work on this and find a solution.

Elon Musk

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

EN: Decrypting a ciphertext in ElGamal's cryptosystem

TH: ถอดรหัสข้อความเข้ารหัสในระบบเข้ารหัสของ ElGamal

RO: Decriptarea unui text cifrat în criptosistemul ElGamal

RU: Расшифровка зашифрованного текста в криптосистеме Эль-Гамаля

VI: Giải mã một bản mã trong hệ thống mật mã của ElGamal

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.