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, ...
user avatar
  • 122k
12 votes
Accepted

ElGamal against chosen ciphertext attacks

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 ...
user avatar
  • 4,822
11 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 ...
user avatar
11 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$ ...
user avatar
  • 7,904
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 ...
user avatar
  • 131k
10 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 ...
user avatar
9 votes
Accepted

Is ElGamal IND-CCA1?

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-...
user avatar
8 votes
Accepted

Mapping of message onto elliptic curve and reverse it?

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 ...
user avatar
  • 12.1k
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{...
user avatar
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....
user avatar
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 ...
user avatar
  • 131k
7 votes

How does chosen ciphertext attack on Elgamal work?

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 ...
user avatar
  • 44.6k
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 ...
user avatar
  • 122k
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)$. ...
user avatar
  • 44.6k
7 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 ...
user avatar
  • 131k
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$ ...
user avatar
  • 122k
7 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 $...
user avatar
  • 131k
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 ...
user avatar
  • 131k
6 votes

Why are we not using multiple ciphers per message?

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 ...
user avatar
  • 1,114
6 votes

Known plaintext attack on ElGamal encryption

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$. ...
user avatar
  • 12.1k
6 votes
Accepted

Reusing the random exponent for ElGamal encryption with different plaintexts

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 ...
user avatar
  • 308
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 ...
user avatar
  • 131k
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; ...
user avatar
  • 131k
5 votes

What differences between Menezes–Vanstone ECC and ElGamal ECC?

The essential difference between these two encryption schemes is that for standard ElGamal encryption on elliptic curves the plaintext space is the set of points in your elliptic curve group while in ...
user avatar
  • 12.1k
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 ...
user avatar
  • 7,904
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 4,382
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible