【破文标题】RSA算法初探
【破文作者】逍遥风
【破解工具】od，
【破解平台】winxp
----------------------------------------------------------------------
一个标准的RSA算法练习的CRACKME。没有加壳之类的保护措施，很容易分析
用OD载入这个CRACKME
在命令行下断点：bp GetDlgItemTextA:
任意输入注册信息后程序中断在这里：
004137FE |. FF15 10894200 call [<&USER32.GetDlgItemTex>; \GetDlgItemTextA
00413804 |. EB 13 jmp short 00413819 ; 取注册码的位数
00413806 |> FF75 10 push dword ptr [ebp+10]
。。。
00413819 |> \5D pop ebp
0041381A \. C2 0C00 retn 0C
运行到这里返回，返回到这里
00402871 . E8 720F0100 call 004137E8 ; \取输入的注册码
00402876 . 8D4C24 24 lea ecx, [esp+24] ; 使ECX等于输入的注册码
0040287A . 51 push ecx ; /Arg1
0040287B . 8BCB mov ecx, ebx ; |
0040287D . E8 2E010000 call 004029B0 ; \关键CALL跟进
00402882 . 85C0 test eax, eax ; 标志位检查
00402884 . 0F84 88000000 je 00402912 ; 相等就注册成功
跟进关键CALL
004029B0 /$ 6A FF push -1 ; 来到这里
004029B2 |. 68 189E4100 push 00419E18
省略一些代码。。。
004029CD |. 68 DC004200 push 004200DC ; 9901
004029D2 |. 8D8C24 E40000>lea ecx, [esp+E4] ; RSA计算的e
004029D9 |. E8 52E7FFFF call 00401130 ; 取数字9901
** 注意这里的数字9901就是后面RSA计算所需要的e **
004029DE |. 68 D0004200 push 004200D0 ; 12790891
004029E3 |. 8D4C24 1C lea ecx, [esp+1C] ; RSA计算的n
004029E7 |. C78424 640600>mov dword ptr [esp+664], 0
004029F2 |. E8 39E7FFFF call 00401130 ; 取数字12790891
** 注意这里的数字12790891就是后面RSA计算所需要的n **
004029F7 |. 68 C8004200 push 004200C8 ; 8483678
004029FC |. 8D8C24 740200>lea ecx, [esp+274] ; 将数字8483678设为A
00402A03 |. C68424 640600>mov byte ptr [esp+664], 1
00402A0B |. E8 20E7FFFF call 00401130 ; 取数字8483678
00402A10 |. 68 C0004200 push 004200C0 ; 5666933
00402A15 |. 8D8C24 AC0100>lea ecx, [esp+1AC] ; 将数字5666933设为B
00402A1C |. C68424 640600>mov byte ptr [esp+664], 2
00402A24 |. E8 07E7FFFF call 00401130 ; 取数字5666933
数字A，B与RSA计算无关，但另有它用。
现在得到了RSA计算最关键的e,n。下面就开始对注册信息进行处理：
------------------------------------------------------------
00402A29 |. 8B9424 680600>mov edx, [esp+668] ; 使EDX等于输入的注册码
00402A30 |. 83CE FF or esi, FFFFFFFF
00402A33 |. 8BFA mov edi, edx ; 使EDI=EDX=输入的注册码
00402A35 |. 8BCE mov ecx, esi
00402A37 |. 33C0 xor eax, eax
00402A39 |. C68424 600600>mov byte ptr [esp+660], 3
00402A41 |. F2:AE repne scas byte ptr es:[edi]
00402A43 |. F7D1 not ecx
00402A45 |. 49 dec ecx
00402A46 |. 83F9 0E cmp ecx, 0E ; 比较输入的注册码的位数是否等于14位
00402A49 |. 0F85 63010000 jnz 00402BB2 ; 注册码不等于14位就跳向失败
00402A4F |. 33C9 xor ecx, ecx ; 清空ECX，开始格式检验
00402A51 |> 8A0411 /mov al, [ecx+edx] ; 取输入注册码的每一位进行格式检验
00402A54 |. 3C 30 |cmp al, 30 ; 与0比较/
00402A56 |. 0F8C 56010000 |jl 00402BB2 ; 小于0就错误
00402A5C |. 3C 39 |cmp al, 39 ; 与9比较
00402A5E |. 0F8F 4E010000 |jg 00402BB2 ; 大于9就错误
00402A64 |. 41 |inc ecx ; 每检查一位ECX中的值加1
00402A65 |. 83F9 0E |cmp ecx, 0E ; 检查14位
00402A68 |.^ 7C E7 \jl short 00402A51 ; 循环检验输入的注册码的每一位都必须是数字
00402A6A |. 8BC2 mov eax, edx ; 经过检验使EAX等于输入的注册码
检查输入的注册码。
输入的注册码必须满足两个条件：
1）注册码必须为14位。2）注册码的每一位必须是数字。
经过了格式验证，下面就要选取合适的信息进行加密了，就是说该选定加密对像了
文章作者逍遥风，写于看雪论坛呵呵!学nbw大哥的防盗版技术
注意：以下以注册码12345678901234为例进行说明。
------------------------------------------------------------
00402A6C |. C64424 17 00 mov byte ptr [esp+17], 0
00402A71 |. C64424 0F 00 mov byte ptr [esp+F], 0
省略一些代码。。。
00402A8F |. 884424 16 mov [esp+16], al
00402A93 |. 8D42 07 lea eax, [edx+7] ; 使EAX等于注册码的后7位
00402A96 |. 8D4C24 10 lea ecx, [esp+10] ; 使ECX等于注册码的前7位
这里将输入的14位注册码按7位一组分成了2组
1~7位第一组，8~14位第2组。
可以想到程序是对这2组数据分别进行加密的，当然这只是猜测。到底是如何
计算的还得看后面的代码
-------------------------------------------------------------
00402AB2 |. E8 79E6FFFF call 00401130 ; 取数字12790891
00402AB7 |. 8D5424 18 lea edx, [esp+18] ; 使EDX等于12790891
00402ABB |. 8D8424 E00000>lea eax, [esp+E0] ; 使EAX等于数字9901
00402AC2 |. 52 push edx ; /取n=12790891准备计算
00402AC3 |. 8D8C24 040400>lea ecx, [esp+404] ; |
00402ACA |. 50 push eax ; |取e=9901准备计算
00402ACB |. 51 push ecx ; |Arg1
00402ACC |. 8D8C24 9C0500>lea ecx, [esp+59C] ; |取注册码前7位1234567准备计算
00402AD3 |. C68424 6C0600>mov byte ptr [esp+66C], 4 ; |
00402ADB |. E8 30F8FFFF call 00402310 ; \进行RSA计算
00402AE0 |. 8D5424 08 lea edx, [esp+8] ; 计算结果设为C1=821602
先分别取出了埋藏已久的e（9901）和n（12790891），又取了注册码的第一部分（前七位1234567）
进行了RSA计算，并得到了结果C1
C1=1234567^9901（mod 12790891）=821602
-----------------------------------------------------------------
00402AF4 |. E8 37E6FFFF call 00401130 ; 取注册码的后7位8901234
00402AF9 |. 8D4424 18 lea eax, [esp+18] ; 使EAX=12790891
00402AFD |. 8D8C24 E00000>lea ecx, [esp+E0] ; 使ECX=9901
00402B04 |. 50 push eax ; /取n=12790891准备计算
00402B05 |. 8D9424 CC0400>lea edx, [esp+4CC] ; |
00402B0C |. 51 push ecx ; |取e=9901准备计算
00402B0D |. 52 push edx ; |取注册码后7位8901234准备计算
00402B0E |. 8D8C24 440300>lea ecx, [esp+344] ; |
00402B15 |. C68424 6C0600>mov byte ptr [esp+66C], 6 ; |
00402B1D |. E8 EEF7FFFF call 00402310 ; \进行RSA计算
00402B22 |. 8D8424 700200>lea eax, [esp+270] ; 结果设为C2=5041268
同上：取e与n后再取注册码的后7位，进行RSA计算。并得到C2
C2=8901234^9901（mod 12790891）=5041268
经过两步计算，已经得到了加密的结果，但是又进行怎样的验证呢
--------------------------------------------------------------------
00402B29 |. 8D8C24 000400>lea ecx, [esp+400] ; ECX等于C1=821602
00402B30 |. 50 push eax ; 取数字A=8483678
00402B31 |. C68424 640600>mov byte ptr [esp+664], 7
00402B39 |. E8 82F2FFFF call 00401DC0 ; 将A与C1进行比较
00402B3E |. 85C0 test eax, eax ; 标志位检查
00402B40 |. 0F84 BF000000 je 00402C05 ; A与C1相等就跳向成功
00402B46 |. 8D8C24 A80100>lea ecx, [esp+1A8] ; 使ECX等于数字B=5666933
00402B4D |. 51 push ecx
00402B4E |. 8D8C24 CC0400>lea ecx, [esp+4CC] ; 使ECX等于计算结果C2
00402B55 |. E8 66F2FFFF call 00401DC0 ; 将B与C2进行比较
00402B5A |. 85C0 test eax, eax ; 标志位检查
00402B5C |. 0F84 A3000000 je 00402C05 ; B与C2相等就跳向成功
原来这个CRACKME的最后验证过程是
用C1与定值A=8483678，进行比较。用C2与定值B=5666933，进行比较
如果比较的结果满足C1=A，C2=B就注册成功了。
由于A和B已知即C1，C2已知。
要求出加密前的值就要用到RSA的解密算法了。
加密:c=m^e mod n;
解密:m=c^d mod n.
目前已知条件还有e=9901,n=12790891。
先分解n
得到：p = 1667 和q = 7673。
再求出d
ed=mod((p-1)(q-1)),用工具得到d=10961333
现在根据解密算法：
可以得到：m= c^d （mod n）
m1=8483678^10961333 (mod 12790891) = 7167622
所以注册码的前7位就是7167622
同理
m2=5666933^10961333 (mod 12790891)= 3196885
所以：正确的注册码就是71676223196885，与注册名无关。
(相关的工具论坛都有下载)
----------------------------------------------------------------------
注意：CRACKME有个小BUG，作者的本意可能是
计算结果满足C1=A，C2=B才能注册成功了，但实际上只要C1=A，且满足14位就可以了
也就是说注册码第一部分必须是7167622但后面7位任意
----------------------------------------------------------------------
【版权声明】本文只为交流，转载请保留作者及文章完整性。
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
