# Tag Info

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, ...
• 122k
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 ...
• 4,822
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 ...
• 16.6k
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$ ...
• 7,904
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 ...
• 131k
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 ...
• 45.6k
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-...
• 26.9k
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 ...
• 12.1k
Accepted

• 131k

### 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 ...
• 131k

### 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 ...
• 1,114

### 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$. ...
• 12.1k
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 ...
• 308
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 ...
• 131k
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; ...
• 131k

### 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 ...
• 12.1k

### 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 ...
• 7,904
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 ...
• 26.9k

### 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,285
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 ...