lelfei参赛题目：CrackMe

答案：97654321

设计说明：

1.设计了一个十进制大数计算类BigNum，计算位数暂定为0x400位，算法仅实现了加法和乘法。

2.要求输入8－20位非0数字N，乘以9后循环计算乘方结果：R=(N*9)^M，同时符合以下四条规则时为正确答案：

  1)R位数为奇数；

  2)R最中间位与N首位相等；

  3)R最后几位与N除首位外的字符相同；

  4)R最开始几位与N除首位外的字符逆序排列。

破解思路：

根据检测规则，如果结合数学上的一个“幻数”12345679就非常简单了：

12345679*9=111111111

111111111^2=12345678987654321

其他说明：

无法确定答案的唯一性，不过这么有特点的数应该不多吧。。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

设计感想：

最开始设计时，苦于没有既好玩又设计巧妙的算法，一直没有什么进展。后来突然想到12345679这个比较特殊的数，灵感来了。首先，12345679*9＝111111111，这么有规律的数，肯定是没有几个的（到底有没有其他符合这种规律的数？我没有穷举过，不知道啊）。然后9个1的平方为12345678987654321，又跟初始值有了联系：前7位相同，后7位逆序排列，以此作为检测条件，肯定是非常巧妙的！

于是开始设计：语言选用经典的VC6，操作数值方便；平方数为17位，超过了32位数的上限，需要设计一个大数计算器，用于计算加法和乘法；大数计算器BigNum使用0x100位，使用0x100字节存储每一位的值；计算输入值*9，然后算平方值，比较前7位和后7位，后来又增加了比较中间位为输入值的末位这一条件。

对于BigNum类加法很好实现，按位相加，然后用CalcValue()校验一下进位就可以了。乘法的实现方法绕了一下，先设计了一个MulSingle(int v)单数乘法，不需要考虑进位；然后再加一个十进制移位操作LeftMove(int v)，相当于N*10^v，只需要按位往前移，后面补0就可以了；最后把乘法转化成：N*(abcd)=N*10^3*a+N*10^2*b+N*10*c+N*10^0*c，把多位乘法简化成移位、单数乘法、加法，简单方便！

第一版设计出来了，后面的事就是增加难度了。考虑到个人能力和个人喜好，就不加壳、不加花、不加VM了，纯算法题，至少我是非常喜欢的。

1.只计算平方，难度太低，于是把检测条件转成循环检测乘方值，当乘方值溢出时跳出循环，让cracker不知道是在循环的哪一层检测成功的；

2.位数只有0x100位，乘方时很快就溢出了，增加到0x400位，把字节存储改成双字32位存储，再扩展起来也方便；

3.存储位是顺序存储的，太容易观察结果了，在BigNum类初始化时添加一个顺序ID列表int id[BBLEN]，然后把每一位随机与其他位交换数值，生成一个随机列表，访问时使用bb[id[n]]，避免内存中出现数值连续存储；

4.在计算乘法时，重新初始化随机数种子，让数值存储再次打乱；

5.在初始化时保存随机数种子GetTickCount，在最后比较数值时查看GetTickCount是否相差太大，如果差的太大则是调试状态，让比较的返回值始终返回错误。

经过这些难度增加，自认为对算法的隐藏做的差不多了，等放出来时才发现大大低估了cracker的水平，基本上在编程时留的后门全部都被发现了。。

最后总结一下设计上存在的不足：

首先是初始化随机列表时，为了让自己观察方便，先初始化顺序列表，然后再随机交换，当处于调试模式时跳过随机交换的过程。结果果然有cracker发现了这个漏洞，直接跳过随机交换的过程，大大降低了观察的难度。

其次是对输入值限制的太窄，8－20位数值，刚开始我觉得0x400位的乘方值应该会延迟穷举的时间，但是忽略了穷举的顺序，大部分cracker会先从平方开始穷举，我自己试了一下8位数的平方值穷举，不到1秒就出结果了。

再次是算法的比较过程太简单了，有几个人是看到算法比较是前面顺序后面逆序，直接上网搜回环数，直接找到了111111111，再除以9就得到结果了。

最后是算法隐藏的还是不够好，很多人猜测是大数算法后，都不用去分析计算过程，直接看结果比对就可以了。应该把大数算法拆分，让cracker不那么容易猜出大数结构。

我自己总结的这一题的特点是：纯分析题，分析出算法后非常容易解出答案。

最后，附上程序源码，祝大家玩的开心！

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界