Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 9 '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 9 '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 9 '11 at 16:37
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 5:32
1  
@Ted, OK, but "eventually" could be a very long time.... –  Gerry Myerson Sep 10 '11 at 10:33

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
2  
Shouldn't P,Q and P,-(P+Q) be colinear? Geometric interpretation here: ec addition –  ted.k Sep 10 '11 at 9:42
    
You're right. I have fixed that. –  Ted Sep 10 '11 at 18:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.