Windows优化大师v2.9+的注册码加密算法

                              written by dr0, 2000/08/22

本文将以汇编代码为例，解释一下“Windows优化大师” v2.9+中用到的RSA算法。
先简单介绍一下RSA算法，便于和汇编代码对照。具体的数学理论我们在此并不太关心，有兴趣的可以去查参考资料。

RSA算法简述：
1、取两个素数p和q。
2、计算n=pq，f=(p-1)(q-1)。
3、随机选取整数e，满足条件gcd(e, f)=1，其中gcd为最大公约数。
4、计算d，使得乘积de对f求余的结果为1，即de和1对f同余。
上述只有e和n对外公开，用于加密。

加密过程（符号^表示乘幂，mod表示求余）：
    e为加密密钥，假定明文为m，则密文c = (m ^ e) mod n。

解密过程：
    d为解密密钥，则解密得到的明文m'= (c ^ d) mod n。

RSA被攻破的一个充分条件是n被因子分解，即得到p和q。因为得到p和q之后便可以计算出f，从而根据“de和1对f同余”这个条件计算出解密密钥d来。

根据上面的加密和解密算法可以看出：
1、RSA的加密和解密是对称的，即加密和解密可以使用同一个函数；
2、RSA加密主要依靠模幂运算，因此这部分运算的复杂度对算法的效率影响最大。关于模幂运算，在《计算机密码学》（清华出版社，卢开澄）一书中讲了一种算法，该算法很容易理解，其指导思想就是不停地降阶，从而降低时间复杂度。用类C语言的伪码描述如下：

//下面这个函数计算(m ^ e) mod n
ReturnValueType  encrypt_decrypt(m, e, n)
{
  LocalVariables a, b, c;

  a = m;
  b = e;
  c = 1;

  while(b)
  {
    if ((b mod 2) == 0)
        {
        b = b / 2;        //降阶
                a = (a * a) mod n;
        }
        else
        {
                b = b - 1;
                c = (a * c) mod n;
        }
  }       
   
  return c;
}

Windows优化大师的破解过程已有很多文章讲过，本文重点分析其对我们输入的注册码进行加密运算的部分，因为只有这一部分求逆的难度比较大些，其它部分可以直接拷贝或者很容易求逆（例如环形移位运算）。我们将会看到，其使用的模幂算法就是上述的算法。

用IDA反汇编OctoDll.dll，可以看到一个名为Registed( )的函数，这显然是在判断注册码。这个函数将对我们输入的两部分注册码分别进行RSA加密，再移位，把移位的结果和一个数（这个数是根据“You are big pig.”、“1234567”以及注册申请码计算出来的，这个计算过程无需求逆）进行比较，然后返回另一个值（它的主程序会判断该值是否为0x14）。

Registed    proc near

    var_10      = dword    ptr -10h
    var_A        = word    ptr -0Ah
    var_8        = dword    ptr -8
    var_4        = dword    ptr -4
    arg_0        = dword    ptr  8
    arg_8        = dword    ptr  10h

        push  ebp
        mov    ebp, esp
        add    esp, 0FFFFFFF0h
        push  ebx
        xor    edx, edx
        mov    [ebp+var_10], edx
        mov    ebx, eax
        xor    eax, eax
        push  ebp
        push  offset loc_4043FE
        push  dword ptr fs:[eax]
        mov    fs:[eax], esp
        mov    eax, [ebp+arg_8]
        mov    [ebp+var_8], eax
        mov    eax, [ebp+arg_0]
        mov    [ebp+var_4], eax
        lea    eax, [ebp+var_10]
        mov    edx, ebx
        call  unknown_libname_17
        mov    eax, [ebp+var_10]
        lea    edx, [ebp+var_A]
        lea    ecx, [ebp+var_8]
        call  sub_4041D8      //核心判断
        test  eax, eax
        jnz    short loc_4043E4
        xor    ebx, ebx        //bad guy
        jmp    short loc_4043E8

loc_4043E4:
        movzx  ebx, [ebp+var_A] //return value

loc_4043E8:
        xor    eax, eax
        pop    edx
        pop    ecx
        pop    ecx
        mov    fs:[eax], edx
        push  offset loc_404405

loc_4043F5:
        lea    eax, [ebp+var_10]
        call  sub_402E5C
        retn

很显然，核心判断在call  sub_4041D8中。跟进去，看见函数体如下。这个函数的前半部分是在根据“You are big pig.”、“1234567”以及注册申请码通过哈希运算计算出几个数来。后半部分才是最值得关心的。注释如下：

sub_4041D8    proc near

var_24        = dword    ptr -24h
var_20        = dword    ptr -20h
var_1C        = dword    ptr -1Ch
var_18        = dword    ptr -18h
var_14        = dword    ptr -14h
var_10        = dword    ptr -10h
var_C        = dword    ptr -0Ch
var_8        = dword    ptr -8
var_4        = dword    ptr -4

        push  ebp
        mov    ebp, esp
        add    esp, 0FFFFFFDCh
        push  ebx
        push  esi
        push  edi
        xor    ebx, ebx
        mov    [ebp+var_14], ebx
        mov    esi, ecx
        lea    edi, [ebp+var_10]
        movsd
        movsd
        mov    [ebp+var_8], edx
        mov    [ebp+var_4], eax
        mov    eax, [ebp+var_4]
        call  sub_402FC0
        xor    eax, eax
        push  ebp
        push  offset loc_40435F
        push  dword ptr fs:[eax]
        mov    fs:[eax], esp
        lea    eax, [ebp+var_14]
        mov    edx, offset _str_You_are_big_pig.Text
        call  sub_402EC4
        mov    eax, [ebp+var_4]
        call  unknown_libname_18
        and    eax, 80000007h
        jns    short loc_40422A
        dec    eax
        or    eax, 0FFFFFFF8h
        inc    eax

loc_40422A:
        test    eax, eax
        jz    short loc_40425A
        lea    eax, [ebp+var_4]
        mov    edx, offset _str_1234567.Text
        call    @System@@LStrCat$qqrv ;    System __linkproc__ LStrCat(void)
        mov    eax, [ebp+var_4]
        call    unknown_libname_18
        test    eax, eax
        jns    short loc_40424A
        add    eax, 7

loc_40424A:
        sar    eax, 3
        mov    edx, eax
        shl    edx, 3
        lea    eax, [ebp+var_4]
        call    @System@@LStrSetLength$qqrv ; System __linkproc__ LStrSetLength(void)

loc_40425A:
        xor    esi, esi
        lea    eax, [ebp+var_4]
        call    sub_402FD0
        mov    edi, eax
        lea    eax, [ebp+var_14]
        call    sub_402FD0
        mov    ebx, eax
        jmp    short loc_4042A2

loc_404272:
        mov    eax, [edi+esi*4]
        mov    [ebp+var_1C], eax
        mov    eax, [edi+esi*4+4]
        mov    [ebp+var_18], eax
        mov    edx, ebx
        lea    eax, [ebp+var_1C]
        call    sub_404170
        mov    eax, [ebx]
        mov    [ebx+8], eax
        mov    eax, [ebx+4]
        mov    [ebx+0Ch], eax
        mov    eax, [ebp+var_1C]
        mov    [ebx], eax
        mov    eax, [ebp+var_18]
        mov    [ebx+4], eax
        add    esi, 2

loc_4042A2:
        mov    eax, [ebp+var_4]
        call    unknown_libname_18
        test    eax, eax
        jns    short loc_4042B1
        add    eax, 3

loc_4042B1:
        sar    eax, 2
        cmp    esi, eax
        jb    short loc_404272  //以上为前半部分，不用求逆

        mov    eax, [ebp+var_10]
        xor    edx, edx
        push    edx            //注册码的第一部分m1的高位（恒为0）
        push    eax            //注册码的第一部分m1的低位
        push    ds:dword_4050D0 //加密密钥e的高位（0）
        push    ds:dword_4050CC //加密密钥e的低位（3B442AF9）
        push    ds:dword_4050D8 //n的高位（0）
        push    ds:dword_4050D4 //n的低位（69AAA0E3）
        call    sub_4040B8      //encrypt_decrypt(m1, e, n)
        sub    eax, 2
        mov    [ebp+var_24], eax
        mov    eax, [ebp+var_C]
        xor    edx, edx
        push    edx              //注册码的第二部分m2的高位（恒为0）
        push    eax              //注册码的第二部分m2的低位
        push    ds:dword_4050D0  //加密密钥e的高位（0）
        push    ds:dword_4050CC  //加密密钥e的低位（3B442AF9）
        push    ds:dword_4050D8  //n的高位（0）
        push    ds:dword_4050D4  //n的低位（69AAA0E3）
        call    sub_4040B8      //encrypt_decrypt(m2, e, n)
        sub    eax, 2
        mov    [ebp+var_20], eax
        shl    [ebp+var_24], 2  //移位
        lea    ecx, [ebp+var_24]
        mov    eax, [ecx]
        mov    edx, [ecx+4]
        shrd  eax, edx, 2    //这条和下面一条完成64 bit环形移位
        shr    edx, 2
        mov    [ecx], eax
        mov    [ecx+4], edx
        mov    eax, [ebp+var_24]
        cmp    eax, [ebp+var_1C] //比较
        jz    short loc_404330
        xor    ebx, ebx
        jmp    short loc_404341

loc_404330:
        mov    ax, word ptr [ebp+var_20] //返回值
        and    ax, 0FFFFh
        mov    edx, [ebp+var_8]
        mov    [edx], ax
        or    ebx, 0FFFFFFFFh

loc_404341:
        xor    eax, eax
        pop    edx
        pop    ecx
        pop    ecx
        mov    fs:[eax], edx
        push    offset loc_404366

loc_40434E:
        lea    eax, [ebp+var_14]
        call    sub_402E5C
        lea    eax, [ebp+var_4]
        call    sub_402E5C
        retn

即上面的两个call sub_4040B8分别等价于
      encrypt_decrypt(m1, e, n)
      encrypt_decrypt(m2, e, n)
只需要把sub_4040B8的函数体和上面的算法伪码描述对照一下就明白为什么等价了（注意windows优化大师使用的是64 bit的运算，每个数要用两个32 bit的数来表示，因此操作每个64 bit的数至少要两条指令）：

sub_4040B8    proc near

var_8        = dword    ptr -8    //局部变量c的低位（c中将存放返回值）
var_4        = dword    ptr -4    //局部变量c的高位
arg_0        = dword    ptr  8      //m的低32位
arg_4        = dword    ptr  0Ch    //m的高32位
arg_8        = dword    ptr  10h    //e的低32位
arg_C        = dword    ptr  14h    //e的高32位
arg_10        = dword    ptr  18h  //n的低32位
arg_14        = dword    ptr  1Ch  //n的高32位

        push    ebp
        mov    ebp, esp
        add    esp, 0FFFFFFF8h
        mov    [ebp+var_8], 1    // c = 1;
        mov    [ebp+var_4], 0
        jmp    short loc_40414A

loc_4040CE:

        push    0
        push    2
        mov    eax, [ebp+arg_8]
        mov    edx, [ebp+arg_C]
        call    __LLMOD          //b mod 2
        cmp    edx, 0
        jnz    short loc_40411B
        cmp    eax, 0
        jnz    short loc_40411B
        push    0
        push    2
        mov    eax, [ebp+arg_8]
        mov    edx, [ebp+arg_C]
        call    __LLDIV          // b = b / 2
        mov    [ebp+arg_8], eax
        mov    [ebp+arg_C], edx
        push    [ebp+arg_14]
        push    [ebp+arg_10]
        push    [ebp+arg_14]
        push    [ebp+arg_10]
        push    [ebp+arg_4]
        push    [ebp+arg_0]
        call    sub_404060      // a = (a * a) mod n
        mov    [ebp+arg_10], eax
        mov    [ebp+arg_14], edx
        jmp    short loc_40414A

loc_40411B:

        mov    eax, [ebp+arg_8]
        mov    edx, [ebp+arg_C]
        sub    eax, 1            // b = b - 1
        sbb    edx, 0
        mov    [ebp+arg_8], eax
        mov    [ebp+arg_C], edx
        push    [ebp+arg_14]
        push    [ebp+arg_10]
        push    [ebp+var_4]
        push    [ebp+var_8]
        push    [ebp+arg_4]
        push    [ebp+arg_0]
        call    sub_404060    //c = (a * c) mod n
        mov    [ebp+var_8], eax
        mov    [ebp+var_4], edx

loc_40414A:
        cmp    [ebp+arg_C], 0    //b等于0吗？
        jnz    short loc_40415C
        cmp    [ebp+arg_8], 0
        ja    loc_4040CE        //继续循环
        jmp    short loc_404162 

loc_40415C:
        jg    loc_4040CE        //继续循环

loc_404162:
        mov    eax, [ebp+var_8]  //返回值c
        mov    edx, [ebp+var_4]
        pop    ecx
        pop    ecx
        pop    ebp
        retn    18h
sub_4040B8    endp

至此我们已经搞清其加密算法，且得到如下结果：
e = 0x000000003B442AF9
n = 0x0000000069AAA0E3
剩下的事情就是对n进行因子分解，写出注册机.