CTFHub

Writeup

rrssaa

发表于 分类于 ， ， ， ，
Challenge | 2020 | XCTF高校网络安全专题挑战赛 | 鲲鹏计算专场 | Crypto | rrssaa

点击此处获得更好的阅读体验

WriteUp来源

官方WP

题目描述

题目考点

  • RSA

解题思路

题目总共用了3种不同的rsa加密需要我们逐层求解。

考察了3种不同的rsa攻击加密

第一层

rsa加密使用的公钥n是3个质数的乘积，且3个质数具有一定的联系

1
2
3
x = getPrime(290)
y = next_prime(21*x)
z = next_prime(3*x*y)

经过推算，可以发现最终的n约等于 21 * 21 * 3 * x**4

我们可以直接对 n 进行开发，得到近似的x的值。

1
guessx = iroot(n/(21*21*3),4)[0]

然后在附近进行爆破即可获得正确的x

完整的脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def generate(x):
   y = next_prime(21*x)
   z = next_prime(3*x*y)
   n = x*y*z
   return x,y,z,n
def solve_level1(n):
   guessp = iroot(n/(21*21*3),4)[0]-1000
   guessp = next_prime(guessp)
   while True:
       x,y,z,guessn = generate(guessp)
       if n == guessn:
           return x,y,z
       else:
           assert(guessn<n)
           guessp = next_prime(guessp)

这样就分解了n1

第二层

第二层rsa使用的n是4个质数的积，同样这些质数之间存在关系

1
2
3
4
o = getPrime(300)
s = getPrime(300)
t = next_prime(o)
u = next_prime(s)

next_prime意味着o和t，以及s和u之间是很相近的，我们可以假设

1
2
t = o + m1
u = s + m2

m1和m2一般是1000以内的整数

这样我们就有

1
2
n1 = o * s
n2 = (o+m1)*(s+m2)

由于m1和m2较小，我们可以直接爆破，在已知m1和m2的情况下，可以构造一元二次方程进行求解

完整脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def quadratic(ga,gb,gc,n):
        delta=gb**2-4*ga*gc
        if delta<=0 or ga==0:
            return 0
        tmp=iroot(delta,2)
        if tmp[1]==True:
            x1 = (-gb + tmp[0]) / (2*ga)
            x2 = (-gb - tmp[0]) / (2 * ga)
            if x1>0 and n%x1==0:
                return x1
            if x2>0 and n%x2==0:
                return x2
        return 0
def solve_level2(n,m):
        for x in range(1500):
            for y in range(1500):
                a=y
                b=x*y-m+n
                c=x*n
                tmp = quadratic(a,b,c,n)
                if tmp!=0:
                    p =  tmp
                    q = n/tmp
                    assert(p*q == n)
                    pp = p+x
                    qq = q+y
                    assert(pp*qq == m)
                    return p,q,pp,qq

这样就分解了n2

第三层

第三层的n是整行的两个大质数的积，但是这个题目没有给出加密公钥e。

同时注意到该题的e生成方式和奇怪

1
2
3
4
s = getPrime(10)
if(gcd(s,p-1) == 1):
    sinv = invert(s,p-1)
    e = 4*s*sinv+3

根据模逆运算的性质，我们有

1
e % (p-1) = 4 + 3 = 7

因此对于加密的密文 pow(m,e)我们有

1
pow(m,e) % p = pow(m,7+k*(p-1)) % p = (pow(m,7) % p) *(pow(m,k*(p-1))%p) % p = pow(m,7) % p

因此有

1
2
3
A = pow(m,e)-pow(m,7) = k * p
B = pow(m,e) = q * p
gcd(A,B) = p

分解了p和q之后 还需要恢复e

注意到生成e的中间变量 s是很小的，因此可以爆破。在有了p的情况下能很容易的根据s生成e并校验爆破的s是否正确。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
def solve_level3(m,c,n):
        p = gcd((c-pow(m,7)),n)
        assert(n%p == 0)
        q = n/p
        while True:
            s = getPrime(10)
            if(gcd(s,p-1)):
                sinv = invert(s,p-1)
                e = 4*s*sinv+3
                if pow(m,e,n) == c:
                    break
        return e,p,q

解密

当n1,n2,n3都被分解了之后，可以很容易的根据rsa解密原理，计算出解密密钥并还原flag

Flag

1
flag{4c2fd4e6-44de-445f-8c34-1235464de2de}