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//33660和r%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了

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