# Tag Info

## Hot answers tagged elgamal

7

Apparently, Schnorr was quite adamant, at that time, about the applicability of his patent to DSS. See this message and that one. These are from 1998, but the controversy had begun earlier; see for instance this bulletin from NIST, from late 1994, where references to it can be found in the "Patent Issues" section. Interestingly, NIST not only tried to avoid ...

7

Your answer is in the paper Elliptic curve cryptosystems from Neal Koblitz: Set up an elliptic curve $E$ over a field $\mathbb{F}_q$ and a point $P$ just the same as for EC-DDH as system parameters. You need a public known function $f(m) \rightarrow P_m$, which maps messages $m$ to points $P_m$ in $E$. It should be invertible, and one way is to use $m$ in ...

7

It is true that elliptic curves allow the same security with smaller key sizes. However, the size is not the only important aspect. Familiarity of algorithm, ease of implementation, performance, how many independent implementations exist, etc. affect how widely algorithm is implemented. For Elliptic Curves, like many other technologies one factor slowing ...

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); ...

5

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

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 what can happen if you don't do this verification: Suppose Alice, Bob and company generate their public key shares honestly, $h_2, h_3, ..., h_n$ Now, Snidely Whiplash (who is also a trustee) is the last to contribute his share, he selects a private key $x_{evil}$ and computes $h_{evil} = g^{x_{evil}}$. However, instead of sharing $h_{evil}$ as his ...

4

You've messed up your question. Since the two ciphertexts both use the same r, anyone can easily check if $m_1=m_2$. This is not the interesting case. But if the two ciphertexts are $(a_1, b_1) = (g^{r_1}, m_1 y^{r_1})$ and $(a_2, b_2) = (g^{r_2}, m_2 y^{r_2})$, then the tuple $(g, y, a_1/a_2, b_1/b_2)$ is of the form the mentioned paper deals with.

3

Generally speaking, this algorithm uses the Chinese Remainder Theorem to split up the group order, and then uses a Babystep-Giantstep algorithm for each prime factor potency of the group order. If the group order is smooth (all prime factors are small, s.t. all BS-GS algorithms can be done efficiently), this can be done very efficiently. However, the ...

3

So why can't AES keys be generated from shared keys, and why not use only AES for message encryption after this point? That is exactly what is done. if there is a shared key from a DH key exchange, why are we still talking about ElGamal asymmetric message encryption Remember, DH is just one way to exchange a key. DH has its problems (no ...

3

The question is not very clear about exactly what you want to prove and what is publicly known, but here's my answer, based on my best guess at what you mean: Each party should publish $(R_1,S_1)$ and $(R_2,S_2)$. They should also publish $(R_3,S_3)$. Now anyone can verify that $(R_3,S_3)$ is a correctly-formed encryption of the sum of the messages ...

3

The subscript $A$ indicates that these numbers ($p_A$, $\alpha_A$, etc.) are the ones involved in Alice's key. In a description of a protocol with more participants each having their own key, Bob's public key would be $(p_B, \alpha_B, \beta_B)$, and so on. A primitive element of a finite field is a generator for the multiplicative group, i.e. the set $\{1, ... 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 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 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 Normal El Gamal is multiplicatively homomorphic:$E(x) E(y) = E(xy)$. If you want to make it additively homomorphic, you fix some generator$g$; then you transform the integer$x$to the group element$g^x$before encrypting with El Gamal. With this transformation,$E(g^x) E(g^y) = E(g^x g^y) = E(g^{x+y})$, so now you have an additive homomorphic property. ... 2 If you have the setting of$G$being a prime order$p$group (written multiplicatively) generated by$g$and your public-secret key pair is$(pk,sk)=(y=g^x,x)$, then encrypting a single message$m\in Z_p$amounts to choosing$k\in_R Z_p$and computing$(c_1,c_2)=(g^k,my^k)$. If you have a message$m=(m_1,\ldots,m_l) \in Z_p^l$, then the ciphertext would be ... 2 The main difference is that Pedersen commitments are unconditionally hiding, as given$g^mh^r$represents an information theoretic hiding commitment, i.e., even an unbounded adversary will not be able to figure out$m$. In exponential ElGamal encryption, since you publish$(g^r,g^mh^r)$, this so obtained commitment is no longer unconditionally hiding, but ... 1 Ok, I assume that you speak of ElGamal working in$Z_p^*$and you mean that$g$is a quadratic residue modulo$p$. The problem with ElGamal, when taking some arbitrary prime$p$is that you cannot achieve IND-CPA security. Recall, in the IND-CPA security game, the adversary chooses two messages$m_0$and$m_1$, obtains the ciphertext of$m_b$, where$b$... 1 unfortunately$x+y$is usually a very large number so i was just asking if there is any modification that i can do on the decryption so i can get the value without using the discrete logarithm In general no, but if you know some additional information about$x+y$it is possible (depending on how good the information is). For example, say$x$and$y\$ ...

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

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