writeup for 2021 MRCTF

Posted on Edited on In Word count in article: 16k Reading time ≈ 15 mins.

啊比赛的时候刚好和npy出去玩了, 也没怎么看题, 就看了半个下午的Common prime rsa. 也没整出来.
最近又在忙学校的HW就是什么成果都没, 只能看着大佬干自己划水的那种. 所以题目复现什么的就慢了好多.
慢慢的更新完吧, 每次做题都一堆paper, 想慢慢的看完只能花多点时间了吧

Strange_GCD

problem

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from gmpy2 import *
from random import *
from Crypto.Util.number import *
from os import urandom
from flag import flag

P_bits = 444
Q_bits = 666
R_bits = 333
key_num = 9
e = 0x1337

while True:
    could_not_solve = False
    p = getPrime(P_bits)
    if gcd(p-1, e) != 1:
        continue
    R = []
    Q = []
    N = []
    for i in range(key_num):
        Q.append(getPrime(Q_bits))
        R.append(getrandbits(R_bits))
        N.append(p * Q[-1] + R[-1])
        if gcd(Q[-1], e) != 1:
            could_not_solve = True
            break
    if not could_not_solve:
        break


C = []
assert len(flag) == 45
for i in range(key_num):
    tmp_cipher = flag[i*len(flag)//key_num:(i+1)*len(flag)//key_num].encode()
    tmp_cipher = urandom(128 - len(tmp_cipher)) + tmp_cipher
    tmp_cipher = pow(bytes_to_long(tmp_cipher), e, p * Q[i])
    C.append(tmp_cipher)

print('N =', N)
print('C =', C)

'''
N = [...]
C = [...]
'''

analyses

这题比完赛以后做的, paper也是直接就看别人找了自己找太浪费时间啦

做的时候没看paper, 造格子没去思考怎么消去比较大的项, 看了paper才明白,

AGCD

先来看看这边的公钥生成, 这共生成了9个
其中的位数分别为, 这个问题看着像LWE但是我们只知道. 尝试了一下造格子也没啥结果, 找paper找到了这个-> The Approximate GCD Problem 这里面提供了一个造格子的方法来分解

其实这里面就有一种造格子的思想吧? 我们想要通过格基规约得出结果, 那么我们必须保证我们需要求出的量不会很大(只有这样才能使得我们要求的向量是最短向量), 所以我们的一个思路, 可以是消去一些比较大的数, 留下一些比较小的.

在这里我们先拿两行等式来分析

我们可以看到式子里有个非常大的, 可以想个办法消去这个大的项并且不引入比他更大的项. 一个办法就是通过减法!

通过减法可以将 bits的变成了小一点的 bits 的, 这里小了点就可以尝试做文章了. 我们可以根据这个式子写出剩下的一样的式子

根据这个式子, 可以造出格子

的取值

这里有个参数需要确定下来, 这个参数跟最短向量的上界有关, 一直以来这个参数都是用来调目标向量长度和格的行列式用的, 也没有具体的分析过, 每次做的时候都直接爆破, 这次慢慢分析了一下.

先来看我们要求的向量, 暂时记为

再来看看


格子是9维的, 那么我们可以有一个粗略的不等式
通过简单的计算就可以得到

得到参数的大概取值范围, 选一个中间的就行了, 想刺激一点可以试试130 359之类的(反正我试了都是可以的).

(2) 式只是粗略得到的, 因为上界还有更严格的条件而且LLL算法实际上要比理论上要好….

我们构造出格子并规约后就能得到了, 剩下的就是仿造这个格子构造求的格子, 求出所有的以后, 因为 , 所以, 直接就可以求出了, 继续求出,然后就是正常的RSA解密了.

exp

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
29
from Crypto.Util.number import long_to_bytes
N = [...]
C = [...]
Q = []
R = []
D = []
t = 0
for _ in range(9):
    M = 2^130
    L = [[0 for _ in range(9)] for _ in range(9)]
    L[0] = [M]+N[0:t] + N[t+1:]
    for i in range(9):
        L[i][i] = - N[t]
    L[0][0] = M
    MQ = abs(matrix(L).LLL()[0][0])
    assert  MQ % M == 0
    Q.append(MQ // M)
    t+=1

for n,q in zip(N,Q):
    R.append(n % q)

p = (N[0] - R[0]) // Q[0]

for i in range(9):
    phi = (p-1) * (Q[i]-1)
    D.append(inverse_mod(0x1337,phi))
for c,d,q in zip(C,D,Q):
    print(long_to_bytes(pow(c,d,p*q))[-5:].decode(),end='')

Common_Prime_RSA

problem

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
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import *
from secret import flag

def get_my_prime(nibt, gamma):
    g = getPrime(int(nibt * gamma))
    while True:
        p = 2 * g * getPrime(int(nibt * (0.5 - gamma))) + 1
        if isPrime(p):
            break

    while True:
        q = 2 * g * getPrime(int(nibt * (0.5 - gamma))) + 1
        if isPrime(q):
            break

    assert 2 * p > q and 2 * q > p
    return p, q, g

p1, q1, g1 = get_my_prime(1024, 0.2247)
p2, q2, g2 = get_my_prime(1024, 0.3247)
n1 = p1 * q1
n2 = p2 * q2

print(hex(n1))
# 0x48b11209b62c5bc580d00fc94886272b92814ce35fcd265b2915c6917a299bc54c2c0603c41f8bf7c8f6f2a545eb03d38f99ec995bf6658bb1a2d23056ee21c7230caa2decec688ea9ee00b0d50b39e8cd23eb2c3ddeb20f5ab26777b80052c171f47b716e72f6aee9cece92776fc65119046f9a1ad92c40e2094d7ed7526d49

print(hex(pow(bytes_to_long(b'Common prime RSA is a variant of RSA' + long_to_bytes(g1) + b'And the common factor g is large prime and p=2ga+1 q=2gb+1'), 3, n1)))
# 0x27d8d7249643668ffc115be8b61775c60596e51f6313b47ad5af8493526922f5e10026a2cdaef74e22c3eec959dd8771abe3495b18d19f97623f5a3f65f22ff8fc294fc37ceb3b43ebbbf8a9bcf622922e22c5520dbd523483b9dc54fdffcd1a1b3f02ca1f53b75413fb79399ca00034f2acf108ac9a01bd24d2b9df6e27d156

print(hex(pow(g2, 65537, n1)))
# 0xeaf06b9050a809659f962251b14d6b93009a7010f0e8d8f0fa4d71591757e98243b8ff50ec98a4e140fd8a63bbb4b8bb0a6d302a48845b8b09d1e40874fcb586ddccbb0bbf86d21540ec6c15c1d2bf925942f6f384fdc1baae7f8e06150ccd9459eb65d0f07eea16a911fa0a17e876a145dbfec83537ca2bee4641897b9f7f5

print(hex(n2))
# 0x6d457110d6044472d786936acbd3cd93c7728daa3343b35ccaa5c55eba6b35c28c831bb245b8cdd8fc8cb67a72f57e62a0e1259f5e804c487a8478f6895b302d39277bd73947598a5f8ec0a535be9e9a4d34df91df948ee44cc3d13d14e23b9651089e4767c7f0e7245df55619c92fe24483225d35f5f3ee6f74375065766ffd

print(hex(pow(bytes_to_long(flag.encode()), 65537, n2)))
# 0x15be2b0eaef8837a753587c47d3f31696a7d239d88837a9b7d903cd0d0648ef8e225ea555402693a23f305d19e7e13905be61b44c651dba5b26614bcf876234e765a724e0ed8af4a4e408e6a233c48ab9cc63e9c552ef9cd1999512aa0aca830fe6cbcbcc3c6bb354903124a2c3a12d442cdbdefdae6576f4bbc1515051b7111

analyses

这道题做的时候自己踩了坑, 也没做出来, 后面看wp找到了那个paper才大概明白, 关于界的确定还得谢谢d33师傅.

coppersmith

这题的第一个problem就是求解, 第一个明文可以分成三部分

和我们都是知道的, 而和的位数分别为

所以理论上式可以写成

这里就有个坑了, 字符串在拼接的时候肯定都是完整的字节在拼的, 所以每一段的位数都应该是8的倍数才对, 所以正确的式应该为:

的位数为, 是满足coppersmith的条件的.

我们记, 那么就有, 化成首一多项式后coppersmith method即可求出

further attacks on server-aided rsa

我们从上部分得到了 , 我们可以看看和的关系, 为了方便讨论, 直接记

那么我们有

这里设, 那么式可以化成

这里的 , 也就是把看成是的结果. 那么都是可以计算出来的, 重点在于新引入的, 求出就可以求了

paper里提供了一种利用bsgs北上广深思想的方法来求出这个c, 但这题跟paper在c的界上有区别.

原paper是这样的, 我们随便找一个素数 , 观察下面的式子

为什么没有了呢? 因为 .

然后求一下的上界, 后面要用到

记, 我们有 , paper里提到了这个是很大概率相等的, 有师傅知道为什么吗?
所以我们可以用bsgs的思想, 计算两组数.

其中

在这两组数中搜索碰撞, 也就是 . 找到碰撞以后就可以计算了, 有了就可以分解了

当我看完paper以后兴奋的写了, 却发现这个北上广深把我内存全部吃完都没有结果(早上起来发现电脑屏幕都打不开了….
怎么会没结果啊…只能去看d33师傅的wp了! 因为他什么都会, 看完才明白原来paper里的界太松散了, 导致太大, 跑出来需要多几根内存才行, 可是我只有一根8G的内存.

d33师傅的界:

因为的位数相同, 所以我们还有一个隐藏的关系式

这个式子很重要, 我们继续观察一下和的关系, 我们可以根据基本不等式写出上界, 再根据式写出下界

根据这个, 咱们就有一个更加严格的的界

同样的, 计算, 再用bsgs就可以求出了, 但我8G的小内存依旧跑不出来, 只能借用一下d33师傅的数据了

分解了就能求出, 由于的位数比较大, , 直接就有:

也可以直接求出来了, 然后依旧是分解, 就可以求出flag了

exp

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from Crypto.Util.number import long_to_bytes as l2b,bytes_to_long as b2l
from time import time
from gmpy2 import iroot
n1 = 0x48b11209b62c5bc580d00fc94886272b92814ce35fcd265b2915c6917a299bc54c2c0603c41f8bf7c8f6f2a545eb03d38f99ec995bf6658bb1a2d23056ee21c7230caa2decec688ea9ee00b0d50b39e8cd23eb2c3ddeb20f5ab26777b80052c171f47b716e72f6aee9cece92776fc65119046f9a1ad92c40e2094d7ed7526d49
n2 = 0x6d457110d6044472d786936acbd3cd93c7728daa3343b35ccaa5c55eba6b35c28c831bb245b8cdd8fc8cb67a72f57e62a0e1259f5e804c487a8478f6895b302d39277bd73947598a5f8ec0a535be9e9a4d34df91df948ee44cc3d13d14e23b9651089e4767c7f0e7245df55619c92fe24483225d35f5f3ee6f74375065766ffd
c1 = 0x27d8d7249643668ffc115be8b61775c60596e51f6313b47ad5af8493526922f5e10026a2cdaef74e22c3eec959dd8771abe3495b18d19f97623f5a3f65f22ff8fc294fc37ceb3b43ebbbf8a9bcf622922e22c5520dbd523483b9dc54fdffcd1a1b3f02ca1f53b75413fb79399ca00034f2acf108ac9a01bd24d2b9df6e27d156
c2 = 0xeaf06b9050a809659f962251b14d6b93009a7010f0e8d8f0fa4d71591757e98243b8ff50ec98a4e140fd8a63bbb4b8bb0a6d302a48845b8b09d1e40874fcb586ddccbb0bbf86d21540ec6c15c1d2bf925942f6f384fdc1baae7f8e06150ccd9459eb65d0f07eea16a911fa0a17e876a145dbfec83537ca2bee4641897b9f7f5
c3 = 0x15be2b0eaef8837a753587c47d3f31696a7d239d88837a9b7d903cd0d0648ef8e225ea555402693a23f305d19e7e13905be61b44c651dba5b26614bcf876234e765a724e0ed8af4a4e408e6a233c48ab9cc63e9c552ef9cd1999512aa0aca830fe6cbcbcc3c6bb354903124a2c3a12d442cdbdefdae6576f4bbc1515051b7111
a = b2l(b'Common prime RSA is a variant of RSA') << 696
b = b2l(b'And the common factor g is large prime and p=2ga+1 q=2gb+1')


mbar = a+b
R.<x> = Zmod(n1)[]
f = ((2^464) * x + mbar) ^ 3 - c1
f = f.monic()
g1 = int(f.small_roots(X=2^230,beta=1)[0])

beta = 2* g1
v = ((n1 - 1) // beta)% beta
u = ((n1 - 1) // beta - v) // beta
b = pow(2,beta,n1)
left = (2*int(sqrt(n1))//beta-2-v)//beta 
right = (3*int(sqrt(2)*sqrt(n1))//(2*beta) - 2 - v )//beta 
D = int(sqrt(right - left)) + 1
#############################################################
#  这部分应该是bsgs部分由于没办法跑出结果,无法确定自己的算法是否正确  #
#  所以就先不放出来了,想知道具体的可以找d33师傅的博客               #
#############################################################

c=left+698170*D+5980588
xy = u - c 
x_y = v + c * beta
x = var('x')
f = x^2 - x_y * x + xy
x,y = f.roots()[0][0],f.roots()[1][0]
p,q = x *beta+1,y*beta+1
assert p*q == n1
g2 = int(pow(c2,int(inverse_mod(65537,(p-1)*(q-1))),n1))
beta = 2 * g2
x_y = ((n2 - 1) // beta)% beta
xy = ((n2 - 1) // beta - x_y) // beta
x = var('x')
f = x^2 - x_y * x + xy
x,y = f.roots()[0][0],f.roots()[1][0]
p,q = x *beta+1,y*beta+1
assert p*q == n2
l2b(pow(c3,int(inverse_mod(65537,(p-1)*(q-1))),n2))

Strange_CRT

problem

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
29
30
31
32
33
34
35
from gmpy2 import *
from random import *
from Crypto.Util.number import *
from flag import flag


beta = 0.34
delta = 0.02
amplification = 2048

p = getPrime(int(beta * amplification))
q = getPrime(int((1 - beta) * amplification))
N = p * q

while True:
    dq = getrandbits(int(delta*amplification))
    dp = getrandbits(int((beta-delta) * amplification))
    if (dp-dq) % gcd(p-1, q-1) != 0:
        continue
    d = ((inverse((p-1)//gcd(p-1, q-1), (q-1)//gcd(p-1, q-1)) * (dq-dp)//gcd(p-1, q-1)) % ((q-1)//gcd(p-1, q-1))) * (p-1) + dp
    if gcd(d, (p-1)*(q-1)) == 1:
        break

e = inverse(d, (p-1)*(q-1))
m = bytes_to_long(flag.encode())
c = pow(m, e, N)
print('N =', N)
print('e =', e)
print('c =', c)

'''
N = 7194944829894746935571965271122989443610702698015123026500274312320541540511952275333536082176132102091625202863345739074691901574020649953130369453360247690506566827078013306825941200018330639608298539682191482947557146237487451707849833303794107411686130468587672820352641436722348277258977791778239539008852841749667581869688275892813664557078043533743669277649148468667399393518112220602616186358353262921270486781426670131125521444335280904901224934061164334131460273779473387748722008412594372005590209919098686472153912130124772089012962023984089123929555594332030502775588070235834837667605812843128059372243
e = 5872666789397408936685003821802975734744078884385553897196686533187747297681714766542317071546532454504513425295170366015384657690105523240363850101369048640430719519784564240908244756652800934680608667950183962226340288720771217107508516125044088043789281574833079766048266075717484676158307477384862873719462770774288252074344824446884295300603035728339571606659365040029505127532956295163195257002051007447197735267997104725561159289832252522298457628452222155625714679911912616173849423059919537353814530280736653541415686756485413316581322357887750268983241858913704388088485132644523120028234659344174431547087
c = 6601667269134560091452287214083525217696007424340765571114688738279264700361513951309195757650152324371826111195352731779137577044473630747863137747356695892337017953751159248388157498368915463745769509485009626774902347006319659852239932231921393353157319713540010424345134411781723171111939891127671029064626426950125001347122070491553845919803891156107693973027238705710354919725550360159383455222982999904576805089837067774838194257113022653159325313574447189639317397889065351340828031907571541750274329094240472180870714728295651611160552345500801797030280900507979459558944006193012524181456837126192865748097
'''

May2002_Chapter_CryptanalysisOfUnbalancedRSAWi 这篇paper介绍了针对dp过小并且p,q相差过大的情况下对rsa的一种攻击方法, 具体的原理可以看这篇论文, 这边就简单的说一下条件

要使用这个攻击方法必须满足两个条件
越小越好吧具体的界我也没看明白
这个方法利用了一个定理

(Howgrave-Graham) Let f (x, y) be a polynomial that is a sum of at most ω monomial. Suppose f (x0, y 0) = 0 mod pm for some positive integer m, where |x0| ≤ X and |y0| ≤ Y . If || f (xX, yY )|| < pm √ω , then f (x0, y 0) = 0 holds over the integers.

是一个最大w阶的多项式, 假设存在,对于一些正整数m有, 如果, 那么在整数上成立, 垃圾翻译 大概就是这个意思

构造格

其中

这个格子每一行都是的倍数, 所以最后组成的最短行向量中的替换成, 得到的方程的根就是,这个方程的根.

所以直接规约格基, 把最短向量中的都除掉, 利用得到的系数重新构造一个整数上的方程, 最后因式分解找到一次的项的系数就是

exp

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from sage.all import *
from Crypto.Util.number import long_to_bytes
N = 7194944829894746935571965271122989443610702698015123026500274312320541540511952275333536082176132102091625202863345739074691901574020649953130369453360247690506566827078013306825941200018330639608298539682191482947557146237487451707849833303794107411686130468587672820352641436722348277258977791778239539008852841749667581869688275892813664557078043533743669277649148468667399393518112220602616186358353262921270486781426670131125521444335280904901224934061164334131460273779473387748722008412594372005590209919098686472153912130124772089012962023984089123929555594332030502775588070235834837667605812843128059372243
e = 5872666789397408936685003821802975734744078884385553897196686533187747297681714766542317071546532454504513425295170366015384657690105523240363850101369048640430719519784564240908244756652800934680608667950183962226340288720771217107508516125044088043789281574833079766048266075717484676158307477384862873719462770774288252074344824446884295300603035728339571606659365040029505127532956295163195257002051007447197735267997104725561159289832252522298457628452222155625714679911912616173849423059919537353814530280736653541415686756485413316581322357887750268983241858913704388088485132644523120028234659344174431547087
c = 6601667269134560091452287214083525217696007424340765571114688738279264700361513951309195757650152324371826111195352731779137577044473630747863137747356695892337017953751159248388157498368915463745769509485009626774902347006319659852239932231921393353157319713540010424345134411781723171111939891127671029064626426950125001347122070491553845919803891156107693973027238705710354919725550360159383455222982999904576805089837067774838194257113022653159325313574447189639317397889065351340828031907571541750274329094240472180870714728295651611160552345500801797030280900507979459558944006193012524181456837126192865748097

beta = 0.34
delta = 0.02
amplification = 2048

X = int(N ** delta)
Y = int(N ** (delta + beta))

M = Matrix(
    [
        [N ** 2 * X ** 3, 0, 0, 0],
        [e * N * X ** 3, -N * X ** 2 * Y, 0, 0],
        [e ** 2 * X ** 3, -2 * e * X ** 2 * Y, X * Y ** 2, 0],
        [e ** 3 * X ** 3, -3 * e ** 2 * X ** 2 * Y, 3 * e * X * Y ** 2, -(Y ** 3)],
    ]
)
L = M.LLL()[0]
x,y = var('x'),var('y')
f = x ** 3*(L[0] // X ** 3) + x ** 2 * y * (L[1] // X**2 // Y)+ x * y ** 2 * (L[2] // X // Y ** 2)+ y ** 3 * (L[3] // Y** 3)
print(f.factor())

'''
(144242809483056840663075735623298553029680437297789965222541248349475437890222709450048997656976387390752105996145725490546933534602744908786700426835710727511955799912350818546609860818884274334936799981304721460528637717*x + 636751972323*y)
'''

dp = 636751972323
k = 144242809483056840663075735623298553029680437297789965222541248349475437890222709450048997656976387390752105996145725490546933534602744908786700426835710727511955799912350818546609860818884274334936799981304721460528637717 + 1

assert (e * dp - 1 ) % k == 0
p = (e * dp - 1 ) // k + 1
assert N % p == 0
q = N // p
phi = (p - 1) * (q - 1)
d = inverse_mod(e,phi)
print(long_to_bytes(pow(c,d,N)))