【(伪)十周年庆典活动】逆算法，送PB
本帖最后由 F8LEFT 于 2014-12-2 19:29 编辑论坛十周年了，在此祝愿论坛越来兴旺。
所以我弄了一个伪活动来了，这几天在分析软件时，发现一个挺简单的算法。于是就拿出来给大家了。
大家只需要把算法化简，使用简单的等式弄出结果就可以了。
第一个答出答案的大神将获得PB50个（大出血啊），大家来玩一下吧。
算法节选自everedit_win32_4037，解密注册码的部分（大数运算部分）。
算法部分：
BigNum Pass; //自己输入的数据
BigNum Max; //= ()静态数据
int Status = 0x2605; (10 0110 0000 0101)//状态判断,二进制长度为0xE
int StatusNew = 0x4000;(100 0000 0000 0000)//(用于判断Status)
BigNum Rel = 1;
while(StatusNew){
StatusNew >>= 1;
Rel *= Rel;
Rel %= Max;
if(StatusNew & Status) { //逐位检查Status的二进制位是否为1
Rel *= Pass;
Rel %= Max;
}
} 其中，各个数据均为整数 请写出Rel与Pass之间的关系，格式为 Rel = ??Pass??, 比如 Rel = 2605 * Pass % Max 之类的
等价的算法非常的简单，只有一句而已。
答案以及分析将在3天后 2014.12.5 20:00 公布，大家都来玩一下吧。估计10来分钟左右就能化简掉了。
简单分析一下：
1.看int Status = 0x2605; (10 0110 0000 0101)//状态判断,二进制长度为0xE应循环14次
2. Rel *= Rel; 和Rel *= Pass; 可以知道是 自乘和 乘 pass; Rel应该是Pass的 几次方关系
3.if(StatusNew & Status) //逐位检查Status的二进制位是否为1,意思当二进制位为1是 运行 (自乘和 乘 pass),为0时仅 运算 自乘。
4. 第1位为1,二个运算都运行了,这时Rel = pass ;
5.从第2位开始，每碰到1位就多了个 自乘 （相当于次方数+1），故 本数0x2605从第2位后,还有4 位为1 的
pass的次方数为(((2*2*2+1) *2+1)*2*2*2*2*2*2*2+1)*2*2+1 = 0x2605
换成C ,就是 Rel = POW( Pass,0x2605 ) % Max
本帖最后由 F8LEFT 于 2014-12-3 22:31 编辑
答案公布了哈哈，在此先恭喜 lhglhg 大神，完全回答正确。它的答案请参考推荐以及第 17 楼的补充回答。我也在这里给出我的答案。 首先，正确答案为 Rel = ( Pass ^ 0x2605 ) % Max； 其中，Pass ^ 0x2605 表示 Pass 的 0x2605 次方，不是求异或，请注意了，下同。
原式中存在乘法与求模运算部分，为了去掉求模运算的影响，我引入一个结论
① [(A % C) * (B % C)] % C = (A * B) % C
证:
不妨设 A / C = n ...... a, B / C = m ......b。
则有 A = n * C + a, B = m * C + b
也即 A % C = a, B % C = b
于是 左式 = (a * b) % C
右式 = [(n * C + a) * (m * C + b) ] % C
= [ n * m * C * C + n * C * b + a * m * C + a * b] % C
= (a * b) % C
故此 左式 = 右式
①得证。
这样下来，无论原代码中做了多少次求模运算，均没有影响，等价于全部乘在一起在求模。
于是，我们现在只需要关注乘法代码：
while(StatusNew){
StatusNew >>= 1;
Rel *= Rel;
if(StatusNew & Status) { //逐位检查Status的二进制位是否为1
Rel *= Pass;
}
} 有关大概的推理 lhglhg 大神已经说过了，这里我就再复述一次。 对于Rel 的操作只有 自乘 以及 乘以 Pass两个，所以可以推出 ，Rel = Pass ^ i,其中，i 未知，反正就是多次方关系。 于是，假设初始 Rel = Pass ^ 0, 进入函数，会发现每一次循环不外乎两个操作 自乘，或者 自乘 再 乘 Pass。 取第k次Rel值为Rel = Pass ^ n, 数学表达式就为：
① StatusNew & Status = 0
Rel = Rel * Rel = (Pass ^ n) * (Pass ^ n) = Pass ^ ( n + n) = Pass ^ (2n)
② StatusNew & Status = 1
Rel = Rel * Rel = (Pass ^ n) * (Pass ^ n) = Pass ^ ( n + n) = Pass ^ (2n)
Rel = Rel * Pass = (Pass ^ 2n) * Pass = Pass ^ (2n + 1)
可以看出，产生变化的只有次方幂的值。
而且，题中已经指出， StatusNew 是 从高位开始诸位检查 Status(0x2605)的二进制位 是否为1，而 2n 与 n 对比，对于计算机来说就是 n 左移了 1 位。不难猜想，实际的操作是把幂系数变为 Status (0x2605)
所以，乘法的结果为 Rel = Pass ^ 2605, 这实际上是求多次幂的变形，也是一种有效的减少运算的方法。
终上所述，最终答案为 Rel = (Pass ^ 2605) % Max
进一步思考：
得出这个答案是没有多大意思的，毕竟我们弄算法，为的就是求出逆运算，弄出注册机，所以我们又必要再一次探讨这个式子。
把上式记为A = (B ^ D) % C
显然，知道 B,D,C,可以轻易的求得A，这也是软件所做的。那么，知道 A,D,C，是否可以求得B呢，现在来讨论。
把模运算部分去除，不妨设 A + n * C = B ^ D, 其中n为整数，显然，这条式子与上面的是等价的。
去除多次方的影响，两边取对数
ln(A + n * C) = D * lnB
=> lnB = ln(A + n * C) * (1 / D) = ln(A + n * C) * k, k = 1 / D。k为已知常数，n属于整数
显然，左式与右式是一一对应的关系。
于是，对于每个给定的A，C，D，随着 n 的 取值的不同，计算出来的 B 值也是不一样的。
所以 A 与 B 之间的关系为 1 对 多 的关系。但是，是可以解的。
接着，再加上一个限制条件，就是 A ，B 必须为整数。这样一来情况就发生了变化。
因为当 A 为 整数时， 计算得到的B不一定为整数。所以便出现困难了。
并且求我目前已知的算法来讲，并不存在特别有效的算法，只能够进行穷举来得到一组A，B值。当然，通过一定的算法是可以有效的减少穷举的量的，这个就不在探讨的范围内了。
如果你有更加好的方法，欢迎来向我提出。谢谢大家，那么答案就到此结束了，是不是感觉比想象中的要来的简单呢？
我特意选了这个算法，是因为它虽然简单，当的确是有效的。它的只能由穷举法求出key，然后安全性由大数保证，非常好用，简单实用，哈哈。
{:soso_e127:}占楼有PB么 正在晕头转向 本帖最后由 lhglhg 于 2014-12-2 23:41 编辑
Pass<< (((2*2*2+1)*2+1)*2*2*2*2*2*2*2+1)*2*2+1 % Max
Rel=(Pass << 0x2605 )% Max
本帖最后由 lhglhg 于 2014-12-2 23:33 编辑
这次应该对了
Rel= pow( Pass , 0x2605 )% Max
看不懂唉，坐等答案。 lhglhg 发表于 2014-12-3 08:53
简单分析一下：
1.看int Status = 0x2605; (10 0110 0000 0101)//状态判断,二进制长度为0xE应循 ...
这个真心看不懂呀。。。。不知道是数学太差，还是对C没有感觉呀。。。。。
强大的算法。呵呵。表示看不懂C语言{:soso_e109:}
页:
[1]
2