Tag Info

Hot answers tagged ecdsa

12

How to provide secure “vanity” bitcoin address service?

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

9

How strong is the ECDSA algorithm?

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

7

Using same keypair for Diffie-Hellman and signing

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

7

What is the signature scheme with the fastest batch verification protocol for multiple signers?

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

7

Secp256k1 test examples

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

7

Can one reduce the size of ECDSA-like signatures?

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

6

Can ECDSA signatures be safely made “deterministic”?

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

6

X9.62 Multiplying an elliptic curve point by a number

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

6

What is the signature scheme with the fastest batch verification protocol for multiple signers?

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

5

Why doesn't this replay attack work on ECDSA?

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

5

What is the signature scheme with the fastest batch verification protocol for multiple signers?

I recommend you use Rabin signatures. Rabin signatures without batch verification are likely to be faster than most other signatures with batch verification. Moreover, read Dan Bernstein's work. He has shown how to make Rabin signatures even faster. For standard Rabin signatures, verification requires approximately one modular multiplication modulo n ...

4

Why are MACs in general deterministic, whereas digital signature constructions are randomized?

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

4

What is the signature scheme with the fastest batch verification protocol for multiple signers?

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

4

Making ECDSA public keys one bit shorter

I think your question can be reduced to the question whether there is a significant subset of weak public/private key pairs in any of the EC groups you mention. I am not aware of any such weakness, but if it exists, it would put a large dent in the security of Elliptic Curve Cryptography as a whole. If there is no significant risk you will get a key pair ...

4

Converting a DER ECDSA signature to ASN.1

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

4

Why is 2 the inverse of 10?

It looks like your main question is determining why $k{_{E}}^{-1} = 2$, correct? As mentioned in the comments to the question, this is because it is the modular multiplicative inverse. The multiplicative inverse is a number, $x^{-1}$, such that $x·x^{-1}=1$. However, since we are in modulo 19, we want to find $x^{-1}$ such that $x·x^{-1}\equiv1 \bmod 19$. ...

4

Using same keypair for Diffie-Hellman and signing

The paper "On the Joint Security of Encryption and Signature in EMV" shows that ECIES and EC-Schnorr signatures can be used together without compromising security: In the random oracle model ECIES-KEM and EC-Schnorr are jointly secure if the gap-DLP problem and gap-DH problem are both hard Ed25519 is extremely similar to EC-Schnorr, and both ECIES ...

3

How to properly add ECDSA private keys?

Well, the normal rules apply, i.e. $(aG + bG) = (a + b)G$, so as long as you add $a$ and $b$ correctly, everything should work fine. Note that you don't actually have to reduce the result of the addition for the point multiplication to give the same result, however your implementation may require the number to be smaller than the order. Also make sure that ...

3

How is the x coordinate of a “point at infinity” encoded in a Secp256k1 signature?

Well, the most common representation of 'point at infinity' would be a value that consists solely of zeros; that is, if normal points are encoded as a series of 64 bytes, then the point at infinity would be encoded as 64 00 bytes. On the other hand, it wouldn't appear to apply to ECDSA; ECDSA signatures consist of two integers between 1 and the curve order, ...

3

How to generate a public key from a private ECDSA key?

The write up on Wikipedia is pretty good. I won't go into all the detail that they do there, but your private key is a randomly selected integer $d_A$ selected from $[1,n-1]$ where $n$ is the order of the group. The public key is $Q_A=d_AG$ where $G$ is the base point on the curve defined in the publicly agreed upon parameters.

3

Academic papers on ECDSA security

I'm just reading the book Advances in Elliptic Curve Cryptography, and Chapter II (by Dan Brown) is about provable security of ECDSA. It lists some necessary conditions for the ECDSA components (group, conversion function, RNG, hash function), each with an associated forgery. For example, the group has to be resistant against discrete logarithms, as well as ...

3

Can A PRNG Be Used To Generate Multiple Private Keys for ECDSA?

The most important property of cryptographic PRNGs is that it's indistinguishable from true random numbers, unless you know the seed, or you have huge computational resources. Two important consequences of this requirement are: You can't find the seed from observing the output You can't predict more outputs from observing some of them. An attacker who ...

3

Can ECDSA signatures be safely made “deterministic”?

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.

2

Can one reduce the size of ECDSA-like signatures?

I don't think there exists an algorithm that could exploit the public key recovery feature in order to compress digital signatures, but even if such an algorithm existed, you would typically not want to use it. If you remove the information that determines the public key $Q$ from the signature $(r,s)$, it would seem plausible to assume that it would become a ...

2

How can I use Weierstrass curve operations with a=-3 for implementing operations for a=0?

I have not thoroughly investigated golang's elliptic library (or Go at all), but I have implemented elliptic curves (with Jacobian coordinates) and I would say that your guess is correct. The "$a$" parameter is not used in the addition of two distinct points, but it appears in the formulas for doubling a point. With Jacobian coordinates, a normal ...

2

Elliptic curves for ECDSA

It is easier to generate a point with order $n$ than to find out the order of a random point: Generate a random point $G'$ (generate random $x$ and solve for $y$) Compute $G = hG'$ (multiply by cofactor) This is guaranteed to generate a point $G$ with order either $n$ or $1$ (the point at infinity). The chance of generating the point at infinity ...

2

How is the x coordinate of a “point at infinity” encoded in a Secp256k1 signature?

Standard encoding of the point at infinity is a single byte of value 0x00 (it is defined as such as least in P1363, possibly also in X9.62). Other representations may exist (such as a lot of bytes of value 0x00), but, in truth, the "point at infinity" does not have well-defined X and Y coordinates. In the case of ECDSA, you generate a random value k which ...

2

Storage of Private Keys

About the best you can do is have a master public/private key pair where the public key is stored on your server and the private key is stored offline. When you generate a new private key, encrypt it with the master public key and store that in the database. That way, if a password is ever lost, you can recover the user's private key by using the master ...

1

Is there a method to break an EC curve for all key-pairs (Q,d) such that (Q=d*G) faster than breaking every single key-pair?

Well, Big-Step/Little-Step can be written as a precompute-table and then lookup type algorithm, however, it doesn't become close to practical with a 160 bit field. Here's how Big-Step/Little-Step works; we first select two integers $a$ and $b$ with $ab \ge size(group)$ (I consistently talk about group rather than the curve; that's because ...

1

Signatures: RSA compared to ECDSA

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

Only top voted, non community-wiki answers of a minimum length are eligible
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 46, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9310112595558167, "perplexity_flag": "middle"}