Tag Info

6

A couple things: This article is two years old, so take its predictions with a grain of salt. In the two years that have elapsed, the predicted advances have not materialized, and there is little indication they will soon. The core of those arguments was Joux's 2013 result on the discrete logarithm problem in finite fields of small characteristic. Those ...

6

Yes a brute force key-guessing attack would be faster, but: It would be ridiculously slow for either. E.g. see this for 256-bit keys. There are faster attacks on both and those attacks break larger RSA sizes than ECC sizes. Related: Why can ECC key sizes be smaller than RSA keys for similar security?

5

I'll consider that you are using a 256-bit curve per ANSI X9.62:2005. Not all 256-bit bitstrings are a formally valid private key; when using big-endian conventions, these must represent a positive integer less than $n$, the order of the largest prime order subgroup. For the Koblitz curve secp256k1 of SEC 2, ...

4

Points on secp256k1 fulfill the equation: $$y^2=x^3+7 \pmod p$$ Your 257 bit compressed point consists of the sign* of $y$ and the value of $x$. You probably want to restrict $x$ to $0 \leq x < p$ as a canonical representation. Since $y^2$ is obviously a square, we need to look at $x^3+7$ to see if it's a square as well: If $x^3+7$ is a square, ...

4

There are three ways to look at it: The mathematics. An elliptic curve key pair is defined as $s, s \cdot G$, where $s$ is an integer, $G$ is the base point and $\cdot$ is elliptic curve point multiplication (scalar multiplication). There is no requirement for $s$ to be smaller than the order of the base point, so you could allow the private key to be ...

3

Yes, there is an exact mapping between valid private and public key. The public key is essentially a representation of a point of the curve (not at infinity), obtained as the private key's representative integer times the generating point. All the points on the curve (not at infinity) are obtained for some public key, and are a valid public key. Depending ...

3

Yes, RSA is an example of a cryptosystem where this is possible. The message is encrypted using the recipient's public key only and even the sender could not decrypt it. However, in the comments you mention that you would like to minimize storage requirements. RSA would require e.g. 2048 bits for just the message. In comparison, with ECIES sending a ...

3

Standards for Efficient Cryptography Group has published SEC1: Elliptic Curve Cryptography (pdf) about elliptic curve algorithms. If it does not explain the mathematics well enough for your purposes, there is also Fundamental Elliptic Curve Cryptography Algorithms (RFC 6090, from IETF) you could look at. There are a lot of issues you can run into, so ...

3

This approach will work, but there's another approach I want you to suggest. As for why it's secure (or better the ways to attack): Break the elliptic curve discrete logarithm problem. If you can do this you can just grab the first address out of your addresses, solve for the private key and derive all subsequent ones. This is generally considered ...

3

As otus already stated in his comment, the correct term for bytes to be signed is “message”. Generally, it does not really matter if a message to be signed is human readable or not. Sometimes, you may also find it mentioned as “digital message”… which practically is the same and merely extends the term to explicitly hint at the fact the message is digitally ...

2

The answer to the question in the title is yes, provided you define "valid keys" appropriately. Since you also do not name a specific cryptosystem you had in mind, I will assume a common denominator: instances of the elliptic-curve discrete logarithm problem. This leads to the following definitions Public parameters: an elliptic curve $E$ and a point $G$ ...

2

We aren't aware of any sich relations. In fact, one assumes that the group of elliptic curve points behave like a Generic Group. A generic group is a group, where the encoding of the elements are chosen as a random values.

2

Trivial solution: generate a random $k$ as part of the private key and include $r$ as part of the public key. The verifier uses $r$ from public key, so the signer must use the same $k$ for every valid signature. The signer could create multiple related public keys and reuse $D_A$, but then, they might as well just create multiple key-pairs in the first ...

2

Generate a random symmetric key (for example an AES key). We will use it only once for this transmission, and call it the session key. encrypt the session key with the public key encrypt the message with the session key forget the session key transmit the two encrypted message to the recipient Since you are using a whole new encryption key for every ...

1

Strictly speaking EdDSA, as defined in "EdDSA for more curves" by Bernstein, Lange et al., can only work for (twisted) Edwards Curves. Thus, IMHO, the correct answer your question is no. In the paper, they define the curve parameters as being the parameters of a (twisted) Edwards curve, the addition law as the addition law on twisted Edwards curves, etc. ...

1

The size of the public key depends on the elliptic curve used. Any private key will produce a point on the curve, which is the same size – approximately 256 bits for 256-bit curves, for example. Random numbers from a small range could be insecure, however. The secure way to generate the private key is to take it from the range $[1, l-1]$, where $l$ is the ...

1

To my knowledge, NIST has not really decided or announced anything about successors to ECC. However, they do run workshops and such on post-quantum cryptography, so when the time is right something will probably move towards standardization. NSA, on the other hand, recently announced that they will soon push for a post-quantum system, going so far as to say ...

1

Secp256k1 is a curve, not a scheme - you can build different schemes over it that have different private/public key relationships. If you do plain ElGamal on secp256k1 for example, $Q_A = D_A . P$ for a public base point $P$ so you get the usual key-sharing properties: if my keypair is $(D_A, Q_A)$ and yours is $(D_B, Q_B)$ then anyone can compute \$Q = Q_A ...

1

There are no relation we are currently aware of. The reason is as follows. The map $$k \mapsto (k G).x$$ is assumed to be a good pseudo random number generator. (The NSA infiltration of the Dual EC drgb has nothing to do with that fact). This basically says that k and r can be seen as independant random variables.

1

Elliptic curve security relies on the hardness of discrete logarithm on that curve. (Well, that's a simplification, but this will do for this answer.) When the curve contains N points, it takes an effort of roughly sqrt(N) "elementary operations" to break discrete logarithm. A prime p of "k bits" means that p is less than 2k, but greater than 2k-1. The ...

1

To expand on Ricky's comment, assuming Alice and Bob are the only participants, they can use an identity-based encryption scheme where Alice also acts as the trusted third-party ("Private Key Generator" in the Wikipedia article). Namely: Alice puts on her PKG hat, and generates the public parameters of the system and a secret which will be used later. ...

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