GKCTF2021 WriteUp


GKCTF WriteUp By huangx607087

0.About

6月22日的GKCTF,由于忙于期末考试直接摸了,20天后回来复现来了。好在自己期末每门课都过了,死而无憾。

自己6月初申请留任了校科协和院科协,看来以后不能再摸鱼了。并且如果CTF和平时文化课双开的话,应该难度并不小,不过希望自己可以做到

1.[GKCTF 2021]Random

通过观察题目代码可以知道,又是一道典型的MT19937预测随机数的题目

1
2
3
4
5
6
7
8
9
10
11
12
import random
from hashlib import md5
def get_mask():
file = open("random.txt","w")
for i in range(104):
file.write(str(random.getrandbits(32))+"\n")
file.write(str(random.getrandbits(64))+"\n")
file.write(str(random.getrandbits(96))+"\n")
file.close()
get_mask()
flag = md5(str(random.getrandbits(32)).encode()).hexdigest()
print(flag)

题目一次给出了$104$组数字,每组数字由$32$位、$64$位、$96$位的二进制数各一个。每一组等价于$6$组$32$位二进制数,总共$624$组$32$位二进制数,因此可以进行预测。

不过这里要注意一下预测的顺序,设一次给出的分别是$^{32}A,^{64}B,^{96}C$,那么我们预测顺序应该是:$^{32}A_{[31,0]}$,$^{64}B_{[31,0]}$,$^{64}B_{[63,32]}$,$^{96}C_{[31,0]}$,$^{96}C_{[63,32]}$,$^{96}C_{[95,64]}$,其中$^{64}B_{[31,0]}$表示$B$一共有$64$位,取其代表着$2^{31}$到$2^{0}$的比特位。

我们可以导入上一个博客我们探究出来的包。将其命名为MT19937tools放入我们的解题文件夹中,通过import到我们的解题脚本中来即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from hashlib import md5
from MT19937tools import *
f=open("random.txt","r")
S=[]
for i in range(104):
a32=int(f.readline())
a64=int(f.readline())
a96=int(f.readline())
S.append(a32)
S.append(a64&0xffffffff)
S.append(a64>>32)
S.append(a96&0xffffffff)
S.append((a96>>32)&0xffffffff)
S.append(a96>>64)
f.close()
D=MT19937(0)
flag= md5(str(D.predict(S)).encode()).hexdigest()
print(flag)
#14c71fec812b754b2061a35a4f6d8421

2.[GKCTF 2021]RRRRsa

Step 1 初步审题

按照惯例先看一下题目代码,然后将题目后面给出来的所有数据放入given.py文件中

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
from Crypto.Util.number import *
from gmpy2 import gcd
flag = b'xxxxxxxxxxxxx'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p*q
e = 65537
c = pow(m,e,n)
print('c={}'.format(c))
p1 = getPrime(512)
q1 = getPrime(512)
n1 = p1*q1
e1 = 65537
assert gcd(e1,(p1-1)*(q1-1)) == 1
c1 = pow(p,e1,n1)
print('n1={}'.format(n1))
print('c1={}'.format(c1))
hint1 = pow(2020 * p1 + q1, 202020, n1)
hint2 = pow(2021 * p1 + 212121, q1, n1)
print('hint1={}'.format(hint1))
print('hint2={}'.format(hint2))
p2 = getPrime(512)
q2 = getPrime(512)
n2 = p2*q2
e2 = 65537
assert gcd(e1,(p2-1)*(q2-1)) == 1
c2 = pow(q,e2,n2)
hint3 = pow(2020 * p2 + 2021 * q2, 202020, n2)
hint4 = pow(2021 * p2 + 2020 * q2, 212121, n2)
print('n2={}'.format(n2))
print('c2={}'.format(c2))
print('hint3={}'.format(hint3))
print('hint4={}'.format(hint4))

可以看出整个过程中先加密了$\mathrm {flag}$,然后对加密$\mathrm{flag}$的$p,q$进行了二次加密。对于第一组式子我们可以得到:
$$
h_1\equiv (2020p_1+q_1)^{202020} \pmod{n_1}
$$

$$
h_2\equiv (2021p_1+212121)^{q_1} \pmod {n_1}
$$

同时我们可以根据代码提炼出第二组式子:
$$
h_3\equiv (2020p_2+2021q_2)^{202020} \pmod{n_2}
$$

$$
h_4\equiv (2021p_2+2020q_2)^{212121} \pmod {n_2}
$$

鉴于第二组式子略微简单一点,我们先化简第二组式子

Step 2 第二组式子的化简

对于第二组式子:
$$
h_3\equiv (2020p_2+2021q_2)^{202020} \pmod{n_2}
$$

$$
h_4\equiv (2021p_2+2020q_2)^{212121} \pmod {n_2}
$$

根据二项式定理,加上$n_2=p_2q_2$,对这两个式子展开,由于中间项全没有了,我们可以得到:
$$
h_3\equiv 2020^{202020}p_2^{202020} + 2021^{202020} q_2^{202020}\pmod{n_2}
$$

$$
h_4\equiv 2021^{212121}p_2^{212121}+2020^{212121}q_2^{212121}\pmod{n_2}
$$

设$t=202020×212121$,那么我们也可以得到:
$$
h_3^{212121}\equiv 2020^tp_2^t+2021^tq_2^t\pmod{n_2}
$$

$$
h_4^{202020}\equiv 2021^tp_2^t +2020^tq_2^t\pmod{n_2}
$$

然后我们可以继续得到
$$
2021^th_3^{212121} \equiv 2020^t2021^tp_2^t+2021^{2t}q_2^t\pmod{n_2}
$$

$$
2020^{t}h_4^{202020}\equiv 2020^t2021^tp_2^t+2020^{2t}q_2^t \pmod{n_2}
$$

两式相减,得
$$
2021^th_3^{212121}-2020^{t}h_4^{202020} \equiv 2021^{2t}q_2^t-2020^{2t}q_2^t=(2021^{2t}-2020^{2t})q_2^t \pmod {n_2}
$$
可以看出这个数字肯定是$q_2$的倍数,将其记为$kq_2$,由于$n_2=p_2q_2$,且$p_2,q_2$均为素数,因此可以得到$\gcd(n,kq_2)=q_2$,进而分解$n_2$,解密后得到$q$。

Step 3 第一组式子的化简

我们再回过来看一下第一组式子:
$$
h_1\equiv (2020p_1+q_1)^{202020} \pmod{n_1}
$$

$$
h_2\equiv (2021p_1+212121)^{q_1} \pmod {n_1}
$$

根据二项式定理,很容易将第一个式子化简
$$
h_1\equiv 2020^{202020}p_1^{202020}+q_1^{202020}\pmod {n_1}
$$
但对于第二个式子,展开化简很显然是不太可能的事情

由于$n_1=p_1q_1$,想到离散对数中的一些内容,很显然,在这里$\mathrm{ord}(p_1) = q_1$,因为$p_1^x \mod n_1$的值只有$q_1$种结果。

1
注:这个结论很好证明,随便搞几个特殊数据试试就出来了

因此,展开式中第一项即为$2021^{q_1}p_1$,但这边还是出现了一个问题,那就是$q_1$总是在指数上,很难去掉。

由于$p$是素数,那么根据费马小定理$a^{p}\equiv a \pmod p$和二项式展开定理,可以得到:
$$
h_2\equiv \sum_{i=0}^{q} \mathrm C_q^{i}2021^ip^i212121^{q-i} \pmod {n_1}
$$
简单化简一下:
$$
h_2\equiv 2021^{q_1}p_1+\sum_{i=0}^{q-1} 212121^{-i}\mathrm C_q^{i}2021^ip^i212121^{q} \pmod {n_1}
$$
干脆别管常数了(
$$
h_2\equiv 2021^{q_1}p_1+\sum_{i=0}^{q-1} K_ip^i212121^{q} \pmod {n_1}
$$
再模一下$q_1$:
$$
H=h_2 \mod q_1 \equiv 2021p_1+212121+Kq_1 \mod q_1 \pmod {n_1}
$$
如果我们减去$212121$,那么$H=2021p_1+Kq_1$,将$H$升高到$202020$次方,然后再用Step2中一样的方法消元,就可以得到$kq_1$,然后与$n_1$求GCD就出结果了。

Step 4 解题代码

根据上面的分析,不难写出解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from given import *
l=202020*212121
H3,H4=pow(hint3,212121,n2),pow(hint4,202020,n2)
HH3,HH4=pow(2021,l,n2)*H3%n2,pow(2020,l,n2)*H4%n2
kq2=HH4-HH3
q2=GCD(kq2,n2)
p2=n2//q2
assert isPrime(p2) and isPrime(q2)
Q=pow(c2,inverse(e2,(p2-1)*(q2-1)),n2)
assert isPrime(Q)
t=pow(hint2-212121,202020,n1)
HH1=pow(2021,202020,n1)*hint1%n1
HH2=pow(2020,202020,n1)*t%n1
kq1=abs(HH1-HH2)
q1=GCD(kq1,n1)
p1=n1//q1
assert isPrime(p1) and isPrime(q1)
P=pow(c1,inverse(e1,(p1-1)*(q1-1)),n1)
assert isPrime(P)
flag=long_to_bytes(pow(c,inverse(e,(P-1)*(Q-1)),P*Q))
print(flag)
#GKCTF{f64310b5-d5e6-45cb-ae69-c86600cdf8d8}

3.[GKCTF 2021]XOR

看一下题目的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from hashlib import md5
a = getPrime(512)
b = getPrime(512)
c = getPrime(512)
d = getPrime(512)
d1 = int(bin(d)[2:][::-1] , 2)
n1 = a*b
x1 = a^b
n2 = c*d
x2 = c^d1
flag = md5(str(a+b+c+d).encode()).hexdigest()
print("n1 =",n1)
print("x1 =",x1)
print("n2 =",n2)
print("x2 =",x2)

题目给出了$a$和$b$的乘积、$a$和$b$异或后的值、$c$和$d$的乘积和$c$和$d’$异或的值。

对于第一个问情况,我们只需要不断枚举它的每一位就可以了。不过注意一下这样一个同余的性质:不论在几进制下,如果已知$A,B$两个数的最后$n$位,那么它们的乘积的最后$n$位我们也会知道了。

例如:

$9×7=63$,$53370$$9$$×18826$$7$$=10047979230$$3$

$5193×8326=43236918$,$8173$$5193$$×6327$$8326$$=517206618832$$6918$

十六进制这种情况也同样存在:

$\mathrm{7ABH×96FH=485625H}$,$8733$$\mathrm{7AB}$$\mathrm {H×62CE}$$\mathrm{96F}$$\mathrm{H=342ED01B03C}$$\mathrm{625}$$\mathrm H$

因此,我们只需要对于第一种情况直接枚举即可。

而第二种情况再之前的XDCTF中,脚本见5月17日发布的21May1中的第三题,不过这里对于三个剪枝条件我再阐述一下:

一:不同余的时候剪枝,这个我刚刚讲过,实现代码如下

1
2
if(CurP*CurQ)%(2**(Round+1))!=n%(2**(Round+1)):
continue

二:最小值情况下总数过大,超过了$n$(定上界)

由于我们是高位低位两头双面夹击,不断补充比特位的,因此在枚举一开始的时候,中间所有的比特位都是$0$。也就是此时枚举时$P,Q$的值都是小于真值的。因此如果此时乘积超过$n$,就说明某个数的高位定大了,需要返回重新定值。实现代码如下

1
2
if CurP*CurQ>n:
continue

三:最大值情况下总数过小,无法到达$n$。(定下界)

有一个很好的办法是把中间所有的未确认的比特位全填充成$1$,这种方法也是可行的,但或许会比较麻烦(

根据第二条中的理论,这个时候我们可以给枚举的数字定个下界。由于我们第$\mathrm {Round}$的轮定下的高位是代表着$2^{511-\mathrm{Round}}$的值,这个时候我们可以给这一位强行$+1$,也就是原本的$0$变$1$,原本的$1$变$2$(进到下一位),如果此时两数的乘积还不到$n$,就说明我们的两个数字确定得小了,需要枚举更大的比特位了。实现代码如下

1
2
if(CurP+2**(511-Round))*((CurQ+2**(511-Round)))<n: 
continue

最后上一下完整的解题代码:

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
49
from Crypto.Util.number import *
from hashlib import md5
from given import *
bina=bin(x2)[2:]
bina='0'*(512-len(bina))+bina
binb=bin(x1)[2:]
binb='0'*(512-len(binb))+binb
def dfs2(P,Q,n,Round):
if Round==256:
if P*Q==n:
global c,d
c,d=P,Q
return 1
for i in range(2):
for j in range(2):
CurP=P+i*(2**(511-Round))+(int(bina[Round])^j)*(2**Round)
CurQ=Q+j*(2**(511-Round))+(int(bina[511-Round])^i)*(2**Round)
if CurP*CurQ>n:
continue
if(CurP+2**(511-Round))*((CurQ+2**(511-Round)))<n:
continue
if(CurP*CurQ)%(2**(Round+1))!=n%(2**(Round+1)):
continue
dfs2(CurP,CurQ,n,Round+1)
return 0
def dfs1(P,Q,n,Round):
if Round>512:
return
if Round==512:
if P*Q==n:
global a,b
a,b=P,Q
return 1
for i in range(2):
CurP=(i<<Round)+P
CurQ=((i^int(binb[511-Round]))<<Round)+Q
if(CurP*CurQ%(2**(Round))!=n%(2**(Round))):
continue
dfs1(CurP,CurQ,n,Round+1)
return 0
#----MAIN BELOW----#
a,b,c,d=None,None,None,None
dfs2(0,0,n2,0)
assert isPrime(c) and isPrime(d)
dfs1(0,0,n1,0)
assert isPrime(a) and isPrime(b)
flag = "GKCTF{"+md5(str(a+b+c+d).encode()).hexdigest()+"}"
print(flag)
#GKCTF{f28ed218415356b4336e2f778f2981bb}

4.总结

暑假放假回家第一篇复现的wp,总体感觉好久没做过CTF水平下降了很多的样子(


文章作者: huangx607087
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 huangx607087 !
  目录