23 votes
Accepted

What is the curve type of SECP256K1?

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 "...
Thomas Pornin's user avatar
22 votes
Accepted

What is the relationship between p (prime), n (order) and h (cofactor) of an elliptic curve?

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 ...
Squeamish Ossifrage's user avatar
14 votes
Accepted

What's wrong with this curve (generation algorithm)?

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-...
Thomas Pornin's user avatar
13 votes
Accepted

Security of elliptic curves

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 ...
Thomas Pornin's user avatar
13 votes

Why are there so many different elliptic curves?

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, ...
poncho's user avatar
  • 147k
12 votes
Accepted

What's up with unnamed elliptic curves in e-passports?

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 ...
poncho's user avatar
  • 147k
12 votes
Accepted

How do malware rely safely on ECDH algorithm to maintain secrecy of keys?

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 ...
Squeamish Ossifrage's user avatar
11 votes
Accepted

How can I generate a Koblitz curve?

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 ...
Squeamish Ossifrage's user avatar
9 votes

What is necessary for generating an elliptic curve?

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 ...
Thomas Pornin's user avatar
8 votes
Accepted

How to find the order of a generator on an elliptic curve?

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 ...
yyyyyyy's user avatar
  • 12.1k
8 votes

Security level difference: supersingular vs non-singular elliptic curve

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 ...
Ruggero's user avatar
  • 7,094
8 votes

What's up with unnamed elliptic curves in e-passports?

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 ...
Maarten Bodewes's user avatar
  • 92.6k
8 votes

curve25519 by openSSL

Use the genpkey command: openssl genpkey -algorithm x25519 or, for edwards25519: ...
Frank Denis's user avatar
  • 2,974
8 votes

Why Elliptic Curve Cryptography protocols depend on fixed curves?

The reason to not fix a specific curve/group/whatever to work over is if it hurts security, namely if: There are precomputation attacks — an attack that costs $T$ that can be amortized over $n$ users ...
Mark Schultz-Wu's user avatar
8 votes
Accepted

Do you know protocols, where it is necessary to obtain several "independent" points on the same elliptic curve?

Do you know protocols where it is necessary to obtain several "independent" points on the same elliptic curve? One obvious place where this occurs if you are implementing a Pedersen ...
poncho's user avatar
  • 147k
7 votes
Accepted

Is there a theorem to determine the elliptic curve parameters based on the group order?

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 (...
Thomas Pornin's user avatar
7 votes
Accepted

Elliptic curve with non-prime generator?

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, ...
CurveEnthusiast's user avatar
6 votes

How can I find the generator of a composite group and $Z_p*$?

$\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 ...
Squeamish Ossifrage's user avatar
6 votes
Accepted

How to find the generator of an elliptic curve?

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. ...
yyyyyyy's user avatar
  • 12.1k
6 votes
Accepted

Is the prime P is fixed for an elliptic curve defined over a particular prime field F_p?

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 ...
Ruggero's user avatar
  • 7,094
6 votes

How do malware rely safely on ECDH algorithm to maintain secrecy of keys?

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. ...
Maarten Bodewes's user avatar
  • 92.6k
6 votes

Order of Edwards curve and its twist

Do your experiments count points at infinity? When $d$ is a quadratic nonresidue over $\mathbb{F}$, the curve $y^2 + x^2 = 1 + d x^2 y^2$ has no points at infinity over $\mathbb{F}$. But if $-1$ is ...
Mike Hamburg's user avatar
6 votes
Accepted

Order of Edwards curve and its twist

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 ...
Conrado's user avatar
  • 6,434
6 votes
Accepted

What is the order of the generator point G=9 in curve25519?

According to this source, the points of this curve are a group of cardinality $8\cdot p'$ with $p':=2^{252}+27742317777372353535851937790883648493$. This number can be computed by using the Schoof ...
Ievgeni's user avatar
  • 2,595
5 votes
Accepted

Short Weierstrass equation is non-singular for not 2 or 3 characteristic

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}{\...
yyyyyyy's user avatar
  • 12.1k
5 votes

Comparing elliptic curves over prime fields against EC over binary fields

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 ...
Yehuda Lindell's user avatar
5 votes
Accepted

Curve point generators for ECC

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 ...
poncho's user avatar
  • 147k
5 votes
Accepted

Probability of a prime number of points on an elliptic curve over a prime field

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 ...
István András Seres's user avatar
5 votes

Modulo p in Elliptic Curve Cryptography

To carry out Elliptic Curve Cryptography between parties, are all elliptic curve equations considered to be in the form $\bmod p$? Yes for secp256k1 when it comes to point coordinates, but not for ...
fgrieu's user avatar
  • 141k
5 votes
Accepted

Binary Elliptic Curves Point Doubling Formula - Calculate Lambda from P3

One can think of $\lambda$ as the (formal) gradient of the tangent to the curve at the point $(x_1,y_1)$, but this will not be the same as the gradient of the tangent to the curve at the point $(x_3,...
Daniel S's user avatar
  • 23.9k

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