【(伪)十周年庆典活动】逆算法，送PB

F8LEFT

     论坛十周年了，在此祝愿论坛越来兴旺。
     所以我弄了一个伪活动来了，这几天在分析软件时，发现一个挺简单的算法。于是就拿出来给大家了。
     大家只需要把算法化简，使用简单的等式弄出结果就可以了。
     第一个答出答案的大神将获得PB50个（大出血啊），大家来玩一下吧。

    算法节选自everedit_win32_4037，解密注册码的部分（大数运算部分）。

算法部分：

1. BigNum Pass;                                 //自己输入的数据
   
2. BigNum Max;                                  //= ()静态数据
   
3. int Status = 0x2605;    (10 0110 0000 0101)  //状态判断,二进制长度为0xE
   
4. int StatusNew = 0x4000;(100 0000 0000 0000)  //(用于判断Status)
   
5. 
   
6. BigNum Rel = 1;
   
7. while(StatusNew){
   
8.    StatusNew >>= 1;
   
9.    Rel *= Rel;
   
10.    Rel %= Max;
    
11.    if(StatusNew & Status) {                  //逐位检查Status的二进制位是否为1
    
12.       Rel *= Pass;
    
13.       Rel %= Max;
    
14.    }
    
15. }

复制代码

       其中，各个数据均为整数       请写出Rel与Pass之间的关系，格式为 Rel = ??Pass??, 比如 Rel = 2605 * Pass % Max 之类的
       等价的算法非常的简单，只有一句而已。      
       答案以及分析将在3天后 2014.12.5 20:00 公布，大家都来玩一下吧。估计10来分钟左右就能化简掉了。

lhglhg

简单分析一下：

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

      答案公布了哈哈，在此先恭喜 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

           故此 左式 = 右式

          ①得证。

       这样下来，无论原代码中做了多少次求模运算，均没有影响，等价于全部乘在一起在求模。

       于是，我们现在只需要关注乘法代码：

1. while(StatusNew){
   
2.    StatusNew >>= 1;
   
3.    Rel *= Rel;
   
4.    if(StatusNew & Status) {                  //逐位检查Status的二进制位是否为1
   
5.       Rel *= Pass;
   
6.    }
   
7. }

复制代码

      有关大概的推理 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，然后安全性由大数保证，非常好用，简单实用，哈哈。

l0v3cr4ck

{:soso_e127:}占楼有PB么

mongolnet

正在晕头转向

lhglhg

Pass  << (((2*2*2+1)*2+1)*2*2*2*2*2*2*2+1)*2*2+1   % Max

Rel=  (Pass << 0x2605 )  % Max

lhglhg

这次应该对了

Rel= pow( Pass , 0x2605 )  % Max

lpxx

看不懂唉，坐等答案。

sndncel

lhglhg 发表于 2014-12-3 08:53
简单分析一下：

1.看int Status = 0x2605;    (10 0110 0000 0101)  //状态判断,二进制长度为0xE  应循 ...

这个真心看不懂呀。。。。不知道是数学太差，还是对C没有感觉呀。。。。。

yosen2001

强大的算法。呵呵。表示看不懂C语言{:soso_e109:}