13
votes
Accepted
Zero knowledge proof for sign of message value
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 ...
- 18.9k
13
votes
Accepted
What is largest prime factor in Diffie-Hellman?
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, ...
- 137k
12
votes
Accepted
Exponentiation in ECC
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$ ...
- 8,072
11
votes
Accepted
ECIES/ ECDHE/ EC-ElGamal encryption comparison
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 ...
- 47.5k
10
votes
Accepted
Do $v_1=\alpha\cdot r_1$ and $v_2=\alpha\cdot r_2$ leak information about $\alpha$
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 ...
- 143k
9
votes
How to verify if $g$ is a generator for $p$?
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 $...
- 143k
8
votes
Accepted
Why do the subexponential algoriths for the DLP not work for the ECDLP?
"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{...
- 18.9k
8
votes
Time gap between Diffie-Hellman Key Exchange and ElGamal encryption?
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....
- 27.5k
8
votes
Accepted
ElGamal with elliptic curves II
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 ...
- 143k
8
votes
Accepted
XOR instead of Multiplication in ElGamal encryption
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 ...
- 143k
8
votes
How to verify if $g$ is a generator for $p$?
In general, proving that $g$ is a primitive root (often called a generator) of a cyclic group is fairly simple. Note this holds true for non prime modulo as well
Step 1:
Verify that $0\leqslant g \...
7
votes
Accepted
Why is it claimed that ElGamal is worse than RSA?
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 ...
- 137k
7
votes
Accepted
ElGamal CPA secure
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)$.
...
- 45.6k
7
votes
Accepted
ElGamal in $\mathbb Z^*_p$ with $g$ not a generator of $\mathbb Z^*_p$
Because in the exercise $g$ is is not a generator of $\mathbb Z^*_p$, the exercise would indeed be incorrect in a context explicitly giving a definition of ElGamal encryption that both
requires $g$ ...
- 137k
7
votes
What is largest prime factor in Diffie-Hellman?
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 ...
- 143k
6
votes
Accepted
On getting beyond LSB in discrete log
If $p = 2q+1$ where $q$ is prime, and then we can efficiently solve for $x_0 \in \{0, 1\}$ for $g^{2x+x_0} = h \pmod p$, if $g$ is a generator.
This is true; this is a special case of the observation ...
- 143k
6
votes
Accepted
How many pairs of ${b_i}^k \equiv g_i\pmod p$ are enough to solve discrete logarithm problem?
Having multiple sets $b_i^k = g_i$ with a common solution $k$ do not help you recover $k$; it cannot make the problem much easier than if you had the simple equation $b^k = g$.
Here's the proof; ...
- 143k
6
votes
How to create an EC point from a plaintext message for encryption
There is also a variant of Koblitz's approach *
Let the message units $m$ be integers $0<m<M$, let $\kappa$ be large enough integer so that we are satisfied with error probability $2^{-\kappa}$, ...
- 46.4k
5
votes
Accepted
One-wayness proof of Elgamal
You are confusing two different security notions.
The proof you describe is regarding the Onewayness under chosen-plaintext attacks (OW-CPA). Basically, this notion covers the idea that it shouldn't ...
- 4,892
5
votes
ElGamal in $Z^*_{p^n}$
The order of $(\mathbf{Z}/3^{1000}\mathbf{Z})^*$ is $\varphi(3^{1000}) = 2\times 3^{999}$, which is a highly composite number, and hence the discrete logarithm in this group is highly vulnerable to ...
- 8,072
5
votes
Which values are used for an elgamal cryptosystem public key?
Let $p$ be a prime such that the Discrete Logarithm problem in $({\mathbb Z_p}^*,.)$ is infeasible, and let $\alpha \in {\mathbb Z_p}^*$ be a primitive element.
$$\beta =\alpha^a \bmod p$$
The ...
- 2,323
5
votes
Accepted
How is El Gamal different from Diffie Hellman Key Exchange
The difference is purely conceptual. That is, when Diffie-Hellman published their paper, they equated between public-key encryption and trapdoor functions. Thus, they did not think that they had ...
- 27.5k
5
votes
How is a re-encryption done with elGamal?
First, I can't find a copy of the RSA mental poker report, so I cannot say for sure what kind of "commutative encryption" they wanted to use, but one type is the Pohlig-Hellman cipher, where you ...
- 4,587
5
votes
Is it insecure using addition instead of multiplication in Elgamal encryption?
In the generic sense of an abstract group, this is a problem since addition may not be defined. However, when working modulo a prime $p$, addition is certainly defined. However, it is not secure. In ...
- 27.5k
5
votes
Accepted
EL gamal cryptosystem
Ok, so now the question makes more sense to me.
Yes you are correct. Sadly, you cannot solve the problem without solving the DLP. This is simply because in the problem he didn't share his secret x ...
- 206
5
votes
Accepted
How to securely map messages to points on an elliptic curve
If I do have to implement a mapping for security, how would you
reccomend I map message values to points, and how should I figure out
the maximum message size based on my curve?
The default ...
- 45.6k
5
votes
Accepted
Verification of encryption for ElGamal cryptosystem
Actually, an ElGamal ciphertext $(a,b)$ is "valid" iff $(a,b) \in G^2$, because for any message $m\in G$ and any $\mathsf{pk}\in G$, the encryption of $m$ will be in $G^2$, because for any $r$, $(g^r,...
- 221
5
votes
Accepted
How to create an EC point from a plaintext message for encryption
The standard approach for this goes as follows, which I think is usually attributed to this paper by Koblitz:
Suppose you have a curve over an $k$-bit prime field. Also suppose you want to encode a ...
- 45.6k
5
votes
Accepted
How to calculate the n in n-bit security of a crypto algorithm?
TLDR: The size of the group/ring is dictated by the fastest currently-known attack (as explained in this Wikipedia article).
Details. For the case of discrete-log in $\mathbb{Z}_p^*$ and factoring $\...
- 5,113
4
votes
ElGamal in a different group
I don't know if anyone has looked at this question specifically. However, Diffie-Hellman modulo a composite $n=pq$ is actually as hard as factoring. See this paper by Biham, Boneh, and Reingold. It is ...
- 27.5k
Only top scored, non community-wiki answers of a minimum length are eligible