Hot answers tagged elgamal
8
In this context, "nondeterministic" means that the algorithm to generate the ciphertext (or the signature) takes a random value as one of its inputs, and it can generate many possible ciphertexts (or signatures) based on the random value. ElGamal is nondetermanistic because the encryptor selects a random exponent as a part of encryption method.
For public ...
8
ElGamal encryption works like this:
We work in a cyclic group $G$ of order $q$ (a prime integer), with $g$ being a generator. Here, we note the operation multiplicatively. For instance, we work with integers modulo $p$ (a big prime such that $q$ divides $p-1$) and $g$ is one of the $q$-th roots of $1$ modulo $p$.
Private key is $x$, an integer modulo $q$.
...
6
There is an asymptotic formula for the General Number Field Sieve for factoring big integers. This is the most efficient known algorithm for breaking RSA keys which are longer than 400 bits or so (since the current world record is 768 bits, a 400-bit RSA key is quite weak). For discrete logarithm (to break DH), the best known algorithm is also known as ...
6
Asymmetric encryption requires some mathematical structure (to enable the magic of asymmetry), and some of that structure is readily apparent to anybody. For instance, with RSA, the encrypted messages are numbers modulo n (the modulus, from the public key), and thus in the range 0 to n-1. This implies that values for the first byte will be quite biased (RSA ...
5
Well, what SSL uses to negotiate the symmetric keys depends on the ciphersuite that both sides agree upon. By far, the most common method is that the client picks a random value (the premaster secret), and encrypts it with the server's RSA public key. However, it is not that unusual for the ciphersuite to specify that the client and the server agree upon a ...
5
I'm not sure what level of explanation you are looking for, but from the very basics, subgroups work like this.
Consider concretely the example of working $\mod{p}$ where $p=11$. Next we have to find a generator $g$. Initially, any number $\{0,\ldots,n-1\}$ (or $\mathbb{Z}_p$ for short) is a candidate.
Below is a chart showing each $g$ value as a row, each ...
5
For $p = 2q+1$, one can note that elements of $\mathbb{G}_q$ are exactly the non-zero quadratic residues modulo $p$:
Since $p$ is prime, $\mathbb{Z}_p$ is a field. Hence, the polynomial $X^q-1$, being of degree $q$, cannot have more than $q$ roots in $\mathbb{Z}_p$. So $\mathbb{G}_q$ contains all the $q$ values of order $1$ or $q$.
If $x$ is a non-zero ...
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
For the second case, mapping numbers from $\mathbb{Z}_q$ to $\mathbb{G}_q$ and back when:
$p=aq+1$ with an $a$ such that, e.g., |p|=1024 and |q|=160
It appears an efficient subgroup encoding/decoding scheme does not exist. Although it has not been proven that one cannot exist, notable cryptographers have conjectured it in the literature. For example, ...
4
Probably the easiest solution for the case a=2 is to map $m\in\{1\ldots q\}$ to $(m/p)m$ where $(m/p)$ is the Legendre symbol. The inverse can be obtained by mapping a quadratic residue $x\in Z/(pZ)^*$ either to x or -x depending on which of the two residue classes contains an integer in $\{1\ldots q\}$.
This is of course a well know solution, but I can't ...
4
Your scheme is not the "true" ElGamal signature scheme: you swapped $x$ and $k$. I assume that $m$ is the hash of the message to sign, not the message itself.
Your scheme is sound, which means that the verification algorithm will return "ok" for a signature which has been generated as you suggest. To see that, remember Fermat's Little Theorem which says ...
4
Actually, for most applications where we want to use asymmetric encryption, we really want something a bit weaker: key agreement (also known as "key exchange"). When RSA or ElGamal is used for that, one party selects a random string, encrypts it with the public key of the other party, and the random string is used as a key for classical symmetric encryption. ...
4
That looks about right. Assume we have two messages $m_1$ and $m_2$ and the corresponding signatures $(r,s_1)$ and $(r,s_2)$ generated using the same $k$ (where $r=g^k$ is thus the same for both signatures).
If we could assume that $s_1 - s_2$ and $r$ were invertible modulo $p-1$, we could simply compute
$$ k \equiv (m_1 - m_2)(s_1 - s_2)^{-1} \mod p-1 $$
...
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 ...
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$, ...
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
There are different crypto-systems that have been called Hash-Elgamal. The one your exam refers to is likely whatever was included in your course. Without knowing that, we can't necessarily answer your question.
The most common is the Elgamal variant defined with encryption function: $c=\mathsf{Enc}(m,r)=\langle g^r, \mathcal{H}(y^r)\oplus m \rangle$
This ...
3
I must confess to not fully understanding your question but hopefully this will assist.
To generate a public key in Elgamal, you need a group (e.g., subgroup $\mathbb{G}_q$ of $\mathbb{Z}_p$ for large primes $p,q$) and a generator ($g$ where $\mathrm{order}(g)=q$).
A secret key is chosen from $x \in_r \mathbb{Z}_q$ and the public key is computed as ...
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
It may be useful to define what is meant by noise. Noise is data that is selected randomly from some distribution. @Thomas deals with comparing to random bitstrings (where each bit is equally likely 0 or 1) and notes that because not all bitstrings of an appropriate length are possible values in most asymmetric encryption functions, real ciphertexts will be ...
2
The conversion of Diffie-Hellmen into Elgamal is assisted by a few factors that are not inherent to key exchange/agreement protocols in general, but a general conversion may be possible.
The DH $\rightarrow$ Elgamal case. In Diffie-Hellman, Alice generates $a$ and sends a representation of it: $g^a$. Bob generates $b$ and sends $g^b$. Both parties can ...
2
$\newcommand\gcd{\operatorname{gcd}}$Let's have a look at the signature equation:
$$ s = (H(m) - x·r)·k^{-1} \mod (p-1), $$
$$ s·k = H(m) - x·r \mod (p-1), $$
and thus
$$ H(m) - s·k = x · r \mod (p-1).$$
$d = \gcd(r, p-1)$ means we find (efficiently, given $r$ and $p-1$, using the extended euclidean algorithm) a $z$ such that ...
2
What you are saying for hashing is actually more commonly known as Cramer-Shoup's crypto-system and yes it is non-malleable. You can read Lecture notes 22 given by Boaz Barak in Fall 2007 for more details.
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
