0xGameDiv2

0xGame Div 2 题解

About

第二周，难度比第一周大好多，只切了两道密码题，到极限了，然后只有3800多分，Top1，2两个全栈大佬都有9000+分，我果然好菜啊

Crypto

1.SmallModulus

提示：做这道题的时候！手速！一定要快！一定要快！一定要快！！！！！，无论是输4位验证码还是输入提示中的1！！！我TM因为手速太慢导致远程连接超时，整个下午都耗费在上面了，忍不住吐槽两句，太草了！

虽然我不知道sha256是个什么东西，原理是什么，不过我还是用一个python脚本，四重循环枚举出了每次需要输入的验证码内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from hashlib import sha256
s="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
t="5d755ec7addaff634907855979bc02d0c279ab60ce736754faa895a81938b3c9"
R="EsHH8BQQsfIMp7gC"
assert len(R)==16
assert len(t)==64
for i1 in s:
    for i2 in s:
        for i3 in s:
            for i4 in s:
                XXXX=i1+i2+i3+i4
                if sha256((XXXX+R).encode()).hexdigest()==t:
                    print (XXXX)

最终我还是手速加快，迅速地得到了许许多多组数据… …，其中一组输出提示：flag mod 9c7f17669e90b219 (in hex) : 3316d33a70b0a941。

加上程序的核心代码可知，输出提示mod后买你的那个数字是质数

1
2
3
4
5
if choice == b"1":
                module = getPrime(64)
                self.send(("flag mod {} (in hex) : {}".format(
                    hex(module)[2:], hex(m % module)[2:])).encode())
                continue

显然，这道题想告诉你的消息无非是许多组类似：$x \equiv a_i \mod m_i$ ，(其中$m$为质数)。根据我这个密码学废物和oi废物的理解，这道题应该是考中国剩余定理（CRT）。

查了一下，百度百科上是这样讲解CRT的：

设$M=\prod_{i=1}^n m_i$，$M_i=M/m_i$，$t_i$为$M_i$模$m_i$的逆元，也就是$M_it_i \equiv 1 \mod m_i$。则$x \equiv \sum_{i=1}^{n} a_it_iM_i \mod M$。也就是$x = \sum_{i=1}^{n}a_it_iM_i +k M$

所以，我们只需要处理一下得到的数据，然后将其放入数组$a$和$m$中。还要用到求逆元的代码(直接从上一个脚本直接移植过来的)。

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
from Crypto.Util.number import *
from MsandAs import m,a
def EX_GCD(a,b,arr): #扩展欧几里得
    if b == 0:
        arr[0] = 1
        arr[1] = 0
        return a
    g = EX_GCD(b, a % b, arr)
    t = arr[0]
    arr[0] = arr[1]
    arr[1] = t - (a // b) * arr[1]
    return g
def ModReverse(a,n): #ax=1(mod n) 求a模n的乘法逆x
    arr = [0,1,]
    gcd = EX_GCD(a,n,arr)
    if gcd == 1:
        return (arr[0] % n + n) % n
    else:
        return -1
arr = [0,1,]

# FUNCTION MAIN#
piM=1
for i in range(40):
    piM*=m[i]
print(piM)
t =[0 for _ in range(40)]
M =[0 for _ in range(40)]
for i in range(40):
    M[i]=piM//m[i]
for i in range(40):
    t[i]=ModReverse(M[i],m[i])
B=0 #B为所有atM之积的和
for i in range(40):
    B+=a[i]*t[i]*M[i]
B%=piM
print(B)
print(long_to_bytes(B))

最后的long_to_bytes(B)算出来的就是答案了。

2021.3.9更新

CRT只能解决模数互素的情况，而模数不互素的情况下可以使用exCRT，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
def LCM(a,b):
    return a*b//GCD(a,b)
def exgcd(a,b):
    if not b:
        return 1,0
    x,y=exgcd(b,a%b)
    return y,x-y*(a//b)
#Main Below
m=[11,25,33]
a=[6,9,17]
r1,m1=a[0],m[0]
for i in range(1,len(m)):
    r2,m2=a[i],m[i]
    d=GCD(m1,m2)
    l1,l2=exgcd(m1//d,m2//d)
    r1,m1=(r1+(r2-r1)//d*l1*m1)%LCM(m1,m2),LCM(m1,m2)
print(r1)
#809
'''
809%11==6
809%25==9
809%33==17
'''

2.parityOracle

这道题需要用到Pwntools，也就意味着需要安装虚拟机。本fw安装一个虚拟机安装了三天，太废了。

我们先了解以下Pwntools在密码学题目里面抓包时需要用到的几个指令：

1
2
3
4
5
6
7
8
9
10
11
本地 ：sh = porcess("./level0")
远程：sh = remote("127.0.0.1",10001)
关闭连接：sh.close()  
sh.send(data)  #发送数据
sh.sendline(data)  #发送一行数据，相当于在数据后面加\n
sh.recv(numb = 2048, timeout = dufault) # 接受数据，numb指定接收的字节，timeout指定超时
sh.recvline(keepends=True)  #接受一行数据，keepends为是否保留行尾的\n
sh.recvuntil("Hello,World\n",drop=fasle)#  接受数据直到我们设置的标志出现
sh.recvall() # 一直接收直到EOF
sh.recvrepeat(timeout = default) # 持续接受直到EOF或timeout
sh.interactive() # 直接进行交互，相当于回到shell的模式，在取得shell之后使用

然后再看一下题目程序中的给出的最核心的代码

1
2
3
4
5
6
if choice == b"1":
                cip = self.recvhex(prompt=b"Your cipher (in hex): ")
                if not cip:
                    break
                result = pow(cip, self.d, self.n) % 4
                self.send(hex(result)[2:].encode())

查阅CTFWIKI上的资料可以知道，我们第$k$次发送只需要向服务器发送数值$C×2^{pk} \mod N$即可。不过需要注意的是要把$10$进制数字转化为$16$进制的字符串发送（不含前缀0x），并且每次向服务器发送的所有内容要转换成bytes类型(包括指令1)。

每次截取字符串的时候可以通过输入看看截取到字符串的是什么东西，然后根据字符串的下标关系（这个要在调试的时候自己数）选择自己需要的部分并保存。某些地方也可以自己加一点输出提示看看程序是否在运行。当然，为了确保自己抓到的内容正确，也可以加几个assert语句试试看看是否出现了报错。

初始化工作做好之后，我们就可以开始进行二分过程了。根据CTFWIKI上的提示：设$L,R$为二分的两端(初始值为$L=0,R=N$)。.然后每次取$M$=$(L+R)/2$。如果得到的数字是奇数。那么我们我们下一次截取$(M,R)$区间继续二分。如果得到的数字是偶数，那么我们截取$(L,M)$区间进行二分。由于CTFWIKI上对这一块的原理进行了详细讲述，故此处不多赘述。

最后，我们可以用下面的脚本来进行二分操作。（前面抓取验证码的程序与上一题的验证码程序一模一样）

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 pwn import *
from hashlib import sha256
from Crypto.Util.number import *
def getyanzhengma(s16len,s64len):
	LTSNMS="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
	assert len(s16len)==16 and len(s64len)==64
	for i1 in LTSNMS:
		for i2 in LTSNMS:
			for i3 in LTSNMS:
				for i4 in LTSNMS:
					if sha256((i1+i2+i3+i4+s16len).encode()).hexdigest()==s64len:
						return i1+i2+i3+i4
sh=remote("49.235.239.97",10001)
while(True):
	str1=sh.recvline(keepends=False)
	if(str1[0:6]=="sha256"):
		break
yanzhengma=(getyanzhengma(str1[12:28],str1[33:97]))
sh.send(yanzhengma)
print("[NOTE]SENT YANZHENGMA")
e,n,c=1,1,1
str2=sh.recvline(keepends=False)
e=str2[18:]
str2=sh.recvline(keepends=False)
n=str2[4:]
str2=sh.recvline(keepends=False)
c=str2[4:]
e,n,c=int(e),int(n),int(c)
print("[NOTE]F=GOT enc")
L,R,Clk=0,n,1
while L<=R:
	if(Clk%50==0):
		print(L,R,Clk)
	M=(L+R)//2
	for i in range(3):
		str3=sh.recvline(keepends=False)
	sh.send(b"1")
	a=(c*pow(2,e*Clk,n))%n
	sh.send(str(hex(a))[2:].encode())
	recnum=sh.recvline(keepends=False)
	recnum=int(recnum[-1])
	if recnum==1 or recnum==3:
		L=M+1
	if recnum==0 or recnum==2:
		R=M-1
	Clk+=1
print(L)
print(long_to_bytes(L))

注意：每次程序跑的时候会存在一定误差,不过一般不超过$100$，这就意味着解出来的字符串的最后$1$到$2$位可能会不对。不过我们可以根据最后一个字符是否成词，或者根据题目中的提示，也可以解出来最后的flag

CTFSeason1
#WriteUp
0xGameDiv2
http://example.com/2020/10/16/0xGameDiv2/
作者
huangx607087
发布于
2020年10月16日
许可协议