30
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
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 ...
15
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 ...
13
How to determine if the largest prime factor of $p-1$ is in fact large?
Most often, it is not determined from $p$ that $p-1$ has a large prime factor. Rather, a large prime factor $q$ is chosen, then it is chosen a prime $p$ of the form $p=2\,q\,r+1$ for some $r\ge1$, which insures that $p-1$ has large prime factor $q$.
Sometime, we want $r=1$, in which ...
11
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 ...
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
What you are looking for is called a range proof. There has been a vast body of research on the topic recently - so vast, in fact, that it can be quite hard to know what is the state of the art, and what solution is the most appropriate in a given situation. Therefore, to let you evaluate by yourself what might best suit your exact situation, I'll attempt at ...
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 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 ...
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
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/...
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
"Attacks that work on the DLP do not work on ECDLP" is a rather vague statement, as ECDLP is just a particular case of DLP, on elliptic curves. I suppose that you refer to DLP over $\mathbb{F}_q$ for some $q = p^k$, $p$ being a prime.
The intuitive reason why the DLP is harder to solve over (well-chosen) elliptic curves is that they are our best ...
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 ...
8
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
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
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 ...
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
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 ...
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.
7
Fix a group $G$ of order $q$ in which discrete logs are hard, and fix a standard base point $g \in G$. Fix an authenticated cipher $E_k$ of bit strings.
In (EC)IES, roughly: A public key is a point $h \in G$.
To encrypt a message $m$, the sender:
picks an exponent $y \in \mathbb Z/q\mathbb Z$ uniformly at random,
computes an ephemeral public key $t = g^...
7
My question is the following: how to determine if the largest prime factor of $p-1$ is in fact large?
Yes, showing that $p-1$ is not smooth (terminology for "has a large prime factor") for random primes $p$ is typically difficult, and so that's not what we do.
Instead, we usually do one of these two things:
Search for a large prime $p$ such that $(p-1)/2$...
6
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.
...
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
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
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
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
Your parameters that you provide are incomplete (in what group are you working?).
Anyways, lets assume that you work in $\mathbb{Z}_p^*$, your have a generator $g$ and your public key is $y=g^x$.
Then, if two ciphertexts share the same randomness $k$, they will look like $(c_1,c_2)=(g^k,m\cdot y^k)$ and $(c_1',c_2')=(g^k,m'\cdot y^k)$ for your two messages ...
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
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.
Only top voted, non community-wiki answers of a minimum length are eligible
