0
$\begingroup$

For context, I was watching this bit of the video: which goes over this source code. The piece is about elliptic curve cryptography and how it works. I want to use some of this knowledge to make my own curve as an exercise. I did some self-study on this stuff and understand how some it works, like how point doubling and point addition operations and that this is all done over some prime field $\mathbb{F}_p$, but some things escape me.

Now, few seconds after the mark in the video, he mentions that changing the generator point $(x_g, y_g)$ on the elliptic curve can easily break the digital signature algorithm. But suppose I want to use a different generator point. How would I go about finding the order of the field $N=\#E(\mathbb{F}_p)$ for some arbitrary generator point $(x_g, y_g)$? What about some arbitrary prime field p? I don't know how to find $G$ or $N$.

My goal here is to do something a little insane. Like... make a 1024-bit elliptic curve I could use to sign things. Again, as an exercise, but I would like to actually code this stuff.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ Does How to find the order of a generator on an elliptic curve? satisfies you? $\endgroup$ – kelalaka Jun 22 '19 at 20:22
  • $\begingroup$ Not really. It does tell me how to find the order of the curve $\#E(\mathbb{F}_p)$ using Schoof's algorithm but not how to find the generator point $(x_g, y_g)$ or the order of the generator. In the answer it says "Factor $n$ to determine its largest prime factor $l$", but that seems unacceptable especially for large values of $n$ because that's essentially the prime factorization problem. What if $n$ is prime? $\endgroup$ – TLane Jun 23 '19 at 16:23
  • 1
    $\begingroup$ The integers that occur in ECDLP-based cryptography are typically small enough to be factored efficiently. Moreover, if $n$ is prime it is of course trivial to find the largest prime factor of $n$: that is $n$ itself. $\endgroup$ – fkraiem Jun 24 '19 at 8:14
  • $\begingroup$ Oh, okay. I read up on Lagrange's theorem which states that the order of the generator point will always be divisible by the order of the curve, so if $\#E(\mathbb{F}_p)$ is prime then all generator points (except the point of infinity) have order $p$. Okay, but chances are I won't get a prime order $N$ for my randomly generated curve most of the time, it'll likely be composite. What if I want, say, an elliptic curve with a 1024 bit prime modulus? Is factoring that still efficient? Or am I limited by the prime factorization problem here? Or is there a trick here I'm not seeing? $\endgroup$ – TLane Jun 24 '19 at 8:43
  • $\begingroup$ 1024 bits will be more challenging, but it is also not typical. $\endgroup$ – fkraiem Jun 24 '19 at 8:59

Your Answer

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

Browse other questions tagged or ask your own question.