# Tag Info

17

I don't believe that there's any way to generate the vanity hashes without iterating. In base 58, there's $\log_2(58) \approx 5.858$ bits per letter, so fixing 8 letters would need in average $58^8/2 = 2^{\log_2(58)·8}/2 \approx 2^{46}$ iterations. Note that Bitcoin addresses always start with a 1 by convention (this comes from the version field), and the ...

17

There is a draft RFC which describes a way to implement deterministic (EC)DSA (with test vectors). In this draft, both $h(m)$ (the hash of the message) and $x$ are used as input to a deterministic PRNG which uses HMAC (that's HMAC-DRBG as specified by NIST); the PRNG output is used to yield $k$. I am not sure your simple multiplication with $x$ would be ...

14

First of all, I'm no expert in this area. Generally $n$ bit ECC seems to have a security level of about $n/2$, but I found some claims that it's lower for certain types of curves. RFC4492 - Elliptic Curve Cryptography (ECC) Cipher Suites contains the following table: for Transport Layer Security (TLS) Symmetric | ECC ...

12

Here are five test vectors for secp256k1, which I just generated with my own code. My code is a generic implementation of elliptic curves; it has been tested for many curves for which test vectors were available (in particular the NIST curves) so I tend to believe that it is correct. Each test vector is a value $m$ (chosen randomly modulo the curve order ...

11

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

10

Disclaimer: I don't know Javascript and I do not practice BouncyCastle. However, I do know Java, and ASN.1. ASN.1 is a notation for structured data, and DER is a set of rules for transforming a data structure (described in ASN.1) into a sequence of bytes, and back. This is ASN.1, namely the description of the structure which an ECDSA signature exhibits: ...

10

On a general basis, you want to keep encryption and signature keys disjoint, because they tend to have distinct life cycles. In broad terms, an encryption key should be escrowed, because loss of the private key implies loss of the data which is encrypted relatively to the public key. However, a signature key must not be escrowed, since the proof value of a ...

10

Let me first answer your actual question (and then I'll proceed to answer something slightly different that I think will be informative and helpful). Your question asks whether it's possible to use only a DSA key. Technically speaking, this is of course possible. The reason is that a DSA key has exactly the same format as an ElGamal key. No one forces you to ...

9

ECDSA is actually a kind-of computational zero-knowledge protocol, played by the signer, with a "reduction function" as impartial verifier. For that matter, ECDSA is not very different from plain DSA. Things basically go this way. There is a known public group $\mathbb{G}$ which I will denote additively, with $G$ as generator, and of size $q$ (a known prime ...

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

Rabin signatures have a very fast verification algorithm: a simple squaring modulo some integer. RSA signature verification (with a public exponent equal to 3) is also very fast. These signature algorithms are simple to implement and will beat ECDSA for verification speed, even if batch verification is used for ECDSA. The Niederreiter digital signature ...

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

8

Yes. Modern cryptosystems are designed and analysed under the assumption that the key is never used for anything else. If you use your encryption keys for digital signatures, you are violating that assumption, and it is very easy to construct schemes where this violation will compromise security. It is possible to construct schemes that can use the same ...

7

In their 1998 SAC paper, M'Raihi et al showed how to use hash functions to turn Schnorr signatures (quite similar to (EC)DSA) deterministic, and proved that if the original signature scheme (with randomness) is secure, so is the deterministic one. Bernstein et al's recent EdDSA signature scheme uses the same technique to avoid randomness.

7

Well, you understand that Elliptic Curves define an operation on points we denote as +; that is, if $A$ and $B$ are two (not necessarily distinct) points, then $A+B$ is a third point (which will be distinct unless either $A$ or $B$ are the 'point-at-infinity'). If $A$ and $B$ are the same, the operation is usually called doubling instead of addition. Now, ...

7

You got tripped up by the fact that there are two different group operations in play here, and they don't play nice with each other. This is implicit in the notation, and it's easy to get tripped up, because the notation expresses both operations in the same way -- but they are not the same. This is arguably a pitfall in the notation: the assumption is ...

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

7

All points on an elliptic curve verify, by definition, the curve equation, usually written as $Y^2 = X^3 + aX + b$, with two given $a$ and $b$ parameters (these two parameters actually define the curve). So, if you know $X$, you can use the curve equation to recompute $Y^2$. A square root extraction will yield $Y$ or $-Y$. The compressed point format ...

7

Actually, it is not possible to uniquely recover the public key from an ECDSA signature $(r,s)$. This remains true even if we also assume you know the curve, the hash function used, and you also have the message that was signed. However, with the signature and the message that was signed, and the knowledge of the curve, it is possible to generate two ...

7

No, in general the hash isn't determined by the curve definition by NIST. Reasonable mappings of course exist (for a 224 bit curve you would probably use a hash with output size of 224 such as SHA-224). The hash used should however be specified by the protocol itself. The ECDSA key size as indicated by the -b of the openssh argument is linked to the hash ...

6

I'm surprised that Daniel J. Bernstein's EdDSA has not been mentioned. High-speed high-security signatures Even faster batch verification. The software performs a batch of 64 separate signature verifications (verifying 64 signatures of 64 messages under 64 public keys) in only 8.55 million cycles, i.e., under 134000 cycles per signature. The ...

6

There isn't a simple answer, as speed of batching depends on a number of parameters. First, the speed of the signature and the speed of the batching is largely independent. If you have two signature algorithms S1 and S2 that both permit batching technique B1, then generally they will both permit batching technique B2. If S1 is faster than S2 for individual ...

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

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

No, signing the hash of the public key cannot introduce a weakness on a secure signature scheme. When we have a signature scheme, we assume that it is secure in an chosen text model, where the attacker has access to the public key, and can ask any text of his choosing to be signed. We can see that any such scheme (such as ECCDSA, or so we believe) cannot ...

6

ECDSA should in general create signatures faster than RSA for the same cryptographic strength if you just look at the mathematics. In the end the modular exponentiation is performed for smaller numbers. However, ECDSA depends on a random number generator, so ECDSA speeds may be slower if the random number generator blocks for any reason (and not using a good ...

6

BouncyCastle has a really bad ECC implementation. It uses affine coordinates which incur a huge performance hit (factor 20 or so) since it computes a field inversion after every single step. Good implementations use Jacobi coordinates (or a similar approach) where denominators are kept and there is only one field inversion at the end. It's also potentially ...

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

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