Tag Info

Hot answers tagged

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


3

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


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

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



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