1
$\begingroup$

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.

  • 0
    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$.2011-09-09
  • 0
    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$.2011-09-09
  • 0
    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.2011-09-09
  • 0
    So how to find $p$, if the field is $F_p$?2011-09-09
  • 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$.2011-09-10
  • 0
    @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).2011-09-10
  • 1
    @Ted, OK, but "eventually" could be a very long time....2011-09-10

1 Answers 1

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$.

  • 2
    Shouldn't P,Q and P,-(P+Q) be colinear? Geometric interpretation here: [ec addition](http://www.certicom.com/index.php/21-elliptic-curve-addition-a-geometric-approach)2011-09-10
  • 0
    You're right. I have fixed that.2011-09-10