3
$\begingroup$

When I know the two points on an elliptic curve, and the two points satisfy the relationship: $Q=e \cdot P$, is it possible for me to solve for $e$.
The equation of the curve is: $y^2 = x^3 + ax + b \pmod p$, while $e$ is a $32$-bit integer.

$\endgroup$
2
  • 1
    $\begingroup$ If e is 32 bit integer, e <2^32 you can solve it in O(2^16), which is very efficient on a computer. $\endgroup$
    – joro
    Commented Jan 21 at 5:23
  • $\begingroup$ This question is better suited to crypto.stackexchange.com. $\endgroup$ Commented Jan 21 at 13:26

2 Answers 2

10
$\begingroup$

Adding on a bit to David Speyer's answer, the elliptic curve discrete logarithm problem (ECDLP) has been studied intensively since the 1980s, and in addition to commercial applications, there is a vast research industry that studies the problem and its applications in cryptography. As Speyer says, it is "believed to be hard", indeed the best known general classical algorithms take exponential time (which in your setting means a fractional power of $p$ or $e$), as opposed to various sub-exponential running time algorithms for factorization (used for RSA) or for solving the finite field discrete logarithm problem (find $e$ that solves $A\equiv B^e\bmod p$). However, there is a quantum algorithm due to Shor that would solve the ECDLP in (practical) polynomial time if/when a sufficiently large quantum computer is built. If you want to find out about some of the algorithms that are used to solve the ECDLP, you might read about the babystep-giantstep method or Pollard's rho method, each of which (in your setting) has a run-time of roughly $\sqrt{p}\approx\sqrt{e}\approx2^{16}$, so would be quite feasible. In cryptographic applications, the $p$ and the $e$ are more like 200 to 1000 bits.

$\endgroup$
0
6
$\begingroup$

This is called the "elliptic curve discrete logarithm problem". It is believed to be hard, and several commercial cryptographic schemes are based on this belief.

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged .