-
-
[原创] 第十一题 虫洞末世 算法题把机器都跑废了
-
2022-6-3 19:46
16490
-
[原创] 第十一题 虫洞末世 算法题把机器都跑废了
面对纯算法题,心里还是比较虚的。但好在这道题一眼看去没有涉及什么高深的数学知识。虽然看着半懂不懂的,却也能硬着头皮看下去。
程序很简洁,主函数获取输入,createkey利用输入的16个字符生成key,cheakkey对key进行校验。本来秉持着每一步都尽量分析清楚的心理,对每一行代码都进行了功能判断,前面基本都是输入到keywords1的等价变换,最后卡在createkey里生成Q的一个循环里。程序运行速度并不快,也是这里造成的。无奈跳过这段代码,来到cheakkey函数,先不管奇怪的doom子函数,这里居然直接对key[0]和key[-1]做了判断,也就是说key[0]和key[-1]的值是已知的。结合createkey里key是Q轮流除以keywords1生成的,可以得到第一个等式
1 | Q = key[ 0 ] * keywords1[ 0 ] = key[ - 1 ] * keywords1[ - 1 ]
|
对于每个keywords1最多不到16384情况,而且keywords1是稀疏的,满足等式的情况应该不多,编写代码应该可以遍历的起。在不考虑多解的情况下,把取值范围限制到[32,223),大概不到10分钟,跑出了第一组解[108,114],[97,115]。即Serial以“lr”开头,以“as”结尾。
再分析doom函数,不难发现mode1就是mode3,当mode1比mode2和mode4都小时,mode1为remembermode的公约数。经分析remembermode的最大公约数为32,有点偏小。抱着侥幸心理利用int((key[1]/key[6])10*16) == 32跑了一遍也确实没有结果。
1 2 | >>> math.gcd( 30413574359725275612744778689984 , 49715060849837149374468109364128 )
32
|
于是换个思路,既然mode1不是最小的,那么mode2和mode4里至少有一个比mode1小,那比mode1小的值必然是remembermode里面的因子。于是分别利用
1 2 | remembermode[ 0 ] % int ((key[ 3 ] / key[ 5 ]) * 10 * * 16 ) = = 0
remembermode[ 1 ] % int ((key[ 2 ] / key[ 4 ]) * 10 * * 16 ) = = 0
|
作为条件进行遍历,各得一个结果,并且利用得到的mode2和mode4都可以推出
mode1的值为14109109473780244。最后利用
1 | int (( (Q / key1) / (Q / key6)) * 10 * * 16 ) = = 14109109473780244
|
作为判断条件,遍历出最后4位的值。最终得到Serial为lrY1314cXy2920as。
多解分析:
在lists的第一步处理中p<=57和p>=48时取值范围为223-232,否则根据p为可见字符时推出取值范围为100-147,158-227。其中出现的223-227的重合表明凡是出现在答案中的数字,只要小于等于5就可以找到另一个可见字符进行替换。
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》,视频+靶场+题目!助力进入CTF世界