GKCTF2021 WriteUp

GKCTF WriteUp By huangx607087

0.About

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

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

1.[GKCTF 2021]Random

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

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到我们的解题脚本中来即可。

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文件中

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$种结果。

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

因此，展开式中第一项即为$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 解题代码

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

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

看一下题目的代码：

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中的第三题，不过这里对于三个剪枝条件我再阐述一下：

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

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

二：最小值情况下总数过大，超过了$n$（定上界）

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

if CurP*CurQ>n:
    continue

三：最大值情况下总数过小，无法到达$n$。（定下界）

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

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

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

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

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水平下降了很多的样子（