# Tag Info

9

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

9

I'm considering switching to ECDSA, would this require less space with the same level of encryption? The answer to that question is yes, both ECDSA signatures and public keys are much smaller than RSA signatures and public keys of similar security levels. If you compare a 192-bit ECDSA curve compared to a 1k RSA key (which are roughly the same security ...

8

One rationale for avoiding randomized schemes in general, and in MACs in particular, is that the random in such schemes tends to increases the size of cryptograms or reduce the size of the payload. An example is scheme 2 in ISO/IEC 9796-2 RSA signature with message recovery, where the size of the random/salt field is directly antagonist with the amount of ...

8

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

6

Well, no, it is not safe to use a GCM authentication tag as a hash. If you know the key, it is straight-forward to find preimages; that is, find a message that hashes to a specific target value. Note that you asked for second preimage resistance; not only does it fail to provide that, it fails to provide the weaker preimage resistance. CCM and OCB have ...

5

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

5

The discrete logarithm problem can be attacked with either a specific or a generic algorithm. A specific algorithm is one that tries to exploit structural weaknesses of the specific group in which discrete logarithm is used; e.g. Index Calculus when we are talking about exponentiation modulo a big prime. Generic algorithms only use the group law and thus ...

5

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 - ... 5 According to How PGP Works it uses a hybrid approach that generates a secret key for symmetric encryption. The wikipedia page for GPG then indicates that CAST5, Camellia, Triple DES, AES, Blowfish, and Twofish are the supported ciphers. 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 ... 4 In DSA (and ECDSA), it is possible and common to share the same domain parameters, across multiples users. AFAIK (and according to common wisdom, including FIPS recommendations) this introduce no known security weakness. The only common reasons to change domain parameters are to increase key size, or purposely introduce on interoperability barrier (e.g. to ... 4 Well, if the hash function is weak, then the attacker might be able to take a valid signature for a signed message, and find a second message for which the signature for this first would also validate for the second. For example, if Alice signs the message "I like chocolate", what Bob might do is find a second message "Alice owes Bob$13,106,107.57", and ...

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

3

It depends how you define what a "public key" is. Typically it is the value of the key itself ($y$), plus information about the group (safe prime $p$, subgroup size $q$, generator of subgroup $g$). For signing a message, you do not need the value of the public key itself. So if you are strict in defining a "public key" to only be $y$, it is not needed to ...

3

According to this answer, RSA with the "usual" "padding scheme, described in PKCS#1 as the 'old-style, v1.5' padding," can be made to satisfy that; one would need to specify NULL or omission and require that the public exponent's prime factors are all easily findable and sufficiently bigger than the 4th root of the modulus.

3

Generically speaking you can do this but you shouldn't. It may well be possible to perform specific calculations when a random number is used for both (I'll leave it to the more theoretically inclined to create a demo if this is possible for ElGamal / DSA). Another reason is that the single secret gets known then both keys/algorithms will be compromised. ...

2

For a 128 bit security level, you need 256 bit ECC. Compressed public keys need about 32 bytes, and signatures use 64 bytes. The verification time depends a lot on the choice of curve, representation and implementation. Ed25519 Is supposed to be one of the fastest versions, especially if you use batch verification. But I'm not sure if it's possible to ...

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

2

So I actually asked the theoretical version of this question a while ago: what happens if you choose multiple keys from the same group? The answer, as best as I determined, is its still secure. First, this practice is used both in the Internet Key Agreement Protocole (IKE) in IPSEC, and for SSH. Second, the best algorithms for breaking DSA effectively ...

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

No. Public key encryption has to be probabilistic (in the sense that we have generic attacks against deterministic encryption schemes), but signatures don't. RSA-FDH is one example of a fully deterministic scheme that is usefully secure.

2

I don't think there's an exact "correct" behaviour in this case. It would be up to the implementation to decide, since the spec is only concerned about the DER encoded portion. If your implementation parses the input as it moves along only, and doesn't concern itself with the overall size, then it would work fine. Having said that, I believe the best ...

2

It depends. If the entire input itself is within a DER encoded structure, then I would bug out. There is nothing defined for BER, CER or DER that would allow padding of structures within constructed values. If the input is just followed by additional data or junk bytes then it is up to the protocol or otherwise your discretion if you want to accept the ...

1

While no SHA1 collisions have been found, there are some attacks: ~$2^{60}$ collision attack. Estimated to cost around \$1-2 million currently in the cloud. Possibly economical soon, especially with specialized hardware. Intractable preimage attacks like$2^{151}$against reduced round variant,$2^{159}$against full hash. (Cf.$2^{160}\$ brute force on any ...

1

In the case of emails your solution is not really practical. The problem is that the sender of an email uses the public key whereas the receiver should have the secret key. This means that whenever somebody wants to send you an email (and therefore generate a new key) you have to be online or you have to provide a set of pre-computed key pairs. If multiple ...

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