Questions tagged [elgamal-encryption]
ElGamal is a public key encryption scheme with security based on the discrete logarithm problem.
242
questions
1
vote
1answer
9 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
43 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 ...
-1
votes
0answers
35 views
What are the potential risks and deficiencies of the ElGamal Algorithm?
I have been studying the ElGamal encryption and read a modified version of it that caters a multi-sender single recipient scenario.
Attached here are the encryption and decryption formula.
...
0
votes
1answer
44 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
74 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
66 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
58 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
37 views
ElGamal: different message with equal length random key
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
31 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
64 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. ...
3
votes
1answer
117 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
43 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
108 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
47 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
159 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
51 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
818 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
0answers
15 views
I2P Tunnel Creation Build on Request Record Question en(de)cryption method
Not sure if anyone here can help, but if so, sure would appreciate the help.
If we read the https://geti2p.net/spec/tunnel-creation documentation page on how I2P creates a tunnel, we can read on the ...
0
votes
1answer
105 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
283 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
133 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
94 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
29 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
84 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
146 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
121 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
69 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
140 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
90 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
101 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
89 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
68 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 ...
0
votes
1answer
48 views
Given paramaters of an Edward's curve and x, determine a y value if it exists
I'm making a demonstration cryptosystem using ECC ElGamal. I've currently got a working implementation of Edward's Curve operations and a basic ElGamal implementation (Encrypts only points on the ...
5
votes
2answers
315 views
How to securely map messages to points on an elliptic curve
I'm implementing a demonstration hybrid cryptosystem in Python (FinCrypt, I know the name is bad) and I'm migrating over from my Weierstrass curve implementation, which was based off of this, to one ...
2
votes
0answers
190 views
Chinese Remainder Theorem and Elgamal
I am studying an encryption scheme which is Elgamal-like where I think CRT can help optimise the encryption and decryption but I am not sure if I am applying CRT the correct way.
I have a cyclic ...
0
votes
1answer
101 views
Is this problem still as hard as discrete logarithm (modified ElGamal)?
I am trying to find a vulnerability or proof for the following problem:
ElGamal part.
Given $g\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$, select randomly $k\in\mathbb Z_p$ and calculate ...
1
vote
1answer
79 views
For ElGamal-based key encapsulation, is it necessary to hash before using as AES key?
I'm working with SJCL, specifically using ElGamal to encrypt messages. Behind the scenes, this is doing something similar to what's described in this SO post (emphasis mine):
Regardless how big ...
4
votes
0answers
134 views
Indistinguishability vs fixed bit-length
Suppose there is a cyclic group $\mathbb{G}$ of prime order $q$ of elements in $Z^{∗}_p$ with a generator $g$ and values $a,b,c,d \in Z_q$.
There is also an equation $g^{ab} = g^{cd}$, where $a,b,c$ ...
1
vote
1answer
156 views
What is an example of elgamal homomorphic double encryption?
I am looking for such an cipher algorithm that is based on assymetric cryptography where the order of encrypting is irrelevant.
For example:
There is a message "x", Bob encrypt that message with his ...
3
votes
3answers
328 views
Zero-knowledge transfer of value protocol inspired by EC El Gamal
This is a follow up on the question I asked here. I designed a scheme that allows the following:
Alice has a value $a$ which she wants to keep secret
Bob has a value $b$ which he wants to keep secret
...
2
votes
0answers
149 views
Is EC El Gamal the only option?
This question is related to the question I asked here. I'm looking for encryption scheme with the following properties:
Given $m$ is a 256-bit value, $pub_a$ and $pub_b$ are public keys, and $priv_a$ ...
1
vote
1answer
167 views
Commutative homomorphic encryption for zero-knowledge transfers
I am trying to design a scheme that would allow the following:
Alice has a number $a$ which she wants to keep secret
Bob has a number $b$ which he wants to keep secret
Alice can "transfer" a number ...
5
votes
1answer
226 views
How to encode messages in $\Bbb Z_p^*$ to be encrypted with ElGamal scheme?
In ElGamal encryption scheme, in order to achieve IND-CPA security, one must use a group where the DDH problem is assumed to be hard. As this answer suggests, one way to achieve that is the following:
...
3
votes
1answer
331 views
ElGamal ciphertext lenght
I'm studying for an exam and answering practice questions and I would love clarification on something. Apologies if it seems really simple.
My lecture notes indicate that for ElGamal:
the ...
0
votes
1answer
136 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 ...
1
vote
2answers
82 views
Implementing commitments and challenges for a distributed ElGamal encryption scheme
I am trying to implement a distributed encryption system by having as a main source of information this book (Introduction to Cryptography by Delfs and Knebl) and this Internet article (More Mix than ...
1
vote
0answers
113 views
Is it possible to re-cipher with Paillier?
I know that with ElGamal we can re-cipher and get a second ciphertext equal to the first.
Is it possible with Paillier too?
When saying "re-cipher", I mean "A sends me a message, that is encrypted ...
1
vote
1answer
384 views
How to recover secret $x$ from Elgamal signatures with repeated $k$?
Set generator $g \equiv 5 \pmod p$ where $p=647$ and $p$ is prime.
With the same $g$, $p$ and secret signing key $x$, Alice sends two messages, $428$ and $129$, with signatures $(433, 239)$ and $(433,...
0
votes
1answer
153 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 ...
0
votes
1answer
254 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 ...
