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.

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

  • 0
    You're right. I have fixed that.2011-09-10