0
$\begingroup$

From what I understand, in order for a curve to be safe, it would appear that $n$ being the order of the cyclic subgroup of the curve, is a prime. Also, it is the theoretical upper-bound on the number of private keys the curve can issue, thus it should be a good candidate for being the limit on the size of the field.

However in practice, it looks like we always choose a different $p$ than $n$. Why do we do this? Also, I'd understand that if $p$ is smaller than $n$, but why do we sometimes have a larger $p$ than $n$? It won't be possible to have up to $p$ private keys when the subgroup has order $n$ right? Lastly, I see some tutorials referring to $p$ as the characteristic of the curve, what does that mean?

I'd love to understand the above a bit further, and I guess in general my question is, given $n$, how would I choose $p$ for a safe curve?

$\endgroup$
  • 1
    $\begingroup$ A curve whose order equals the cardinality of the base field is called anomalous. Look into it. $\endgroup$ – fkraiem Sep 12 '17 at 5:35
  • $\begingroup$ Thank you for the note. I tried to looking online but couldn't locate information on the properties of anomalous elliptic curves. Would you mind help pointing me to some resources? Thank you. $\endgroup$ – gtr32x Sep 12 '17 at 5:54
  • 1
    $\begingroup$ If you search for "anomalous curve" as suggested, you should find papers / thesises on polynomial-time attacks on the ECDLP for these curves. $\endgroup$ – SEJPM Sep 12 '17 at 10:13
3
$\begingroup$

Also, I'd understand that if p is smaller than n, but why sometimes we have a larger p than n? It won't be possible to have up to p private keys when the subgroup has order n right?

I suspect you're using an analogy with more normal discrete log problem, where the value is a value between 0 and $p-1$; obviously, you can't have more than $p$ values.

In contrast, the standard way of viewing an elliptic curve point is that is a solution $(x, y)$ to an equation such as $y^2 \equiv x^3 + ax + b \pmod p$ for fixed values $a, b, p$ (or a special "point at infinity", an artificial group member that's needed to make the group closed).

As a point consists of two values, each of which are between 0 and $p-1$, we have $p^2+1$ values that are potential candidates to be group members. It should be obvious that the vast majority of those potential solutions aren't actually solutions to the equation; it turns that that there will always be approximately $p$ solutions (within the "Hasse interval"); and this "approximately" can be slightly larger or slightly smaller than $p$ (but always within $\sqrt{2p}$)

given n, how would I choose p for a safe curve?

At your level of understanding, you don't. The issues in selecting a curve are subtle, and you currently don't know nearly enough. Instead, you should rely on someone who does know what they are doing to choose a good curve (which specifies $p$ and $n$) for you.

Lastly, I see some tutorials referring to p as the characteristic of the curve, what does that mean?

Elliptic curves are defined using an equation over a field; for cryptography, we always use a finite field (as we generally prefer our ciphertexts to be expressible in a bounded number of bits). A finite field always has exactly $p^k$ elements, where $p$ can be any prime, and $k$ any positive integer. We define the characteric as the value $c$ where we always have $\underbrace{x+x\ +...+\ x}_{c\text{ times}} = 0$ for all field elements $x$ (and where addition is the field addition operation). It turns out that, for all finite field, we have $c=p$ (even if $k>1$).

Currently, it is most common to have elliptic curves with $p$ being a large prime and $k=1$; in this case, you can perform the field addition and multiplication operations modulo $p$ (for $k>1$, it gets more complicated), and the modulus $p$ is the characteristic.

$\endgroup$
  • $\begingroup$ WRT to domain parameter generation: there are of course libraries that implement domain parameter generation for you, so creating your own set would then be analogous to pressing a button. This is especially true for DH. For ECC it is also possible, but I'd get some coffee before starting the calculations; using a named curve would be highly recommended instead. $\endgroup$ – Maarten Bodewes Sep 12 '17 at 13:55
  • $\begingroup$ @MaartenBodewes It would be much more efficient to get coffee while running the calculations $\endgroup$ – CurveEnthusiast Sep 13 '17 at 1:03
  • $\begingroup$ Thank you so much for the answers. I have a follow up question, the part that confuses me heavily is, you mentioned that c = p where cx = 0. My understanding was that the subgroup order of the curve in finite field, n, has such a property where nx = 0. As I understand now, n is the order of the subgroup, but p is the characteristic of the subgroup, it now appears that they are equivalent? Yet in many curves they aren't the same, sorry for asking really primitive questions and I've missed in my understanding by a huge mile. Thanks! $\endgroup$ – gtr32x Sep 13 '17 at 3:06
  • $\begingroup$ 'c=p where cx=0'; actually, I wrote $\underbrace{x+x\ +...+\ x}_{c\text{ times}} = 0$; that is not multiplication (at least, not the field multiplication operation). If multiplication within $cx$ is the field operation, then the only solutions for $cx=0$ are $c=0$ or $x=0$. $\endgroup$ – poncho Sep 13 '17 at 22:23
  • $\begingroup$ 'p is the characteristic of the subgroup'; actually, it's the characteristic of the field that the curve is defined on. It has nothing to do with any subgroups that might be in the elliptic curve group. $\endgroup$ – poncho Sep 13 '17 at 22:25

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.