Pollard p-1 Algorithm (科普向)

Lyutoon

发布于：2020年11月17日

一、引言

当我们首先接触到这个陌生的算法的时候,肯定想要知道这个算法是干什么用的。对于Pollard p-1算法,它可以在一定条件下完成对某些具有特定性质的大整数的分解问题。那么,什么是大整数分解问题？为何它如此重要？这个算法又在什么条件下用什么数学原理可以完成这一问题呢？接下来我会慢慢讲解。

二、大整数分解问题

关于大整数分解问题,未接触过密码学的朋友们请想像一下自己对大整数的理解,何为大整数？一千万？一亿？一千亿？其实这都不算是足够作为密码学体制中严格意义的大整数。在密码学中,一般的RSA加密体制用的模数n的强度为1024bit或者更强的2048bit,也就是意味着是$2^{1204} \sim 2^{2048}$这样的数字才可被称为可用于加密的大整数。大整数分解就是把这个大整数分解成为一个一个素数的乘积。而我们为什么要对它进行分解呢？这就要提到刚刚我们讲过的RSA加密体制了。

RSA加密体制是典型的公钥密码体系,而它的应用也算是十分广泛,我们在生成github的ssh密钥的命令ssh-keygen -t rsa -C中就出现了它的身影。而RSA之所以保密性如此强大,其背后的数学原理就是大整数分解的困难性。下面我们来具体看看RSA的做法：

首先Alice选择两个大素数(一般为512bit强度)$p$和$q$,计算$n=p\cdot q$作为公钥的一部分。接下来选择一个较大整数$e$,满足$gcd(e,\phi(n)) = 1$,其中$\phi(n)$是n的欧拉函数。一般来说,通用的$e=65537$,太大太小都容易遭受攻击(具体以后会讲)。这样我们就得到了一组公钥$(e,n)$。

之后,Alice根据$p$和$q$来确定私钥$d = e^{-1}mod\phi(n)$。

接下来,因为公钥$(e,n)$是公开的,因此如果Bob想对Alice发消息,那么就可以对明文$m$采用公钥进行加密,得到密文$c$传输给Alice,Alice对其加密后的密文用私钥$d$进行解密,即可恢复明文$m$。具体实现过程如下：

$c = m^e mod\,n$ $m = c^d mod\,n$

具体的数学原理涉及到简单的数论知识：(如果看不懂请继续看下去,在pollard p-1算法中会讲解简单的数论知识,再回过头就明白啦)

$m = c^dmod\,n = m^{ed}mod\,n = m^{k\phi(n)+1}mod\,n=m\,mod\,n$

讲完了RSA 的实现之后,我们不禁想到：“如果我们知道n的因数p和q不就可以恢复d,进而进行消息破解了吗？”正是如此,如果我们可以有多项式时间的算法来分解大整数$n$,那么RSA也就不再安全。

三、Pollard p-1 算法

1、数论知识的回顾

开始之前,

我们要先具备一些数论的知识。

(1) 算数基本定理

算术基本定理可表述为：任何一个大于1的自然数$N$,如果$N$不是素数,那么我们都可以把它分解成有限个素数的乘积。写成公式为：

$N=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$

其中对于不同的$i$和$j$,$p_i^{e_i}\neq p_j^{e_j}$

(2) 同余

我们说a和b模n同余指的是两个数除以n的余数是相同的,记作$a\equiv b\,mod\,n$

(3) Fermat’s Little Theorem

如果p是一个质数,而整数a不是p的倍数,则有$a^{p-1}\equiv 1\,mod\,p$。

(4) Euler’s $\phi$ Function’s Property

欧拉函数的性质是费马小定理的推广,也是RSA解密的核心数学原理,具体的表达式为：$a^{\phi(p)}\equiv 1\, mod\,p$,其中a不是p的倍数。

2、Pollard p-1 算法解析

了解了以上数论知识时候,我们就可以开始学习Pollard p-1算法了！(此处针对的是$n=pq$,$p$和$q$为素数的情况,多素因子的情况其实是类似的,为了容易理解,此处取$n=pq$的情况。)

(1) 适用条件

首先,Pollard p-1算法是有使用条件的：$n=pq$,其中$p-1$是比较平滑的。那么什么是平滑的呢？其实就是如果将$p-1$用算数基本定理分解成$p-1=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$的形式,对于每个$ p_i^{e_i}$都小于等于某个特定的(较小的)整数$B$。

(2) 主要思想

我们主要思想是：$2^{B!}-1$是p的倍数,或者写为$2^{B!}\equiv 1\,mod\,p$。下面我们来证明一下：

首先我们知道$p-1$的每一个$p_i^{e_i}$都小于等于$B$,而且对于不同的$i$,$p_i^{e_i}$也是不相等的,因此,对于每一个$p_i^{e_i}$,都包含在$[2,B]$这个区间内。因此$B!$是$p-1$的倍数,或者写为：$B!=k(p-1)$,$k$是大于0的整数。

有了这个条件,我们就可以得到：$2^{B!}\equiv 2^{k(p-1)}\,mod\,p$,而我们应用学过的费马小定理可以发现：$2^{B!}\equiv 2^{k(p-1)}\,mod\,p \equiv 1\,mod\,p$

到此我们就证明了$2^{B!}-1$是$p$的倍数这件事,聪明的朋友应该已经发现了,如果我们对$2^{B!}-1$和$n$求最大公因数,我们就可以得到$p$的准确值,因为$n$只有两个不相等素因数$p$和$q$。

(3) 代码实现

from random import randint
# gcd 算法,或者直接用libnum的libnum.gcd
def gcd(a, b):
    if a == 0: return b
    if b == 0: return a
    while b:
        a, b = b, a % b
    return abs(a)

#适用于不那么大的整数,并且可以输出满足条件的最小的B
def pollard_p_small(n):
    B = 2
    while True: 
        a = 2
        for i in range(2, B+1):
            a = pow(a, i, n)
        d = gcd(a-1, n)
        if d != 1 and d != n:
            print('[+] Find p:', d)
            print('[+] Find min_B:', B)
            return d, B
        B += 1
#大整数(只进行了二分查找,还是挺慢的,暂时没有太多考虑优化问题)
def pollard_p_big(n):
    #上限可以自己定,一般来说n就够了
    B = randint(2, n)
    while True: 
        a = 2
        for i in range(2, B+1):
            a = pow(a, i, n)
        d = gcd(a-1, n)
        #此处的步长为1,在大整数的时候步长可以设长一点,为了节省时间,使B的选取更均匀
        if d == 1:
            B = randint(B+1, n)
        elif d == n:
            B = randint(2, B-1)
        else:
            print('[+] Find p:', d)
            return d
n1 = 262063
n2 = 9420457
pollard_p_small(n1)
pollard_p_small(n2)

""""
output:
[+] Find p: 521
[+] Find min_B: 13
[+] Find p: 2351
[+] Find min_B: 47
""""

四、结语

该算法提醒我们在RSA素数生成的时候,不要选取过于$smooth$的素数,这样可以有效防止Pollard p-1算法的攻击。

感谢大家能读到这里,希望看完我的文章大家可以收获一些知识和乐趣,以后我会再更新更多的有关密码学的科普和解析博客,也会更新我最近的所思所想,感谢大家的阅读。

更新于：2020年11月19日

Pollard Rho Algorithm Study

一、引言在上一篇博客中,我们了解了Pollard p-1 算法,这次,请随我看看另一个名叫Pollard Rho的算法又能对大整数分解问题提供什么帮助吧！不过同样的,大整数分解问题在因子选取得当...