【文章标题】: 再谈一个CrackMe解密算法的数学原理
【文章作者】: kaien
【作者邮箱】: kkaien@hotmail.com
【软件名称】: echap511.exe
【加壳方式】: 无壳
【使用工具】: OllyDbg,winxp自带的计算器,VC(写注册机用)
【操作平台】: winxp
--------------------------------------------------------------------------------
【详细过程】
  昨天看到WAKU写的一篇题为“<<加密与解密第二版>>光盘中的一个CrackMe破解”的破解文章。我看文章前直接下了CrackMe自己破了一下。发现虽然很简单，但是很精彩！！！
  所以忍不住要借WAKU的光也写一篇破解文章。好东西就是不厌其谈，百遍不穿啊！
  本文我将侧重与讨论这个解密算法的数学原理和演变方法，从而大大的简化了解密过程。
  这是本人在看雪的第二篇破文，希望本人这篇拙作能对新手们有所帮助。
  
  算法部分代码如下，很好理解，看我后面的注释:
  
  004010CE   |.  33FF               xor edi,edi                                      ;  edi清零
  004010D0   |.  B9 08000000        mov ecx,8                                        ;  下面的循环次数为8次（估计密码是8位）
  004010D5   |.  BE 44304000        mov esi,echap511.00403044                        ;  取密码到esi
  004010DA   |>  8036 32            /xor byte ptr ds:[esi],32                        ;  每个字母都和32 xor
  004010DD   |.  46                 |inc esi
  004010DE   |.^ E2 FA              \loopd short echap511.004010DA
  004010E0   |.  BE 44304000        mov esi,echap511.00403044                        ;  变换后的密码的地址给esi
  004010E5   |.  B9 04000000        mov ecx,4                                        ;  ecx=4 这里就是说，下面循环4次
  004010EA   |>  8A06               /mov al,byte ptr ds:[esi]                        ;  取第一位
  004010EC   |.  8A5E 01            |mov bl,byte ptr ds:[esi+1]                      ;  取第二位
  004010EF   |.  32C3               |xor al,bl                                       ;  al=al^bl
  004010F1   |.  8887 4C304000      |mov byte ptr ds:[edi+40304C],al                 ;  因为前面edi已经清零了(看第一行)。所以第一次循环时这里就是取地址40304c
  004010F7   |.  83C6 02            |add esi,2                                       ;  地址跳两位
  004010FA   |.  47                 |inc edi                                         ;  edi++
  004010FB   |.^ E2 ED              \loopd short echap511.004010EA
  004010FD   |.  BE 4C304000        mov esi,echap511.0040304C                        ;  计算后把地址给esi.其实40304c在内存里面，就在前面8位密码后面
  00401102   |.  8A06               mov al,byte ptr ds:[esi]                         ;  在4个计算结果中，取第一位给al
  00401104   |.  8A5E 01            mov bl,byte ptr ds:[esi+1]                       ;  取第二位给bl
  00401107   |.  32C3               xor al,bl                                        ;  al=al^bl
  00401109   |.  8A5E 02            mov bl,byte ptr ds:[esi+2]                       ;  第三位->bl
  0040110C   |.  8A4E 03            mov cl,byte ptr ds:[esi+3]                       ;  第四位->cl
  0040110F   |.  32D9               xor bl,cl                                        ;  bl=bl^cl
  00401111   |.  32C3               xor al,bl                                        ;  两个xor后的结果再xor给al
  00401113   |.  B9 08000000        mov ecx,8                                        ;  ecx=8,就是下面循环8次
  00401118   |.  BE 44304000        mov esi,echap511.00403044                        ;  esi其实就是第一次变换后的密码的开始地址
  0040111D   |>  3006               /xor byte ptr ds:[esi],al                        ;  把密码的每一位都和al xor
  0040111F   |.  46                 |inc esi
  00401120   |.^ E2 FB              \loopd short echap511.0040111D
  00401122   |.  B9 08000000        mov ecx,8                                        ;  现在得到了新的密码
  00401127   |.  BE 44304000        mov esi,echap511.00403044                        ;  esi = 密码开始地址
  0040112C   |.  BF 08304000        mov edi,echap511.00403008                        ;  edi,这个地址403008的内容是怎么得到的？
  （OD中搜索所有常量403008（也可以设内存写入断点）会发现没有其他语句修改这段内存，而且这些数值从一开始就没有变化，估计这些是程序设计好的8个字符，而不是计算出来的，应该是用来做比较的字符常量）
  00401131   |>  8A06               /mov al,byte ptr ds:[esi]                        ;  把两段字符串（8个字符）做比较，不相等就完蛋
  00401133   |.  3A07               |cmp al,byte ptr ds:[edi]
  00401135   |.  75 1D              |jnz short echap511.00401154
  00401137   |.  46                 |inc esi
  00401138   |.  47                 |inc edi
  00401139   |.^ E2 F6              \loopd short echap511.00401131
  
  OD内存窗口里看到，地址403008处的8个字符的16进制分别为：
  71 18 59 1B 79 42 45 4C
  
  分析和总结:
  首先，密码必须8位。然后进行密码验证。
  
  密码验证算法:
  
  1。先把密码的8个数分别和32 xor
  2。然后两个两个的取，每两个数都xor一下，这样就得到了4个数
  3。把上面计算出的4个数分成前后两组。每组的两个数都xor，又得到两个数
  4。再把这两个数xor给al
  5。我们下面就要使用al了。先把前面变换后的密码（即经过第1步运算后的密码）每位都和al xor.然后把结果和 71 18 59 1B 79 42 45 4C这8个数比较。不等就game over!
  
  下面才是本文的关键所在，请大家仔细看好了，认真理解!
  
  上面5个步骤地代数表示形式为:
  
  假设输入的原密码为: c1 c2 c3 c4 c5 c6 c7 c8
  
  第一步:
  Ci=ci^32 i=1..8
  
  第二步:
  A1=C1^C2
  A2=C3^C4
  A3=C5^C6
  A4=C7^C8
  
  第三步:
  B1=A1^A2=C1^C2^C3^C4
  B2=A3^A4=C5^C6^C7^C8
  
  第四步:
  al = B1^B2 = C1^C2^C3^C4^C5^C6^C7^C8 = (c1^32)^(c2^32)^....^(c8^32) = c1^c2^c3^c4^c5^c6^c7^c8
  
  即al = C1^C2^C3^C4^C5^C6^C7^C8 = c1^c2^c3^c4^c5^c6^c7^c8
  上式表明，原密码所有位数xor的值 = 变换后的密码所有位数xor的值 = al的值
  
  第五步:
  C1^al=71
  C2^al=18
  C3^al=59
  C4^al=1B
  C5^al=79
  C6^al=42
  C7^al=45
  C8^al=4C
  
  我们看到，如果我们把第5步中得到的8个等式xor,即(C1^al)^(C2^al)^...^(C8^al) = C1^C2^C3^C4^C5^C6^C7^C8 = 71^18^59^1B^79^42^45^4C = 19 这是一个常数
  
  结合第四步的结果，我们有如下结论：
  al = C1^C2^C3^C4^C5^C6^C7^C8 = c1^c2^c3^c4^c5^c6^c7^c8 = 71^18^59^1B^79^42^45^4C = 19
  
  这是多么美妙的式子啊！！！
  
  
  请大家注意了，我们回头再来看看我们的问题。
  我们的问题是找注册码，即：求解所有的ci,i=1..8
  如果我们可以求解出Ci,i=1..8,那么就等同于求解出了ci,因为ci = Ci^32
  
  也就是说，我们需要求解第5步所给出的方程组。
  到这里，解密的问题完全变成一个数学问题了。
  
  我们仔细观察一下会发现, 这个方程组中有8个方程和8个未知数。
  且这8个方程是彼此线性无关的。
  也就是说，如果存在解。那么解就是唯一的。
  这样，我们就从理论上证明了解的唯一性了！^_^
  
  下面的问题就是，怎么求解方程组呢？
  
  方法很多！
  首先，让我们用第一个等式分别和其他七个等式xor. 我们可以得到:
  (C1^al)^(C2^al) = C1^C2 = c1^32^c2^32 = c1^c2 = 71^18
  即 c1^c2 = 71^18
  依此类推
  c1^c3=71^59
  ...........
  c1^c8=71^4C
  
  注意：上面有七个方程。而且形式已经非常简单了。
  
  我们看到，只要我们给定任意一个c1则分别可以唯一的计算出c2,c3,...c8来, 因为我们有如下变换:
  c2=71^18^c1
  c3=71^59^c1
  ...........
  c8=71^4C^c1
  
  也就是说，我们只要确定c1的值，就能通过上面的7个方程唯一的计算出c2,...,c8的值。
  
  问题一：我们可以随便取c1吗？
  
  答案很明显是不可以。因为我们已经从理论上证明了解的唯一性了。
  
  问题二：那么，如何计算c1呢？
  
  我们来看，
  al = c1^c2^c3^c4^c5^c6^c7^c8 = 19 这一点我们已经证明了。
  所以说al=19是个常数，确定无疑。
  那么，根据第5步中的第一个方程C1^al=71 我们可以得到。
  C1^al = c1^32^al = c1^32^19 = 71
  注意到了吗？这里只有一个未知数c1。
  所以，我们可以唯一的计算出c1 = 71^32^19 = 5A = 'Z'
  这样c1的值也被确定了。
  
  总结注册码算法如下:
  
  算法一:
  
  c1 = 71^32^19 = 5A
  c2=71^18^c1
  c3=71^59^c1
  c4=71^1B^c1
  c5=71^79^c1
  c6=71^42^c1
  c7=71^45^c1
  c8=71^4C^c1
  
  通过数学的分析和变换，我们看到算法大大的被简化了。
  而且，此问题有且只有一个解: Z3r0Ring
  
  其实，本问题还有更直接、更简单的解法。^_^
  我上面介绍的是先找到c1和c2,...,c8的关系，然后通过变换求解出c1，就可以依次计算出c2,...,c8的数值。
  这是求解方程组的一种常用的思路。
  
  然而，对于这个问题，其实完全不用这么做。
  明眼的人可能已经注意到了我前面的提示以及如何计算c1的过程了。
  事实上，我们完全可以用同样的方法，直接计算出c2,...,c8来。
  我们有算法二:
  
  C2^al=18 => c2^32^al = c2^32^19 = 18 => c2 = 18^32^19
  即 c2 = 18^32^19 = '3'
  
  同理
  c3 = 59^32^19 = 'r'
  c4 = 1B^32^19 = '0'
  c5 = 79^32^19 = 'R'
  c6 = 42^32^19 = 'i'
  c7 = 45^32^19 = 'n'
  c8 = 4C^32^19 = 'g'
  
  这算法够直白了！直接计算，已经化简到不能再简单了吧！:)
  
  
  因为算法已经被简化到了极限，所以第二个算法的注册机就不写了。
  贴一个第一种算法的注册机好了, C代码如下:
  
  #include<stdio.h>
  
  void main()
  {
          char c[8],al,b[8]={0x71,0x18,0x59,0x1B,0x79,0x42,0x45,0x4C};
         
          al=b[0];
          for(int i=1;i<=7;i++) al=al^b[i]; //或者直接写al=0x19就可以了,可以省略计算al的运算 :)
          c[0]=b[0]^0x32^al; //计算c0
          for(i=1;i<=7;i++)
          {
                  c[i]=b[0]^b[i]^c[0]; //分别计算c1...c7
          }
          c[8]='\0';
          printf("注册码: %s\n",c); //输出结果
  }
  
  
  这是我在看雪的第二篇教程，希望在文中我已经解释的足够清楚了。
  还有对解密算法不理解的可以提问, 也希望这篇教程大家能喜欢。^_^
  
  破解完毕!
  
--------------------------------------------------------------------------------
【下载地址】: 还没上传权限！:(  大家请先到WAKU的帖子里下
（http://bbs.pediy.com/showthread.php?s=&threadid=21636&highlight=%3C%3C%BC%D3%C3%DC%D3%EB%BD%E2%C3%DC%B5%DA%B6%FE%B0%E6%3E%3E%B9%E2%C5%CC%D6%D0%B5%C4%D2%BB%B8%F6CrackMe%C6%C6%BD%E2）
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!

                                                       2006年11月24日 15:43:08

[注意]看雪招聘，专注安全领域的专业人才平台！