Hot answers tagged elgamal
5
For ElGamal to be secure, the 'discrete log problem' (which is, given $g$ and $g^x$, find $x$) must be intractable. You give a generic way to attack the discrete log problem for a group with $n$ elements with something like $n$ steps (I say about because your approach isn't the simplest version of this type of attack; the simplest does take $n$ steps); ...
4
As an alternative solution to the correct answer that Barack has posted, if you have $p=7 \bmod 8$, then the selection $g=2$ works just fine. In this case, $g=2$ is a quadratic residue (and hence has order $(p-1)/2$). In addition, you can show that if you can decrypt ElGamal messages with $g=2$, then you can decrypt ElGamal messages with any $g$; hence we ...
4
Here's the deal. The discrete log problem is feasible in the special case where the exponent is known to come from a small range of possibilities (e.g., the exponent is not too large).
Suppose we are given $y=g^m$, and we want to find $m$. Suppose moreover we know that $m$ is small: $0 \le m < 2^{30}$, say. Then it turns out it is easy to recover $m$, ...
4
Computations on elliptic curves are more efficient. Roughly speaking, when the base field has size $n$ (for DH/ElGamal/DSA, the size in bits of the modulus $p$; for elliptic curves, the size of the field for point coordinates) and a "security level" $t$ (e.g. $t = 80$ for "80-bit security" as can be expected when using a 160-bit subgroup and a 160-bit hash ...
3
At a purely technical level, having the two group elements and secret exponents enables a proof, in the random oracle model, that the scheme is CCA secure assuming that decision Diffie-Hellman is hard. For regular (hashed) ElGamal, we only know how to prove CCA security in the random oracle model under a stronger assumption (in our paper we called it strong ...
3
See section D.2.2 of FIPS 186-3. The modular reduction can be expressed as two additions and two subtractions of values which are assembled by concatenating selected 32-bit words of the 448-bit value which is to be reduced. Note that these additions and subtractions are modular, so you may have to mind some carries.
3
Elgamal can be made additive by encrypting $g^m$ instead of $m$ with traditional Elgamal for some generator $g$ (usually the same one used to generate the public key). This variant is sometimes called exponential Elgamal. The difficulty is decryption: running the standard decryption gives you $g^m$ and recovering $m$ requires you to solve the discrete log. ...
3
While I haven't read the paper, I believe I can answer these questions:
I'm not sure if the implied modulus of each operation is $q$, as I added myself to the above formulas. Could someone please clarify this? The paper omits it...
No, the arithmetic is done modulo $p$. Remember, you're working in a subgroup of size $q$ of $\mathbb{Z}^*_{p}$; ...
3
As far as I can tell from your description, the modulus is p. To multiply two group elements, you compute x*y (mod p); because the generator g you choose has period q it'll all work out fine.
No, p, q, and g can (and must) all be public. This is ElGamal, not RSA we're talking about - the security comes from the (presumed) hardness of taking discrete ...
3
I took the world's shortest look at the code, so please don't hold me to any of this. But it seems that the implementation is textbook. You provide a block of data, it gets encoded to an integer in the range 1,...,p-1 and then encrypted using standard Elgamal without padding.
There's does not seem** to be an encoding to the subgroup of quadratic residues, ...
3
You could protect the ECIES ciphertext with a superencipherment of DLIES, and you would not be weakening your security unless you slipped up and reused keys or used related keys. That means each step should be done carefully and thoughtfully as if it was the only protection step you would be taking. For example, when generating the cryptographically random ...
2
It depends.
It depends on a lot of things. For example a generator of 2 is great for encryption, but makes for awful signatures. If you use a generator of 2, then no. Your signatures will get broken. Then the encryption will.
Elgamal signatures are pretty controversial. They're tetchy to get right (see above) and there are many things you can get wrong. ...
2
Finding the corresponding $m'$ using $c'$ is a chosen cipher text attack. It's possible for a scheme to be semantically secure under certain types of attacks (perhaps something weaker like chosen-plaintext attack), but be broken under heavier attacks (like the chosen ciphertext attack you talk about).
2
There is no known way to compute $(g^a)^k \mod p = g^{ak} \mod p$,
given only
$g^k \mod p$ and
$g^a \mod p$
as per the Decisional Diffie–Hellman assumption. This is roughly equivalent to the discrete log problem. This is described in more detail in this paper.
2
The attacker can distinguish $\langle C_1, C_2 \rangle$ from a random pair if the attacker knows a value $q < p-1$ such that $g^q = 1 \mod p$.
Here's how the distinguisher would work: he simply computes $C_1 ^ q$ and checks to see if that value is 1. If this $C_1$ corresponds to a valid ciphertext, then that value will always be 1. If this $C_1$ is ...
2
Elliptic Curve Cryptography (ECC) is not known to be specifically more resistant to side channel attacks (of course the next question is more resistant than what).
This paper reviews power analysis side-channel attacks against ECC and countermeasures.
Given that ECC uses multiplication and many common implementations of the MUL instruction run in time ...
1
Guillo-Quisquater scheme uses the Fiat-Shamir trick to convert a proof of knowledge into a signature. There is a paper out there about the security of such schemes in the random oracle model here which seems to give what you want.
1
With most finite field crypto using a standard group is no problem. I think ElGamal encryption doesn't have any specific requirements for group or generator that plain Diffie-Hellman doesn't have.
So you could look into RFC 2409 Internet Key Exchange or RFC 5114 Additional Diffie-Hellman Groups for Use with IETF Standards for groups.
AFAIK ElGamal ...
1
How can I prove in zero knowldege that an ElGamal shuffle is correct for a special setting? [closed]
I don't understand the question (what is public? what is secret? what is the definition of all variables and functions?), but I can give you a pointer to literature that I strongly expect is highly relevant:
Take a look at mixnets. There's an enormous amount of research literature on the subject. It solves the following sort of problem (as well as ...
1
It seems you want to decrypt the final value without revealing the private key. First, if someone knows the private key, they can issue a very simple non-interactive zero knowledge proof that the plaintext is a decryption of the ciphertext (the ciphertext being the accumulation of all the ballots) without revealing the actual value of the key. This is the ...
1
There has been extensive research literature on this subject. If you are considering using this for real, please read my answer to a similar question first.
As far as the specific question you asked, there is a general technique here. Rather than trusting a single electoral authority with the ability to decrypt all the votes (and thus the ability to learn ...
1
A problem I see is that you're not actually achieving the goal you're trying to reach: Prove to the public that the authority is honest.
By making $A_y$ public, you're only proving that you used the (secondary) key that you said you would be using. What you're not proving though, is that it actually is the correct one, the sum of the ephemeral keys.
To ...
1
There seem to be no standardized ElGamal test vectors available in the public domain. However, there are some ElGamal test vectors generated with libgcrypt 1.5.0 available in this fork of the pycrypto project.
Only top voted, non community-wiki answers of a minimum length are eligible
