Tagged Questions

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.

learn more… | top users | synonyms

0
votes
0answers
17 views

Validity of ElGamal signature variation

I'm trying to solve excersise 7.6 from Hoffstein - Introduction to Mathematical Cryptography page 459 (http://goo.gl/oRyInT) Let $p$ be a prime and let $i$ and $j$ be integers with $gcd(j, p − 1) = ...
2
votes
1answer
44 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 ...
1
vote
1answer
85 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
103 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 ...
1
vote
0answers
84 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 ...
1
vote
1answer
135 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$ ...
5
votes
1answer
988 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 ...
0
votes
0answers
110 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
230 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 ...
1
vote
0answers
146 views

Why do we need to hash both the message and the $h$ value in ElGamal signature?

The professor left us a question on ElGamal signatures: Given the hash function $H$ and message $M$, choose a random $r$ and compute $h=g^r$ and $H(M||h)$. Show that, if $H(M)$ is used instead of ...
2
votes
1answer
210 views

ElGamal signature: Forging a signature of a specific form

I have a question I can't solve from one of the courses I'm currently taking: Show that given a legitimate ElGamal signature $(S,R)$ on a given message $m$, an attacker can compute a signature ...
3
votes
1answer
338 views

Can ElGamal encryption and ElGamal signatures be used together sharing the same key-pairs?

I'm working on a encryption system where each party can store exactly a single ElGamal private key in a device. This is a hardware limit. The system must be expanded to support signatures and ...
5
votes
1answer
302 views

Safe generator for ElGamal signature

What are the properties a generator $g$ should have to be secure for ElGamal signatures (original scheme)? I am aware that it is poorly chosen and not secure when $g|p-1$ or $g^{-1}|p-1$, where $p$ ...
1
vote
1answer
475 views

Recovering the key in an ElGamal Signature Scheme variant

From page 318 in Stinson's "Cryptography: Theory and Practice", question 7.3: Suppose that Alice is using ElGamal Signature Scheme. In order to save time in generating >the random numbers k that ...
3
votes
1answer
208 views

Elgamal test vectors

I know that Elgamal algorithms have fallen out of fashion, and they are not included in any widespread cryptographic standard nowadays. However, they are still present in several popular crypto ...
5
votes
1answer
2k views

ElGamal Signature Scheme: Recovering the key when reusing randomness

Show how if Alice uses the same value of $k$ to sign two different messages $m_1$ and $m_2$, using the ElGamal signature scheme, Eve can recover the value of $a$ from the corresponding signatures ...
4
votes
1answer
893 views

Why is ElGamal considered non-deterministic?

One difference between RSA and ElGamal is that ElGamal isn't necessarily deterministic (while RSA is). What makes it non-deterministic? Is this advantageous to security? How else does this property ...
7
votes
1answer
830 views

How can one show that an ElGamal-like signature verification scheme is valid?

For an ElGamal-like signature scheme, I am given two things: The signing function, the verification function. How can I show that the verification function is valid? Example 1: Signing: $s := ...
3
votes
1answer
338 views

ElGamal message signatures retrieving the secret value x

If the GCD(r, p-1) is small and the value k is used to sign a message using ElGamal is also small. Then the secret value of x can be determined. Why is this true? How would one retrieve x?
3
votes
1answer
272 views

ElGamal signature - exploiting fallacious implementation

This question is related to ElGamal signature scheme as defined here ElGamal signature without calculating the inverse Show how one could exploit an implementation ElGamal signature scheme in which ...
5
votes
2answers
637 views

ElGamal signature without calculating the inverse

I stumbled upon this question in some textbook. Propose a variant of ElGamal signature scheme such that there is no need to calculate the inverse $k^{-1}$ as it is usually done using the EEA. ...