2
$\begingroup$

I read the following paragraph in a book about Elliptic Curve Cryptography, but didn't understand it:

The primary security in ECC is the parameter $n$; where $n$ is Order of point $G$, that is $n$ is the smallest positive integer such that $nG = O$, where $G$ is a base point represented by $G= (x_g, y_g)\ on\ E (F_P)$

What does that mean? Does a larger $n$ value imply a higher security level?

$\endgroup$
3
$\begingroup$

Take a point $G$ on the elliptic curve $E$. Someone calculates point $P = h*G$ where $h$ is some secret number (this can be done with point addition and duplications fast). Your task: Given public points $P$ and $G$ and curve $E$, find the secret $h$.

Solving this problem is hard. That is the problem that makes elliptic curves secure.

Does a larger n value imply a higher security level?

Yes, the $n$ in your explanation is the order of a point on a curve, or put another way, it is the number of times you have to add the point to itself until you end up with the point at infinity $O$.

(There is also the order of the group of points on $E$ which is simply the number of points on the curve. Don't confuse these two orders, they are not the same thing).

Having a point $G$ with high point-order $n$ implies that the group has at least order $n$ as well.

So why do you want to pick a point with high order $n$?

The reason for this is, that if you pick a point with low order, there is a mathematical way that allows an attacker to solve the elliptic curves discrete logarithm problem faster. This is known as the MOV attack on elliptic curves:

http://www.cs.rit.edu/~txb7419/Crypto/MOVAttack.php

Note: If you play around with curves (something I suggest you should do), you will find that some points can have a scary low order. I did some experiments with a toy curve in the past:

$y^2 = x^3 + 1001*x + 75$, modulo prime $p$ = 7919

This curve has group order 7888. If you examine the points on this toy curve (you can brute-force everything) you'll find most of them have point-order 7888 as well. Point <4023, 6036> is for example one of them. The point with the lowest point-order I've found on this curve is <7285, 14> with order of just 6.

Due to the MOV condition the second point would be a very bad point choice as G on this curve.

$\endgroup$
  • $\begingroup$ As far as I know the order of the point alone can't be related to the embedding degree which allows/disallows the effectiveness of the MOV attack. You also need an extension of the field. See this $\endgroup$ – Ruggero Nov 14 '14 at 9:23
  • $\begingroup$ @Ruggero, thanks for pointing this out. I'm still learning about elliptic curves as well so I might miss things like that. You're welcome to edit the answer :-) $\endgroup$ – Nils Pipenbrinck Nov 14 '14 at 9:27
  • $\begingroup$ The toy curve you share here has been very helpful (+1). Do you happen to have other examples (ideally a "catalog") of elliptic curves involving higher p and having points with high order? I'm having trouble coming up with the right EC parameters for that (even after brute-forcing points on curves, which quickly becomes impractical). $\endgroup$ – Iñaki Viggers Aug 15 at 11:32
1
$\begingroup$

It means that $n$ is the order of the elliptic curve group, that is, the number of points in that group. The private key in ECC is a scalar value $k$ where $1 \leq k \lt n$.

A larger $n$ implies a higher security level. The size of $n$ should be twice your expected security level in bits e.g. a 256-bit $n$ for 128-bit security.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.