-
-
[原创]第六题 一尺之棰
-
发表于:
2020-4-26 20:47
4147
-
首先看文件大小，75k。看起来很精悍的样子，是我喜欢的题目类型。系统要求WIN10/64，但是我在WIN7/64下运行也很正常，没有影响解题。
题目基本所有关键代码都在main函数中，不需要花费太多精力在流程跳转上。
输入在转换为16进制数后会进入了一个16次的大循环，每次循环结束都会将输出转为输入继续下一轮。整个循环结束后判断输出长度是否为0x38A并与循环前初始化的一个疑似大数进行比较，如果验证通过则输出成功信息。
大循环里面还有输入长度加5次的中循环，中循环里面还有256次小循环。
进一步分析可以发现输出的前2个字节为前一次输入的长度，所以最后一次的输入（即倒数第二次的输出）应该是0x305字节。256次的小循环是产生与输入无关的固定随机数，中循环逐个字节读取输入并产生若干比特的输出，该输出长度可以为0。
根据题目的输出模式，很容易理解每个循环的输入和输出之间存在着很强的前后对应关系，而且题目运算最耗费时间的是产生固定随机数。如果使用爆破方法，在去掉产生固定随机数的算法后，还可以按照顺序用输出对输入进行逐个字节校正，从而加快爆破速度。
题目比较耗费时间的就是正向算法的重构，还是由于所有关键代码都在main函数中，所以大量变量都在一起，很难区分。最关键的是浮点运算的精度控制寄存器在printf调用的output_l函数里被改变了，导致固定随机数与题目计算的对不上，最后解决办法是在代码开始处加上_mm_setcsr(_mm_getcsr() | 0x4000);
恢复算法之后，构造数据结构存储每一个字节的所有路径，对最后一次的输入采用深度优先算法进行遍历。在优化算法后对0x305字节的遍历速度在10分钟以内，对整个16轮的遍历不到半个小时。最后得到的结果为：504964774D526B756F467A705C4D654B7645587746634A7A75505F757A75776C。
typedef struct PathStr {
WORD MaxNum;
WORD CurNum;
BYTE Path[0x100];
}PathStr;
PathStr Paths[0x400];[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
最后于 2020-4-26 23:53
被xym编辑
，原因：
