# Tag Info

15

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

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$$ ...

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 ...

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 ...

5

TL;DR: The main reasons to prefer RSA over ElGamal signatures boild down to speed, signature size, standardization, understandability of the method and historical establishment as the result of a lot of lobby work. The main technical advantage of RSA is speed. With RSA you only need to do a small-exponent exponentation to verify a signature, where as with ...

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

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 $m$...

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

$\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

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

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, \delta)$ ...

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. ...

2

I wonder, is there any real-world applications of ElGamal signatures and encryption? Rarely. ElGamal encryption is used very rarely, with GPG being nearly the only common tool, not library, to historically support ElGamal due to patent restrictions with RSA. Other than that it sees little use due to RSA being better promoted, supported and standardized. ...

2

Existential forgery attacks allow the attacker to choose (or calculate) a signature, and then the message is derived from this signature (and the public key) using the existential forgery attack algorithm. The signature is valid for the derived message, but the problem is that the attacker cannot control the message. It could be anything. Hashing the ...

1

For $c\ne0$, the definition of $a\equiv b\pmod c$ is: $\exists d\in\mathbb Z$ such that $a=b+cd$. Applying that definition to $H(m)\equiv xr+sk\pmod{p-1}$, we have that $\exists d\in\mathbb Z$ such that $H(m)=xr+sk+(p-1)d\;\text{ (equ. 1)}$. Fermat's little theorem is that for $p$ prime and $g\not\equiv0\pmod p$, it holds that $g^{p-1}\equiv1\pmod p\;\text{... 1 Thanks to fgrieu's comment above and the following quote from here (PDF): Theorem: Let$p$be a prime and let$a$be a number not divisible by$p$. Then if $$r \equiv s \pmod {p − 1}$$ we have $$a^r \equiv a^s \pmod p$$ In brief, when we work$\mod p$, exponents can be taken$\mod{p − 1}$. I (think i) understood, how the first (implicit) ... 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 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 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

Daniel Bleichenbacher has described such kind of attacks in his article Generating ElGamal signatures without knowing the secret key. (PDF) He noticed that if verifier would accept signatures where $r$ is larger than $p$ then any signature $(r,s)$ on $H(M)$ could be used to generate a signature $(r2, s2)$ on arbitrary hash value $H(M2)$. For that attacker ...

1

It's not a complete answer because an adversary needs control on the random choice of a signing algorithm. First let me define ElGamal signature to not get lost in notation. $x \in N$ is the secret key. $p$ is a prime, it defines $Z_p^*$. $g$ is a generator of $Z_p^*$. $y=g^x$ and the public key is $(p, g, g^x)$. Then $k$ is picked at random from $0<k&... 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 ps\equiv (m-xk)k^{-1} \pmod{p-1}$which is equivalent to$m\equiv ...

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