# Find Elliptic Curve Parameters, a and b, Given Two Points on the Curve

I am new to Elliptic Curve Cryptography and am working on a CTF challenge that uses Elliptic Curves. Currently, I am trying to find the generator, $$G$$, and am given the public and private keys, $$P$$ and $$k$$, s.t. $$P = [k]G$$, as well as one other random point on the curve. I know the order, $$n$$, of the group, and I know the two prime numbers, $$p$$ and $$q$$, which are the sole factors of $$n$$.

I read that if you have the private and public keys, you can compute the generator as ...

$$G = [k^{-1}]P\pmod n$$

... where $$k^{-1} = n - k$$.

That's all great, but, unfortunately, I do not know the parameters, $$a$$ and $$b$$, of the elliptic curve, $$y^2 = x^3 + ax + b$$, and so I'm having trouble performing EC point multiplication by $$k^{-1}$$.

I was thinking, since I know the values of two points on the curve, I essentially have the following system of linear equations:

\begin{align} y_1^2 &= x_1^3 + ax_1 + b\\ y_2^2 &= x_2^3 + ax_2 + b\\ \end{align}

I tried solving this using the z3 theorem solver but was given an answer, asserting that the system is unsatisfiable. I then tried modifying my system of equations so that both sides of the equation are calculated modulo $$n$$, but this resulted in z3 taking forever to find the solution, presumably because $$a$$ and $$b$$ are 128-bit numbers and $$n$$ is a 512-bit number. This got me thinking back to my undergraduate computer science classes, where I remember learning about various problems in computer science, and this seems similar to Integer Programming, which is NP-complete.

Therefore, is it possible to efficiently compute the parameters, $$a$$ and $$b$$, of an elliptic curve if I know the order $$n$$ and two points $$P$$ and $$Q$$ on the curve?

Given two point on the curve $$P=(x_1,y_1), Q=(x_2,y_2)$$ we can determine the parameters of the short Weierstrass form $$y^2 = x^2 + ax +b$$. Insert the coordinates of points to the curve equation to get two equations as you did;

\begin{align} y_1^2 &= x_1^3 + ax_1 + b &\pmod{n} \\ y_2^2 &= x_2^3 + ax_2 + b &\pmod{n}\\ \hline & & \text{subtract}\\ y_1^2 - y_2^2 &= x_1^3 - x_2^3 + a (x_1 - x_2) &\pmod{n}\\ (y_1^2 - y_2^2) -(x_1^3 - x_2^3)&= a (x_1 - x_2) &\pmod{n}\\ [(y_1^2 - y_2^2) -(x_1^3 - x_2^3)] \cdot (x_1 - x_2)^{-1}&= a &\pmod{n}\\ \end{align}

To be able to find $$a$$ the only problem is the existence of the modular multiplicative inverse of $$(x_1 - x_2)$$ to the $$\bmod n$$.

• If $$\gcd((x_1 - x_2),n) = 1$$ then the modular multiplicative inverse is exist and can be easily found with Extended Euclidean algorithm (Ext-GCD)
• If $$\gcd((x_1 - x_2),n) \neq 1$$ then there is no inverse (see What if below).
• Note that, in the case $$x_1 - x_2 = 0$$ then we have $$\gcd(0,n) = n.$$ In other words, there is no inverse.

Once $$a$$ is successfully found, finding $$b$$ is easier. Plug the known into the equation then solve for the only unknown $$b$$.

SageMath for the modular inverse;

Zn = Integers(12)
a = Zn(5)
b = a^-1
a


if set $$a = 4$$ then you will get the error: ZeroDivisionError: inverse of Mod(4, 12) does not exist.

What if There is no inverse of $$(x_1 - x_2)$$ to $$\bmod{n}$$. Can we find solutions to below?

$$(y_1^2 - y_2^2) -(x_1^3 - x_2^3)= a (x_1 - x_2) \pmod{n} \label{a}\tag{1}$$

Yes, we can still find solutions to $$\ref{a}$$ but they will not be unique.

Lemma: If $$d$$ is the greatest common divisor of a and m then the linear congruence $$ax \equiv b \pmod m$$ has solutions if and only if $$d$$ divides $$b$$. If $$d$$ divides $$b$$, then there are exactly $$d$$ solutions

To find them, from $$a/d \cdot x \equiv b/d \pmod{m/d}$$. It is clear that $$\gcd(a/d,m/d)=1$$. Then we can invert $$a/d$$ and solve for $$x$$. Then $$\{x, x+\dfrac{m}{d},x+\dfrac{2m}{d}, \ldots, x+\dfrac{(d-1)m}{d} \}$$ are the $$d$$ solutions for equation $$\ref{a}$$.

For each of the solutions, it is expected to have a different $$b$$, therefore for uniquely determine additional information will be needed.

• The equation $ab = c (\text{mod} n)$ can hold even if neither a nor b has a multiplicative inverse. Shouldn't the correct condition be whether $(y_1^2 - y_2^2) - (x_1^3 - x_2^3)$ divides $\gcd(x_1 - x_2, n)$? Dec 25, 2021 at 19:45
• @2.71828-asy Take the case $4x \equiv 6 \bmod 10$, $4x = 6 + 10 k$ divide by 2, we have $2x = 3 \bmod 5$ so $x = 4$ and the other one is $x+5$ since both satisfies $4x \equiv 6 \bmod 10$ they are both solutions. The inverse, however, must be unique! Dec 25, 2021 at 20:15
• Ok, so since we know there must be a unique $a$, we know that we are looking for an inverse and not a solution? Dec 25, 2021 at 22:11
• @2.71828-asy while answering in the first case, I was considering this case, too. However, I did not think that the OP will need that so concentrated on the unique solution. Added a part for that. In a second look, I've seen that they may need. Added as What if, thanks. This is a very common problem in Hill cipher solutions that we propose to look... Dec 25, 2021 at 23:38
• @kelalaka Thanks! Your explanation helped me realize my mistake. I was doing regular division by $(x_1 - x_2)$ rather than modular division. Dec 26, 2021 at 3:46