1

Given a procedure that adds two points on an unknown elliptic curve, is it possible to determine curve's parameters, treating this procedure as a black box?

We are given two points on this curve $P$ and $Q$ ($Q=k*P$, for some $k$), and a function $f$, such that $f(P,Q)=P+Q$. The problem is to determine parameters in EC equation: $y^2+a_1xy+a_2y=x^3+a_3x^2+a_4x+a_5$.

Note that the curve might be over a finite field ($F_p$ for example), so it's not as easy a solving linear system of equations.

ted.k
  • 181
  • 1
    Are we given the field? If so, I think it is just solving a linear system of equations. If not, you won't be able to determine the field, because given any finite amount of data, $\mathbb{Q}$ will be indistinguishable from $F_p$ for sufficiently large $p$. – Ted Sep 09 '11 at 16:23
  • Let's assume the field is $F_p$, but $p$ is unknown, is it possible to determine p? I'd very much like to know why $Q$ would be indistinguishable from $F_p$. – ted.k Sep 09 '11 at 16:28
  • Basically, it's because if you do any finite calculation in $\mathbb{Q}$, the same calculation is equally valid in every $F_p$, unless you have a division by $p$ somewhere. But you do only a finite number of divisions and so there are only a finite number of bad primes, so if you pick $p$ large enough, then there will be no problem. – Ted Sep 09 '11 at 16:37
  • So how to find $p$, if the field is $F_p$? – ted.k Sep 09 '11 at 16:46
  • 2
    I think Ted is saying you can't find $p$. Think about a simpler problem; given two numbers, and a function that gives their sum, can you tell what field you're in? Yes, if you get lucky and add two numbers whose sum exceeds $p$, but if you keep getting the same answer you'd get in the integers, it just means $p$ is really big, and gives you no other information on $p$. – Gerry Myerson Sep 10 '11 at 05:32
  • @Gerry: That's right. But if you assume the field has to be $F_p$ and not $\mathbb{Q}$ (sounds like that's what the OP wants now), then you can try bigger and bigger numbers and eventually the sum will exceed $p$. A similar technique should work for the elliptic curve problem (see my answer below). – Ted Sep 10 '11 at 06:51
  • 1
    @Ted, OK, but "eventually" could be a very long time.... – Gerry Myerson Sep 10 '11 at 10:33

1 Answers1

2

If you assume your black box will return results in $F_p$ in "normalized" form (values in the range 0,1,...p-1, say), then for any 2 points P, Q that you put in, you know that P,Q,-(P+Q) will be collinear. So the slope between P and Q, and between P and -(P+Q), will be equal. If you calculate these slopes as rational numbers, and subtract the 2 slopes, you can conclude that the numerator of the difference will be divisible by $p$. By factoring the numerator, you reduce the possibilities for $p$ to a finite number of primes. By doing this several times, hopefully you'll be reduced to just one possibility for $p$. (If at some point, you get a numerator of 0 (meaning the slopes are actually equal in $\mathbb{Q}$), then just ignore that iteration and keep trying. The bigger $p$ is, the more likely this is to happen. This is the same issue as the problem of distinguishing $\mathbb{Q}$ from $F_p$.)

Once you have $p$, you can put in more points to get a system of linear equations for the $a_i$.

Ted
  • 33,788