Cryptography

Questions tagged [elgamal-signature]

Ask Question

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
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
0
votes
1answer
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?
2
votes
0answers
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?
0
votes
2answers
150 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, ...
1
vote
1answer
166 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 ...
2
votes
0answers
87 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 ...
0
votes
0answers
81 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 ...
1
vote
2answers
179 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 ...
9
votes
2answers
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 ...
2
votes
1answer
152 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$ ...
0
votes
0answers
85 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 ...
0
votes
1answer
348 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?
2
votes
2answers
168 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. ...
2
votes
1answer
792 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,(\...
5
votes
1answer
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 ...
1
vote
1answer
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$...
1
vote
1answer
1k 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,...
0
votes
1answer
201 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 ...
4
votes
2answers
4k 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 ...
1
vote
1answer
2k 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 ...
4
votes
1answer
268 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 ...
2
votes
1answer
290 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 ...
1
vote
1answer
210 views

Does ElGamal authentication exist?

Are there any natural ways to transform ElGamal encryption system or ElGamal signature scheme into an authentication protocol?
1
vote
1answer
75 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 ...
0
votes
1answer
734 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,...
3
votes
1answer
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$. ...
2
votes
1answer
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)
2
votes
1answer
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 ...
4
votes
1answer
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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:...
2
votes
2answers
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... ...
2
votes
3answers
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. ...
3
votes
1answer
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 ...
6
votes
1answer
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?
3
votes
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
1
vote
2answers
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 ...
4
votes
1answer
398 views

ElGamal Signatures

I know various applications of RSA signatures. I wonder, is there any real-world applications of ElGamal signatures and encryption?
0
votes
0answers
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 ...
1
vote
1answer
109 views

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 ...
1
vote
1answer
105 views

For $p=23$, $g=2$, $q=11$ you are given the signature $(18,3)$ in the message $m=2$. Construct a signature in the message $m'=3$

Alice uses an ElGamal signature in group $(Z/pZ)^{*}$ without using hash function. To sign the message $m \in (Z/pZ)^*$ calculates the signature $(r,s)$ as follows: choose random $k \in \{0, 1, \dots, ...
1
vote
0answers
135 views

ElGamal signatures systems

Let $p$ prime number $q/p-1$ prime and $g\in (Z/pZ)^*$ element of order $q$.Also $a\in \{1,...,q-1\}$ the private key and $y\equiv g^a\pmod p$ the correspoding public key.For each of the following ...
1
vote
2answers
856 views

El-Gamal signature with two messages

Alice uses an ElGamal signature with base the group $Z^*_{107}$ and parameter $g=3$ of order $q=53$.The private key of Alice is some $x \in \{0,1,.....,52\}$ and the public key of her is $y=10$. To ...

1
2

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.