Questions tagged [elgamal-encryption]
ElGamal is a public key encryption scheme with security based on the discrete logarithm problem.
283
questions
-1
votes
0answers
24 views
Explain why you should not reuse the random choice of exponent used for encryption in the ElGamal cryptosystem [closed]
Explain why you should not reuse the random choice of exponent used for encryption in the ElGamal cryptosystem.
2
votes
2answers
65 views
ElGamal encryption security
Assume we have 2 prime numbers in form p = 2q + 1.
Is it safe to use the cyclic group of order p-1 instead of one with order <...
0
votes
0answers
42 views
Attack on ElGamal Encryption
Bob is holding a secret-bid auction using ElGamal encryption. He chooses a “safe” prime $p$ of sufficient size, a generator $g$ in $\operatorname{QR}(\mathbb Z_p)$ and a value $b$ in $[1, p]$. He then ...
0
votes
0answers
25 views
Is there an Elgamal implementation in javascript?
Does anyone know a good, well known implementation of ElGamal encryption and decryption in JavaScript?
I was told that Stanford Javascript Crypto Library https://github.com/bitwiseshiftleft/sjcl/ ...
0
votes
1answer
49 views
Why Bellare-Micali Oblivious Transfer Construction requires ElGamal with hashed key?
The idea of the Bellare-Micali Oblivious Transfer Constructions is the following:
Informally, the receiver is required to generate two public keys $y_b$, $y_{b-1}$ such that it knows only the secret ...
0
votes
0answers
33 views
How to determine if ElGamal message was a quadratic residue?
Consider the following ElGamal encryption (using a generator of $\mathbb Z^*_p$):
Key gen:
find a big prime $p$ and $g$ a generator of $\mathbb Z^*_p$.
choose $a\in \mathbb Z_{p-1}$ randomly and ...
0
votes
1answer
75 views
Breaking Elgamal private key
I have been given a task to explain if - given a public key and a portion of a private key (over 300bits) with a remain unknown of 80 bits - the private key can be broken with an algorithm faster than ...
0
votes
0answers
33 views
Is there a concept of Pedersen commitment “in the base”?
This question Can Elgamal be made additively homomorphic and how could it be used for E-voting?
says ElGamal can be made homomorphic over multiplication. So you can have $(g^r, h^r g^m)$ (i.e., ...
0
votes
0answers
46 views
ElGamal with massage hashed ind-cca secure?
It is well known that text book ElGamal is not IND-CCA secure, because an attacker can just have $$(Y,W)\leftarrow E_{x}(LR(M1,M2,b))$$ where M1, and M2 can be any message in the group, and than just ...
0
votes
1answer
47 views
ElGamal Decryption variant
I am trying to do some ElGamal encryption but having a different encryption formula.
For that I doing the following steps:
The key generator:
Choosing value $p = 107$ and $a = 2$
Random number $d = ...
0
votes
1answer
65 views
Elgamal Encryption: Why does Bob get to reuse his keypair while Alice has to generate a new one for every message?
From Christof Paar's book
The protocol consists of two phases, the classical DHKE (Steps a–f) which is followed by the message encryption and decryption (Steps g and h, respectively). Bob computes ...
2
votes
0answers
33 views
Why is confusion & diffusion not required PKI encryption schemes like Elgamal encryption?
The Elgamal encryption scheme is a Multiplicative Mask with the shared key. It doesn't seem to have any confusion or diffusion.
So why is it not necessary here as compared to Block Ciphers?
2
votes
1answer
94 views
Questions about Symmetric Encryption part of TLS
In TLS, we use DHKE for establishing the session key & then encrypt the actual communication with session key using symmetric encryption. While reading about DHKE, I learnt that you could use the ...
1
vote
0answers
69 views
0
votes
1answer
54 views
Is there a way to confirm that a homomorphic division (multiplication with inverse) using ElGamal produced the correct result?
By running some tests I observed that if I perform a homomorphic division (multiplication with the multiplicative inverse) between two values using the ElGamal scheme, I get the correct result when ...
1
vote
2answers
162 views
Adversary for attack on one variant of ElGamal
I came by the following question:
Consider the following variant of ElGamal encryption. Let $p= 2q+ 1$,
let $G$ be the group of squares modulo $p$ so $G$ is a subgroup of
$Z_p^*$ of order $q$, and ...
2
votes
1answer
71 views
How do I encrypt a long message using ElGamal encryption correctly?
According to ElGamal encryption, in order to encrypt a message I need to generate a shared secret s and after that I am to calculate ...
2
votes
1answer
187 views
Negative numbers with additive ElGamal
I'm trying to implement Private Set Intersection using the additive ElGamal public key encryption system. The code I've written can encrypt and decrypt numbers using the ElGamal system, so far so good....
0
votes
1answer
138 views
Number of operations for Elgamal cryptosystem
In page 408 of Hoffstein, Piper, and Silverman's Introduction to Mathematical Cryptography, it says
"Roughly speaking, in order to achieve $k$ bits of security,
encryption and decryption for ...
2
votes
1answer
104 views
Can Eve break this public key cryptosystem if she can solve DLP or DHP?
The PKC is in this way:
Alice and Bob fix a publicly known prime $p$, and all of the other numbers used are private (unless sent). Alice takes her message $m$, chooses a random exponent $a$, and ...
0
votes
0answers
38 views
Secure asymmetric encryption with 32byte ciphertext
I need securely asymmetrically encrypt the up to 16 bytes plaintext and receive up to 32 bytes ciphertext. I found that ElGamal produces ciphertext that is 2 times keysize. So I would need to use ...
0
votes
0answers
93 views
How can breaking the ElGamal encryption scheme break the Diffie-helman protocol?
I have been studying how ElGamal is a public-key algorithm built on top of the Diffie-Hellman key exchange but I got confused. How exactly could an attacker break the Diffie-Hellman protocol (i.e. ...
1
vote
1answer
53 views
Standard for asymmetric encryption based on elliptic curves
Most parts of public key cryptography has established standards which are in turn used in a large amount of real world applications. There is PKCS#1 for RSA based encryption and signatures and there ...
1
vote
0answers
31 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.
4
votes
1answer
189 views
How can I prove that ElGamal 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
21 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
178 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
222 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
255 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
168 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
104 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
67 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
55 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
212 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
132 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
486 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
946 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
189 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
266 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
58 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
50 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
54 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
248 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
131 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
178 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
913 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
157 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
115 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
52 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?
...
