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.

Well, if you have a pseudocurve  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$$

: I'll explain why it's called pseudocurve below

• 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$ Aug 15, 2019 at 20:06
• Excellent answer, thanks! Jun 2, 2021 at 23:35