0xGame Div 1 题解
About
第一周题目还算比较简单,把密码切了两题,Misc简单看了看。搞了2000多分,很多大佬7000多分,wtcl
Crypto
1.Calendar
根据给的日历图片,THU1表示第一行的星期四对应的日期,同理,TUE2表示第二行的星期二对应的日期,不是这个月第二个星期二对应的日期。纠错方法:有个码是TUE4,如果按照后者进行理解,那么得到的值是$27$。同时题目给了提示为:“明文字母全为小写,请将明文包含在0xGame{}内提交”,说明每个数字不会超过$26$。(因为我一开始就是错误的理解,然后发现了问题)
这个可以直接手打出所有的数字,保存在一个txt文件中,然后用下面的脚本就可以得出flag了
1 |
|
2.easyXor
必备常识:已知$a$ xor $ b = c$ ,可以得到$c$ xor $b = a$
下面是题目的Python代码:
1 | from random import randint |
很显然,题目给出了最终的输出,也知道最后增加的一位内容。从最后一位出发,我们可以一个一个回推以前的步骤。
将最后的输出结果复制到一个txt文件中,用替换功能把所有的逗号换成空格,删除无关符号,用以下的C++脚本代码运行即可
1 |
|
3.Superaffine
我们先来看一下程序代码
1 | from Crypto.Util.number import * |
很显然,这是一个仿射密码,单层加密过程为一个一次函数$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 |
|
$y=E(x)\equiv 35x+59 \mod 62$
然后我们可以用Python的脚本,求出$35$在模$62$的意义下乘法逆元为$39$,脚本如下(下一题用到的也是这个脚本,这个脚本可以求最大公约数和逆元)
1 | def EX_GCD(a,b,arr): #扩展欧几里得 |
由于$62-59=3$,所以$59$在模$62$的意义下加法逆元为$3$,所以解密函数为$x=D(y)\equiv 39y+3 \mod 62$
同样,将密文放入一个txt文件,用C++写一个脚本,即可求出明文
1 |
|
4.equationSet
1 | from Crypto.Util.number import * |
这是一个简单的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 | n = reduce(lambda a, b: a*b, [getPrime(4) for _ in range(4)]) |
这仍然是个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 |
|
由于输出的第一个数字为$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 |
|
3.lowerBase64
根据0xgame
的开头Base64加密可知:这边应该是把正确的密文全部小写后得到给出的字符串
使用以下的python脚本,每次在$k$后面加$2$位字符,可以确定后面$1$到$2$个$f$的内容,就这样手动地一步一步地扩充字符串$k$和$f$的内容,当$f$内容完整时,我们就得到了flag
1 | from base64 import b64encode |
Web
由于本人没选择web方向,所以web简单切了2题,这两题对于主修web的是非常非常$H_2O$但我还是用了很久才做出来
1.View Source
按F12
就出来Flag了,Pass
2.robots协议
网址后面加/robots.txt
得到一个界面,看到了Disallow
内容,最后把/robots.txt
改为/flaaaggg.php
就得到flag了