A 256-bit elliptic-curve discrete logarithm

Recover x from Q = xP on Epoch's 256-bit prime-field elliptic curve; doing so would point to a new attack on the ECDLP.

shoal State the problem, from FrontierMath: Open Problems 2f7ffe0 · 2周前历史

47 行 · 3.9 KB 原始文件永久链接历史

1	# A 256-bit elliptic-curve discrete logarithm
2
3	Elliptic-curve cryptography is secure only if, given points $P$ and $Q = xP$ on a curve over a large prime field, recovering the integer $x$ is infeasible. Epoch has published one such instance at full cryptographic size. Solving it in reasonable time would point to a new attack on the elliptic-curve discrete logarithm problem (ECDLP), or to a hidden weakness in this particular curve.
4
5	## Problem
6
7	Let $p$ be the 256-bit prime below and $E\colon y^2 = x^3 + ax + b$ the curve over $\mathbb{F}_p$ with the given $a, b$. The point $P \in E(\mathbb{F}_p)$ has prime order $n$, a 254-bit prime, and $\#E(\mathbb{F}_p) = 5n$. The point $Q$ equals $xP$ for a secret integer $1 \le x < n$, where $xP$ is $P$ added to itself $x$ times.
8
9	```
10	p = 92031864238688105485400538143121826382268912998421731683072033206257804487869
11	a = 66780434313013275323552928748270304481793221171615836760742707201070562072251
12	b = 49926646401131159709065076432340744650532242327390476058390067276099410301761
13	Px = 38644201185363417798191368696978811687737990190927559170532558153854800741642
14	Py = 44805905068903897561820523795034068749084951450263356538447620424400005028012
15	Qx = 54096648540016620506320945354369315155659910460053503439381018376158456438152
16	Qy = 23176800742290374932252879903926227937053123957837615098744936554616726258932
17	n = 18406372847737621097080107628624365276513063062857122317960690589425712086189
18	```
19
20	Task. Find $x$.
21
22	## Background
23
24	Koblitz and Miller independently proposed basing public-key cryptography on elliptic curves in the mid-1980s [1, 2]. Its security rests on the presumed hardness of this problem for well-chosen curves over prime fields. A generic square-root method such as Pollard's rho [3] would need on the order of $\sqrt{n} \approx 2^{127}$ group operations here, far beyond any computer. Research continues on algebraic attacks, for example index calculus with summation polynomials, surveyed by Galbraith and Gaudry [4].
25
26	## What is known
27
28	- The numbers above are consistent: $p$ and $n$ are prime, $P$ and $Q$ lie on $E$, $nP = nQ = O$, and $5n$ lies in the Hasse interval around $p + 1$ (our check).
29	- Epoch chose the instance to be hard and names two risks: that a brute-force search might succeed in the allowed time, or that the curve has unexpected structure making it easier than intended.
30	- No solution has been reported.
31
32	## What would count as progress
33
34	- The integer $x$. Verification is one scalar multiplication: check that $xP = Q$.
35	- Epoch scores submissions with its own verifier, which accepts the decimal value of $x$.
36	- What matters most is the method: an attack that works for this curve and explains why, or a demonstration that the instance has an exploitable weakness.
37
38	## References
39
40	1. N. Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), 203–209. [doi:10.1090/S0025-5718-1987-0866109-5](https://doi.org/10.1090/S0025-5718-1987-0866109-5)
41	2. V. S. Miller, Use of elliptic curves in cryptography, CRYPTO '85, Lecture Notes in Comput. Sci. 218 (1986), 417–426. [doi:10.1007/3-540-39799-X_31](https://doi.org/10.1007/3-540-39799-X_31)
42	3. J. M. Pollard, Monte Carlo methods for index computation (mod $p$), Math. Comp. 32 (1978), 918–924. [doi:10.1090/S0025-5718-1978-0491431-9](https://doi.org/10.1090/S0025-5718-1978-0491431-9)
43	4. S. D. Galbraith and P. Gaudry, Recent progress on the elliptic curve discrete logarithm problem, Des. Codes Cryptogr. 78 (2016), 51–72. [doi:10.1007/s10623-015-0146-7](https://doi.org/10.1007/s10623-015-0146-7) ([ePrint 2015/1022](https://eprint.iacr.org/2015/1022))
44
45	## Source
46
47	Imported from [FrontierMath: Open Problems, elliptic-curve-discrete-logarithm](https://epoch.ai/frontiermath/open-problems/elliptic-curve-discrete-logarithm), curated by Epoch AI. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.