0xGameDiv1

0xGame Div 1 题解

About

第一周题目还算比较简单,把密码切了两题,Misc简单看了看。搞了2000多分,很多大佬7000多分,wtcl

Crypto

1.Calendar

根据给的日历图片,THU1表示第一行的星期四对应的日期,同理,TUE2表示第二行的星期二对应的日期,不是这个月第二个星期二对应的日期。纠错方法:有个码是TUE4,如果按照后者进行理解,那么得到的值是$27$。同时题目给了提示为:“明文字母全为小写,请将明文包含在0xGame{}内提交”,说明每个数字不会超过$26$。(因为我一开始就是错误的理解,然后发现了问题)

这个可以直接手打出所有的数字,保存在一个txt文件中,然后用下面的脚本就可以得出flag了

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x;
freopen("1.txt","r",stdin);
while(~scanf("%d",&x))
{
printf("%c",x+96);
}
return 0;
}

2.easyXor

必备常识:已知$a$ xor $ b = c$ ,可以得到$c$ xor $b = a$

下面是题目的Python代码:

1
2
3
4
5
6
7
8
9
10
from random import randint
from secret import flag

flag+="^"
cipher=[]
for i in range(len(flag)-1):
cipher.append(ord(flag[i])^ord(flag[i+1]))
print(cipher)
#[72, 63, 38, 12, 8, 30, 30, 6, 82, 4, 84, 88, 92, 7, 79, 29, 8, 90, 85, 26, 25, 87, 80, 10, 20, 20, 9, 4, 80, 73, 31, 5, 82, 0, 1, 92, 0, 0, 94, 81, 4, 85, 27, 35]

很显然,题目给出了最终的输出,也知道最后增加的一位内容。从最后一位出发,我们可以一个一个回推以前的步骤。

将最后的输出结果复制到一个txt文件中,用替换功能把所有的逗号换成空格,删除无关符号,用以下的C++脚本代码运行即可

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
#include<bits/stdc++.h>
using namespace std;
stack<int>s,r;
int main()
{
freopen("1.txt","r",stdin);
int x;
while(~scanf("%d",&x))
{
s.push(x);
}
int t='^';
while(!s.empty())
{
t=t^s.top();
r.push(t);
s.pop();
}
while(!r.empty())
{
printf("%c",r.top());
r.pop();
}
return 0;
}

3.Superaffine

我们先来看一下程序代码

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
from Crypto.Util.number import *
from string import ascii_letters, digits
from random import randint
from secret import flag

assert flag.startswith("0xGame{") and flag.endswith("}")
table = ascii_letters+digits# 先小写,再大写,再数字
MOD = len(table)#mod = 62

def affine(x, a, b): return a*x+b

def genKey():
a = [randint(1, 64) for _ in range(3)]
b = [randint(1, 64) for _ in range(3)]
while GCD(MOD, a[0]*a[1]*a[2]) != 1:
a = [randint(1, 64) for _ in range(3)]
return a, b


cipher = ""
A, B = genKey()
for i in flag:
if i not in table:
cipher += i
else:
cipher += table[affine(affine(affine(table.find(i),A[0], B[0]), A[1], B[1]), A[2], B[2]) % MOD]

print("cipher =", cipher)
# cipher = t6b7Tn{2GByBZBB-aan2-JRWn-GnZB-Jyf7a722ffnZ}

很显然,这是一个仿射密码,单层加密过程为一个一次函数$y=e(x)\equiv ax+b \mod m$

Python中,ascii_letters对应一个字符串为“abc……xyzABC….XYZ”,digits对应一个字符串为”0123456789”,所以此处有$MOD=62$。

根据defgenkey可知:此处的$a_0,a_1,a_2,b_0,b_1,b_2$均为随机生成的$[1,63]$内的整数,如果暴力枚举,复杂度为$O(63^6)≈625.2亿$。所以暴力是不可以的。

化简加密公式,我们可以得到解密公式$x= d(y)\equiv a^{-1}(y-b)$。所以这里涉及到求逆元。又由于$62$为合数,$phi(62)=30$,也就是只有$30$个字符可以正确地加密并解密,说明本替换密码的密钥空间为$30×62=1860$,并不是很大。

下面我们探讨一下两重仿射密码 $e_1(x)\equiv a_1x+b_1 \mod m$ 和$e_2(x)\equiv a_2x+b_2 \mod m$,所以$e_2(e_1(x))=a_2a_1x+a_2b_1+b_2 \equiv m$,仍然是一个一次函数,还是能够写成$E=Ax+B$的形式,密钥空间不变,仍然是$30×62=1860$。所以得到一个很重要的结论:无论仿射加密有几层,密钥空间总是不变!因为可正常转换的字符数量本来就是有限的。

所以,我们根据推出的公式:$E(x)=a_2a_1a_0x+a_2a_1b_0+a_2b_1+b_2 \mod m$,写成$E(x)\equiv Ax+B \mod m$的形式,并且由于密钥空间不变,$A,B$仍然是$[1,63]$中的整数。所以我们根据代码assert的内容,写出如下的C++脚本

注:C++中不等于a!=b可以写成a-b(很毒瘤的一种写法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int check(int a,int b)
{
if((a*52+b+62*8)%62-19) return 0;
if((a*23+b+62*8)%62-58) return 0;
if((a*32+b+62*8)%62-1) return 0;
if((a*0+b+62*8)%62-59) return 0;
if((a*12+b+62*8)%62-45) return 0;
if((a*4+b+62*8)%62-13) return 0;
return 1;
}
int main()
{
int i,j;
for(i=1;i<=63;i++)
for(j=1;j<=63;j++)
{
if(check(i,j)) printf("A=%d B=%d\n",i,j);
}
return 0;
}
//运行结果:A=35,B=59

$y=E(x)\equiv 35x+59 \mod 62$

然后我们可以用Python的脚本,求出$35$在模$62$的意义下乘法逆元为$39$,脚本如下(下一题用到的也是这个脚本,这个脚本可以求最大公约数和逆元)

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
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,]


a=35,b=62

print("niyuan",ModReverse(a,b))
print('zuidagonyueshu',EX_GCD(a,b,arr))

由于$62-59=3$,所以$59$在模$62$的意义下加法逆元为$3$,所以解密函数为$x=D(y)\equiv 39y+3 \mod 62$

同样,将密文放入一个txt文件,用C++写一个脚本,即可求出明文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const string s="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
int f(int x)
{
return ((x+3)*39)%62;
}
int main()
{
int i,j;
char c;
freopen("tst2002.txt","r",stdin);
while(cin>>c)
{
if((int)(s.find(c))==-1) cout<<c;
else
{
cout<<s[f(s.find(c))] ;
}
}
}

4.equationSet

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

e = 65537
m = bytes_to_long(flag.encode())
p, q, r = getPrime(512), getPrime(512), getPrime(512)

n = p*q*r
c = pow(m, e, n)
print(c)
print(n)
print(p+q+r)
print(p*q+p*r)
# 给出部分略

这是一个简单的RSA变式,三个质数相乘,根据我们得到的线索:有以下3个数据可用:$S=p+q+r$,$n=p×q×r$,$T=p×(q+r)$。

由于$p,q,r$均为质数,我们只需要求$T$和$n$的最大公约数即为$p$的值,然后我们很快就得到以下两个数字:$M_2=q×r$和$T_2=q+r$。

怎么解$q,r$? 换元解二次方程?显然很麻烦!

实际上我们不需要解出来这2个值,因为RSA加密为$c=m^e \mod n$,解密为$m=c^d \mod n$,其中$d$是$e$在模$phi(n)$的逆元,所以我们只需要求$phi(n)$,又因为$p,q,r$均为质数,所以$phi(n)=phi(p)×phi(q)×phi(r)=(p-1)(q-1)(r-1)=(p-1)(M_2-T_2+1)$

然后我们再用上一题的那个脚本解出$d$,进而得到$m$

得到$m$后,来一波long_to_bytes操作就得到了flag。

注:未配置相关环境的话,可以使用进制分解的手段,将$m$分解为$256$进制,然后一位一位逐一转成字符

5.Fibonacci

先放一下题目中最核心的代码,并且题目给出了 $r,n,c,N$ 这 $4$ 个数的值

1
2
3
4
5
6
7
8
9
10
n = reduce(lambda a, b: a*b, [getPrime(4) for _ in range(4)])
r = getRandomNBitInteger(67)
S = sum([F(i) % n for i in range(r)])
p = next_prime(S**16)
q = getPrime(p.bit_length())
m = bytes_to_long(flag)
c = pow(m, 65537, p*q)
N=p*q
#n=34969
#r,c,N数字过大,此处略去

这仍然是个RSA的变式题。首先我们可以看到 $p$ 跟$S$的值是密切相关的。所以我们应当先求出$S = \sum_{i=1}^r (F_i \mod 34969) $的值

根据斐波那契数列的递推公式$F_i=F_{i-1}+F_{i-2}$,其中$F_1=F_2=1$,我们可以知道:如果所有的$F_i$对同一个数取模,这个数列应当是有周期性的,所以我们应当求这个数列的周期。而模数为$34969$,并不是一个很大的数字,所以我们可以估计周期不超过$500万$,用以下的C++脚本确定周期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int n,f[9607087];
int main()
{
int i,j;
f[1]=f[2]=1;
for(i=3;i<=5000000;i++)
{
f[i]=(f[i-1]+f[i-2])%34969;
if(f[i]==f[i-1]&&f[i]==1) printf("%d\n",i-1);
}
return 0;
}

由于输出的第一个数字为$33661$,说明$f_{33661}=f_{33662}=1$,确定周期为$33660$,这样我们可以求出一个周期内的数字之和$S_T = \sum_{i=1}^{33660} (F_i \mod 34969)$。

然后,我们在python中计算r//33660r%33660的值,然后就可以确定数据的组数和多出来的组数了。

最终,我们得到$S=\lfloor r/33660 \rfloor × S_T +$ $ \sum_{i=1}^{r \mod 33660} (F_i \mod 34969)$。然后我们可以计算出$p$的值,进而求出$q$的值。

有了$p,q$两个数字,我们就可以求出$N$的欧拉函数 然后用跟上一题一样的脚本(Superaffine中提到的求最大公约数和逆元的脚本),用RSA解密方法迅速得出$d$和$m$,来一波long_to_bytes,得出flag。

Misc

1.签到题

这个就不写题解了吧~Rules能找到

2.easeBase

随便在百度上找个Base64加密解密网页,可以得到以下内容:307847616D657B68407070794D4953435F4D4953435F4D4953437D

观察可知这是一个$16$进制的数字,应该是ASCII码。存入一个文本文档中,然后两位一组按一个回车。最后用以下C++脚本即可得到flag

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x;
freopen("1.txt","r",stdin);
while(~scanf("%x",&x))
{
printf("%c",x);
}
return 0;
}

3.lowerBase64

根据0xgame的开头Base64加密可知:这边应该是把正确的密文全部小写后得到给出的字符串

使用以下的python脚本,每次在$k$后面加$2$位字符,可以确定后面$1$到$2$个$f$的内容,就这样手动地一步一步地扩充字符串$k$和$f$的内容,当$f$内容完整时,我们就得到了flag

1
2
3
4
5
6
7
8
9
from base64 import b64encode
from string import *
f='0xgame{'
k='mhhnyw1le'
s="abcdefghijklmnopqrstuvwxyz0123456789-{}"
for i in s:
for j in s:
if((b64encode((f+i+j).encode()).decode().lower()).startswith(k)):
print (i+j)

Web

由于本人没选择web方向,所以web简单切了2题,这两题对于主修web的是非常非常$H_2O$但我还是用了很久才做出来

1.View Source

F12就出来Flag了,Pass

2.robots协议

网址后面加/robots.txt得到一个界面,看到了Disallow内容,最后把/robots.txt改为/flaaaggg.php就得到flag了