7
$\begingroup$

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?

$\endgroup$
1

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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)$? $\endgroup$ Dec 25, 2021 at 19:45
  • $\begingroup$ @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! $\endgroup$
    – kelalaka
    Dec 25, 2021 at 20:15
  • $\begingroup$ Ok, so since we know there must be a unique $a$, we know that we are looking for an inverse and not a solution? $\endgroup$ Dec 25, 2021 at 22:11
  • $\begingroup$ @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... $\endgroup$
    – kelalaka
    Dec 25, 2021 at 23:38
  • $\begingroup$ @kelalaka Thanks! Your explanation helped me realize my mistake. I was doing regular division by $(x_1 - x_2)$ rather than modular division. $\endgroup$
    – jinscoe123
    Dec 26, 2021 at 3:46

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.