Questions tagged [elgamal-encryption]
ElGamal is a public key encryption scheme with security based on the discrete logarithm problem.
260
questions
1
vote
0answers
21 views
Two ElGamal ciphertexts equivalence
Is there a way to prove that two ElGamal ciphertexts encrypt the same message with different public keys without knowing the private keys?
The prover is the producer of both ciphertexts.
3
votes
0answers
72 views
How can I prove that ElGmamal encryption in $\mathbb{Z}_p^*$ with OAEP padding is ind-CPA secure?
How I can prove that ElGamal encryption in $\mathbb{Z}_p^*$ with Optimal Asymmetric Encryption Padding (OAEP) is IND-CPA secure?
0
votes
0answers
20 views
Does reusing the same $R$ in Elliptic Curve ElGamal breach its security? [duplicate]
In Elliptic Curve ElGamal if I reuse the same randomness to get the same point $R$ for different messages, how can it breach its security ?
Can you please illustrate with an example?
Please see my ...
3
votes
1answer
133 views
How to secure Elliptic Curve ElGamal encryption against known plaintext attacks?
If I have an encoding function $f(x)$ that maps a message $m$ to a point $P$ on a suitable Elliptic Curve $E$ . If I have the public key $Q$ of my recepient then I can encrypt the message as follows:
...
0
votes
1answer
47 views
ElGamal Threshold Cryptosystem
Suppose we have a threshold ElGamal cryptosystem $(t, n)$ over an Elliptic Curve $E_p$, $p$ being a large prime, with the following parameters:
$G$ is a generator point of $E_p$ with order $q$
A ...
9
votes
2answers
2k views
What is largest prime factor in Diffie-Hellman?
I was reading the paper of A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms by TAHER ELGAMAL to better understand ElGamal public-key scheme, and he stated that for any ...
0
votes
0answers
67 views
What are the safe primes for $p$ and $q$ used in ElGamal?
I need to generate a 2048 bit key for ElGamal and I was looking for the $p$ and $q$ for PGP but I couldn't find them. the only thing I could find was this RFC but those are not safe primes.
Does ...
1
vote
1answer
79 views
Is it possible to perfom quadratic residues attack on elgamal cryptosystem?
I understand how this attack work on mental poker, but i am unable to see how can i apply it in Elgamal.
0
votes
1answer
43 views
Message space when using the group of QR's for El Gamal Encryption
My textbook states, that the DDH-assumption is not satisfied when we use the group
$\mathbb{Z}/p \mathbb{Z}$ and demonstrates an attack using Eulers Criterion. After that, it states that one should ...
3
votes
0answers
47 views
How to know if an ElGamal ciphertext is well-formed?
Is there a way to prove/verify that an exponential ElGamal ciphertext of a message representative $\widetilde{m}=mG$ is well-formed, meaning that $r_1 = r_2$ in:
$$C = (R, S) = (r_1G, \widetilde m + ...
0
votes
1answer
36 views
Retrieving ElGamal message with negative exponent value
Although the ElGamal scheme states that the message $M$ must be $1 \le M \le p-1$ in this paper: A Secure and Optimally Efficient
Multi-Authority Election Scheme they propose a method where the ...
0
votes
1answer
45 views
decrypting el gamal encrypted messages in regards to k being used
i am trying to understand the differences of using k in the following scenarios to better understand the protocol and most importantly the consequences of using such k.
so i wonder, some user, call ...
1
vote
1answer
82 views
EL Gamal Attack without a secret key
I have the following data where all the inputs are Big Integers,
group size $p$,
group generator $g$
public key of the receiver $y$
$c_1$ and $c_2$
Random Number as well
I am trying to execute an ...
2
votes
2answers
151 views
Construct another ciphertext that decrypts to same message without knowing key in Elgamal
I read about ElGamal from various resources and I was wondering if the following is true. Would appreciate if you could elaborate on it so I can understand better:
Is it possible to construct, given ...
6
votes
2answers
482 views
How to create an EC point from a plaintext message for encryption
It seems that ElGamal encryption is also possible for Elliptic Curve cryptography. However, that requires the user to convert the message to a point on the curve. What strategies are there to derive a ...
4
votes
0answers
74 views
Security properties of ElGamal encryption variants
I'll use Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (July 1985 in IEEE Transactions on Information Theory, formerly in proceedings of Crypto 1984) as ...
-1
votes
1answer
203 views
Randomness in Elgamel [closed]
Suppose that, instead of choosing r completely at random in ElGamal public key encryption, a lazy encryptor (Alice) derives it by following r′= 2r. Suppose also that Eve knows that Alice ...
1
vote
1answer
39 views
Are short ElGamal keysizes acceptable (1024-bit or lower) in cases where security is only necessary in a short timeframe
I am working on an efficient mental poker framework. I have implemented a functional and secure commutative encryption scheme based on ElGamal as described in:
http://groups.csail.mit.edu/cis/theses/...
2
votes
1answer
46 views
Does the discrete log assumption hold if k > p
In discrete log cryptosystems like ElGamal it is noted that the "private key" $k$ should be chosen as any element of the group $G$ i.e. $k < p-1$. Does the integrity of the cryptosystem rely on $k$ ...
1
vote
1answer
42 views
Retrieving correct ciphertext from additive ElGamal
I have been studying additive ElGamal and I think I have the hang of it except the part where the message $M$ must be retrieved by computing the discrete log of $g^M$.
From what I've read, the ...
1
vote
1answer
123 views
Understanding message reversible mapping function in group G
In ElGamal encryption, it says that the message M that is about to get encrypted must be mapped to its m counterpart in the group G using a reversible mapping function.
Map the message M to an ...
2
votes
1answer
98 views
Can Paillier ,RSA or any other schemes be used for universal re-encryption like elGamal?
ElGamal, RSA, and Paillier cryptosystem have homomorphic property, and can be used fro re-encryption purposes. I want to use the encryption to re-encrypt ciphertext(as in proxy re-encryption but ...
0
votes
1answer
75 views
How to compute ElGamal decryption by hand
Lets say that $u=3, x=5, v=2$, how do we work out $u^{-x}*v$, so $3^{-5} * 2$. I know how to work out the answer if it was $3^5 * 2$ but how do we do it with negative exponents?
0
votes
1answer
370 views
Proving the CCA-insecurity of El Gamal encryption scheme
I am trying to prove that El Gamal Encryption is not CCA-Secure.
If an adversary queried the encryption oracle for the encryption of $m=1$, he'll get a pair $(c_1,c_2)=(g^y,g^{xy}\cdot m)=(g^y,g^{xy}\...
1
vote
0answers
101 views
How can I prove that the plaintext of an elgamal ciphertext is the discrete log of an element?
Is there any (efficient) method to prove that the plaintext of an ElGamal ciphertext is the discrete log of an element?
In the scenario I concerned, I have an El Gamal key pair $(pk, sk) = (g^y, y)$....
2
votes
1answer
83 views
Post-quantum alternative to ElGamal? (public key verifiability)
Are there any alternatives to ElGamal that would be resistant/annoying to quantum machines?
I would like to preserve public key derivability/verifiability -- ability to ensure existence of ...
1
vote
0answers
49 views
ElGamal: different message with equal length random key [closed]
This situation applies to ElGamal digital signatures: consider messages m1 and m2 which we will encipher with a random key. The random key has the same Hamming weight. Is this situation secure? Why?
...
2
votes
0answers
65 views
Intuition for Cramer Shoup Encryption Scheme?
I was reading the Cramer Shoup CCA2 secure encryption scheme. The scheme is as follows.
Public key = $(g_1, g_2, c, d, h, hk)$, where $c = g_1^{x_1}g_2^{y_1}$, $d = g_1^{x_2}g_2^{y_2}$, $h = g_1^z$, ...
2
votes
2answers
89 views
Whats wrong with my El Gamal signature example
I'm trying to digitally sign a message m using El Gamal. So far I've been unable to verify the digital signature ive made using El Gamal.
I am using prime number, p = 8369. prime root g = 3031. ...
4
votes
1answer
298 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) ...
0
votes
1answer
44 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 ...
1
vote
1answer
253 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 ...
0
votes
0answers
48 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?
2
votes
1answer
324 views
find $a$ and $k$ for a given el gamal cryptosystem
I am given this question:
Suppose Alice is using the ElGamal Signature scheme with parameters
$p = 31847$, $\alpha = 5$, and $\beta = 25703$
Assuming that we have received signed messages
$(x_1,(\...
0
votes
0answers
63 views
ElGamal re-encrypts data
I try to learn ElGamal re-encrypts scheme and I have a question about the example: How is a re-encryption done with elGamal?.
The $g$ value of Alice must be the same as $g$ value of Bob or not?
And ...
5
votes
3answers
1k views
How to verify if g is a generator for p?
For learning purpose, supposed I have a 16-digit prime which is 2685735182215187, how do I verify if g is a generator? (p is supposedly a special kind of prime)
0
votes
1answer
320 views
El Gamal Cryptosystem Proof, Step-by-Step Explanation Needed. I feel like I don't understand what I have on this proof
Can someone provide a good and thorough explanation of the El Gamal proof? Basically, I need a step-by-step breakdown of what is happening at each important part in the algorithm.
I haven't been able ...
3
votes
1answer
399 views
Diffie-Hellman private key recover with non-prime modulus
Say we have a classic Diffie-Hellman key exchange. We have the following parameters of a public key:
p,g,y
Where $p$ is the modulus, $g$ is the base, $y$ is the ...
3
votes
1answer
164 views
Elgamal problem on $\mathbb{QR}_p$ with $p$ a safe prime
I need some orientation to solve the following problem:
Let $p = 2q+1$ be a safe prime and $s(x)$ the smallest of the two square roots of $x$ modulo $p$. Then:
Determine the distribution of $s(g^{ab}...
1
vote
1answer
184 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 ...
0
votes
0answers
46 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 ...
0
votes
1answer
95 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.
...
2
votes
1answer
300 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, ...
2
votes
1answer
181 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 ...
2
votes
0answers
74 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 ...
3
votes
1answer
194 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 ...
4
votes
0answers
109 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 ...
2
votes
1answer
166 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 ?
2
votes
1answer
96 views
Does this scheme break under a DHP adversary?
Consider the following cryptography scheme:
We are given a prime $p$.
Alice wants to send the plaintext $m \pmod p$ to Bob.
Alice chooses $a$ s.t. $\text{gcd}(a,p-1)=1$, and sends Bob, $u = m^a \...
2
votes
1answer
78 views
Usefulness of OAEP with ECC
Does OAEP make sense for use in an ECC ElGamal cryptosystem? The way I see it, OAEP makes questionable sense even for RSA because even though it's a "all or nothing" transformation, many RSA ...
