• tags: crypto, elliptic curve, ecc, smart's attack, Pohlig-Hellman Attack
• original_url: https://wstein.org/edu/2010/414/projects/novotney.pdf
• version: v0.1.0

[论文学习] Peter Novotney: Weak Curves In Elliptic Curve Cryptography

摘要

本文介绍了Pohlig-Hellman attack 和 Smart's attack，并讨论了推荐的 NIST 曲线是如何抵御这种攻击的。

1. Elliptic Curves

椭圆曲线的通用定义形式为

如果域的特征 > 3， 曲线可以简化为

1.1 Group Operation

+

:

1. 如果
2. 如果

椭圆曲线的阶记为

1.2 Choice of Field

素域：

二进制域:

本文仅讨论素域上的攻击

1.3 The Elliptic Curve Discrete Logarithm Problem

椭圆曲线的两点 ， 求k, 记作

最快的算法是  Pohlig-Hellman attack 和 Pollard Rho Algorithm

2. Attacks on Weak Curves

• 在没有较大的素子群时，受 Pohlig-Hellman attack 影响
• #E(Fp) = p 时，受Smart's attack 影响

2.1 Pohlig-Hellman Attack

Pohlig-Hellman attack 将 上的 ECDLP 问题简化为 素子群 上的ECDLP问题。

对椭圆曲线的阶 n 素因子分解，得到 ， 对每个素因子，我们希望找到

令

由中国剩余定理，即可恢复k。

其中 的计算还可以进一步简化为 进制上的

令 , 的阶为 ， 因为

因为 的阶为 , 是 进制上的第一位数，所以 。 可以由 上的ECDLP求解。

可以将其扩展至 求解 上的ECDLP ， 其中

例如

实现

def PolligHellman(P,Q):
    zList = list()
    conjList = list()
    rootList = list()
    n = P.order()
    factorList = n.factor()
    for facTuple in factorList:
        P0 = (ZZ(n/facTuple[0]))*P
        conjList.append(0)
        rootList.append(facTuple[0]^facTuple[1])
        for i in range(facTuple[1]):
            Qpart = Q
            for j in range(1,i+1):
                Qpart = Qpart - (zList[j-1]*(facTuple[0]^(j-1))*P)
            Qi = (ZZ(n/(facTuple[0]^(i+1))))*Qpart
        zList.insert(i,discrete_log(Qi,P0,operation='+'))
        conjList[-1] = conjList[-1] + zList[i]*(facTuple[0]^i)
    return crt(conjList,rootList)

2.2 Smart's Attack where #E(Fp) = p

Smart's attack 描述了一种线性时间内计算 #E(Fp) = p 的椭圆曲线上 ECDLP的方法。

换一句话说，椭圆曲线的 trace of Frobenius 为1时，可以利用。t = p+1+#E(Fp) = 1。

已知 x 为 的一个解, 偏导 存在模p上的乘法逆元u, 即存在 u使得 ，则 是 的解。

这个求解过程称为lift，在 时， 对r的lift是无法预测的，有时候无lift，有时候又多个lift

proof

http://web.archive.org/web/20190613022920/http://www.maths.gla.ac.uk/~ajb/dvi-ps/padicnotes.pdf

Theorem 1.33 (Hensel’s Lemma: first version).

令 , 假设 是 的一个根，f'(x) 存在关于模p的乘法逆元。则有 的根 , 满足 ,  x' 可由公式计算：

proof:

p-adic 数可以表示为

p-adic数构成的域记为 , 如果这些数没有负次幂(即， ) 则表示为

我们 可以在p-adic 数构成的域上定义 椭圆曲线，使用 上文介绍的 lift 方法 ，lift 上的椭圆曲线的点。这将允许我们将 ECDLP 约化(reduce)至 群 上。

令 是定义在 p-adic 域上的椭圆曲线，通过约化 的系数，得到

点的映射也类似，对

这个映射是从 到 的群同态。

P-adic Elliptic Logarithm 提供了 到 的同构。

对点

lift 上的点 P, Q 到 ，得到P', Q'。

因为在 上 ，所以  在 E(Q_p) 上 模p 为无穷远点。

因为 的阶为p， 所以任意点 都将被约化为 上的 ，所以   的任意元素乘p，都将映射到

因为 , 可以应用 P-Adic Elliptic Log:

再将 以约化回 ，解决 ECDLP。

3. NIST Recommended Curve

nist 推荐的曲线，不满足Smart's Attack 的利用条件，Pohlig-Hellman attack 也不能起到加速效果。

4. 总结

介绍了两种对不当选择的椭圆曲线及其底层域的攻击方法。还有很多其他的攻击方法。

本文同步发表于

• blog: ssst0n3.github.io
• 公众号: 石头的安全料理屋
• 知乎专栏: 石头的安全料理屋