Elgamal is a public key encryption scheme and signature scheme with security based on the discrete logarithm problem.
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 ...
2
votes
1answer
69 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 ...
-1
votes
1answer
48 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 ...
0
votes
1answer
46 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
2answers
69 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 ...
2
votes
1answer
46 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 ...
3
votes
1answer
54 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 ...
0
votes
1answer
54 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
0answers
65 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 ...
1
vote
1answer
66 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$, ...
0
votes
0answers
40 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.
...
2
votes
1answer
272 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$. ...
0
votes
1answer
84 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.
1
vote
1answer
120 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
138 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 :
$$ ...
2
votes
1answer
194 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 ...
0
votes
1answer
196 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 ...
5
votes
2answers
203 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 ...
1
vote
1answer
262 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 ...
2
votes
3answers
218 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
221 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 ...
4
votes
1answer
479 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
295 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 ...
2
votes
0answers
133 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$ ...
3
votes
1answer
107 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 ...
3
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
641 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 ...
3
votes
2answers
229 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 ...
4
votes
1answer
441 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 ...
2
votes
1answer
366 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!
4
votes
3answers
540 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 ...
2
votes
1answer
320 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
0answers
588 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 := ...
5
votes
1answer
330 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 := ...
2
votes
1answer
175 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?
...
4
votes
2answers
348 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
2answers
771 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 ...
2
votes
2answers
348 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 ...
6
votes
3answers
268 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 ...
2
votes
1answer
200 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 ...
4
votes
2answers
362 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 ...
8
votes
2answers
555 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 ...
