Tag Info

8

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

5

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

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

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

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$\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 ... 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 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 ps\equiv (m-xk)k^{-1} \pmod{p-1}$which is equivalent to$m\equiv ...

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

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.

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