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进行因子分解，写出注册机.
--------------------------------------------------------------------------------
|