【破解作者】
ryosuke
【原贴】
http://bbs.pediy.com/showthread.php?threadid=26514
【分析】
cnbragon兄的keygenme用到了ECC和SHA，采用miracl库，我是通过手工定位的方法，分析程序中使用的miracl函数的。分析如下:
004010A0 81EC 74050000 sub esp, 574
004010A6 53 push ebx
004010A7 55 push ebp
004010A8 56 push esi
004010A9 57 push edi
004010AA 6A 10 push 10
004010AC 68 20030000 push 320
004010B1 E8 AA0B0000 call 00401C60 ; mirsys(0x320,0x10)
004010B6 8B0D A4004100 mov ecx, [4100A4] ; 544352
004010BC 894424 24 mov [esp+24], eax ; miracl*
004010C0 A1 A0004100 mov eax, [4100A0] ; 26425069
004010C5 894C24 38 mov [esp+38], ecx
004010C9 894424 34 mov [esp+34], eax
004010CD B9 31000000 mov ecx, 31
004010D2 33C0 xor eax, eax
004010D4 8DBC24 05010000 lea edi, [esp+105]
004010DB C68424 04010000>mov byte ptr [esp+104], 0
004010E3 C68424 94020000>mov byte ptr [esp+294], 0
004010EB F3:AB rep stos dword ptr es:[edi]
004010ED 66:AB stos word ptr es:[edi]
004010EF AA stos byte ptr es:[edi]
004010F0 B9 31000000 mov ecx, 31
004010F5 33C0 xor eax, eax
004010F7 8DBC24 95020000 lea edi, [esp+295]
004010FE C64424 3C 00 mov byte ptr [esp+3C], 0
00401103 F3:AB rep stos dword ptr es:[edi]
00401105 66:AB stos word ptr es:[edi]
00401107 AA stos byte ptr es:[edi]
00401108 B9 31000000 mov ecx, 31
0040110D 33C0 xor eax, eax
0040110F 8D7C24 3D lea edi, [esp+3D]
00401113 C68424 5C030000>mov byte ptr [esp+35C], 0
0040111B F3:AB rep stos dword ptr es:[edi]
0040111D 66:AB stos word ptr es:[edi]
0040111F AA stos byte ptr es:[edi]
00401120 B9 31000000 mov ecx, 31
00401125 33C0 xor eax, eax
00401127 8DBC24 5D030000 lea edi, [esp+35D]
0040112E C68424 CC010000>mov byte ptr [esp+1CC], 0
00401136 F3:AB rep stos dword ptr es:[edi]
00401138 66:AB stos word ptr es:[edi]
0040113A AA stos byte ptr es:[edi]
0040113B B9 31000000 mov ecx, 31
00401140 33C0 xor eax, eax
00401142 8DBC24 CD010000 lea edi, [esp+1CD]
00401149 8B9C24 90050000 mov ebx, [esp+590]
00401150 F3:AB rep stos dword ptr es:[edi]
00401152 8B35 B8F04000 mov esi, [<&user32.GetDlgItemTextA>] ; user32.GetDlgItemTextA
00401158 83C4 08 add esp, 8
0040115B 8D9424 FC000000 lea edx, [esp+FC]
00401162 66:AB stos word ptr es:[edi]
00401164 68 C9000000 push 0C9
00401169 52 push edx
0040116A 68 E8030000 push 3E8
0040116F 53 push ebx
00401170 AA stos byte ptr es:[edi] ; 上面都是初始化数据
00401171 FFD6 call esi ; 得到name
00401173 8DBC24 FC000000 lea edi, [esp+FC]
0040117A 83C9 FF or ecx, FFFFFFFF
0040117D 33C0 xor eax, eax
0040117F F2:AE repne scas byte ptr es:[edi]
00401181 F7D1 not ecx
00401183 49 dec ecx ; name长度
00401184 0F84 03040000 je 0040158D
0040118A 8D4424 34 lea eax, [esp+34]
0040118E 68 C9000000 push 0C9
00401193 50 push eax
00401194 68 E9030000 push 3E9
00401199 53 push ebx
0040119A FFD6 call esi
0040119C 8BE8 mov ebp, eax
0040119E 85ED test ebp, ebp
004011A0 0F84 E7030000 je 0040158D
004011A6 8D4C24 34 lea ecx, [esp+34] ; 这个是serial
004011AA 6A 2D push 2D
004011AC 51 push ecx
004011AD E8 8E8F0000 call 0040A140 ; 格式验证有'-'
004011B2 83C4 08 add esp, 8
004011B5 85C0 test eax, eax
004011B7 0F84 D0030000 je 0040158D
004011BD 8D5424 34 lea edx, [esp+34]
004011C1 6A 2D push 2D
004011C3 52 push edx
004011C4 E8 778F0000 call 0040A140
004011C9 8BF8 mov edi, eax
004011CB 8D4424 3C lea eax, [esp+3C]
004011CF 2BF8 sub edi, eax ; 计算'-'的位置
004011D1 8A4424 3C mov al, [esp+3C]
004011D5 83C4 08 add esp, 8
004011D8 33F6 xor esi, esi
004011DA 84C0 test al, al
004011DC 74 45 je short 00401223
004011DE 3BF7 cmp esi, edi ; edi -的未知
004011E0 74 38 je short 0040121A
004011E2 833D 1C0F4100 0>cmp dword ptr [410F1C], 1 ; 标准=1
004011E9 7E 15 jle short 00401200
004011EB 0FBE4C34 34 movsx ecx, byte ptr [esp+esi+34]
004011F0 68 80000000 push 80
004011F5 51 push ecx
004011F6 E8 B38E0000 call 0040A0AE
004011FB 83C4 08 add esp, 8
004011FE EB 12 jmp short 00401212
00401200 0FBE5434 34 movsx edx, byte ptr [esp+esi+34] ; 取serial前
00401205 A1 100D4100 mov eax, [410D10]
0040120A 8A0450 mov al, [eax+edx*2]
0040120D 25 80000000 and eax, 80
00401212 85C0 test eax, eax
00401214 0F84 73030000 je 0040158D
0040121A 8A4434 35 mov al, [esp+esi+35]
0040121E 46 inc esi
0040121F 84C0 test al, al
00401221 ^ 75 BB jnz short 004011DE
00401223 8D4C24 34 lea ecx, [esp+34] ; 序列号
00401227 57 push edi
00401228 8D9424 58030000 lea edx, [esp+358]
0040122F 51 push ecx
00401230 52 push edx
00401231 E8 7A8D0000 call 00409FB0 ; 保存'-'之前的数据
00401236 2BEF sub ebp, edi ; 计算剩余长度
00401238 8D443C 41 lea eax, [esp+edi+41] ; 剩余数据
0040123C 4D dec ebp
0040123D 8D8C24 D0010000 lea ecx, [esp+1D0]
00401244 55 push ebp
00401245 50 push eax
00401246 51 push ecx
00401247 E8 648D0000 call 00409FB0 ; 保存剩余数据
0040124C 8B5424 34 mov edx, [esp+34]
00401250 6A 00 push 0
00401252 C782 34020000 1>mov dword ptr [edx+234], 10
0040125C E8 DF070000 call 00401A40 ; x=mirvar(0)
00401261 8BE8 mov ebp, eax
00401263 6A 00 push 0
00401265 896C24 3C mov [esp+3C], ebp ; 保存x
00401269 E8 D2070000 call 00401A40 ; sn=mirvar(0)
0040126E 6A 00 push 0
00401270 8BF0 mov esi, eax ; 保存sn
00401272 E8 C9070000 call 00401A40 ; n=mirvar(0)
00401277 8BF8 mov edi, eax
00401279 68 90004100 push 00410090 ; dc3685f90267
0040127E 57 push edi ; n
0040127F E8 5C630000 call 004075E0 ; cinstr
00401284 8D8424 80030000 lea eax, [esp+380]
0040128B 50 push eax ; 前面几位送x
0040128C 55 push ebp ; x
0040128D E8 4E630000 call 004075E0 ; x=cinstr
00401292 8D8C24 F8010000 lea ecx, [esp+1F8]
00401299 51 push ecx
0040129A 56 push esi
0040129B E8 40630000 call 004075E0 ; sn是后面几位
004012A0 57 push edi ; x
004012A1 55 push ebp ; n
004012A2 E8 99160000 call 00402940 ; 比较x,n大小,x<n
004012A7 83C4 44 add esp, 44
004012AA 83F8 01 cmp eax, 1
004012AD 0F84 DA020000 je 0040158D
004012B3 57 push edi
004012B4 56 push esi
004012B5 E8 86160000 call 00402940 ; 后面位数比较
004012BA 83C4 08 add esp, 8
004012BD 83F8 01 cmp eax, 1
004012C0 0F84 C7020000 je 0040158D
004012C6 8D9424 1C040000 lea edx, [esp+41C]
004012CD 52 push edx
004012CE E8 DD5F0000 call 004072B0 ; SHA初始话
004012D3 83C4 04 add esp, 4
004012D6 8D8424 FC000000 lea eax, [esp+FC]
004012DD 33DB xor ebx, ebx
004012DF 50 push eax
004012E0 FF15 00F04000 call [<&kernel32.lstrlen>] ; kernel32.lstrlenA
004012E6 85C0 test eax, eax ; name长度
004012E8 7E 2C jle short 00401316
004012EA 0FBE8C1C FC0000>movsx ecx, byte ptr [esp+ebx+FC]
004012F2 8D9424 1C040000 lea edx, [esp+41C]
004012F9 51 push ecx ; 挨个取name
004012FA 52 push edx
004012FB E8 F05F0000 call 004072F0 ; SHA变换
00401300 83C4 08 add esp, 8
00401303 8D8424 FC000000 lea eax, [esp+FC] ; name
0040130A 43 inc ebx
0040130B 50 push eax ; name
0040130C FF15 00F04000 call [<&kernel32.lstrlen>] ; kernel32.lstrlenA
00401312 3BD8 cmp ebx, eax
00401314 ^ 7C D4 jl short 004012EA
00401316 33DB xor ebx, ebx
00401318 0FBE4C1C 2C movsx ecx, byte ptr [esp+ebx+2C]
0040131D 8D9424 1C040000 lea edx, [esp+41C]
00401324 51 push ecx
00401325 52 push edx
00401326 E8 C55F0000 call 004072F0 ; SHA变换
0040132B 83C4 08 add esp, 8
0040132E 43 inc ebx
0040132F 83FB 07 cmp ebx, 7
00401332 ^ 7C E4 jl short 00401318
00401334 8D8424 8C020000 lea eax, [esp+28C]
0040133B 8D8C24 1C040000 lea ecx, [esp+41C]
00401342 50 push eax
00401343 51 push ecx
00401344 E8 F7610000 call 00407540 ; sha(name+iPB&RCT)
00401349 6A 00 push 0
0040134B E8 F0060000 call 00401A40 ; hash=mirvar(0)
00401350 8BD8 mov ebx, eax ; 保存hash
00401352 8D9424 98020000 lea edx, [esp+298] ; sha结果
00401359 53 push ebx
0040135A 52 push edx
0040135B 6A 14 push 14
0040135D 895C24 44 mov [esp+44], ebx
00401361 E8 CA5D0000 call 00407130 ; bytes_to_big(0x14,sha_result,hash)
00401366 56 push esi
00401367 56 push esi
00401368 56 push esi
00401369 57 push edi ; n
0040136A 56 push esi ; sn
0040136B E8 504D0000 call 004060C0 ; xgcd(sn,n,sn,sn,sn) 计算sn^-1
00401370 6A 00 push 0
00401372 E8 C9060000 call 00401A40 ; mirvar(0)
00401377 6A 00 push 0
00401379 894424 5C mov [esp+5C], eax ; var e
0040137D E8 BE060000 call 00401A40 ; mirvar(0)
00401382 894424 54 mov [esp+54], eax ; var f
00401386 8B4424 5C mov eax, [esp+5C] ; e
0040138A 50 push eax ; e
0040138B 57 push edi ; n
0040138C 57 push edi ; n
0040138D 56 push esi ; sn^-1
0040138E 56 push esi ; sn^-1
0040138F 53 push ebx ; sha_result hash
00401390 E8 6B2E0000 call 00404200 ; mad 计算sha_result*sn^-1 mod n
00401395 8B4C24 6C mov ecx, [esp+6C]
00401399 83C4 4C add esp, 4C
0040139C 51 push ecx ; f
0040139D 57 push edi ; n
0040139E 57 push edi
0040139F 56 push esi ; b^-1
004013A0 56 push esi
004013A1 55 push ebp
004013A2 E8 592E0000 call 00404200 ; mad x*sn^-1 mod n
004013A7 6A 00 push 0
004013A9 E8 92060000 call 00401A40 ; g=mirval(0)
004013AE 6A 00 push 0
004013B0 8BD8 mov ebx, eax ; g
004013B2 E8 89060000 call 00401A40 ; h=mirval(0)
004013B7 68 AABD0000 push 0BDAA
004013BC 894424 48 mov [esp+48], eax ; h
004013C0 E8 7B060000 call 00401A40 ; a=mirval(bdaa)
004013C5 68 6F990000 push 996F
004013CA 894424 38 mov [esp+38], eax ; a
004013CE E8 6D060000 call 00401A40 ; b=mirval(996f)
004013D3 6A 00 push 0
004013D5 894424 44 mov [esp+44], eax ; b
004013D9 E8 62060000 call 00401A40 ; p=mirval(0)
004013DE 68 80004100 push 00410080 ; abef29bf2bd2a27
004013E3 53 push ebx ; g
004013E4 8BE8 mov ebp, eax ; p
004013E6 E8 F5610000 call 004075E0 ; cinstr(g,"abef29bf2bd2a27")
004013EB 8B5424 58 mov edx, [esp+58]
004013EF 68 6C004100 push 0041006C ; 30484100d4143f7c
004013F4 52 push edx ; h
004013F5 E8 E6610000 call 004075E0 ; cinstr(h,"30484100d4143f7c")
004013FA 68 58004100 push 00410058 ; 985ef1df49354377
004013FF 55 push ebp ; p
00401400 E8 DB610000 call 004075E0 ; cinstr(p,"985ef1df49354377")
00401405 8B4424 5C mov eax, [esp+5C] ; b
00401409 8B4C24 54 mov ecx, [esp+54] ; a
0040140D 83C4 44 add esp, 44
00401410 6A 00 push 0 ; MR_PROJECTIVE
00401412 55 push ebp ; p
00401413 50 push eax ; b
00401414 51 push ecx ; a
00401415 E8 F62E0000 call 00404310 ; ecurve_init(a,b,p,MR_PROJECTIVE)
0040141A E8 711B0000 call 00402F90 ; epoint_init
0040141F 894424 20 mov [esp+20], eax ; G
00401423 E8 681B0000 call 00402F90 ; epoint_init
00401428 894424 24 mov [esp+24], eax ; K
0040142C E8 5F1B0000 call 00402F90 ; epoint_init
00401431 8B5424 20 mov edx, [esp+20] ; G
00401435 8BE8 mov ebp, eax ; p3
00401437 52 push edx ; G
00401438 6A 00 push 0
0040143A 53 push ebx
0040143B 53 push ebx ; g
0040143C E8 2F310000 call 00404570 ; epoint_set(g,g,0,G)
00401441 8B4424 34 mov eax, [esp+34]
00401445 50 push eax ; p2
00401446 8B4424 48 mov eax, [esp+48]
0040144A 6A 00 push 0
0040144C 50 push eax ; 30484100d4143f7c
0040144D 50 push eax
0040144E E8 1D310000 call 00404570 ; epoint_set(h,h,0,K)
00401453 8B4C24 44 mov ecx, [esp+44] ; G
00401457 8B5424 50 mov edx, [esp+50] ; f
0040145B 8B4424 40 mov eax, [esp+40] ; G
0040145F 55 push ebp ; p3
00401460 51 push ecx ; K
00401461 8B4C24 60 mov ecx, [esp+60] ; e
00401465 52 push edx ; f
00401466 50 push eax ; G
00401467 51 push ecx ; e
00401468 E8 D3470000 call 00405C40 ; ecurve_mult2(e,G,f,K,p3) p3=e*G+f*K
0040146D 83C4 44 add esp, 44
00401470 55 push ebp ; p3
00401471 E8 FA1A0000 call 00402F70
00401476 83C4 04 add esp, 4
00401479 83F8 01 cmp eax, 1
0040147C 74 35 je short 004014B3
0040147E 6A 00 push 0
00401480 E8 BB050000 call 00401A40 ; mirvar(0)
00401485 50 push eax ; l
00401486 50 push eax ; l
00401487 55 push ebp ; p3
00401488 894424 28 mov [esp+28], eax
0040148C E8 9F320000 call 00404730 ; epoint_get(p3,l,l)得到p3的x坐标
00401491 8B5424 28 mov edx, [esp+28] ; l
00401495 57 push edi ; n
00401496 57 push edi ; n
00401497 52 push edx ; l
00401498 E8 73230000 call 00403810 ; divide(l,n,n) 坐标x mod n
0040149D 8B4424 38 mov eax, [esp+38]
004014A1 8B4C24 34 mov ecx, [esp+34]
004014A5 50 push eax ; x
004014A6 51 push ecx ; l
004014A7 E8 94140000 call 00402940 ; 比较大小
004014AC 83C4 24 add esp, 24
004014AF 85C0 test eax, eax
004014B1 74 42 je short 004014F5
004014B3 8B9424 88050000 mov edx, [esp+588]
004014BA 68 48004100 push 00410048 ; wrong serial!
可以看出这个keygen是个ecc验证过程，过程如下。
1、从用户输入的序列号中，提取sn以及x’；
2、将用户名作为参数，计算Hash=SHA(username)；
3、计算 R=(Hash*G+x’*K)/sn，如果sn、Hash正确,其值等于R(x,y)，因为
sn≡(Hash+x’*k)/r (mod n)
4、xR≡x (mod n)
5、如果xR=x’ 则注册成功。如果xR≠x’ ，则注册失败。
破解过程就是:
1、椭圆曲线Ep(a,b)，和基点G；(a,b,G见程序上面注解)
2、选择私有密钥k（k<n），利用基点G计算公开密钥K=kG； （关键所在，找到k)
3、产生一个随机整数r（r<n），计算点R(x,y)=rG；
4、将用户名作为参数，计算Hash=SHA(username)；
5、计算 x’=x (mod n)
6、计算sn≡(Hash+x’*k)/r (mod n)
7、将sn和x’作为 用户名username的序列号
程序中
big a=mirvar(0xBDAA);
big b=mirvar(0x996F);
big p=mirvar(0);
char* strp="985EF1DF49354377";
cinstr(p,strp);
表示的椭圆方程:y^2=x^3+a*x+b mod p
G点
big g=mirvar(0);
char* strg="ABEF29BF2BD2A27";
cinstr(g,strg);
epoint_set(g,g,0,G);
K点
big h=mirvar(0);
char* strh="30484100D4143F7C";
cinstr(h,strh);
epoint_set(h,h,0,K);
k的计算先用到了SEA算法，找G的阶。
G的阶是10979478881483589806=2*7*41*79*242126734033511
找到G阶后，通过Pollard-Rho算法，计算k，计算出来的k是45CA6906B47E57B
找到key,破解过程也就完成了，注册机算法完全按照上面编写，请看源代码，用到miracl库编程。
我的注册号：
name:nightfox
serial:3A75BD7A817D-C45DDA935B9F
【总结】
cnbragon兄的keygenme很不错，又复习了一遍ecc，呵呵，破解起来很有意思，谢谢cnbragon兄，也谢谢看到这里的你。
[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)
楼主的数学基础也很扎实啊
