5
$\begingroup$

Is it possible to find points that are on two elliptic curves, and how?

More precisely, I'm looking for coordinates $(x,y)$ that satisfy the defining equations of two elliptic curves on prime fields $\mathbb{F}_{p_1}$ and $\mathbb{F}_{p_2}$: $$ \begin{cases} y^2 \equiv x^3 + a_1 x + b_1 \mod{p_1} \\ y^2 \equiv x^3 + a_2 x + b_2 \mod{p_2} \\ \end{cases} $$ Is this even tractable, and if so how can I calculate at least one intersection point? Is it tractable to have the private key on one of the curves (for given generators)?

I'm curious about the question in general, but in order for this to be practically useful to me now, the curves need to be supported by the software I'm working on: two curves among SECP256R1, SECP256K1, BP256R1 or their 224-bit or 384-bit counterparts.

The motivation is a data validation bug in this software that leads to a public key to be interpreted on the wrong curve, but it has to satisfy both curves' equation. I want to understand how easy it is to exploit it and I'd like to write a non-regression test (which only requires the public values).

$\endgroup$
6
$\begingroup$

Interesting problem. One should distinguish between two distinct cases, according as whether $p_1=p_2$ or not.

The case $p_1=p_2$ (let's call this common prime $p$) is easy. You can just subtract the two equations and get: $$(a_1-a_2)x + (b_1-b_2) \equiv 0 \pmod p $$ which gives either a unique choice for $x$ (if $a_1\neq a_2$) or none at all (if $a_1=a_2$ but the $b_i$'s are distinct). In the former case, you can easily check whether that coordinate $x$ corresponds to an actual point on the elliptic curves; for randomly chosen curves, the chance of this happening is about 1/2. Note however that standard curve parameters often mandate that $a=-3$, in which case you are always in the latter case, and intersections simply don't occur for curves over the same base field.

The case $p_1\neq p_2$ is more subtle, because it isn't obvious how to interpret the question anymore. Mathematically speaking, the problem doesn't really make sense, because the fields $\mathbb{F}_{p_1}$ and $\mathbb{F}_{p_2}$ are distinct, unrelated objects.

One can look, however, for points $(x,y)$ with integer coefficients (or even, in some sense, rational coefficients), with the property that when reduced modulo $p_1$ we get a point on the first curve, and when reduced modulo $p_2$ we get a point on the second curve. Constructing such points is straightforward: take any point $P_1$ on the first curve, any point $P_2$ on the second curve, and apply the Chinese remainder theorem to their coefficients to get what you want. But this may not be the problem you are actually interested in, because if you do that, the bit size of the coefficients of the resulting point $(x,y)$ will be as large as the sum of the bit sizes of $p_1$ and $p_2$ in general.

One could also ask for such integer solutions $(x,y)$ with the additional requirement that, for example, $x$ and $y$ should be at most $\min(p_1,p_2)$ in absolute value (or perhaps $\max(p_1,p_2)$ depending on the application). This amounts to looking for points with small coefficients on the lifted curve $$y^2 \equiv x^3 + \hat{a}x + \hat{b} \pmod {p_1p_2}$$ where $\hat{a},\hat{b}$ are obtained by Chinese remaindering. Heuristically, if $p_1$ and $p_2$ are roughly of the same size, say $m$ bits, such a point should exist with good probability (there are about $2^m$ possible $x$ coordinates of the right size, and at least one of the corresponding $y$ coordinates fall in the right interval with probability around $2^{-m}$; one can make this rough estimate more precise if necessary). It is not completely obvious how to find such a point, however. The usual technique to find small solutions of algebraic equations is to use some variant of Coppersmith's theorem, but depending on the precise version of the problem you are interested in, the bounds offered by Coppersmith are likely to be insufficient.

If you can say more about your precise application, one could have a closer look. It might even be worth writing a paper about it.

$\endgroup$
  • $\begingroup$ As I explain in my question, my “application” is investigating the consequences of a data validation bug. What other information would you like to have? $\endgroup$ – Gilles Nov 14 '18 at 15:06
  • $\begingroup$ Probably some details about how validation works, precisely. As I mentioned above, if points $(x,y)$ with integer coefficients $x$, $y$ larger than the moduli pass validation, then constructing what you want is easy. However, it becomes a lot harder if there's an added requirement on the size of $x$ and $y$. $\endgroup$ – Mehdi Tibouchi Nov 16 '18 at 7:06

Your Answer

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

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