密码学学习笔记 之 浅析Pollard's rho algorithm及其应用

首发于先知社区

前言

这几天在学密码学，其中有关RSA的内容。由于各种攻击算法的出现，RSA现在其实已经不太安全了(由于不恰当的参数的使用)，但不得不承认的是，当今RSA加密技术还是被普遍应用的~

然后在做题的时候，遇到了这样一题

12345678910111213141516171819202122232425262728293031

from Crypto.Util.number import getPrime, isPrimeflag = 'BCNS{***************}'nbits = 2048gbits = 1000g = getPrime(int(gbits))while True:    a = getPrime(int(nbits * 0.5) - gbits)    p = 2 * g * a + 1    if isPrime(p):        breakwhile True:    b = getPrime(int(nbits * 0.5) - gbits)    q = 2 * g * b + 1    if p != q and isPrime(q):        breakN = p * qe = 65537def str2int(s):    return int(s.encode('hex'), 16)with open('pubkey.txt', 'w') as f:    f.write(str(e) + '\n')    f.write(str(N) + '\n')plain = str2int(flag)c = pow(plain, e, N)with open('cipher.txt', 'w') as f:    f.write(hex(c))

这里我们引入Further Attacks on Server-Aided RSA Cryptosystems

Further Attacks on Server-Aided RSA Cryptosystems解决的是大数分解的一个问题，

利用条件是当$N=p*q(N≥512bit)$,其中，$(p-1)$和 $(q-1)$有一个大的公因数β

在Further Attacks on Server-Aided RSA Cryptosystems的第一个攻击阶段中提到：运用Pollard’s ρ methods ，其中用于取伪随机值的maps函数为 $g(x)=x^{N-1}+3 \pmod {N}$，这将在时间复杂度O($\sqrt{p/β}$)内分解N，因为在$x^{N-1}\pmod{N}$中，至多有 $\frac{(p-1)}{β}+1$个值

Pollard’s ρ algorithm

波拉德的 ρ 算法是整数分解的一种算法。 它是约翰 · 波拉德在1975年发明的。 它只占用了很少的空间，并且它的预期运行时间与被分解的合数的最小质因数大小的平方根成正比

核心思想

假设我们需要分解$n$，$n=q*p$，其中$q$为$n$的非平凡因子（即$q$不等于$1$ 或$ n$)。我们需要一个模$n$的多项式，例如：$g(x) \equiv x^2+1 \pmod{n}$，用于生成“伪随机”数列。我们选择一个起始值，例如，$2$，即$x_1=g(2)，x_2=g(g(2))，x3=g(g(g(2)))……$

这里值得注意的是，这个数列是有限的，由于生日问题，序列 $x_k $mod（$n$）最终会重复，一旦一个序列由重复的值，这个序列就会循环，因为每个值依赖于它之前的值， 这种最终循环的结构产生了“ ρ 算法”的名称

这里我们可以举一个简单的小例子，我们设$n$为640，$g(x)=x^2$，$x$起始值为2，

123

while True:    b*=2    print b%640

我们可以看到，128为这个取模多项式的循环节点，

回到话题，这里继续用 Floyd’s cycle-finding algorithm发现：设立两个节点，$i$，$j$，在每一步中，$i$每次移动一个节点，$j$每次移动两个节点，然后检查$gcd(x_i-x_j,n)$是否≠1，如果不等于，那么$gcd$的结果便是$p$。并且，这也意味着序列${ x_k \pmod p}$也会重复。这是因为，如果$x_i \equiv x_j \pmod{p}$, 那么$x_i$与$x_j$之间的差必然是$p$的倍数。同时，这也说明，$gcd(x_i-x_j，n)$不等于1的结果无论如何最终都会到来，但是可能是$n$自己，此时，代表Pollard’s ρ algorithm失败了，可以使用不同的起始值，再次运算。

代码表示

123456789101112131415161718192021

def gcd(a, b):    while b:        a, b = b, a%b    return adef mapx(x):    x=(x*x+1)%n    return xdef pollard_rho (x1,x2):    while True:        x1=mapx(x1)        x2=mapx(mapx(x2))        p=gcd(x1-x2,n)        if (p == n):            print "fail"            return        elif (p!=1):            print("p: "+str(p))            print("q: "+str(n/p))            break

变体

1980年，Richard Brent 发表了 rho 算法的一个更快的变体。 他使用了与Pollard相同的核心思想，但是使用了不同的循环检测方法，用相关的 Brent’s cycle finding method取代了 Floyd’s cycle-finding algorithm

他观察到，如果 $gcd(a,n)>1$，那么$gcd(a*b,n)>1$（b为任意正整数）。所以，取代Floyd’s cycle-finding algorithm的每一步都检查$gcd(a,n)$，他定义了一个$z，z=(x_2-x_3·(x_3-x_5……(x_{101}-x_{201} \pmod {n} $即每一百步才检查一次$gcd(x_i-x_j,n)$，这么作主要是为了加速结果。 但有时它可能会引入重复因子导致算法失败，例如当n是一个正方形时。 但是这样使用常规算法就好了。

解题

那么回过头来我们解最初出现的那一道题，题中，$p-1$和$q-1$有很明显的公因子2g，于是根据Further Attacks on Server-Aided RSA Cryptosystems中The first stage of the attack所提到的，为了分解n，我们只需要运用Pollard’s ρ algorithm，其中用于生成“伪随机”数列的多项式为：$g(x)=(x^{n-1}+3)$%$n$

python代码：

12345678910111213141516171819202122232425262728

def gcd(a, b):    while b:        a, b = b, a%b    return adef mapx(x):    x=(pow(x,n-1,n)+3)%n    #pow(x,n-1,n)是为了减小数值，加速运算，    return xdef pollard_rho (x1,x2):    while True:        x1=mapx(x1)        x2=mapx(mapx(x2))        p=gcd(x1-x2,n)        if (p == n):            print "fail"            return        elif (p!=1):            print("p: "+str(p))            print("q: "+str(n/p))            breakdef main():    pollard_rho(1,1)    return n= #题目所给        main()

运行十来秒成功分解。

UNCTF-simple_rsa

前几天打的UNCTF其中有一道极其简单粗暴的rsa的题目

题目简单粗暴，给了$e,n,c$

显然是要分解$n$得到$p$和$q$

但是，其中，$n$有2092位，除非人手超算~

但其实这里可以用到Pollard’s ρ algorithm，前面提到它的预期运行时间与被分解的合数的最小质因数大小的平方根成正比

而这么大的模数$n$，显然不可能只有$p,q$两个因数，否则真的是要让超算出动，

所以我们猜测$n$是由若干个小素数的乘积而来

于是利用Pollard’s ρ algorithm分解这个$n$

12345678910111213141516171819202122

def gcd(a, b):    while b:        a, b = b, a%b    return adef mapx(x):    x=(x*x+1)%n    return xdef pollard_rho(x1,x2):    while 1:        x1 = mapx(x1)        x2 = mapx(mapx(x2))        p = gcd(a - i, n)        if p != 1:            return pn=...while (n!=1):    p = pollard_rho(2,2)    print p    n = n / p

跑个十来分钟应该可以得到

（我放着程序没管，跑了好几个小时后得到）

但其实有前面6个740160703366837大概已经是够了，740160703366837的6次方大概有90位，而如果flag是md5值得话，长度是32+6。由76位十六进制表示，最大由92位十进制表示（显然是不可能的，这个时候已经不是可打印字符了）所以90位作为n应该已经是够了。（再不济就再等一会儿,多出来几个就好了）

exp：

123456789

from gmpy2 import *e = 0x10001c = #题目所给p = 740160703366837n = p**6c = c % nphi = (p-1)*(p**6)d = invert(e,phi)print(hex(pow(c,d,n))[2:].decode('hex'))

这里相当于我们直接把原题的$n$给纂改了，

但为啥这里我们可以直接改$n$呢？

这里再回顾一下基础知识好了

以下是 $M\equiv C^d pmod{N}$ 的证明

首先，看到这里要求$m<n$，所以这里n_new大于m即可

其次，由于n_new | n，所以 c % n_new == pow(m ,e ,n_new)

推理如下

12345

          n = n_new * x          c = m^e % n        m^e = k*n + c        m^e = k*n_new*x + cm^e % n_new = c % n_new

所以只要新的N满足，$m<N$, $m^e \equiv c \pmod {N}$，并且$gcd(e,phi(N))=1$，即可逆向求出$m$来。

而一般情况下$n=p*q$，所以基本不给你篡改$n$的机会~

总结

这一次学习大概了解了

Further Attacks on Server-Aided RSA Cryptosystems，

Pollard’s ρ algorithm，

以及多素数RSA系统的其中一种解法，

最后，感谢Lur大佬的指点~

但虽然知道这个算法的流程，其实并不懂原理，好神奇的感觉，有没有大佬教教俺

参考

Pollard’s rho algorithm

UNCTF-simple-rsa Write-Up

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 [email protected] - source:Van1sh的小屋