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.
2
votes
1answer
123 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,(\...
3
votes
0answers
147 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
76 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
339 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
96 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 ...
3
votes
2answers
989 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
594 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
204 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 ...
3
votes
1answer
185 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
127 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
64 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
371 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
826 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$.
...
0
votes
1answer
438 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
250 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
256 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
144 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
313 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
667 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
91 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
765 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
111 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
362 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
753 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
547 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 ...
5
votes
1answer
3k 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
719 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
171 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 ...
2
votes
1answer
132 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
262 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 ...
0
votes
1answer
437 views
Inverse in ElGamal signature
I am learning about ElGamal signature verification. During the signature generation one has to choose a k such that ...
2
votes
2answers
536 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
237 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
85 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
85 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
98 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
118 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
464 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 ...
3
votes
0answers
170 views
Why does the ElGamal signature have the specific form that it does?
In the original paper, ElGamal(1985) starts his discussion of signatures by saying:
"The signature ..... is chosen such that the equation:
$\alpha^m = y^r r^s \text{mod p}$ (equation 3 from the ...
1
vote
2answers
276 views
Usage of GF(p^m) fields, where p != 2
$GF(2^m)$ Galois fields are widely used in different cryptographic algorithms, for example, in Rijndael.
However, $GF(p^m)$ fields are possible with any prime $p$, not only 2, but $GF(2^m)$ fields ...
2
votes
0answers
190 views
Recovering El Gamal secret key from signatures [duplicate]
Assume out of a set of ElGamal signatures, I've discovered that two have the same y i.e. $signature_{1}$ on $m_{1}$ = $(y,s_{1})$ and $signature_{2}$ on $m_{2}$ = $(y,s_{2})$.
The public keys for $...
3
votes
2answers
1k views
How does hash function in Elgamal signature scheme prevent existential forgery attack?
I have heard that hashing the message M prevents an existential forgery attack. I was wondering how.
3
votes
1answer
225 views
ElGamal signature scheme: Why is r included in s
In the ElGamal signature scheme we calculate a signature for a (hashed) message $m$ as
$r \equiv_p g^k$,
$s \equiv_{p-1} (m - xr) k^{-1}$
and verify it by checking
$g^m \equiv_p y^r r^s$.
Here $r$...
1
vote
1answer
533 views
ElGamal digital signature. why mod p-1 in delta?
Im trying to figure out why $\delta$ in the signature part of ElGamal has mod $p-1$ when $\gamma$ has mod $p$?
$\gamma = \alpha^k \mod p$
$\delta = (x-a\gamma)k^{-1} \mod p-1$
1
vote
1answer
179 views
Is ElGamal still unforgable if the adversary knows r
Is ElGamal still unforgable if the adversary knows the value of $r$ that was calculated by $g^k$?
When we do sign the message $msg$, we calculate $r = g^k$.
As we know the regular ElGamal ...
3
votes
1answer
449 views
Generating a valid signature on El-Gamal without knowing the private key
Suppose we are given $p$, the large prime, $g$ which is the primitive root for $p$, $b$ which is calculated as $b=g^x$ mod $p$ where $x$ is the private key and $0<x<p-1$.
Also suppose we know $...
2
votes
1answer
244 views
Recovering the random number r
For a padded message, M, using the El Gamal encryption schema, how can we determine the random number $r$, when we are given $p$, the prime number, $g$ which is the primitive root of $p$, $b$ and $x$ ...
12
votes
1answer
5k views
DSA vs. ElGamal vs. Schnorr
It has been well known for a long time that NSA played a primary role in the development of the Digital Signature Algorithm (DSA).
DSA is a sort of hybrid of the ElGamal and Schnorr signature schemes....
1
vote
0answers
155 views
RSA vs El Gamal digital signature. Which is more secure? [duplicate]
I'm reading about the notions of security concerning digital signatures and I can't understand whether RSA is more secure than El Gamal digital signature. Well, they are both prone to forgery, but I ...
1
vote
2answers
976 views
ElGamal: Generation of “g” value?
I haven't been able to find a clear explanation on this (and I'm probably just confused in general). I have the following parameters of ElGamal signatures:
$p$ = safe prime
$q = (p-1)/2$
$g$ = an ...
