Hot answers tagged

18

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


15

The answer is about the difficulty of discrete logarithm. The notion of isomorphism does not capture all that matters in cryptography; we also need to consider computing costs. Suppose that we have an abelian group $\mathbb{G}$ with additive notation. Let $G$ be a conventional element of $\mathbb{G}$ of order $n$. The subgroup generated by $G$ is: $$\langle ...


14

Some claim that Curve25519 has 112 bit security, others that it has 128 bit security; which is it? Well, actually, neither - it's actually somewhere in the middle. For a curve without known weaknesses (and Curve25519 doesn't have known weaknesses), then if the curve order has a large prime factor around $2^{2k}$, then the best known attacks against it ...


12

There is a rather deep polynomial-time algorithm for counting the $\mathbb F_q$-rational points of an elliptic curve published by René Schoof in 1985 (with subsequent improvements by Noam Elkies and A. O. L. Atkin). It is based on two core ideas: The number of points is closely linked to a functional equation $$ \varphi^2-t\varphi+q = 0 ...


12

The security level of an elliptic curve group is approximately $\log_2{0.886\sqrt{2^n}}$. You can use this to approximate the security level of a $n$-bit key, eg: $\log_2{0.886\sqrt{2^{571}}} = 285.32537860389294$ The real computation (at least for curves over a finite field defined by a prime $p$) is $ \log_2{\sqrt{\pi/4}\sqrt{ℓ}} $, where $ℓ$ is the ...


9

Let's recall how discrete logarithms are solved in strong elliptic curve groups. The basic idea is to iteratively walk through many combinations of the form $x_i = a_iP + b_iQ$ until we find a distinguished one, i.e., one that shares some common property (like the lowest $k$ bits of $x_i$ set to 0). We accumulate enough distinguished points until we find a ...


9

If I understand your question correctly, you are essentially asking if points in Edwards and Montgomery curves can be represented in Weierstrass coordinates. This is true; in fact, any elliptic curve over a prime field can be represented in Weierstrass form $\mathcal{E}_{w}^{a, b} : y^2 = x^3 + ax + b$, and by extension its points can too. The question, ...


8

If that were possible, that is, if you could take an x-coordinate, and find the private key $k$ such that $kG$ has that x-coordinate, well, you've just solved the discrete log problem. If you can do that, you've just shown that the curve is insecure. If you're thinking "I'm not specifying the y-coordinate; doesn't this make it easier than the discrete log ...


8

Computing $d$ given $P$ and $Q$, with $Q = dP$ is known as the "elliptic curve discrete logarithm problem" and is considered to be infeasible under some hypothesis. The security of Elliptic Curves Cryptography is based exactly on the ability to compute the point multiplication and the intractability of the inverse operation: given two points find out the ...


7

These are "red flags". No one knows of a specific exploit, only some possible reasons to be concerned that one might exist. Since no one knows of a specific attack, we can't possibly know how much speedup such a hypothetical attack might allow. Basically, you're asking for speculation where there is not enough information to allow meaningful speculation, ...


7

ECC is indeed used by CloudFlare's website but only for the session key agreement. The authentication is performed using an RSA 2048 bit private key. The corresponding RSA public key is in the certificate. In other words, although ECC is being used, it is not used for authentication and therefore not part of the certificate. The ciphersuite is: ...


7

First off, your equation is correct and there seems to be no calculation mistake. To understand on how to get from $$(2+d)x^{2}+dy^{2}=d+(d-2)x^{2}y^{2}$$ to $$x^{2}+y^{2}=1+e\cdot x^{2}y^{2}$$ one first needs to observe that $e=(d-2)/(d+2)=121665/121666$ holds. The next step is to consider: "What operations are actually allowed with birational ...


7

It's not related to the possibility of backdoors in curve25519, no one thinks that curve25519 can have backdoors. It's related to having a trusted procedure to generate publicly verifiable random numbers, which is an interesting thing to have, not only related to elliptic curves. There is the need for a way to generate curves, any possible way is arbitrary. ...


6

In the context of the papers you reference, Generalized Mersenne prime numbers and Pseudo-Mersenne prime numbers are indeed two different things. A Pseudo-Mersenne prime number has the form $2^{\alpha}-\gamma$ for a small integer $\gamma \gt 0$. The term Generalized Mersenne prime number is defined by example in the referenced paper, and the examples given ...


6

Yes, there are a few reasons to prefer ECDH over RSA: ECDH will perform much better; ECDH can provide forward security when used with ephemeral key pairs without a large performance overhead for creating those key pairs; ECDH should be impervious to most oracle attacks, i.e. timing based padding oracle attacks on OAEP. For the forward secrecy you require ...


6

Non-Adjacent Form (NAF), also called Balanced Binary Representation (BBR), is a representation of integers reminiscent of binary, but with an extra $-1$ value for digits, and such that at least one of two adjacent digits is $0$. Because the resulting representation has at least half of its digits at zero (typically about $2/3$), it can be used to speed-up ...


6

In the basic fixed window method of performing point multiplication, we compute the value $nP$ (where $n$ is the integer we're multiplying by, and $P$ is the basis point) by finding the base $b$ representation $n = d_k b^k + d_{k-1} b^{k-1} + ... + d_1 b^1 + d_0 b^0$ (where $0 \le d_i < b$), and then computing first $1P, 2P, ..., (b-1)P$ and then $nP = ...


6

SHA-1 is still thought to be secure whenever collision resistance isn't required. The hash is both used for signing certificates and ECDHE public keys. There's however a difference with regard to collision attacks. It is possible for an attacker to attack the collision resistance with certificates by getting their own certificate signed by a CA. In ECDHE ...


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?


6

I just want to highlight: The new advancement need to be realized and validated. ECC and DH are quite similar although ECC discrete logarithm problem is harder. In other words, whatever effects the security of DH might not affect ECC with the same magnitude.


6

The previous answer has the correct formula for estimating the security level of prime field elliptic curves. However, the table seems to just list the closest Koblitz curve sizes used, as Richie Frame points out. If you computed the actual security strength of the curves in question, you would not end up with exactly the values in the left column. For ...


6

There is no such thing as the most secure curve. For one you can always come up with a larger curve if you need one. For another there are many measures of security and not all curves are directly comparable. If you wanted the curve for which the current best known attack is the slowest, then by that measure sect571k1 is actually the most secure out of the ...


5

It is possible to find the desired values in an acceptable amount of time. TL;DR: Find the curve order, factor it, select a (random) point until you have one with the desired order and calculate the cofactor as quotient of curve and point order. First, you can use yyyyyyy's answer to find the order $n$ of the described curve using Schoof's algorithm. ...


5

The following is more or less a copy-paste of a comment I made on the related ArsTechnica thread. Indeed, StackExchange is probably one of the better places to debate this. A few reminders first: there are approximately $p$ elliptic curves over the finite field of integers $\pmod{p}$; of these curves, only those with (almost) prime order are of ...


5

You might want to checkout Wikipedia page of elliptic curves to get a basic overview. The difference between DH and ECDH is mainly the group which is being chosen to compute the secret key(s). While DH uses a multiplicative group of integers modulo a prime $p$, ECDH uses a multiplicative group of points on an elliptic curve: Alice and Bob agree on an ...


5

After a multiplication you have a number with $2 \cdot 255$ bits. Since $2^{255} = 19 \pmod q$, you can take the upper half, multiply it by 19 and add it to the lower half. This gives you an equivalent number smaller than $20 \cdot 2^{255}$. Repeat this to get a number that's smaller than $2 \cdot q$. Now check if the value is greater or equal to $q$ and ...


5

To generate your pair of keys with elliptic curves first you have to chose your domain parameters (I think this name may comes from the P1363 naming convention, or perhaps it's previous). Those domain parameters will be public. For example for curves over finite fields those parameters are: ${p,a,b,G,n,h}$. The lower level operations will be made in ...


5

We, for the most part, don't bother with elliptic curve-based pseudorandom generators. DUAL_EC_DRBG was shoehorned into a NIST standard that also included a block cipher generator, CTR_DRBG, and two hash-based ones—Hash_DRBG and HMAC_DRBG—that are actually used in the field. Number-theoretic generators, which include Blum-Blum-Shub, DUAL_EC_DRBG, and ...


5

All of these are answered by the SafeCurves project: $x^2 + y^2 \equiv 1 + dx^2y^2 \pmod p$ Edwards curves can be converted to Montgomery form.Montgomery curves can be converted to Weierstrass form.Some, but not all, Weierstrass curves can be converted to Montgomery form. The Montgomery ladder (applicable only to Edwards and Montgomery curves) is faster ...


5

Bits of entropy The assumption for all cryptographic operations is that a random key of n bits has n bits of entropy. If it doesn't (due to PRNG defect or implementation error) then the key will be weaker than expected but the underlying assumption of all cryptographic primitives is that an n bit key has n bits of entropy. This is the same for all types ...



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