0xGame Div 1 题解 About第一周题目还算比较简单,把密码切了两题,Misc简单看了看。搞了2000多分,很多大佬7000多分,wtcl
Crypto 1.Calendar根据给的日历图片,THU1表示第一行 的星期四对应的日期,同理,TUE2表示第二行 的星期二对应的日期,不是这个月第二个星期二对应的日期 。纠错方法:有个码是TUE4 ,如果按照后者进行理解,那么得到的值是。同时题目给了提示为:“明文字母 全为小写,请将明文包含在0xGame{}内提交”,说明每个数字不会超过。(因为我一开始就是错误的理解,然后发现了问题)
这个可以直接手打出所有的数字,保存在一个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 randintfrom secret import flag flag+="^" cipher=[]for i in range (len (flag)-1 ): cipher.append(ord (flag[i])^ord (flag[i+1 ]))print (cipher)
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, digitsfrom random import randintfrom secret import flagassert flag.startswith("0xGame{" ) and flag.endswith("}" ) table = ascii_letters+digits MOD = len (table)def affine (x, a, b ): return a*x+bdef 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)
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 ; }
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 gdef ModReverse (a,n ): 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.equationSet1 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
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//33660
和r%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 b64encodefrom 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了