Hot answers tagged

19

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


19

By the same argument, they would have to forbid $d = 1234$; after all, an attacker can trivially compute the value of $1234 G$; and if they see it, then they can immediately infer $d$ without having to complete a discrete log over an elliptic curve. Of course, this logic would forbid all possible values of $d$... The issue is that if the attacker gets ...


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


15

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 \qquad\in\...


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


11

This is true of any group of prime order, over elliptic curves or not. This is due to Lagrange's Theorem which states that the order of a subgroup $H$ of group $G$ divides the order of $G$. Since orders are elements of the ring of integers and since this is a principal ideal domain, unique factorization exists and primes make sense. Or put another way, ...


10

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


10

There are three use cases where RSA beats common ECC algorithms, such as ECDSA: Signature with verification frequent or/and by low-power devices. The verification cost of $n$-bit RSA with usual public exponents is $O(n^2)$, but the verification cost of ECC-based signatures is $O(n^3)$ (using usual algorithms). Together with simpler math, that's why RSA can ...


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


9

This is not correct, the private key $d_A$ must always be an integer. Your mistake is that you are doing modular division e.g. $\frac{a}{b} \text{ mod } n$ incorrectly. You cannot simply divide the integers and then reduce by the modulus. The correct way to do this is to compute the modular inverse of $b$ i.e. $b^{-1} \text{ mod } n$ and then compute $a*b^{-...


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

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


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

There is a method known as "Complex Multiplication". However, it is not simple at all, and tends to be overly expensive for most target orders. See this article for some details. There is also the (theoretical) concern that a curve constructed that way may have a special structure though could possibly be leveraged into an attack one day; generally speaking, ...


7

Post-quantum crypto is a very young field and is still changing quite rapidly. If you just want a reading list to introduce you to the topics, I would recommend the March 2015 report released by the EU's PQCrypto Project, and the April 2016 report from NIST. As of today, here's an (incomplete) list of candidate algorithms for post-quantum cryptography ...


7

Actually, you can recover $n$ from ECDSA signatures (assuming that you can obtain several signatures with the same $k$ value, which means that the ECDSA signature implementation is broken); however it would require 3 such signatures (if you don't mind factoring a value circa $n^2$), or 4 such signatures (if you don't have that many resources conveniently at ...


7

What's missing is the authentication of the entities. If you don't authenticate the entity then you don't know who you've established the master secret with. This means an attacker can pose as a man in the middle or the attacker can simply act as one of the entities. You can use static DH key pairs, but in that case the DH public keys must be trusted and ...


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

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


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

"Attacks that work on the DLP do not work on ECDLP" is a rather vague statement, as ECDLP is just a particular case of DLP, on elliptic curves. I suppose that you refer to DLP over $\mathbb{F}_q$ for some $q = p^k$, $p$ being a prime. The intuitive reason why the DLP is harder to solve over (well chosen) elliptic curves is that they are our best ...


6

Yes, the attack you sketched out would work - in theory. In practice, it's an efficient (computable in polynomial time) mapping $\psi:E\rightarrow\mathbb Z_n$ we're lacking. As for the unefficient mappings, $\psi:x\cdot P\mapsto x$ would be perfectly fine theoretically, but we don't know how to calculate it (it's the elliptic curve discrete logarithm ...


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


5

Any key generation algorithm for any cryptosystem is going to be weak if the attacker can predict what seed was used to generate the key. They can just generate the same key. However, assuming the the random number generator is not that bad, different algorithms start to look different. If you are just using the output of the random number generator as a ...


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

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



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