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]