# Tag Info

## Hot answers tagged elgamal-signature

13

Apparently, Schnorr was quite adamant, at that time, about the applicability of his patent to DSS. See this message and that one. These are from 1998, but the controversy had begun earlier; see for instance this bulletin from NIST, from late 1994, where references to it can be found in the "Patent Issues" section. Interestingly, NIST not only tried to avoid ...

8

In this context, "nondeterministic" means that the algorithm to generate the ciphertext (or the signature) takes a random value as one of its inputs, and it can generate many possible ciphertexts (or signatures) based on the random value. ElGamal is nondetermanistic because the encryptor selects a random exponent as a part of encryption method. For public ...

7

That looks about right. Assume we have two messages $m_1$ and $m_2$ and the corresponding signatures $(r,s_1)$ and $(r,s_2)$ generated using the same $k$ (where $r=g^k$ is thus the same for both signatures). If we could assume that $s_1 - s_2$ and $r$ were invertible modulo $p-1$, we could simply compute $$k \equiv (m_1 - m_2)(s_1 - s_2)^{-1} \mod p-1$$ ...

5

Your scheme is not the "true" ElGamal signature scheme: you swapped $x$ and $k$. I assume that $m$ is the hash of the message to sign, not the message itself. Your scheme is sound, which means that the verification algorithm will return "ok" for a signature which has been generated as you suggest. To see that, remember Fermat's Little Theorem which says ...

4

It seems that you mix things up. ElGamal signatures are existentially forgeable in various different ways if it's not using the hash-then-sign paradigm, i.e., you sign the message directly instead of signing the message $m=H(M)$ with $H$ being a secure cryptographic hash function. Given the type of forgery in your question that works, you compute your ...

4

As an alternative solution to the correct answer that Barack has posted, if you have $p=7 \bmod 8$, then the selection $g=2$ works just fine. In this case, $g=2$ is a quadratic residue (and hence has order $(p-1)/2$). In addition, you can show that if you can decrypt ElGamal messages with $g=2$, then you can decrypt ElGamal messages with any $g$; hence we ...

4

If $q$ is prime (which is a common additional constraint) then the possible orders for a random $F_p$ between $2$ and $p-2$ inclusive is either $q$ or $2q$ so you can avoid having to check the order by picking one at random, squaring it and using the result.

4

The order of $(\mathbf{Z}/3^{1000}\mathbf{Z})^*$ is $\varphi(3^{1000}) = 2\times 3^{999}$, which is a highly composite number, and hence the discrete logarithm in this group is highly vulnerable to the Pohlig-Hellman algorithm. If you are not familiar with the Pohlig-Hellman algorithm, you can peruse for example Section 2.9 of the book by Hoffstein, Pipher ...

3

With your proposed modification of the ElGamal signature scheme you can produce forgeries for arbitrary (hashed) messages $m$. By looking at the verification equation $$g^m = yr^s$$ you just have to set $r$ to $r=(g^my^{-1})^{s^{-1}}$ (just by rearranging the verification equation) which you can do for any $s$ from $\mathbb{Z}_{p-1}^*$, i.e., every $s$ ...

3

Basically because of Fermat's little theorem: if $a$ is not divisible by $p$ then $a^{p-1} = 1$ $mod$ $p$. A part of the expression for $\delta$ appears as a power of $a$ in the ElGamal signature verification equation, which "happens" to work because it is reduced modulo $p-1$ so Fermat's little theorem applies.

3

Well, we can approach it this way: if we denote the hashes of the two consecutive messages $H_1, H_2$, the signer used the internal values $k, k+2$, resulting in signatures $(r_1, s_1), (r_2, s_2)$, then we have (and all this arithmetic is modulo $p-1$): $s_1 = (H_1 - x r_1) k^{-1}$ $s_2 = (H_2 - x r_2) (k+2)^{-1}$ where $x$ is the secret key we're ...

3

$\newcommand\gcd{\operatorname{gcd}}$Let's have a look at the signature equation: $$s = (H(m) - x·r)·k^{-1} \mod (p-1),$$ $$s·k = H(m) - x·r \mod (p-1),$$ and thus $$H(m) - s·k = x · r \mod (p-1).$$ $d = \gcd(r, p-1)$ means we find (efficiently, given $r$ and $p-1$, using the extended euclidean algorithm) a $z$ such that ...

3

Try switching $\alpha$ and $\gamma$ during the verify. Fix a prime number $p$ and a generator $\alpha$ of $Z_p^*$. User $A$ then chooses a number $a \in \{0, \ldots, p-1\}$ as its private key and sets $\beta = \alpha^a \pmod{p}$ as its public key. To sign a message $x$, $A$ chooses a random $k \in Z_{p-1}^*$. The signed message is then $(\gamma, ... 2 Schnorr signatures and KCDSA are two ElGamal variants that don't need an inverse for computing a signature. 2 It depends. It depends on a lot of things. For example a generator of 2 is great for encryption, but makes for awful signatures. If you use a generator of 2, then no. Your signatures will get broken. Then the encryption will. Elgamal signatures are pretty controversial. They're tetchy to get right (see above) and there are many things you can get wrong. ... 1 Just read the original paper for ElGamal signatures. Especially one of the attacks in section IV. B should help you out. Alternatively, the Wikipedia article about ElGamals signatures also has a section about existential forgeries. Since this is clearly homework, I'll leave the rest up to you. One last hint: Use q instead of p-1, since you're actually in a ... 1 Before continuing to read this answer, read my above hint: Try writing down all the equations for the different s and try to solve the system of equations. If you still can't solve this one, you may read the remainder of the answer. First observe that$s_1 \equiv k_1 \cdot h(m) + r_1\cdot x \pmod {53}$and$s_2 \equiv k_2 \cdot h(m') + r_2\cdot x ...

1

There have been some research in Optimal Extension Fields (OEF), introduced at Crypto'98 by Bailey and Paar paper. The idea is to work in a field $GF(p^n)$ with $p$ prime and of the form $2^{32}\pm c$ with small $c$ for 32-bit CPUs ($2^{64}\pm c$ for 64-bit CPUs), so that they can leverage on CPU's ALU for most computations, therefore OEF based systems are ...

1

Yes, cryptosystems like ElGamal or Shnorr based on the intractability of Dlog Problem are are indicated to be implemented on finite field, which is not the case of the RSA for which a model was proposed in the early $80^{ies}$, and immediatly broken. As you know, a finite field is denoted by $GF(q)$ where $q=p^m$ and p would be any Prime. But in the case ...

1

First, I think you have a typo in your question since in the original article $s = (M - x y)(r^{-1}) \mod p-1$, and not $s = (M - x^y)(r^{-1}) \mod p-1$. Knowing that, then we can construct $s_2$ from $s, r, M$ and $M_2$: $s_2 = s + (M_2 - M)r^{-1} = (M - x^y)r^{-1} + (M_2 - M)r^{-1} = (M - x^y + M_2 - M)r^{-1} = (M_2 - x y)r^{-1}$ A valid signature for ...

1

First you should know that Elgamal encryption and signature security is based on DDH problem (Decisional Diffie Hellman) which is tractable in some groups that CDH problem is believed to be hard (Computational Diffie Hellman). As in the case of $\mathbb{Z_q}$ in which CDH is believed to be hard but DDH is apparently tractable. Let $p = 2p_1 + 1$ where both ...

1

At first glance $r = s^{-1} (M - a^y) \bmod p-1$ would appear to be what you're looking for. If $s$ isn't invertable modulo $p-1$, then you can work around this by working with the factors of $p-1$; in this case, $p-1 = uv$ where $s$ is a multiple of $u$ and $s$ is relatively prime to $v$. So, we can solve: $r_v = s^{-1} (M - a^y) \bmod v$ and so we ...

1

I assume that the deadline for the homework is passed, so I will provide an answer: Let us assume that we have the public key $y=g^x \pmod p$ and the private key to be $x$. Computing an ElGamal signature for a message $m \in Z_p^*$ amounts to: choosing $k\in Z_p^*$ $r\equiv g^k \pmod p$ $s\equiv (m-xk)k^{-1} \pmod{p-1}$ which is equivalent to \$m\equiv ...

1

There seem to be no standardized ElGamal test vectors available in the public domain. However, there are some ElGamal test vectors generated with libgcrypt 1.5.0 available in this fork of the pycrypto project.

1

Hint #1: Chinese remainder theorem.

Only top voted, non community-wiki answers of a minimum length are eligible