Elliptic Curve Cryptography is a class of public-key cryptographic algorithms with exponential attack difficulty, widely used in fields such as the encryption of second-generation ID cards. Shor’s algorithm theoretically poses a fatal threat to public-key cryptography, but to date, there have been no reports in the open literature on successful applications of quantum algorithms to attack ECC. In response to the current gap in quantum algorithms for ECC attacks, this paper proposes a quantum annealing-based algorithm for attacking the Elliptic Curve Discrete Logarithm Problem over finite fields. The approach begins by optimizing the coefficients in the Ising model conversion process during quantum annealing, significantly reducing the weight and coupling strengths (hi and Ji,j) of the relevant qubits by over 89.02%. By using quantum annealing to solve the Ising model optimized with the Semaev summation polynomial, the energy gap during the annealing process is greatly reduced, thereby revealing the relationships between points on the elliptic curve. Next, a sufficient number of Semaev polynomials are solved, and the resulting relationships are transformed into a system of linear equations. For this transformed linear system, a new algorithm based on quantum annealing is proposed for solving linear equations, enabling the solution of underdetermined and non-square linear systems. Ultimately, this work successfully solves the ECDLP over a finite field of up to 10-bits using the D-Wave Advantage, achieving a finite field size that is 289% larger than that of the previous largest solution. Experimental results show that the proposed method can effectively reduce the solution difficulty of D-Wave quantum annealing, and is a new quantum algorithm that can effectively attack ECDLP.
