2
$\begingroup$

Elliptic curves are usually defined over prime rings (fields), but what if we chose a ring of composite order? Let $n = pq$ for $p,q$ large primes. Say I have elliptic curve $y^2 = x^3 + ax + b$ over the Ring of integers mod $n$. And I have two points on the curve, say $A, B$ such that $A = xB$. From this alone, it should be enough to determine $x$ correct? I have $n$, I have the factorization of $n = pq$, and I have $A,B$. Everything I read on elliptic curves seems to initialize over our prime field. I can find no discussion of what the actual attack is. I understand the hardness of the problem has been reduced to the integers now mod $p$ and $q$, but I don't understand the process to determine $x$ here.

$\endgroup$
5
$\begingroup$

Well, if you have a pseudocurve [1] based on the formula:

$$y^2 = x^3 + ax + b \pmod{ pq }$$

what you have is really two different curves stapled together; that is, the curves based on:

$$y^2 = x^3 + ax + b \pmod{ p }$$

$$y^2 = x^3 + ax + b \pmod{ q }$$

You can look at a point in the $pq$ curve as really being a point in the $p$ curve and a point in the $q$ curve; and when you perform an operation, the two component curves act independently.

So, if we denote a point $A$ as the pair $(A_p, A_q)$ and the point $B$ as the pair $(B_p, B_q)$, then the result of the point addition $A+B$ is the pair $(A_p + B_p, A_q + B_q)$, where the first addition is an addition in the $p$ curve, and the second addition is in the $q$ curve. And if exactly one of $A_p+B_p, A_q+B_q$ is the point at infinity, then it turns out that the value $A+B$ is not defined in the $pq$ curve - that's why it's called a pseudocurve, because not all operations within the pseudocurve have defined results - it fails to be a group because it is not closed.

More to the point, if you take a point $P$ in the original $pq$, and compute $kA$, then that is equivalent:

  • Mapping the point $P$ to a point on the $p$ curve (by taking the $x$ and $y$ coordinates modulo $p$), and then computing $kA_p$

  • Mapping the point $P$ to a point on the $q$ curve (by taking the $x$ and $y$ coordinates modulo $q$), and then computing $kA_q$

  • Recombining $kA_p$ and $kA_q$ by reconstructing both the $x$ and $y$ coordinates using the Chinese Remainder Theorem.

With this observation, we have the following method to solve the original $A = xB$ problem:

  • Factor $n$ into $p, q$

  • Point count both the $p$ curve and the $q$ curve

  • Solve $A = xB$ over the $p$ curve (resulting in $x \bmod n_p$, where $n_p$ is the number of points on the $p$ curve)

  • Solve $A = xB$ over the $q$ curve (resulting in $x \bmod n_q$, where $n_q$ is the number of points on the $q$ curve)

  • Use the Chinese remainder theorem to combine $x \bmod n_p$ and $x \bmod n_q$ into $x$

These operations are jointly cheaper than solving an ECDLog problem over a prime the same size as $pq$


[1]: I'll explain why it's called pseudocurve below

$\endgroup$
  • $\begingroup$ Thank you. This explains it quite simply. The missing piece for me was modding out by the point count of the curves, and not modding out by $p+1$ or $q+1$ $\endgroup$ – abrahimladha Aug 15 at 20: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.