【(伪)十周年庆典活动】逆算法,送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