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 ...
22
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 ...
12
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 ...
11
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 ...
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 ...
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
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
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 ...
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 (...
8
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
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). ...
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
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)$ ...
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
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
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
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 ...
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
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
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
