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

7

Well, it's been an entire day, and no one has given an authoritative answer; I'll throw in my guess as to why the people designing DSA made the choices they did. With DSA, there are three operations that are relevent to this discussion: A: do precomputation of a signature (without seeing the message being signed) B: given a precomputed signature and a ...

7

If you compare DSA with SHA-256 and a 2048 bit group modulus $p$, to RSA with SHA-256, a 2048 bit modulus $n$ and public exponent $e = 65537$, on you will at least perform the following operations: DSA $g^{u_1}y^{u_2}$ - 2*256 squares $\mod p$, up to on average 2*128 multiplications $\mod p$, depending on implementation optimizations. RSA $s^e$ - 16 ...

6

We are talking about signatures here, not encryption. The two activities are quite different. In the case of signatures, there is nothing secret except the private key, whereas in the case of encryption, both the private key and the message to encrypt should remain confidential (you encrypt the data precisely because you want to keep it confidential). ...

4

You got three equations with two unknowns ($k$ and $x$). You only need two signatures to solve the private key $x$: $s_1k \equiv h_1 + xr_1 \pmod q$ $s_2k + s_2 \equiv h_2 + xr_2 \pmod q$ This might be solved using Gaussian elimination. Step 1: $s_1k/r_1 \equiv h_1/r_1 + x \pmod q$ - Divide 0.1 by $r_1$ $s_2k + s_2 - s_1kr_2/r_1 \equiv h_2 - ... 4 I am given$p = 4916335901$,$q = 88903$and am asked to show these are prime To check whether a given integer$n$is prime you have to check whether it is only divisible by$1$and$n$, i.e., that it is not a composite integer. If you are given such an integer you can either factor the given integer, use primality tests to check for primality or in ... 4 There are two ways to solve a discrete log problem over$Z^*/p$, that is, given$g$and$h$, find$x$with$h \equiv g^x \bmod p$: If the point$g$generates a subgroup of size$q$, use a general Discrete Log algorithm (such as Pollard Rho) to recover$x$in$O( \sqrt{q})$time. Use the Number Field Sieve algorithm to attack the discrete log problem in ... 3 Well, lets go through the issues: It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone Nope, not quite. You also need the message being signed. And, with that, it doesn't give you the unique public key; it does allow you to narrow it down to two possibilities (assuming you're using a ... 3 From these three, ECDSA is faster - it does arithmetic with smaller numbers, and is thus faster. (RSA verification is faster than ECDSA, even though it uses larger numbers, because it computes a exponentiation by a small number.) Still, elliptic curve Schnorr signature should be around 5-10% faster than ECDSA (or even more in a side-channel resistant ... 2 In a sense, you are correct in not understanding where the equations in DSA and ElGamal signatures come from. To a certain extent, they are just (distinct) choices from a family of equations that all seem to work, and all for the same-ish reasons. See e.g. Meta-ElGamal signature schemes by Patrick Horster, Holger Petersen, Markus Michels, ... 2 The fundamental difference between RSA-groups and prime order groups is that in RSA groups the multiplicative order of the group is unknown (without knowledge of the factorization). This allows much easier constructions for unforgeable signatures (although hashing and padding are required to ensure existential unforgeability). With knowledge of the group ... 2 If the messages are unknown, there are no two messages$m_i, m_j$such that$m_i = m_j$and the messages have sufficiently high entropy (which might be shared across several messages, if the hash function is a CSOWF and the messages e.g. have low entropy unique sub strings or are made unique in some other way), and the underlying hash function is secure in a ... 1 Ok, back to my initial answer (which I edited to the last version, thinking that you did not choose an appropriate generator): I now think that you may calculate the inverses wrongly: I tried it with$k=2$and get:$r=9,k^{-1}=6, s=10, w=10, u_1=3, u_2=2$which works out. Just as an additional comment: Choosing a generator Since the order$11\$ is ...

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