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

74 questions
Filter by
Sorted by
Tagged with
36 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?
27 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?
150 views

177 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 ...
170 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$...
1k views

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$. ...
2k 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)
518 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 ...
576 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 ...
244 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 ...
543 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 ...
932 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 ...
110 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 ...
1k views

### How to apply Pollard's Rho Method on elliptic curves to solve discrete logarithm problem in finite field?

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 ...
160 views

### Elgamal Protocol Failure

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:...
581 views

### How to find $r$ for El-Gamal signature with known private key

For public key $(g,b,P)$ and private key $x$ I have that... ...
1k views

### What can I do if I get private key of signing algorithm in Digital signiture

I am confused in digital signature. what is use of encryption with private key and decryption with public key. Using public key we can decrypt the signature then what is use of private key privacy. ...
751 views

### El Gamal signature scheme variant

Suppose we have the following El Gamal digital signature scheme variant: We fix a prime number $p$ and a generator $g$ of the group $Z_p^*$. We choose $x \in Z_{p-1}^*$, which is going to be our ...
5k views

### RSA Digital Signature vs Elgamal Digital Signature

What are the advantages of RSA signatures against ElGamal signatures? Is there a situation in which it would be better e.g. to use RSA signatures?
1k views

### El Gamal existential forgery using Pointcheval–Stern signature algorithm

I found that there exists an algorithm that claims to make the El Gamal signature generation more secure. The algorithm can be found here as a pdf. I'm mainly interested in the two-parameter forgery ...
194 views

### How to generate an El Gamal signature without knowing the private key x?

Let $x$ be the private key. Let $k$ be a random generated number $< p-1$, with $p$ the large prime. Let $g$ be the generator of $p$ the large prime. Let $r$ be the equality $r=g^k$ Let $m_e$ be an ...
303 views

### Attacks on schemes based on elliptic curves when the transmitted points are not on the curve

Some elliptic curve schemes require to send a curve point during the normal execution of the protocol. For example, ElGamal encryption and ElGamal signature require this. On the other hand, ECDSA does ...
321 views

### ElGamal scheme signature: if private key a mod p is equal to private sig. key k mod p-1, can an attacker notice and determine the value of a?

If someone is signing a document using the ElGamal signature scheme, and if the random involved in the signature $k \mod (p-1)$ is equal to $a$ (the private key), can an attacker notice? If so can he ...
1k views

### Inverse in ElGamal signature

I am learning about ElGamal signature verification. During the signature generation one has to choose a k such that ...
958 views

### Role of Fermat's little theorem in the proof of correctness of ElGamal signature

In the Wikipedia article about the ElGamal signature scheme it is written, that Fermat's little theorem is used in the following proof of correctness: From the signature generation in ElGamal we can ...
398 views

### ElGamal Signatures

I know various applications of RSA signatures. I wonder, is there any real-world applications of ElGamal signatures and encryption?
105 views

### Batch ElGamal Scheme

I know about ElGamal scheme and its key generation, encryption, and decryption methods. I'm not sure about what is meant by batch ElGamal. Can someone please clarify it. How it differs from ElGamal ...
### ElGamal in $Z^*_{p^n}$
If $p$ is an odd prime and $n$ natural,it is known that the group $Z^*_{p^n}$ is cyclic.Explain why the selection-choice of the group $Z^*_{{3^{1000}}}$ for the construction of a cryptosystem ElGamal ...