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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
47 views

ElGamal signature scheme problem and unsure whether my calculations are wrong or that's the answer

Trying to solve problem with verifying a message through the ElGamal signature scheme and I end up getting two different values. I'm given a prime number p=881 , e1=3, d=60 , and a random value r=11 . ...
Justin B's user avatar
0 votes
0 answers
43 views

What is the purpose of $k \in \{2, \dots, p-2\}$ in ElGamal signatures on ${\mathbb{Z_{p}^{*}}}$?

The question is mainly stated in the title. I had to do a refreshment on public key cryptography. The algorithms are pretty straightforward however, I always stumbled upon this question. Is it in ...
tur11ng's user avatar
  • 878
3 votes
1 answer
81 views

Occasional failure of an attack on ElGamal signature

I am following the procedure described on p. 319 of the fourth edition of Douglas Stinson and (since that edition) Maura Paterson's Cryptography − Theory and Practice (IBSN 978-1-03-247604-9). The ...
user109426's user avatar
5 votes
1 answer
965 views

Is it insecure to sign the value 0 with ElGamal?

Is it insecure to sign the plaintext 0 with ElGamal signature algorithm? Can this leak the private key, give the possibility to forge other signatures or does provide any other attack vector?
PCFX's user avatar
  • 63
0 votes
0 answers
135 views

Difference between ElGamal and Schnorr signature

A question about Schnorr group. Am I right that this is basically a protection against discrete-log solvers? So Schnorr signature is better than ElGamal in that sense?
Arthur Strong's user avatar
3 votes
2 answers
172 views

How is sum of two share of (2,n) shamir scheme equal to the secret?

I am refering to Privacy Aware Incentive Mechanism to Collect Mobile Data While Preventing Duplication https://ieeexplore.ieee.org/document/7357616. They claim to split secret $X$ into $X_s=\{x_0,\...
xyyaoliusan's user avatar
1 vote
2 answers
234 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 ...
mrwarrdy's user avatar
0 votes
1 answer
450 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 ...
Public IP's user avatar
0 votes
1 answer
451 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 ...
Lawrence Meigs's user avatar
1 vote
1 answer
203 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$?
Mohammadsadeq Borjiyan's user avatar
0 votes
1 answer
81 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 ...
amycandyit's user avatar
0 votes
0 answers
255 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 ...
Sarah's user avatar
  • 1
0 votes
1 answer
229 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 ...
Mary's user avatar
  • 11
0 votes
1 answer
274 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?
Andre's user avatar
  • 103
2 votes
0 answers
59 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?
Adam Stanisław Jagielski's user avatar
0 votes
2 answers
221 views

Break El Gamal for Elliptic Curves

There is an elliptic curve El Gamal digital signature scheme. Alice fixes an elliptic curve $E$, a prime $p$, a point $A$ on $E$, a secret integer $a$, and computes $B = aA$. She makes $(E, ...
budding_crypto's user avatar
1 vote
1 answer
322 views

How to compute certificates using Diffie-Hellman key exchange with certificates and Elgamal signature scheme

We consider the Diffie–Hellman key exchange scheme with certificates. We have a system with the three users Alice, Bob and Charley. The Diffie–Hellman algorithm uses p = 61 and α = 18. The three ...
CEL's user avatar
  • 31
2 votes
0 answers
382 views

Elgamal security if same key used twice

Assume that user A sends to user B a message, unencrypted, and signs it with an Elgamal signature. Can some adversary, call it C, who eavesdrops, learn the private key if user A signed both messages ...
beginningcrypto's user avatar
0 votes
0 answers
122 views

In ElGamal, how does knowing the secret number used for a signature reveal the signer's private key?

In ElGamal, how does knowing the secret number used for a signature reveal the signer's private key? How do two signatures using the same secret number reveal the signer's private key? [Hint: p-1 is ...
user78876's user avatar
1 vote
2 answers
471 views

How to properly sign and verify using DSA? Can anyone spot my mistake?

The question that I am trying to answer is as follows: 10.14. The parameters of DSA are given by p = 59,q = 29,α = 3, and Bob’s private key is d = 23. Show the process of signing (Bob) and ...
CEL's user avatar
  • 31
9 votes
2 answers
2k views

What is largest prime factor in Diffie-Hellman?

I was reading the paper of A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms by TAHER ELGAMAL to better understand ElGamal public-key scheme, and he stated that for any ...
vxek's user avatar
  • 445
2 votes
1 answer
522 views

Why ElGamal signature is insecure with nonrandom k?

In ElGamal signature scheme like: Keygen: $\beta:=\alpha^a\bmod p$ where $\alpha$ and $p$ are large prime numbers. Public key is $(p,\alpha,\beta)$ and secret key is $a$. Sign: Choosing random $k$ ...
kimia sepehri's user avatar
0 votes
0 answers
141 views

In DSA digital signature, why does k have to be random and unique each for each signing? [duplicate]

If we repeat k, I think there is little chance for s to repeat since user's private key x is ...
cscisgqr's user avatar
0 votes
1 answer
529 views

How to compute ElGamal decryption by hand

Lets say that $u=3, x=5, v=2$, how do we work out $u^{-x}*v$, so $3^{-5} * 2$. I know how to work out the answer if it was $3^5 * 2$ but how do we do it with negative exponents?
Mark Janweison's user avatar
2 votes
2 answers
493 views

Whats wrong with my El Gamal signature example

I'm trying to digitally sign a message m using El Gamal. So far I've been unable to verify the digital signature ive made using El Gamal. I am using prime number, p = 8369. prime root g = 3031. ...
archhmod's user avatar
2 votes
1 answer
1k views

find $a$ and $k$ for a given el gamal cryptosystem

I am given this question: Suppose Alice is using the ElGamal Signature scheme with parameters $p = 31847$, $\alpha = 5$, and $\beta = 25703$ Assuming that we have received signed messages $(x_1,(\...
wade king's user avatar
  • 131
5 votes
1 answer
215 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 ...
rafael's user avatar
  • 71
1 vote
1 answer
404 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$...
A. Darwin's user avatar
  • 466
1 vote
1 answer
2k views

How to recover secret $x$ from Elgamal signatures with repeated $k$?

Set generator $g \equiv 5 \pmod p$ where $p=647$ and $p$ is prime. With the same $g$, $p$ and secret signing key $x$, Alice sends two messages, $428$ and $129$, with signatures $(433, 239)$ and $(433,...
Elena's user avatar
  • 13
0 votes
1 answer
247 views

Find private key from knowing random exponents are an arithmetic series

Let $p$ be a large prime and $g$ a primitive root modulo $p$, and $h$ a collision-resistant hash function. Person A chooses a random integer $1 < u< p$ and $y \equiv g^u \pmod p$ is publicly ...
user366818's user avatar
4 votes
2 answers
7k views

Recovering private key from Secp256k1 signatures

I've seen many answers here and many articles that says we can recover the private key from reused R signatures. But, what if the r,s signatures are different in transaction of bitcoin then is there a ...
Harvy Sam's user avatar
1 vote
1 answer
3k views

primitive root of a very big prime number (Elgamal DS)

For encryption methods there is a need for (very large) prime numbers. So for Elgamal digital signature there is the problem of finding a primitive root of $(p)$ where $p$ must be very large prime ...
Q.M.J's user avatar
  • 21
5 votes
1 answer
320 views

Signature Scheme with proof of data possession

Most signature schemes first hash the data and than sign the hash. Correct me if I am wrong: The signature does not prove that the signatory was in possession of the document itself? In cases where ...
Titusz's user avatar
  • 153
2 votes
1 answer
362 views

Any scenario for using ElGamal-SIGNATURE over RSA?

On a homework assignment, we're asked to give an example in which scenario one would use an ElGamal-Signature over an RSA-Signature. I found this question, but the answer also only describes why RSA ...
Andreas H.'s user avatar
1 vote
1 answer
270 views

Does ElGamal authentication exist?

Are there any natural ways to transform ElGamal encryption system or ElGamal signature scheme into an authentication protocol?
Alexey Ustinov's user avatar
1 vote
1 answer
87 views

Given 2 Digital Signature generated by $S=D\times k^r$ how do you solve for $k$?

Given 2 signature $(D_1, r_1, S_1)$ and $(D_2, r_2, S_2)$ and the Signature is generated as $S=D\times k^r \mod N$ where $N$ is a product of 2 primes and $r_1$, $r_2$ is co-prime. How do you solve for ...
albusSimba's user avatar
0 votes
1 answer
1k views

El Gamal Signature: Attack to recover private key if $k$ is generated as $k_{i+1}=k_{i}+a$ where $a$ is a large unknown constant

$k_0$ is randomly generated and subsequently $k_{i+1} = k_{i}+a$, where $a$ is a large unknown constant I've tried formulating an attack as such: Given 3 Messages $M_0$, $M_1$ $M_2$and with $(r_0,...
albusSimba's user avatar
3 votes
1 answer
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$. ...
Yevhen Vlasenko's user avatar
2 votes
1 answer
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)
Adan Kalamsyah's user avatar
4 votes
1 answer
755 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 ...
rzdzc2WUQKJeB6GS's user avatar
4 votes
1 answer
697 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 ...
Mario's user avatar
  • 41
2 votes
1 answer
309 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 ...
Tina Ch's user avatar
  • 115
3 votes
1 answer
788 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 ...
NuminousName's user avatar
0 votes
1 answer
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 ...
Evinda's user avatar
  • 133
2 votes
0 answers
131 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 ...
Mikhail Koipish's user avatar
2 votes
2 answers
2k 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 ...
Gleb Ignatev's user avatar
0 votes
1 answer
201 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:...
Anonymous's user avatar
2 votes
2 answers
675 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... ...
Math4Life's user avatar
  • 131
2 votes
3 answers
2k 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. ...
Arunkumar Topagi's user avatar
3 votes
1 answer
901 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 ...
blaze9's user avatar
  • 33