Tag Info

Hot answers tagged elliptic-curve-generation

21

There are curve types, and equation types. As algebraic objects, all curves can be expressed with a "Weierstraß equation". Through some changes of variables, that equation can be simplified into a "short Weierstraß format", which, for a finite field of characteristic more than 3, looks like: $$Y^2 = X^3 + aX + b$$ for two constants $a$ and $b$. In the ...

15

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

15

The prime $p$ is chosen to make arithmetic in a choice of field $k$ efficient. Typically $k = \mathbb F_p$ or $k = \mathbb F_{p^2}$. Popular choices of $p$ are near powers of two, e.g. the Mersenne primes $2^{127} - 1$ used by FourQ and $2^{521} - 1$ used by E-521 and NIST P-521, or $2^{255} - 19$ used by Curve25519. Other popular choices differ from a ...

14

As a lone curve, yours is not bad. But Barreto's proposal offers an extra property, which is that the quadratic twist also has prime order. In general, in a given finite field $K$, if you have a non-quadratic residue $d$ (i.e. a field element which is not a square), then, for the curve $E$: $$E: Y^2 = X^3 + aX + b$$ then you can define another curve ...

12

I don't have any visibility into the BSI standardization process, and so this is a guess; I suspect one of two things happened: This is a potential way to deal with someone figuring out how to break both Brainpool and NIST curves (but not arbitrary elliptic curves; if they managed that, this hook won't help). In that case, if someone did that (or if we ...

12

Why is there not just one or two curves that have been widely accepted as useful? Several reasons; some of it is politics (for example, I suspect a good part of the reason behind national curves is, in fact, national pride), some of it is multiple teams working independently (for example, the Brainpool team, the NUMS time, the people behind the million ...

12

Quick summary. Ransomware works by a public-key key encapsulation mechanism: pick a secret key $h$ and an encapsulation $\sigma$ of it for the malware operator's public key, so that only the malware operator can recover $h$ from $\sigma$ using their private key; then encrypt all the files using a symmetric cipher under the key $h$, erase $h$, and pay the ...

11

Mathematically speaking, we cannot. There is no proof that elliptic curves are actually "secure". But the same apply to about all other cryptographic algorithms, so we have to make do with the next best thing: since we cannot prove that any curve is "secure", we'll use curves that we do not know how to break (and not for lack of trying). That last part is ...

9

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

9

Of course there are others. Of interest might be the paper 'Efficient ephemeral elliptic curve cryptographic keys' by Mieli and Lenstra, which claims to generate fresh Elliptic Curves sufficiently quickly that they can be created on the fly for a single ECDH exchange, and then discarded.

8

Political reasons likely wins. E.g. France has an own set of domain parameters. Note that when the spec was created that the Brainpool curves where rather new. Generating safe parameters is not trivial, but we're talking countries here. Most of them will simply copy what's out there or buy a solution, but a few of the more advanced ones can try other curves ...

8

The paper introducing the application of endomorphisms in arbitrary curves to cryptography was Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone, ‘Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms’, in Joe Kilian, ed., Proceedings of Advances in Cryptology—CRYPTO 2001, Springer LNCS 2139, pp. 190–200, after the initial ...

7

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

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

Let's suppose that you want to generate a classic $n$-bit curve in a prime field, with the complete curve order being prime. The process goes about thus: Get a prime $p$ of size $n$ bits. The curve will be defined in the field of integers modulo $p$. For all we know, you can use $p$ to have a "special form" that promotes more efficient computations (e.g. $p ... 7 The reason why to achieve the same security level a supersingular elliptic curve requires to have a greater field size is due to the MOV attack. In the MOV attack, for a curve$E(\mathbb{F}_p)$you use a Weil Pairing to move the discrete logarithm from$E(\mathbb{F}_p)$to$\mathbb{F}_{p^k}$where$k$is called the embedding degree of the curve. The ... 7 The question is a bit broad. Generating secure elliptic curves is highly non-trivial, see for example this question, which contains references to this and this paper. Considering a black box group, the fact that it has order$6\cdot q$does not break the DLP. What happens is that the DLP can easily be reduced to a group of order$q$by eliminating the ... 7 Due to the Pohlig-Hellman algorithm, the hardness of discrete logarithms is dominated by the largest prime factor$\ell$of the group order$n$. In particular, one typically works in a subgroup of order$\ell$of the curve group, since the additional factors$h$in a generator's order would not significantly contribute to security. In that, note that$\ell$... 6 In general you start by fixing the field, which translates into fixing the prime, and then you start to look to a suitable (i.e. secure/safe) elliptic curve defined over that field. Note that, once you've fixed$p$, there are$\sim2p$isomorphism class of elliptic curves defined over$\mathbb{F}_p$, which grants you a big set where you are supposed to find ... 6 ECDH can be used for public key encryption just like RSA can be used for public key encryption. However, the EC problem cannot be used directly to encrypt data like the RSA algorithm can be used. Instead Diffie-Hellman is with a static key pair (similar to RSA) and an ephemeral key pair. The public key of the receiver can be used with the temporary private ... 5 Counting number of points on elliptic curve over$\mathbb F_2$is very easy.For extension of fields we can use of this theorem: Theorem : Let$E$be an elliptic curve defined over$F_q$, and let$\#E(F_q ) = q +1−t$. Then$\#E(F_{q^n} ) = q^n + 1 − V_n$for all$n ≥ 2$, where$\{V_n\}$is the sequence defined recursively by$V_0 = 2, V_1 = t$, and$V_n = ...

5

By definition, a point on the affine curve $$E\colon\quad \underbrace{y^2-x^3-ax-b}_{=:f}=0$$ is singular if and only if the Jacobi matrix $$J_f =\Big(\frac{\partial}{\partial x}f,\frac{\partial}{\partial y}f\Big) =(-3x^2-a,2y)$$ does not have maximal rank at that point, that is (here), vanishes. Hence precisely the points $(x,0)$, where $x$ annihilates ...

5

Binary fields were developed since they yield more efficient implementations. This is especially true given the Intel PCLMULQDQ instruction. Note, that there are special types of Binary fields that are even more efficient, like Koblitz curves. However, in general, our confidence in the security of these curves is less than for prime-field curves. Thus, in ...

5

If the elliptic curve has prime order of points, then all of its points are generators. Almost: The point at infinity is not a generator, but (if the number of points is prime) all finite points are. This is a consequence to Lagrange's theorem. If so, how can I find the optimized generator (which generates more points) among them? This does not make ...

5

Now, this is where I'm confused. I've read once that selecting right points isn't a trivial task, there exists an algorithm to test the rank of a point, but it's somewhat complex to implement. However I've also heard that most of the points on an elliptic curve are generators, and when selected in a pseudo-random manner it's very unlikely to fall onto a bad ...

5

It is known, that as in your setting, when $p$ is prime every possible integer in the Hasse-interval $\mathcal{H}_p$ arises as group order of an elliptic curve $E/\mathbb{F}_p$. For arbitrary prime powers $q = p^f$ this is not generally true: there are often not enough supersingular curves to cover the cases $N \equiv 1 \mod p$. Galbraith and McKee gives a ...

5

Regarding the [B] and [C] parts of the question per the comments: I'm not sure how exactly did Mike Hamburg find the curve, but from what I know it's usually easier to find the order of the matching Montgomery curve. Recall that Montgomery curves have the form $By^2 = x^3 + Ax^2 + x$. If $B$ is 1, then it fits into the generalized Weierstrass form, and most ...

4

$\newcommand{\Z}{\mathbb{Z}}$If I have understood your question correctly, your goal is to find a primitive root modulo $p$, also called a generator of $(\Z/p\Z)^\times$, knowing that $p$ is prime. Do you know the prime factorization of $\phi(p) = p - 1$? If you don't, this is hard. If you do, there's at least one common fast case, and there's always a ...

4

For most cases, you can take this as a (simplified) definition of Elliptic Curve: An elliptic curve over $K$ (a field) is a plane algebraic curve over $K$ defined by an equation of the form $y^{2}=x^{3}+ax+b$ (1) ($a,b \in K$) that is non-singular (it has no cups or self-intersection). Since the curve you give in the question is of the form \$y^{2}=x^{3}...

4

The algorithm for generating EC curve is in appendix D.5 of NIST FIPS 186-4, and the verification algorithm is in D.6. They are taken from ANSI X9.62, which justified the rationale as the following: In order to verify that a given elliptic curve was indeed generated at random, the defining parameters of the elliptic curve are defined to be outputs of ...

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