前言

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

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

from Crypto.Util.number import getPrime, isPrime
flag = 'BCNS{***************}'
nbits = 2048
gbits = 1000
g = getPrime(int(gbits))
while True:
    a = getPrime(int(nbits * 0.5) - gbits)
    p = 2 * g * a + 1
    if isPrime(p):
        break

while True:
    b = getPrime(int(nbits * 0.5) - gbits)
    q = 2 * g * b + 1
    if p != q and isPrime(q):
        break
N = p * q
e = 65537

def 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

介绍

该攻击方式首先由Chae Hoon Lim和Pil joong Lee提出，利用条件，

N=pq（N≥512bit）,其中，（p-1）和 (q-1)有一个大的公因数β，

并且该算法的时间复杂度为O(N^1/4^/β)

攻击方式

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

Pollard's ρ algorithm

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

核心思想

假设我们需要分解n，n=qp，其中q为n的非平凡因子（即q不等于1 或 n)。我们需要一个模n的多项式，例如：g(x) = x^2^+1 (mod n)，用于生成“伪随机”数列。我们选择一个起始值，例如，2，即x~1~=g(2)，x~2~=g(g(2))，x~3~=g(g(g(2)))......

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

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

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~ mod p}也会重复。这是因为，如果x~i~ mod p = x~j~ mod p, 那么x~i~与x~j~之间的差必然是p的倍数。同时，这也说明，gcd(x~i~-x~j~，n)不等于1的结果无论如何最终都会到来，因为它有可能是n自己，此时，代表Pollard's ρ algorithm失败了，可以使用不同的起始值，再次运算。

代码表示

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def mapx(x):
    x=(x*x+1)%n
    return x

def 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(ab,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~) mod 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代码：

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def mapx(x):
    x=(pow(x,n-1,n)+3)%n    #pow(x,n-1,n)是为了减小数值，加速运算，
    return x

def 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

def 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，显然不可能只有pq两个因数，否则真的是要让超算出动，

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

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

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def mapx(x):
    x=(x*x+1)%n
    return x

def pollard_rho(x1,x2):
    while 1:
        x1 = mapx(x1)
        x2 = mapx(mapx(x2))
        p = gcd(a - i, n)
        if p != 1:
            return p
n=...

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：

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

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

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

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

以下是 M=C^d^ mod N 的证明

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

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

推理如下

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

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

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

总结

这一次学习大概了解了

Further Attacks on Server-Aided RSA Cryptosystems，

Pollard's ρ algorithm，

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

再接再厉~

参考

Pollard's rho algorithm

Further Attacks on Server-Aided RSA Cryptosystems

UNCTF-simple-rsa Write-Up