28
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$ of order $N$ just the same as for EC-DDH as system parameters.
You need a public known function $f : m \mapsto P_m$, which maps messages $m$ to points $P_m$ on $E$. It should be invertible, and one way is to ...
21
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. ...
21
Diffie Hellman
Diffie Hellman is a key exchange protocol. It is an interactive protocol with the aim that two parties can compute a common secret which can then be used to derive a secret key typically used for some symmetric encryption scheme.
I take the notation from the link above and this means we have a group $\mathbb{Z}_p^*$ for prime $p$ generated ...
20
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 ...
17
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. ...
12
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$.
...
11
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 ...
10
Question: Given $n$ values $v_1=\alpha \cdot r_1 \bmod p,..., v_n=\alpha \cdot r_n \bmod p$ for a large $n$ can the adversary learn the value $\alpha$?
Answer: assuming that the $r_i$ values are random (that is, equidistributed and uncorrelated), then the attacker gets absolutely no information about $\alpha$ (other than whether or not it's 0).
We can see ...
10
In a group, where there is by definition only one operation, exponentiation means repeated application of the group operation, whatever that is. That is, if the group operation is noted $\circ$, $g$ is a group element, and $x$ is a positive integer, $g^x$ is short for $\underbrace{g\circ g\circ\dots\circ g}_\text{$x$ terms}$.
In elliptic curve groups, the ...
9
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$, ...
9
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 ...
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 appears to be used instead of Diffie-Hellman (or IES) in OpenPGP mostly because when that format was put together, there were some unresolved intellectual property issues surrounding both RSA and Diffie-Hellman, while ElGamal was unproblematic. This trend for ElGamal seems to stick around, mostly by force of habit, e.g. when switching to elliptic-...
8
Actually, if you read Diffie and Hellman's paper closely, you'll see that they explicitly talk about taking another's party value from a public file. Thus, it really already does public-key encryption. However, they didn't call it that, and people didn't view it as public-key encryption, but rather as key distribution.
The reason for this is that at the ...
7
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 ...
7
When using ElGamal on elliptic curves you have two possibilities:
Encoding free Version of El Gamal
Use a version of ElGamal such as "hashed ElGamal" that avoids the task of mapping
messages to points on the curve. In standard ElGamal on elliptic curves you would compute
the ciphertext as $(C_1,C_2)=(kP,M+kY)$ where $k$ is a random integer, $M$ the ...
7
As already mentioned in a previous answer and the comments, you are right regarding that ElGamal is not secure against chosen-ciphertext attacks. An immediate reason is that the scheme is multiplicatively homomorphic, and that is not compatible with CCA: the attacker could query the decryption oracle with the ciphertext that results of multiplying the ...
7
What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because the ciphertext $(u,v)$ in ElGamal has 2 integers, when $y$ in RSA has 1; and $u$, $v$, $y$ are about the same size (also the size of $p$ and $N$). Making $p$ ...
7
One small question, from the DDH assumption we know $g^{xy}$ is random.
Actually, that's not true. What the DDH assumption says is that we cannot distinguish $g^{xy}$ from $g^z$; however it does not say that we can't distinguish either from a random string.
Indeed, we can; if the order of $g$ has no small factors, then $g$ must be a quadratic residue (...
7
Steps:
Factor $p-1$, that is, find the primes which, multiplied together, produce $p-1$. In your case, $2685735182215186 = 2 \times 1342867591107593$
For each prime factor $q$ of $p-1$, verify that $g^{(p-1)/q} \not\equiv 1\pmod p$
If every such $q$ verifies (that is, they were all not 1), then $g$ is a generator.
6
Actually, it is possible to define RSA in such a way that the RSA ciphertexts are indistinguishable from random bit strings of the same length. The method is quite simple:
When you select the RSA key, you deliberately pick a modulus that is just under a power of 256; for example, if you are generating a 2048 bit key, you select a modulus between $2^{2048} -...
6
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 ...
6
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 authentication). ...
6
Well, if $g$ is a generator of $\bmod\ p$ for prime $p$; that is, if all values in the range $[1, p-1]$ are possible values for $g^i \bmod p$, then we have $g^a \neq 1 \bmod p$ for any $a = (p-1)/r$ where $r$ is a prime factor of $p-1$.
You select $p$ to be a "safe prime", that is $p-1 = 2 \times q$ where $q$ is also a prime. This implies that, in this ...
6
I don't know about computing things in parallel, so I will ignore that part of the question.
First, please note that the encryption algorithm is rarely the the weak point of the security. It is far more likely that
you will have problems with the implementation,
some spyware installed on your computer,
a weak password (If you use qwerty as your password, ...
6
Assuming you don't use counter-measures against this kind of an attack, a chosen-ciphertext attack works as follows:
Variables: $p$ is field prime, $\alpha$ is the chosen generator, $a$ is the private key, $\alpha^a=\beta$ is the public key. $k'$ and $m'$ are chosen at random.
Note: all the following equations are $(mod$ $p)$.
Suppose you want to decrypt ...
6
No, you can't. In this case, an attacker can compute $m_1/m_2$ by multiplying the first ciphertext for the inverse of the second and, for instance, determine if $m_1=m_2$ or not. This should not be possible in a secure scheme.
6
The CCA1 security of ElGamal is a big open question. There are no attacks known, but standard reductions don't seem to work.
In 1991, Damgard proposed an ElGamal variant and proved it to be CCA1-secure (albeit under a very problematic non-falsifiable assumption, called the "knowledge of exponent assumption"); see the paper here http://link.springer.com/...
6
So let's go through the IND-CPA game, shall we?
Pick two messages $m_0$ and $m_1$ arbitrarily.
Send them to the challenger who chooses $b\in\{0,1\}$ uniformly at random and returns you $c=E(m_b)$.
Output your guess for $b$ named $b'$. You "win" iff $b=b'$.
So you have two messages $m_0,m_1$, a ciphertext $c=(u,v)=(g^k,y^k\cdot m_b)=(g^k,g^{xk}\cdot m_b)$ ...
6
I have a concern regarding the security of the scheme -- let's suppose that there are only two possible messages, $m_0$ and $m_1$. Then, the encryption is done by multiplying, in the field, the chosen message with the $x$-coordinate of an unknown point on the curve.
What I highlighted is your problem; that is an invalid way of combining the point which is ...
Only top voted, non community-wiki answers of a minimum length are eligible
