14、椭圆曲线离散对数问题的经典与量子计算方法

椭圆曲线离散对数问题的经典与量子计算方法

1. 椭圆曲线离散对数问题概述

椭圆曲线离散对数问题（ECDLP）是密码学领域的一个重要问题，它比离散对数问题（DLP）更具挑战性，而椭圆曲线数字签名算法（ECDSA）正是基于 ECDLP。ECDLP 可以描述为：设 $E$ 是有限域 $F_p$ 上的椭圆曲线，由魏尔斯特拉斯方程 $E: y^2 \equiv x^3 + ax + b \pmod{p}$ 给出，$S$ 和 $T$ 是椭圆曲线群 $E(F_p)$ 中的两个点，ECDLP 就是要找到整数 $k$（假设这样的整数 $k$ 存在），使得 $S = kT \in E(F_p)$，即 $k = \log_T S \in \mathbb{Z}$ 或 $k \equiv \log_T S \pmod{p}$。

2. 解决 ECDLP 的经典算法

2.1 Pohlig - Hellman 算法

由于 ECDLP 是 DLP 的推广，许多解决 DLP 甚至整数分解问题（IFP）的方法都可以扩展到 ECDLP，Pohlig - Hellman 算法就是其中之一。以下是一个使用该算法解决 ECDLP 的示例：
设 $Q \equiv kP \pmod{1009}$，其中椭圆曲线 $E: y^2 \equiv x^3 + 71x + 602 \pmod{1009}$，$P = (1, 237)$，$Q = (190, 271)$，$order(E(F_{1009})) = 1060 = 2^2 \times 5 \times 53$，$order(P) = 530 = 2 \times 5 \times 53$。
-步骤 1：求模 2 的离散对数