Questions tagged [elgamal-encryption]

ElGamal is a public key encryption scheme with security based on the discrete logarithm problem.

232 questions
44 views

ECIES/ ECDHE/ EC-ElGamal encryption comparison

I need to choose an encryption system, so I am trying to understand the differences between the existing options. I always find that people compare ECIES (Elliptic Curve Integrated Encryption Scheme) ...
41 views

How much more secure is $c = mg_1^r + g_2(g_1(g_1^r-1)/(g_1-1)) \mod p$ compared to just $c = mg_1^r \mod p$ (dis. log), all known but $r$?

To encode a message $m$ to a cipher $c$ you can use the only hard solvable problem of computing the discrete logarithm with a generator $g$ in base over a prime $p$. $c = mg_1^r$ mod p If an ...
210 views

Getting a key size of DSA/Elgamal certificate

I've tried to get a public key size of DSA/Elgamal PGP certificate. Using the Cleopatra I find out that there is actually two public keys - one with DSA with key ...
65 views

Proof of correctness of an ElGamal encryption given a specific public key

Suppose Alice sends an ElGamal encryption of a value $v$ to Bob (using either the normal or exponential version of ElGamal). E.g. assuming publicly-known $pk_{BOB} = h$ and a generator $g$, Alice ...
826 views

ElGamal encryption and signature using same keys

In ElGamal scheme we have message $M$; $p$, $g$ and $y=g^x \bmod p$ as public key where $x$ is unknown private key. Encrypted message $(c,d)$, where $c=g^k \bmod p$ and $d=M \cdot y^k \bmod p$. ...
43 views

Beginners question regarding ElGamal

How to motivate, that in ElGamal Alice the recipient keeps her keys fixed, while Bob the sender changes the key each time - why not both of them change their keys each time?
123 views

15k views

ElGamal with elliptic curves

I've searched some information on ECC, but so far I have only found Diffie-Hellman key-exchange implementations using ECC, but I don't want to exchange keys, I want to encrypt & decrypt data like ...
70 views

Give a CPA-attack on Elgamal when used with $\mathbb{Z}_p^*$

We know that if the decisional Diffie-Hellmann problem is hard then the Elgamal encryption is CPA-secure. One show that if the chosen group is $\mathbb{Z}_p^*$ then the decisional Diffie-Hellman ...
25 views

How to decrypt plain text x using man in the middle attack

Suppose Alice want to share a plain text $x = 5$ to Bob; using RSA, DHKE, and El-Gamal. My question is if Man-in-the-middle attack is applied then weather oscar can compute/decrypt plain text in all ...
56 views

Simplified ECC non-point public key example, how it works

I know that ECC public key is in fact point on curve calculated by $(x,y) = k \times G$ , while $k$ is random and $G$ is the base point, it performs "Point addition" which involves some math behind. ...
64 views

ElGamal variant

I came across this problem, while currently reading "Introduction to Modern Cryptography" by Katz and Lindell. I am new to crypto and just trying to go through the book and solve the exercises, ...
107 views

NIZK proof for cipher randomisation

Is it possible to contract NIZK proof that a cipher was randomised? Suppose Alice creates a cipher $c = \text{Enc}(m,r)$ and ZK proof that $c$ was formed correctly (for example, $\text{Enc}$ could ...
111 views

Non interactive ZKP that encrypted additive elgamal message is in set of valid messages

This is taken from Anonymous voting by two-round public discussion by F. Hao P.Y.A. Ryan P. Zielinski Votes are encrypted using the additive variant of ElGamal. I am also using ECElgamal. The idea is ...
105 views

Can I perform a division of two integers homomorphically using ElGamal?

How can I perform a division of two integers homomorphically? (Simplifying assumptions can be made if needed, that is, I am fine with dividing numbers that are whole and the result will be whole as ...
111 views

Verification of encryption for ElGamal cryptosystem

Suppose Alice wants to convince Bob that ciphertext c = (a, b) = (gr, m*hr) is some properly encrypted plaintext (not just random numbers). Obviously she can use zk-proof of discrete logarithm ...
67 views

El-Gamal like encryption, how can i guess the key?

There is $p$ (large prime number), $g$ (generator of $p$), and $x_a$, $x_b$, $r$ (which are between $1$ and $p-1$). I know $g^{x_a}$, $g^{x_b}$, $g^r$, $g^{x_a\cdot x_b\cdot r} \bmod p$. How can I ...
442 views

Secure ElGamal with OAEP

Is it possible to make ElGamal IND-CCA2 using OAEP or OAEP+? (OAEP+ from: "OAEP Reconsiderd" by Shoup) The reason I ask is that I recently answered this question and it came to my mind that OAEP or ...
85 views

Use of randomness in an Elgamal like encryption

Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and ...
75 views

Why $\alpha$ in ElGamal cryptosystem has to be a primitive root? [duplicate]

When choosing the public key for ElGamal, $\alpha$ must be chosen as a primitive mod p. What if $\alpha$ is not a primitive root ? How will it influence the encryption and decryption ?
84 views

213 views

ElGamal with weak public key

Assuming this setup: A prime $p$, a generator $\alpha$ in $\mathbb{Z}_p^\ast$. Alice chooses her private exponent $d$ from $[2, p-2]$ and calculates her public key $\beta$ = $\alpha^d$. Bob then ...
141 views

How to recover private key in ElGamal when random value k is known

Given following ElGamal encryption scheme: $\delta = M(\alpha^a)^k \mod{p}$. Assume that an attacker knows the random value $k$. How can he recover the private key $a$? I know that it's possible to ...