# Questions tagged [elgamal-signature]

A digital signature scheme based on the discrete logarithm problem, published by Taher ElGamal in 1984. Not to be confused with the ElGamal encryption system.

90 questions
Filter by
Sorted by
Tagged with
1 vote
80 views

### Why $1\leq r\leq p-1$ verification is needed for (hashed) Elgamal signature?

I am reading the "Handbook of Applied Cryptography" by Menezes et al. (hashed) ElGamal Signature verification in this book talks about verification of $1\leq r\leq p-1$. Subsequently, this ...
• 31
1 vote
30 views

### What is the best possible security for authentication of entity?

The classical security for authentication is computational provided by RSA or EC based signatures. With the advent of new PQ schemes the security claims are upgraded though nothing is proved. So the ...
• 171
1 vote
51 views

1 vote
250 views

### Using ElGamal instead of RSA in FDH

In RSA-FDH to sign a message $m$, we apply a hash function $H$ and then "decrypt" it using the private key $d$, so $Sign(m) = H(m)^d \mod N =: \sigma$ and then to verify, we use the public ...
• 13
622 views

### ElGamal same private and random key attack

I'm having difficulty understanding this. Consider two messages are encrypted using the same cyclic group order $q$, generator $g$, private key $x$, and random parameter $y$. The attacker knows a ...
1 vote
575 views

### Malleability of El Gamal encryption

Suppose Alice encrypts a number 𝑥 which indicates her bid on a contract, using textbook ElGamal encryption (malleable). This encryption of 𝑥 produces a ciphertext pair 𝑐1 and 𝑐2. How can Eve ...
1 vote
244 views

### Why $s=0$ is not allowed in Elgamal signature?

In Elgamal signature scheme $\text{sig}_{k_{pr}}(x,k_E)=(r,s)$, $s=0$ is not allowed. How does this lead to finding the private key $d$?
95 views

### Security of ElGamal signature scheme with generator of small order

For $p$ a 1024-bit prime, we have a 1021-bit element $g \in \mathbb{Z}_p^*$, where the order of $g$ is much smaller than the order of $\mathbb{Z}_p^*$. How does this small-order $g$ affect the ...
266 views

### Using GP/PARI how would you solve this randomised Elgamal question?

I know how to solve this question manually, but I don't know how to solve it using the program gp/pari. It is based on randomised Elgamal Let p = 739. Given the following ciphertext of some message m1 ...
254 views

### malleability of the Elgamal cryptosystem

In bidding for a contract, a company might outbid its competitor by simply multiplying its rival company’s encrypted bid by 0.9, without even knowing the bid. Now Suppose we are given the ciphertext c ...
• 11
1 vote
353 views

### How many valid signatures can the same message have using ElGamal?

I know that messages in ElGamal are not deterministic, so a message can have more than one valid signature. But is the number of valid subscriptions infinite?
• 113
65 views

### Does having CDH oracle breaks El-Gamal signature scheme?

Having a oracle that solves Computational Diffie-Hellman problem which for given values $(g, g^a, g^b)$ outputs $g^{ab}$, is it possible to forge a signature in El-Gamal (wiki) signature scheme?
243 views

• 131
232 views

### Security analysis for a extended ElGamal Signature against selective unforgeability

Let $H$ is a cryptography hash function and $\Pi=(\mathsf{G}, \mathsf{S}, \mathsf{V})$ is a digital signature, as follows: $(h_1=g^x,h_2=g^y) \leftarrow \mathsf{G}(1^n)$, where $x,y$ uniformly ...
• 71
1 vote
445 views

### Is K=1 a valid random integer in ElGamal signature?

In the ElGamal signature scheme, in addition to the public/private keypair, a random integer $K$ such that $\operatorname{gcd}(K,p-1)=1$ is chosen in the range $[1,p-1]$. This clearly excludes $K=p-1$...
• 496
1 vote
2k views

• 137
2k views

### ElGamal encryption and signature using same keys

In ElGamal scheme we have message $M$; $p$, $g$ and $y=g^x \bmod p$ as public key where $x$ is unknown private key. Encrypted message $(c,d)$, where $c=g^k \bmod p$ and $d=M \cdot y^k \bmod p$. ...
4k views

### Base Point on elliptic curve

How can i define the base point of the elliptic curve group element used as the elliptic curve domain parameter over Fp (prime)
813 views

### Why is the El Gamal commitment scheme information theoretically binding?

I am a bit stuck on the following claim: The ElGamal commitment scheme is information theoretically binding As far as I understand, an adversary $A$ would win the binding game if it is able to ...
732 views

### Length of ElGamal signature compared to RSA signature

In his original work (1) on the ElGamal encryption and signature scheme Taher ElGamal states in chapter V. section B.: For the signature scheme using the above arguments for the sizes ...
• 41
321 views

### ElGamal signature - show that $(\gamma, \delta)$ signs $m$

We have as a given: $gcd(j, p − 1) = 1$. $$γ = \alpha^i \beta^j \bmod p$$ $$\delta = −\gamma j^{-1} \bmod (p−1)$$ $$m = i \delta \bmod (p − 1)$$ I want to show that $(\gamma; \delta)$ is an ...
• 115
823 views

### Is it possible to combine digital signature to provide message addition?

Let's assume we are using the textbook RSA where $Sig(x)=x^d$. Alice has public key $(e,N)$, and private key $(d,p,q)$. Now, if Alice sends $Sig(5)$ and $Sig(10)$ to Bob, where $5$ and $10$ is just ...
• 452
1k views

### What is wrong with my Elgamal signature example?

I want to construct an Elgamal signature scheme with the group $\mathbb{Z}_{23}^{\star}$ and then to compute the signature for the message $m$ with $h(m)=4$, where $h$ is the hash function that we are ...
• 133
138 views

### Could be El-Gamal signature scheme constructed via Fiat-Shamir heuristic?

For example, Schnorr signature is pretty similar to El-Gamal. And everywhere where Schnorr signature is explained (for example - on Wikipedia), there's said that there's Schnorr scheme which is ...
I have ElGamal signature scheme implemented in finite field $\mathbb{F}_p$. The thing is that I need to apply Pollard's Rho Method on elliptic curve $E(\mathbb{F}_p)$ to this scheme, solve discrete ...
I'm having a difficult time trying to solve this problem. Suppose Alice uses the Elgamal signature scheme with $(\alpha, \beta, p) = (2, 33384, 65539)$. She publishes the two signed messages:...