Elgamal is a public key encryption scheme and signature scheme with security based on the discrete logarithm problem.
8
votes
2answers
565 views
Are any of the major asymmetric ciphers distinguishable (EG, RSA, ECC) ?
Related to this question.
Given ciphertexts generated by any of the major asymmetric ciphers (RSA, ElGamal, ECC, etc..) can these ciphertexts be distinguished from random noise? Justify why, why ...
6
votes
3answers
270 views
Mapping between subgroups and the integers
This question is a companion to the equivalent question on elliptic curves.
Preliminaries
Diffie-Hellman, Elgamal, DSA, etc. are examples of protocols that work in the integers modulus a large prime ...
5
votes
2answers
211 views
Besides key and ciphertext sizes what are other advantages of elliptic curve versions of various protocols?
There are elliptic curve variants of Diffie-Hellman, ElGamal, DSA and possibly other protocols/algorithms. I know that these elliptic curve variants have smaller key and ciphertext sizes which will ...
5
votes
1answer
345 views
How can one show that an ElGamal-like signature verification scheme is valid?
For an ElGamal-like signature scheme, I am given two things:
The signing function,
the verification function.
How can I show that the verification function is valid?
Example 1:
Signing: $s := ...
4
votes
1answer
451 views
Why is ElGamal considered non-deterministic?
One difference between RSA and ElGamal is that ElGamal isn't necessarily deterministic (while RSA is).
What makes it non-deterministic? Is this advantageous to security? How else does this property ...
4
votes
2answers
355 views
Random Coin Flip using ElGamal and a Trusted Party
An old exam question I am trying to figure out:
Consider the following protocol for two parties to flip a fair coin.
Trusted party T publishes her public key pk
A chooses a random bit ...
4
votes
3answers
571 views
ElGamal: Multiplicative cyclic group and key generation
Here on the ElGamal wikipedia page http://en.wikipedia.org/wiki/ElGamal_encryption
Alice generates an efficient description of a multiplicative cyclic group G, of order q, with generator g.
How ...
4
votes
2answers
811 views
How to calculate the time it'll take to crack RSA or DH?
Sometimes the easiest way to describe security of a type of cryptography is to say that "the time it takes to solve for an x-bit key would be y years". How would one go about doing such a calculation ...
4
votes
2answers
3k views
When to use RSA and when ElGamal asymmetric encryption
If i am not wrong in cryptography there are 2 basic cryptographic schemes for public key cryptography. RSA encryption whose security is based on the infeasibility of solving the factoring of big ...
4
votes
1answer
719 views
ElGamal Signature Scheme: Recovering the key when reusing randomness
Show how if Alice uses the same value of $k$ to sign two different messages $m_1$ and $m_2$, using the ElGamal signature scheme, Eve can recover the value of $a$ from the corresponding signatures ...
4
votes
1answer
487 views
How to securely use Elgamal encryption in libgcrypt?
How secure is libgcrypt's Elgamal implementation of encryption (how different it is from textbook Elgamal), and how can I tweak padding and other preprocessing actions?
For example, I know that usign ...
4
votes
2answers
367 views
ElGamal signature without calculating the inverse
Last time I asked a question of this type on math.se it was redirected here, so I hope this one is also appropriatete for crypto.se.
I stumbled uppon this question in some textbook.
Propose a ...
4
votes
2answers
322 views
Using bad generator in ElGamal Encryption
Suppose Alice chooses a random Prime $p$ and a random private Key $a \in \mathbb{Z}^*_p$. By accident, she also chooses a random number $g \in \mathbb{Z}^*_p$, which is not a generator of ...
3
votes
2answers
235 views
Malleability of ElGamal and Hashed ElGamal
Question: Suppose A encrypts a number $x$ which indicates her bid on a contract, using ElGamal encryption. Say that the encryption of $x$ produces a ciphertext $c$. Explain how E can modify $c$ to ...
3
votes
1answer
60 views
Chosen ciphertext insecurity in an ElGamal variant
I'm trying to prove something and if I can show that there is a simple way to calculate $(g^a \bmod p)^k$ if I know both $g^k \bmod p$ and $g^a \bmod p$, then (I think) it will help me prove it, but ...
3
votes
1answer
109 views
Elgamal test vectors
I know that Elgamal algorithms have fallen out of fashion, and they are not included in any widespread cryptographic standard nowadays. However, they are still present in several popular crypto ...
2
votes
2answers
234 views
Additive ElGamal cryptosystem using a finite field
I'm trying to implement a modified version of the ElGamal cryptosystem as specified by Cramer et al. in "A secure and optimally efficient multi-authority election scheme", which possesses additive ...
2
votes
1answer
283 views
Why can't I break ElGamal encryption by brute-forcing the secret exponent?
I am doing a course on cryptography on coursera and one of the topics covered was the ElGamal Encryption system.
I am using the terms as defined in Wikipedia.
Alice publishes $g$ and $g^x$. ...
2
votes
1answer
380 views
What does SSL use? RSA? El-Gamal? Elliptic curves?
I'm not sure what SSL uses to share the symmetric key to both end users, i.e. at the beginning of the communication. Is it RSA? Or El-Gamal? Or something else?
Thanks!
2
votes
1answer
80 views
Why is the discrete log problem easy when the exponent comes from a binomial distribution?
I read in http://epubs.surrey.ac.uk/7219/2/esorics06.pdf that in exponential El Gamal the discrete log problem for recovering $m$ from $g^m$ can be made tractable when $m$ is drawn from a binomial ...
2
votes
3answers
222 views
Existing works on pre-computing ElGamal ephermal keys
I was playing around with a problem in e-voting schemes that use additive homomorphic encryption to tally votes, namely that at the end of the day somebody (or somebodies, if the secret material has ...
2
votes
2answers
360 views
Public key generation in homomorphic encryption schemes
Is there any way to effectively generate valid distributed public key in schemes like ElGamal or Benaloh for a number of participants? There's no need in private keys since there's no intent to ...
2
votes
1answer
51 views
How is ElGamal not secure under chosen ciphertext attack, but semantically secure in some cases?
I know that you can create a ciphertext c' using c and then find the corresponding m' for c' which you can use to find m for c. So, doesn't this mean that it is not semantically secure? But I also ...
2
votes
1answer
210 views
Can ElGamal encryption and ElGamal signatures be used together sharing the same key-pairs?
I'm working on a encryption system where each party can store exactly a single ElGamal private key in a device. This is a hardware limit. The system must be expanded to support signatures and ...
2
votes
1answer
335 views
Generalizing the conversion of Diffie-Hellman to El Gamal
How can we generalize the conversion of Diffie-Hellman to El Gamal public-key encryption scheme? The goals is to be eventually able to show that any 2-round key-exchange protocol can be converted into ...
2
votes
1answer
178 views
ElGamal message signatures retrieving the secret value x
If the GCD(r, p-1) is small and the value k is used to sign a message using ElGamal is also small. Then the secret value of x can be determined.
Why is this true? How would one retrieve x?
...
2
votes
1answer
203 views
ElGamal signature - exploiting fallacious implementation
This question is related to ElGamal signature scheme as defined here
ElGamal signature without calculating the inverse
Show how one could exploit an implementation ElGamal signature scheme in which ...
2
votes
0answers
136 views
Safe generator for ElGamal signature
What are the properties a generator $g$ should have to be secure for ElGamal signatures (original scheme)?
I am aware that it is poorly chosen and not secure when $g|p-1$ or $g^{-1}|p-1$, where $p$ ...
2
votes
0answers
627 views
An existential forgery attack on ElGamal [closed]
From an old exam question:
Consider this existential forgery attack on ElGamal. Choose $u$, and $v$ such that $\operatorname{gcd}(v, p - 1) = 1$.
Compute $r := y^v g^u \mod p$ and $s := ...
1
vote
1answer
286 views
Can Elgamal be made additively homomorphic and how could it be used for E-voting?
Elgamal is a cryptosystem that is homomorphic over multiplication.
How can I convert it to an additive homomorphic cryptosystem?
How can I use this additive homomorphic Elgamal cryptosystem for ...
1
vote
1answer
69 views
Is Guillou-Quisquater existentially unforgeable against adaptive message attack under a random oracle model?
First of all, the Guillou-Quisquater digital signature scheme is:
Note everything is $\bmod n$. Message is denoted by $m$.
Private key: $s$
Public key: Hash function $H$, $e$, ...
1
vote
1answer
125 views
What's a good P to use in ElGamal key generation?
I need to generate a 1024 bit ElGamal key on Android, and key generation takes forever (~10 minutes on a Galaxy Nexus), I suspect because it take so long to generate a safe prime.
Is it dangerous for ...
1
vote
1answer
144 views
How can I prove in zero knowldege that an ElGamal shuffle is correct for a special setting? [closed]
In a special ElGamal encryption scheme, every user has an ElGamal encryption key-pair using the same cyclic group $G$ and generator $g$.
The system has a special function :
$$ ...
0
votes
2answers
73 views
ElGamal: Generation of “g” value?
I haven't been able to find a clear explanation on this (and I'm probably just confused in general). I have the following parameters of ElGamal signatures:
$p$ = safe prime
$q = (p-1)/2$
$g$ = an ...
0
votes
1answer
51 views
chaining rsa with ecies
In an answer to a previous question it was suggested that one way to protect your asymmetrically encrypted AES-256 keys, from say a solution to prime factorization, would be to chain asymmetric ...
0
votes
1answer
63 views
Efficient algorithm for remainder calculation over prime field for ECC implementation?
I am working on 224-bit elliptic curve cryptography. In this 224-bit * 224-bit multiplication results 448-bit output. I am reducing 448-bit into prime field range( prime number $2^{224}-2^{96}+1$) ...
0
votes
1answer
89 views
Need for Twin Elgamal encryption
What is the need for two private/public keys in twin elgamal?
I'm relatively new and would need some help.
0
votes
0answers
33 views
calculating beta for elgamal elliptic curves [duplicate]
Suppose we use elgamal elliptic curves for secure communication. Bob selects a prime $p$, an elliptic curve $E$, a point $\alpha$ on $E \pmod p$, and a secret integer $f$. Suppose that Bob has ...
0
votes
0answers
69 views
Use curve25519 for ElGamal crypto
DJB described curve25519 in his paper which can be found here: http://cr.yp.to/ecdh/curve25519-20060209.pdf. It seems that the main purpose was for Diffie-Hellman key exchange. I think this means that ...
0
votes
0answers
43 views
elgamal based decryption mixnet
Can anybody help me to understand elgamal based decryption mixnet? Pure elgamal can be used in mixnet (re-encryption mixnet) and its very easy, and I have implemented decryption mixnet using RSA also.
...
0
votes
1answer
208 views
Problems with implementation of ElGamal using OpenSSL [closed]
I recently did an implementation of a semantically secure modification of ElGamal using OpenSSL. I'm implementing part of a book that i have, and several parts of the book do not agree with things ...
-1
votes
1answer
52 views
Solving a discrete logarithm using GDlog
I am trying to calculate an x, such that t = g^x mod p (I need to crack a weak elgamal encryption for university). I found gdlog, but I cant figure out how I can use the input to calculate my x. Here ...
