# 不基础的数学基础

# 椭圆曲线上的映射和 Frobenius 迹

在一个素域$\mathbb{F}_p$ 上，我们定义一个椭圆曲线$E$，在这条椭圆曲线上我们选择一个基点$P$，在密码学中我们使用的也就是这个基点生成的循环群$\langle P\rangle$。

我们定义一个从椭圆曲线$E(K)$ 到其自身的有理映射 (Rational Map) 是椭圆曲线$E(K(E))$ 的一个元素。（$K(E)$ 是$E$ 的 “值域”）

对于$(g_x,g_y)\in E(K(E))$，可以知道$g_x(X,Y)$ 和$g_y(X,Y)$ 都是满足方程$E$ 的有理函数。那么对于椭圆曲线$E(K)$ 上面的一个点$P=(x,y)$，点$(g_x(x,y),g_y(x,y))$ 也是椭圆曲线$E(K)$ 上面的点。

也就是这个有理映射就是用来描述$(x,y)\rightarrow(g_x(x,y),g_y(x,y))$，也就是怎么样去把椭圆曲线$E(K)$ 上的点映射到$E(K)$ 上面其他的点。

如果这个有理映射能够将无穷远点$O$ 映射到其自身，那么这个映射又叫做自同态 (endomorphism) ，所有自同态的集合记作$\rm{End}(E)$，$\rm{End}(E)$ 是一个环。

下面列举一些特殊的有理映射：

• 恒等映射 (Identity Map)：这个映射是一对有理函数$X$ 和$Y$，$id=(X,Y)$，也就是将一个点映射到其自身。
• 常映射 (Constant Map)：对于一个点$P=(x,y)$，常映射将每一个输入的点都映射到点$P$：$C_P=(x,y)$。
• Translation Map：（这个不知道怎么翻译） 这个映射是将一个点$P=(x,y)$ 加到每一个输入上，也就是$\tau_P=id+C_P$。
• 乘法映射 (Multiplication Map)：这是将常数$m$ 乘在每个点上，将点$P$ 转换为$[m]P$。
• Frobenius 映射：对于在素域$\mathbb{F}_q$ 上的椭圆曲线$E$，Frobenius 映射是一个自同态：$\phi=(X^q,Y^q)$。

在特征为$q$ 的域$\mathbb{F}_q$ 上的一条椭圆曲线，令$t=q+1-\#E(\mathbb{F}_q)$ 即 Frobenius 迹 (trace of Frobenius) ，$\phi$ 为 Frobenius 映射。

根据 Hasse 定理，上面的各个参数满足下面的条件：

• $$\phi^2-[t]\phi+[q]=[0]$$

• $$|t|\le2\sqrt{q}$$

通过 Hasse 定理能够确定椭圆曲线上点数量的上下界。

# Hensel 引理

Hensel 引理是模算数中的一个结论。在模给定质数$p$ 的多项式方程有单根的情况下，可以通过这个单根求解出该方程模$p$ 更高次方时的根。

也就是说，对于一个整系数多项式$f$ 和素数$p$，对于一个不小于 2 的整数$k$，如果$r\in\mathbb{Z}$ 满足：

$$f(r)\equiv 0\mod p^{k-1}$$

那么对于

$$f(r+tp^{k-1})\equiv 0\mod p^k$$

若$f'(r)\not\equiv 0$，则存在$0\le t\le p-1$ 使得上式成立，且$tf'(r)\equiv-(f(r)/p^{k-1})\mod p$。

若$f'(r)\equiv 0\mod p$，如果$f(r)\equiv 0\mod p^k$，则上式对任意整数$t$ 恒成立，否则无整数解。

可以通过 Taylor 公式证明该引理：

$$f(r+tp^{k-1})=f(r)+tp^{k-1}f'(r)+\frac{1}{2}t^2p^{2(k-1)}f''(r)+\frac{1}{6}t^3p^{3(k-1)}f'''(r)+...$$

从第三项开始的项都能被$p^k$ 整除，故

$$f(r+tp^{k-1})\equiv f(r)+tp^{k-1}f'(r)\mod p^k$$

到此证明完毕。

一个对于 Hensel 引理的应用，就是所谓的 Hensel Lifting ，将椭圆曲线上的点 “提升” 到更高阶的曲线上。举个例子，对于一条椭圆曲线$E(\mathbb{F}_p):y^2\equiv x^3+ax+b\mod p$，我们已经知道了一个点$P(x_1,y_1)$ 在椭圆曲线上，那么$y_1$ 是方程$f(y)=x^3+ax+b-y^2\equiv 0\mod p$ 的一个根，也就是说$f(y_1)\equiv 0\mod p$。

那么根据 Hensel 引理，$f(y_1+tp)\equiv 0\mod p^2$ 有解，其中$tf'(y)\equiv-(f(y)/p)\mod p$。而我们知道$f'(y)=(x^3+ax+b-y^2)'=-2y$，那么

$$t\equiv \cfrac{(x_1^3+ax_1+b-y_1^2)}{p}\cdot (2y_1)^{-1}\mod p$$

也就是能够求解出满足方程 $$f (y)\equiv 0\mod p^2$$ 的一个解$y=y_1+tp$。也就是说点$(x,y_1+tp)$ 实际上是在曲线$y^2\equiv x^3+ax+b\mod p^2$ 上的一个点。

通过上面的这一段过程，我们就把曲线$E(\mathbb{F_p})$ 上的一个点转换到了曲线$E(\mathbb{F}_{p^2})$ 上。

比较容易地可以实现代码：

def hensel_lift(E, P):

    x, y = P.x, P.y

    a, b, p = E.a, E.b, E.p

    t = ((pow(x, 3) + a * x + b - pow(y, 2)) // p) % p

    t = inverse(2 * y, p) * t % p

    return (x, t * p + y)

# SSSA Attack

目前求解 ECDLP 的一个应用十分广泛的方法是 Pollard rho 算法，这个算法的复杂度是$O(\sqrt N)$，$N$ 为群$E(\mathbb{F}_p)$ 的阶的最大素因子。

为了避免 Pollard rho 算法的攻击，一个思路就是去构造阶包含十分大的素因子的椭圆曲线群。上面提到了 Hasse 定理给出了椭圆曲线阶的上限，如果我们构造$\mathbb{F}_p$ 上一个阶为$p$ 的曲线（也就是 Frobenius 迹为 1），那自然是可以免受 Pollard rho 算法的攻击的。

这看似是一个安全的解决方案，然而却存在着十分高效的算法用以求解 ECDLP。

# 基本原理

SSSA 是由 Smart、Semaev 和 Satoh-Araki 分别独立发现的，用以将$\mathbb{F}_p$ 上的椭圆曲线转换到$\mathbb{Q}_p$ 上。这个算法针对的是这样的一个问题，对于定义在模素数$p$ 的有限域$\mathbb{F}_p$ 上的椭圆曲线$\overline{E}(\mathbb{F}_p)$，这个椭圆曲线满足上面的点的数量$\#\overline{E}(\mathbb{F}_p)$ 等于$p$，也就是说 Frobenius 迹$t=p+1-\#E(\mathbb{F}_q)=1$。这一类曲线叫做异常曲线 (Anomalous Curve) 。

我们都知道 ECDLP 实际上是针对椭圆曲线$\overline{E}(\mathbb{F}_p)$ 上的两个点$\overline{P}$ 和$\overline{Q}$，求解下面的离散对数问题：

$$\overline{Q}=[m]\overline{P}$$

很明显 ECDLP 问题是一个计算困难问题，直接去暴力破解是很不现实的。一个解决思路在于去构造一个 “对数” 映射（实际上就是一个群$\overline{E}$ 的一个同态），将椭圆曲线中的元素映射到一个求解 DLP 比较容易的群里去求解 DLP 问题。

一个比较容易计算 DLP 问题的群是$\mathbb{F}_p^+$，也就是模$p$ 意义上的加法群。但是现在并没有一个从在$\mathbb{F}_p$ 上的椭圆曲线群到$\mathbb{F}_p^+$ 的同态映射，不过对于$\mathbb{Q}_p$ 上的椭圆曲线群，倒是存在着这样的映射。

选择一条定义在$\mathbb{Q}_p$ 上的椭圆曲线$E$，它模$p$ 约减会得到曲线$\overline{E}$。我们可以计算$\overline{E}$ 上的点$\overline{P}$ 和$\overline{Q}$ 在曲线$E$ 上的对应点$P$ 和$Q$，对应的点的横坐标是原来点的横坐标，纵坐标则可以通过计算得到。

记$E(\mathbb{Q}_p)$ 的一个子群$E_n(\mathbb{Q}_p)$ 为

$$E_n(\mathbb{Q}_p)=\{P\in E(\mathbb{Q}_p)|v_p(x(P))\le-2n\}\cup\{O\}$$

这里的$x(P)$ 是点$P$ 的横坐标，$v_p(x)$ 是$x$ 的$p$ - 进赋值。我们将$x\in \mathbb{Q}$ 表示为分数形式$\cfrac{a}{b}$，其中$a,b$ 为整数，根据算数基本定理对$a$ 和$b$ 得到唯一分解，其中$p$ 在$a$ 和$b$ 的分解式中的次数分别是$ord_p(a)$ 和$ord_p(b)$，定义：

$$v_p(x)=ord_p(a)-ord_p(b)$$

同时有约定$v_p(0)=+\infty$。

例如对于$p=5, x=\frac{53}{250}$，因为$53=53,250=5^3*2$，那么$ord_5(53)=0,ord_5(250)=3$，故$v_p(x)=0-3=-3$。

这个子群定义中$v_p(x(P))\le-2n$ 也就意味着$P$ 的经过约减的横坐标的分母上至少有$p^{2r}$。

这里实际上可以对椭圆曲线进行一个替换。对于$y^2=x^3+ax+b$，我们设$z=-x/y$，$w=-1/y$，带入曲线的方程中可以得到：

$$w=z^3+azw^2+bw^3$$

将这条式子的$w$ 带入自身迭代，可以得到一个$w$ 关于$z$ 的无穷级数$w(z)$。
(好难算)

利用这些能反过来表示$x=\cfrac{z}{w(z)}$，$y=-\cfrac{x(z)}{z}$，那么只要这个级数$w(z)$ 收敛，我们就能够仅用$z$ 去表示$x$ 和$y$，也就是表示椭圆曲线上的点。实际上在域$\mathbb{Q}_p$ 上，$z\in p\mathbb{Z}_p$，$a,b\in\mathbb{Z}_p$ 时，这个数列是收敛的。

这样子我们也能够用$z$ 去表示两个点的$z_1,z_2$ 加法，记作$F(z_1,z_2)=z_1+z_2-az_1z_2...$。我们定义群$\hat{E}(p^n\mathbb{Z}_p)$，这是集合$p^n\mathbb{Z}_p$ 中的元素在$F$ 定义的加法运算下构成的群。

上面定义了：

$$E_n(\mathbb{Q}_p)=\{P\in E(\mathbb{Q}_p)|v_p(x(P))\le-2n\}\cup\{O\}$$

而我们也得到了$x=\cfrac{z}{w(z)}$，$y=-\cfrac{x(z)}{z}$，将这个记作一个映射$\mathcal{V}_p(z):=(\cfrac{z}{w(z)},-\cfrac{x(z)}{z})$，这个映射是群$\hat{E}(p^n\mathbb{Z}_p)$ 和群$E_n(\mathbb{Q}_p)$ 之间的一个同构。

我们需要一个从群$\hat{E}(p\mathbb{Z}_p)$ 到加法群$p^n\mathbb{Z}_p$ 的映射，也就是要找到一个函数$log$，满足$\forall z_1,z_2\in p\mathbb{Z}_p,\ s.t.\ log(F(z_1,z_2))=log(z_1)+log(z_2)$。一个映射是这样的：$log(T)=T+\frac{d_1}{2}T^2+\frac{d_2}{3}T^3+...$

我们前面得出了$\hat{E}(p\mathbb{Z}_p)\cong E_n(\mathbb{Q}_p)$，又有$\hat{E}(p\mathbb{Z}_p)\cong p\mathbb{Z}_p$，那么很明显有$E_n(\mathbb{Q}_p)\cong p\mathbb{Z}_p$，它们之间的同构是$\psi_p:=log\circ\mathcal{V}_p^{-1}$。

将前面这些同构用于商群，能够得到$E_n(\mathbb{Q}_p)/E_{n+1}(\mathbb{Q}_p)\cong p^n\mathbb{Z}_p/p^{n+1}\mathbb{Z}_p\cong \mathbb{F}_p^+$。

我们上面的这些操作得到了这样的一系列同构。下面让我们来看 Smart 构造的方式。

通过前面的 ECDLP 问题的定义：

$$\overline{Q}=[m]\overline{P}$$

可以通过 Hensel 定理推出：

$$Q-[m]P=R\in E_1(\mathbb{Q}_p)$$

这里有下面的结论：

$$E_0(\mathbb{Q}_p)/E_1(\mathbb{Q}_p)\cong \overline{E}(\mathbb{F}_p)\\[2ex] E_1(\mathbb{Q}_p)/E_2(\mathbb{Q}_p)\cong \mathbb{F}_p^+\\$$

也就是说商群$E_0(\mathbb{Q}_p)/E_1(\mathbb{Q}_p)$ 和$E(\mathbb{F}_p)$ 同构，商群$E_1(\mathbb{Q}_p)/E_2(\mathbb{Q}_p)$ 和$\mathbb{F}_p^+$ 同构。群$E(\mathbb{F}_p)=\overline{E(\mathbb{F}_p)}$ 和$\mathbb{F}_p^+$ 的阶都为$p$，那么乘以$p$（对于椭圆曲线实际上是$p$ 倍点）能够将$E(\mathbb{Q}_p)$ 中的元素映射到$E_1(\mathbb{Q}_p)$、将$E_1(\mathbb{Q}_p)$ 中的元素映射到$E_2(\mathbb{Q}_p)$ 中。

$$[p]Q-[m]([p]P)=[p]R\in E_2(\mathbb{Q}_p)$$

这样子就可以采用对数映射$\psi_p$ 对$E_1(\mathbb{Q}_p)$ 上的点$[p]Q,[p]P,[p]R$ 进行计算。这里注意上面有$R\in E_1(\mathbb{Q}_p)$，那么有$[p]R\in E_2(\mathbb{Q}_p)$：

$$\psi_p([p]Q)-m\psi_p([p]P)=\psi_p([p]R)\equiv 0\mod p^2$$

如果将上面的各个元素写作$p$ - 进数的系数，可以得到：

$$c_1p+c_2p^2+...-m(d_1p+d_2p^2+...)=b_2p^2+...$$

$c_i$ 是$p$ - 进数形式的$\psi_p([p]Q)$ 的系数，$d_i$ 是$p$ - 进数形式的$\psi_p([p]P)$ 的系数。那么需要计算$m$，只需要：

$$m\equiv\frac{\psi_p([p]Q)}{\psi_p([p]P)}\mod p$$

接下来要关心的就是怎么样去计算$\psi_p([p]Q)$ 和$\psi_p([p]P)$ 模$p^2$ 的系数。

对于一个点$S\in E_1(\mathbb{Q}_p)$，参考前面$\mathcal{V}_p$ 的定义可以得到：

$$\mathcal{V}_p^{-1}(S)=-\cfrac{x(S)}{y(S)}\in p\mathbb{Z}_p$$

其中$x(S),y(S)$ 分别对应了$S$ 的横、纵坐标。带回到前面给出的定义，我们能够得到$\psi_p(S)$ 的值：

$$\psi_p(S)\equiv-\frac{x(S)}{y(S)}\mod p^2$$

这样子的话只要知道群的 Frobenius 迹为 1，那么就能够在线性的时间内求解出这个 DLP 问题。这里要做的也就是计算出$E$ 上的$[p]P$ 和$[p]Q$，通过快速幂也可以在$\log p$ 时间内完成。而且上面计算$\psi_p$ 需要模$p$，故这些计算在曲线$E(\mathbb{Z}/p^2\mathbb{Z})$ 就行了。

# 实现

这里用 Sage 实现，网络上也有一些能够参考的资料。

def sssa(a, b, p, xP, yP, xQ, yQ):

    # 根据数据建立原始的数域、椭圆曲线和点

    gf = GF(p)

    # 原始的椭圆曲线定义在 F_p 上

    E = EllipticCurve(gf, [a, b])

    P = E(xP, yP)

    Q = E(xQ, yQ)

    # 构造 “lifted” 的椭圆曲线，注意这个椭圆曲线是定义在 Q_p 上

    lE = EllipticCurve(Qp(p), [a, b])

    # 通过 Hensel 引理将点进行转换

    # 这里直接使用了 Sage 中 EllipticCurve 类的 lift_x 方法

    # pl means 'p lift'

    pl = hensel_lift(lE, P, gf)

    ql = hensel_lift(lE, Q, gf)

    # 计算 [p] P 和 [p] Q

    pPl = p * pl

    pQl = p * ql

    plx, ply = pPl.xy()

    qlx, qly = pQl.xy()

    # 计算对应的域上的离散对数

    return int(gf((qlx / qly) / (plx / ply)))

这里拿一个异常的椭圆曲线为例：

p  = 0xb0000000000000006c5b40000000000010ad7f77
a  = 0x7cbc14e5e0a72f05864385397829cbc15a2fe1d6
b  = 0xa9cbc14e5e0a72f0bc20f05397829cbc24fd94a8
xP = 0x725c5b2943cc60511e0ff0dc2caa3d5b718c5453
yP = 0xf7eac9839e184ed16dcf70880867c8bcb094fae
xQ = 0x2a7e3b1a3960ee48d5e74dbb59859e433ead2dc0
yQ = 0x598275e68ac488066c93dc89f4e23748346c0365

经过计算可以发现这条椭圆曲线的 Frobenius 迹为 1，因此可以进行 SSSA 攻击，得到结果：

x = 0x46a79bf05f70d85552d0c2e587354e6bd8ad972f

# 参考资料

[1] Smart N P. The discrete logarithm problem on elliptic curves of trace one[J]. Journal of cryptology, 1999, 12(3): 193-196.

[2] https://crypto.stanford.edu/pbc/notes/elliptic/

[3] https://github.com/elliptic-shiho/ecpy/blob/master/ecpy/elliptic_curve/sssa_attack.py

[4] https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/smart_attack.py

[5] Satoh T, Araki K. Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves[J]. Rikkyo Daigaku sugaku zasshi, 1998, 47(1): 81-92.

[6] https://zh.wikipedia.org/wiki/ 亨泽尔引理

[7] https://en.wikipedia.org/wiki/P-adic_number

[8] Semaev I. Evaluation of discrete logarithms in a group of 𝑝-torsion points of an elliptic curve in characteristic 𝑝[J]. Mathematics of computation, 1998, 67(221): 353-356.

[9] Kenneth H. Rosen. Handbook of Elliptic and Hyperelliptic Curve Cryptography.

[10] Joseph H. Silverman. The Arithmetic of Elliptic Curves.

[11] 朱玉清，庄金成，于伟，等。特征 p 椭圆曲线上 p - 群的离散对数问题 [J]. 密码学报，2018, 5 (4): 368-375.

[12] WASHINGTON L C. Elliptic Curves: Number Theory and Cryptography[M]. New York: CRC Press.

[13] https://math.stackexchange.com/questions/3021935/what-is-p-adic-logarithmic-map-of-an-elliptic-curve-how-to-compute-it

[14] Leprévost F, Monnerat J, Varrette S, et al. Generating anomalous elliptic curves[J]. Information processing letters, 2005, 93(5): 225-230.