密码学 | Lenstra的椭圆曲线分解算法

密码学 12个月前 admin

146 0 0

很久没有讲《数学密码学导论》了，今天继续讲6.6节。

6.6 Lenstra’s Elliptic Curve Factorization Algorithm

在3.5节中，我们介绍了Pollard’s p−1分解算法，首先简单地回顾一下。

假设现在我要分解，如果可以找到一个底数和指数，使得且的话，根据费马小定理可得，从而实现的分解。

为了能达到上述要求，需要是的一个因子，而不为的因子，Pollard’s p−1算法中的做法是让为或最大因子的阶乘，即若为或的最大因子，则，在不大的情况下，通过迭代即可枚举出然后实现分解。

显然这种分解算法有局限性，目前RSA算法所使用的素数都会选择安全素数，即先选一个大素数，然后计算作为RSA算法所使用的素数，这样的最大因子是，不可能通过枚举得出。

分析一下造成以上局限的原因，由于Pollard’s p−1运算在群上，其子群和的群阶确定为和，所以算法的设计者就可以根据这个固定的群阶选出对应的安全素数以用于预防Pollard’s p−1攻击。那么如果把Pollard’s p−1的攻击思路应用在别的群阶不可预测的群上呢？

在上几节我们介绍了椭圆曲线群，恰好就有这个特性。Lenstra就是根据这种启发（我猜的），把Pollard’s p−1算法的攻击思路应用在椭圆曲线群上，设计出本节的分解算法。

首先Pollard的算法是运行在群上，类似地，Lenstra的算法运行在一个模的椭圆曲线群上，不妨先令某个符合这个条件的椭圆曲线群为。然后和Pollard的算法中需要选择一个底数类似，Lenstra的算法也需要先选择一个上的椭圆曲线点。

但是如果的曲线确定的话，找上的一个点是个困难的问题，因为曲线的方程为，如果需要找到这个曲线上的一个点的话，就需要先选择，然后解出对应的。由于不是素数，所以这是一个非域上的二次方程，解出的难度不易于解模的二次剩余问题，或者也可以说不易于分解。

所以就需要逆转一下思维，可以先选择点，在构造出对应的曲线，即可得

只要先选择然后计算即可。

有了曲线和点后，就可以对点进行数乘运算，接下来和Pollard的算法的算法类似，令是模数为且以为参数的椭圆曲线群，是模数为且以为参数的椭圆曲线群。Lenstra的算法希望可以找到一个数，使得

其中是无穷远点，或者说是群或的单位元。结论上来说，需要的群阶为的因子，而的群阶不为的因子。

如果可以找到符合以上条件的，Lenstra的算法即可从中分解出，分解的方法和Pollard的求gcd最大公约数不同，从结论上来说，这时在上算会有一个求模的逆元的操作，由于，所以并不能求出模的逆元，从而触发错误。

但是这个错误就恰好帮我们求出了的因子，从而实现分解！

下面可以来一点直观的代码验证一下，以下代码中，我先生成和，然后再用中国剩余定理求出上的一个点N，最后分别使用的群阶和的群阶和这个点相乘，最后触发了SageMath的报错并分解了n。

#!/usr/bin/env sage
bits = 64
p = random_prime(2^bits)
q = random_prime(2^bits)
n = p * q
print('p = %d' % p)
print('q = %d' % q)
print('n = %d' % n)

a = 3
b = 7
Ep = EllipticCurve(Zmod(p), [3, 7])
Eq = EllipticCurve(Zmod(q), [3, 7])
En = EllipticCurve(Zmod(n), [3, 7])
P = Ep.random_element()
Q = Eq.random_element()
xn = crt([Integer(P.xy()[0]), Integer(Q.xy()[0])], [p, q])
yn = crt([Integer(P.xy()[1]), Integer(Q.xy()[1])], [p, q])
N = En([xn, yn])
phip = Ep.order()
phiq = Eq.order()
phin = phip * phiq
print('phip = %d' % phip)
print('phiq = %d' % phiq)
print()

try:
  phip * N
except Exception as e:
  E = e
print(E.args[0].split('characteristic = ')[1][:-1])
print()

try:
  phiq * N
except Exception as e:
  E = e
print(E.args[0].split('characteristic = ')[1][:-1])

'''
p = 548633948767114901
q = 17627849644445796449
n = 9671236758705279712661172994840786549
phip = 548633949895444576
phiq = 17627849643539354301

9671236758705279712661172994840786549 = 548633948767114901*17627849644445796449

9671236758705279712661172994840786549 = 17627849644445796449*548633948767114901
'''