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;
}
C++

2.easyXor

必备常识:已知 xor ,可以得到 xor

下面是题目的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]

PYTHON

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

将最后的输出结果复制到一个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;
}
C++

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}

PYTHON

很显然,这是一个仿射密码,单层加密过程为一个一次函数

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

根据defgenkey可知:此处的均为随机生成的内的整数,如果暴力枚举,复杂度为。所以暴力是不可以的。

化简加密公式,我们可以得到解密公式。所以这里涉及到求逆元。又由于为合数,,也就是只有个字符可以正确地加密并解密,说明本替换密码的密钥空间为,并不是很大。

下面我们探讨一下两重仿射密码 ,所以,仍然是一个一次函数,还是能够写成的形式,密钥空间不变,仍然是。所以得到一个很重要的结论:无论仿射加密有几层,密钥空间总是不变!因为可正常转换的字符数量本来就是有限的。

所以,我们根据推出的公式:,写成的形式,并且由于密钥空间不变,仍然是中的整数。所以我们根据代码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
C++

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

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))

PYTHON

由于,所以在模的意义下加法逆元为,所以解密函数为

同样,将密文放入一个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))] ;
}
}
}
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)
# 给出部分略
PYTHON

这是一个简单的RSA变式,三个质数相乘,根据我们得到的线索:有以下3个数据可用:

由于均为质数,我们只需要求的最大公约数即为的值,然后我们很快就得到以下两个数字:

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

实际上我们不需要解出来这2个值,因为RSA加密为,解密为,其中在模的逆元,所以我们只需要求,又因为均为质数,所以

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

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

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

5.Fibonacci

先放一下题目中最核心的代码,并且题目给出了 个数的值

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数字过大,此处略去
PYTHON

这仍然是个RSA的变式题。首先我们可以看到 的值是密切相关的。所以我们应当先求出的值

根据斐波那契数列的递推公式,其中,我们可以知道:如果所有的对同一个数取模,这个数列应当是有周期性的,所以我们应当求这个数列的周期。而模数为,并不是一个很大的数字,所以我们可以估计周期不超过,用以下的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;
}
C++

由于输出的第一个数字为,说明,确定周期为,这样我们可以求出一个周期内的数字之和

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

最终,我们得到 。然后我们可以计算出的值,进而求出的值。

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

Misc

1.签到题

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

2.easeBase

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

观察可知这是一个进制的数字,应该是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;
}
C++

3.lowerBase64

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

使用以下的python脚本,每次在后面加位字符,可以确定后面的内容,就这样手动地一步一步地扩充字符串的内容,当内容完整时,我们就得到了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)
PYTHON

Web

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

1.View Source

F12就出来Flag了,Pass

2.robots协议

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


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