0xGameDiv3

0xGame Div 3 题解

About

第三周，密码学难度还可以，前2题难度不大，第3题难度有点大，不过还是能够用一天的时间切出来了。不过第三周结束还没有到达到7000分，第一周就有很多全栈大佬7000了，我还没他们1/3的效率高。看来奖励拿不到了。。

Crypto

1. signinRSA

这道题看到时签到题，读了一下代码，这跟上一周的parityOracle竟然有$99$%的相似。

不多说，直接复制上周写好的脚本 ,改一下nc地址，把上周脚本的倒数第$8$行的recnum=int(recnum[-1])改为recnum=int(recnum[-1],16)，然后把倒数第$7$行和倒数第$5$行的对recnum的判断加上%$4$操作（如下），直接运行，几分钟就出结果了。

1
2
3
4
if recnum%4==1 or recnum%4==3:
	L=M+1
if recnum%4==0 or recnum%4==2:
	R=M-1

2.easyRSA

先看一下题目的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag.encode())
e = 65537
p, q = getPrime(1024), getPrime(1024)
d = inverse(e, (p-1)*(q-1))
x = 11*d+7*(p-1)*(q-1)
c = pow(m, e, p*q)

print("n =", p*q)
print("c =", c)
print("x =", x)
## 给出部分略

题目给出了$n,c,x$的值（当然也有$e=65537$），其中$x=11d+7\phi$ ，所以这道题不同寻常之处就是给出了$x$,故突破口在x处。

通过之前RSA中相关知识可知：$d$ 是$e$在模$\phi$意义下的乘法逆元，也就是$ed \equiv 1 \mod \phi$ 。而由于$p,q$均为质数，所以$\phi=(p-1)(q-1)$

既然题目给出$x=11d+7phi$ ，而$d,phi$均为未知量。所以根据方程校园思想，我们可以两边同乘$d$，得到$ex=11de+7e \phi$ 。这个式子对$\phi$取模之后，我们可以得到$ex \equiv 11 \mod \phi$，这时候这个式子仅剩下一个未知数，所以我们可以提出$\phi$ ，得到$k\phi=ex-11$

在$\phi=(p-1)(q-1)=pq-p-q+1=n-p-q+1$，由于$p,q$均为$1024$位，$n$为$2047$位，远远大于$p+q$。故$\phi$的二进制位数跟$n$应该基本是一样的，计算可知，$phi$是$2068$位，所以$k$应当是$21$位或者$22$位，也就是$k∈[2^{21},2^{22})$。

我们用以下脚本枚举$k$，然后直接进行long_to_bytes 的操作，虽然有大概$50$多组解，然而最像flag的只有一组，故我们就得到了flag。

1
2
3
4
5
6
7
8
9
10
11
12
from given import n,x,e,c
from Crypto.Util.number import *
def solve(T):
    tot=0
    for i in range(2**20,2**22):
        if T%i==0 and T//i%2^1 :
            P=T//i
            d=inverse(e,P)
            print(long_to_bytes(pow(c,d,n)))
T=e*x-11
solve(T)

3. paddingOracle

又是一道Oracle，想到上一条Oracle我搞了好久= =。果然，上题12小时，还没人做出来。上题18小时后，才有人拿一血。我就比较逊了。上题35小时才把2血拿到。感觉后面密码学题目会越来越难的样子，awsl

简单地看了一下相关资料，然而本人太菜，连书都看不懂，最后摸索了12小时才搞懂题目意思，就让我用简洁的语言讲一下这道题的意思吧

首先，服务器会给你一个长度为$32$位的$16$进制数为初始向量，然后再给你$32k$个$16$进制数为密文（本题中$k=3$，也就是一共$96$位）。有些题目它直接给你一个$32(k+1)$位的$16$进制数，这个时候就默认最前面$32$位为初始向量，后面的$32k$位作为密文。

得到初始向量后，将密文分为$k$组，每组$32$位。记初始向量为$I_0$,后面的密文组为$I_1,I_2,I_3,…,I_k$

这个时候，我们还需要$3$个$16$位数组：$Clc$、$Tlc$和$Alc$，分别用于存储每一次解密的枚举值、中间值和破解出来的明文

第一轮枚举，我们枚举$Clc$最后一个数字也就是$Clc_{15}$，当服务器返回success时，计算$Tlc_{15}=Clc_{15}$xor$1$的值，然后轮数进入第二轮，用$Tlc_{15}$更新$Clc_{15}$,也就是$Clc_{15}=Tlc_{15}$ xor $2$。

需要注意的是：第$p$轮枚举，我们枚举的值是$Clc_{16-p}$,用$Clc_{16-p}$更新$Tlc_{16-p}$为$Clc_{16-p}$ xor $p$，然后轮数进入$p+1$，这时我们需要用$Tlc_{16-p}$及其以后所有解出来的$Tlc$去改变所有已知的$Clc$值，也就是把后面所有的$Clc$改为 $Tlc$ xor $p+1$**。换句话讲就是说$Tlc$解出来之后永远不能变，$Clc$每一次解出来以后会被不断更新。$Clc$更新$Tlc$,只更新最新解出来的一位，$Tlc$更新$Clc$，需要更新解出来的所有$Clc$内容**

上面的解释可能比较抽象，那我就用下面的例子来解释一下吧(数字下标$h$表示$16$进制，也就是$14_h$的真实值为十进制的$20$：

Round 0

初始状态：

$Clc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00]_h$

$Tlc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00]_h$

Round 1(枚举 $Clc_{15}$ )

第$1$轮，我们枚举$Clc_{15}$的值，假设我们枚举到$Clc_{15}=78_h$的时候服务器发回Success

那么此时：$Clc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$78$]$_h$

用$Clc_{15}$更新$Tlc_{15}$，$Tlc_{15}=Clc_{15}$ xor $1$（轮数）$=79_h$

$Tlc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$79$]$_h$

Round 2(枚举$Clc_{14}$ )

然后进入第$2$轮，我们首先得更新一下$Clc_{15}$的值为$Tlc_{15}$ xor $2=7B_h$

此时$Clc$发生了变化：$Clc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$7B$]$_h$

然后我们枚举$Clc_{14}$的值，假如我们枚举到$Clc_{14}=52_h$时服务器返回Success

那么此时：$Clc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$52$$,7B]_h$

用$Clc_{14}$更新$Tlc_{14}$，$Tlc_{14}=Clc_{14}$ xor $2$（轮数）$=50_h$

此时的$Tlc$：$Tlc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$50$$,79]_h$

Round 3(枚举$Clc_{13}$)

进入第$3$轮，此时一个易错点（敲黑板）出现了：由于此时已经出来了$Clc_{14}$和$Clc_{15}$，第$3$轮异或值为$3$，所以我们要对$Clc_{14}$和$Clc_{15}$都进行异或$3$的操作

此时：$Clc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$53,78$$]_h$,两位都进行了更新

所以以上操作就是我们所讲的：$Clc$更新$Tlc$ 只更新这次解出来的一位，而$Tlc$更新$Clc$，需要更新$Clc$中已经解出来的所有$Clc$值

$16$个$Tlc$解出来后，本轮$Alc$就等于$Tlc$ xor $I_{m-1}$($m$为第$m$解密)。然后重新初始化，进行下一大轮的解密。$k$轮解密结束，我们就得到了所有的明文了（注意过滤掉里面的无关字符）

这个该死的脚本写了我98行，7个子函数。还是比较烦人的。因为一开始没规划好导致一会用$16$位数组（每个正数不超过$255$），一会用$32$位数组（每个正数不超过$15$）。虽然写起来简单，但还是减少了代码的可读性，究其原因，只有一个：作为密码学废物的我太菜了

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
from pwn import *
from Crypto.Util.number import *
from hashlib import sha256
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
def Transnbs(s):
	T=[0 for _ in range(16)]
	for i in range(16):
		T[i]=int(s[2*i:2*i+2],16)
	return T
def Transstr(x32):
	Cmb=b""
	Qld=b"0123456789abcdef"
	for i in range(32):
		Cmb+=Qld[x32[i]]
	return Cmb
def x32tox16(x32):
	X16=[0 for _ in range(16)]
	for i in range(16):
		X16[i]=x32[2*i]*16+x32[2*i+1]
	return X16
def x16tox32(x16):
	X32=[0 for _ in range(32)]
	for i in range(16):
		X32[2*i]=x16[i]//16
		X32[2*i+1]=x16[i]%16
	return X32
def findtwonum(x32,loc,sender,Strcchp):
	print("You are entered")
	S32=x32
	for i in range(256):
		S32[2*loc]=i//16
		S32[2*loc+1]=i%16
		Te=Transstr(x32)
		for j in range(3):
			Info1=sender.recvline(keepends=False)
		Info1=sender.recv(numb=44,timeout=20000)
		sender.send(b"1")
		Info1=sender.recv(numb=44,timeout=20000)
		sender.send(Te)
		Info1=sender.recv(numb=44,timeout=20000)
		sender.send(Strcchp)
		assert len(Te)==32 and len(Strcchp)==32
		R=sender.recvline(keepends=False)
		if(R[:4]=="succ"):
			return S32
def Decrypt1(iiv,cchp,Strcchp,sender):
	Cel=[0 for _ in range(32)]
	Tlc=[0 for _ in range(16)]
	Alc=[0 for _ in range(16)]
	cnt,Rnd=15,1
	while(cnt+1):
		Cel=findtwonum(Cel,cnt,sender,Strcchp)
		Clc=x32tox16(Cel)
		Tlc[16-Rnd]=Rnd^Clc[16-Rnd]	
		print('Tlc=',Tlc)
		Rnd+=1
		cnt-=1
		for i in range(Rnd-1):
			Clc[15-i]=Tlc[15-i]^Rnd
		print('Tlc xor',Rnd,'=', Clc)
		Cel=x16tox32(Clc)
		print(Transstr(Cel))
	for i in range(16):
		Alc[i]=iiv[i]^Tlc[i]
	return Alc
#--------MAIN BELOW---------#
sh=remote("49.235.239.97",10003)
while True:
	str1=sh.recvline(keepends=False)
	print(str1)
	if(str1[0:6]=="sha256"):
		break
yanzhengma=(getyanzhengma(str1[12:28],str1[33:97]))
sh.send(yanzhengma)
print("[NOTE]SENT YANZHENGMA")
str1=sh.recvline(keepends=False)
iv=str1[19:]
str1=sh.recvline(keepends=False)
print(str1)
y=str1[12:]
BA,BB,BC=y[0:32],y[32:64],y[64:96]
I,A,B,C=Transnbs(iv),Transnbs(BA),Transnbs(BB),Transnbs(BC)
Ans=Decrypt1(I,A,BA,sh)
print ('Ans=',Ans)
Bns=Decrypt1(A,B,BB,sh)
print ('Bns=',Bns)
Cns=Decrypt1(B,C,BC,sh)
print ('Cns=',Cns)
print(Ans,Bns,Cns)
#[48, 120, 71, 97, 109, 101, 123, 55, 48, 54, 52, 97, 98, 52, 56, 45]
#[51, 99, 53, 102, 45, 52, 50, 99, 49, 45, 97, 100, 51, 51, 45, 54]
#[99, 101, 98, 101, 98, 98, 102, 101, 101, 57, 101, 125, 4, 4, 4, 4]

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