HappyTowns 30th CrackMe 算法分析及注册机
很早以前就放出来的一个CrackMe，是关于算法方面的，我比较感兴趣，所以就研究了下。
使用了Miracl大数运算库，逆向的难度不大。算法是求解二次剩余问题，有一定的难度。
用PEiD查壳，显示
Microsoft Visual C++ 6.0
经验证，确实没有加壳。
用PEiD的Krypto ANAlyzer插件检查，结果如下：
SHA1 [Compress] :: 00004C71 :: 00404C71
{Big number} :: 0000B0D4 :: 0040B0D4
{Big number} :: 0000B118 :: 0040B118
用IDA载入，并加载常用的sig。找到注册验证的关键函数，初步分析的结果如下：
.text:00401130 ; int __cdecl OnCheck(HWND hDlg)
.text:00401130 OnCheck proc near ; CODE XREF: DialogFunc+61p
.text:00401130
.text:00401130 ba = dword ptr -958h
.text:00401130 bc = dword ptr -954h
.text:00401130 be = dword ptr -950h
.text:00401130 hash_out = dword ptr -94Ch
.text:00401130 var_947 = dword ptr -947h
.text:00401130 var_943 = dword ptr -943h
.text:00401130 var_93F = dword ptr -93Fh
.text:00401130 var_93B = word ptr -93Bh
.text:00401130 var_939 = byte ptr -939h
.text:00401130 Serial = byte ptr -938h
.text:00401130 Serial_1 = dword ptr -744h
.text:00401130 Serial_2 = dword ptr -550h
.text:00401130 Name = byte ptr -35Ch
.text:00401130 sha_ctx = dword ptr -168h
.text:00401130 hDlg = dword ptr 4
.text:00401130
.text:00401130 sub esp, 958h
.text:00401136 push ebx
.text:00401137 push ebp
.text:00401138 push esi
.text:00401139 push edi
.text:0040113A mov ecx, 124
.text:0040113F xor eax, eax
.text:00401141 lea edi, [esp+60Dh]
.text:00401148 mov [esp+968h+Name], 0
.text:00401150 rep stosd
.text:00401152 stosw
.text:00401154 stosb
.text:00401155 mov ecx, 124
.text:0040115A xor eax, eax
.text:0040115C lea edi, [esp+31h]
.text:00401160 mov [esp+968h+Serial], 0
.text:00401165 rep stosd
.text:00401167 stosw
.text:00401169 stosb
.text:0040116A mov ecx, 124
.text:0040116F xor eax, eax
.text:00401171 lea edi, [esp+968h+Serial_1+1]
.text:00401178 mov byte ptr [esp+968h+Serial_1], 0
.text:00401180 rep stosd
.text:00401182 stosw
.text:00401184 stosb
.text:00401185 mov ecx, 124
.text:0040118A xor eax, eax
.text:0040118C lea edi, [esp+968h+Serial_2+1]
.text:00401193 mov byte ptr [esp+968h+Serial_2], 0
.text:0040119B rep stosd
.text:0040119D stosw
.text:0040119F stosb
.text:004011A0 xor eax, eax
.text:004011A2 push 10h
.text:004011A4 mov [esp+96Ch+hash_out+1], eax
.text:004011A8 push 320h
.text:004011AD mov [esp+970h+var_947], eax
.text:004011B1 mov byte ptr [esp+970h+hash_out], 0
.text:004011B6 mov [esp+970h+var_943], eax
.text:004011BA mov [esp+970h+var_93F], eax
.text:004011BE mov [esp+970h+var_93B], ax
.text:004011C3 mov [esp+970h+var_939], al
以上是初始化几个数组变量：szName[500]，szSerial[500]，szSerial1[500]，szSerial2[500]，
hash_out[20]。
.text:004011C7 call _mirsys
.text:004011CC push 0
.text:004011CE mov dword ptr [eax+234h], 16
.text:004011D8 call _mirvar
.text:004011DD push 0
.text:004011DF mov ebx, eax
.text:004011E1 call _mirvar
.text:004011E6 push 0
.text:004011E8 mov [esp+97Ch+be], eax
.text:004011EC call _mirvar
.text:004011F1 push 0
.text:004011F3 mov ebp, eax
.text:004011F5 call _mirvar
.text:004011FA push 0
.text:004011FC mov [esp+984h+bc], eax
.text:00401200 call _mirvar
.text:00401205 mov esi, [esp+984h+hDlg]
.text:0040120C mov edi, ds:GetDlgItemTextA
.text:00401212 add esp, 1Ch
.text:00401215 lea ecx, [esp+968h+Name]
.text:0040121C mov [esp+968h+ba], eax
.text:00401220 push 501 ; nMaxCount
.text:00401225 push ecx ; lpString
.text:00401226 push 1000 ; nIDDlgItem
.text:0040122B push esi ; hDlg
.text:0040122C call edi ; GetDlgItemTextA ; 取用户名
.text:0040122E cmp eax, 2
.text:00401231 jb to_exit
.text:00401237 lea edx, [esp+968h+Serial]
.text:0040123B push 501 ; nMaxCount
.text:00401240 push edx ; lpString
.text:00401241 push 1001 ; nIDDlgItem
.text:00401246 push esi ; hDlg
.text:00401247 call edi ; GetDlgItemTextA ; 取注册码
.text:00401249 lea eax, [esp+968h+Serial]
.text:0040124D push '-' ; int
.text:0040124F push eax ; char *
.text:00401250 call _strchr
.text:00401255 add esp, 8
.text:00401258 test eax, eax
.text:0040125A jz to_exit
.text:00401260 mov cl, [esp+968h+Serial]
.text:00401264 cmp cl, '-'
.text:00401267 jz short loc_40127C
.text:00401269 xor eax, eax
.text:0040126B
.text:0040126B loc_40126B: ; CODE XREF: OnCheck+14Aj
.text:0040126B mov byte ptr [esp+eax+968h+Serial_1], cl
.text:00401272 mov cl, [esp+eax+31h]
.text:00401276 inc eax
.text:00401277 cmp cl, '-'
.text:0040127A jnz short loc_40126B
.text:0040127C
.text:0040127C loc_40127C: ; CODE XREF: OnCheck+137j
.text:0040127C lea ecx, [esp+968h+Serial]
.text:00401280 push '-' ; int
.text:00401282 push ecx ; char *
.text:00401283 call _strchr
.text:00401288 lea edx, [esp+970h+Serial]
.text:0040128C add esp, 8
.text:0040128F sub eax, edx
.text:00401291 mov cl, [esp+eax+968h+Serial]
.text:00401295 lea eax, [esp+eax+968h+Serial]
.text:00401299 test cl, cl
.text:0040129B jz short loc_4012B2
.text:0040129D lea ecx, [esp+968h+Serial_2]
.text:004012A4
.text:004012A4 loc_4012A4: ; CODE XREF: OnCheck+180j
.text:004012A4 mov dl, [eax+1]
.text:004012A7 mov [ecx], dl
.text:004012A9 mov dl, [eax+1]
.text:004012AC inc ecx
.text:004012AD inc eax
.text:004012AE test dl, dl
.text:004012B0 jnz short loc_4012A4
.text:004012B2
.text:004012B2 loc_4012B2: ; CODE XREF: OnCheck+16Bj
.text:004012B2 lea edi, [esp+968h+Serial_1]
.text:004012B9 or ecx, 0FFFFFFFFh
.text:004012BC xor eax, eax
.text:004012BE repne scasb
.text:004012C0 not ecx
.text:004012C2 dec ecx
.text:004012C3 jz to_exit
.text:004012C9 lea edi, [esp+968h+Serial_2]
.text:004012D0 or ecx, 0FFFFFFFFh
.text:004012D3 repne scasb
.text:004012D5 not ecx
.text:004012D7 dec ecx
.text:004012D8 jz to_exit
.text:004012DE mov al, byte ptr [esp+968h+Serial_1]
.text:004012E5 mov edi, 1
.text:004012EA test al, al
.text:004012EC jz short loc_401333
.text:004012EE lea esi, [esp+968h+Serial_1]
.text:004012F5
.text:004012F5 loc_4012F5: ; CODE XREF: OnCheck+201j
.text:004012F5 cmp dword_40BFD0, edi
.text:004012FB jle short loc_401311
.text:004012FD xor eax, eax
.text:004012FF push 80h ; int
.text:00401304 mov al, [esi]
.text:00401306 push eax ; int
.text:00401307 call __isctype
.text:0040130C add esp, 8
.text:0040130F jmp short loc_401323
.text:00401311 ; ---------------------------------------------------------------------------
.text:00401311
.text:00401311 loc_401311: ; CODE XREF: OnCheck+1CBj
.text:00401311 mov edx, off_40BDC4
.text:00401317 xor ecx, ecx
.text:00401319 mov cl, [esi]
.text:0040131B mov al, [edx+ecx*2]
.text:0040131E and eax, 80h
.text:00401323
.text:00401323 loc_401323: ; CODE XREF: OnCheck+1DFj
.text:00401323 test eax, eax
.text:00401325 jz to_exit
.text:0040132B mov al, [esi+1]
.text:0040132E inc esi
.text:0040132F test al, al
.text:00401331 jnz short loc_4012F5
.text:00401333
.text:00401333 loc_401333: ; CODE XREF: OnCheck+1BCj
.text:00401333 mov al, byte ptr [esp+968h+Serial_2]
.text:0040133A test al, al
.text:0040133C jz short loc_401383
.text:0040133E lea esi, [esp+968h+Serial_2]
.text:00401345
.text:00401345 loc_401345: ; CODE XREF: OnCheck+251j
.text:00401345 cmp dword_40BFD0, edi
.text:0040134B jle short loc_401361
.text:0040134D xor eax, eax
.text:0040134F push 80h ; int
.text:00401354 mov al, [esi]
.text:00401356 push eax ; int
.text:00401357 call __isctype
.text:0040135C add esp, 8
.text:0040135F jmp short loc_401373
.text:00401361 ; ---------------------------------------------------------------------------
.text:00401361
.text:00401361 loc_401361: ; CODE XREF: OnCheck+21Bj
.text:00401361 mov edx, off_40BDC4
.text:00401367 xor ecx, ecx
.text:00401369 mov cl, [esi]
.text:0040136B mov al, [edx+ecx*2]
.text:0040136E and eax, 80h
.text:00401373
.text:00401373 loc_401373: ; CODE XREF: OnCheck+22Fj
.text:00401373 test eax, eax
.text:00401375 jz to_exit
.text:0040137B mov al, [esi+1]
.text:0040137E inc esi
.text:0040137F test al, al
.text:00401381 jnz short loc_401345
.text:00401383
.text:00401383 loc_401383: ; CODE XREF: OnCheck+20Cj
.text:00401383 mov edi, offset aPediy ; "&PEdiy"
.text:00401388 or ecx, 0FFFFFFFFh
.text:0040138B xor eax, eax
.text:0040138D lea edx, [esp+968h+Name]
.text:00401394 repne scasb
.text:00401396 not ecx
.text:00401398 sub edi, ecx
.text:0040139A mov esi, edi
.text:0040139C mov edi, edx
.text:0040139E mov edx, ecx
.text:004013A0 or ecx, 0FFFFFFFFh
.text:004013A3 repne scasb
.text:004013A5 mov ecx, edx
.text:004013A7 dec edi
.text:004013A8 shr ecx, 2
.text:004013AB rep movsd
.text:004013AD mov ecx, edx
.text:004013AF lea eax, [esp+968h+sha_ctx]
.text:004013B6 and ecx, 3
.text:004013B9 push eax
.text:004013BA rep movsb
.text:004013BC call _shs_init ; SHA1初始化
.text:004013C1 mov al, [esp+96Ch+Name]
.text:004013C8 add esp, 4
.text:004013CB test al, al
.text:004013CD jz short loc_4013F4
.text:004013CF lea esi, [esp+968h+Name]
.text:004013D6
.text:004013D6 loc_4013D6: ; CODE XREF: OnCheck+2C2j
.text:004013D6 and eax, 0FFh
.text:004013DB lea ecx, [esp+968h+sha_ctx]
.text:004013E2 push eax
.text:004013E3 push ecx
.text:004013E4 call _shs_process
.text:004013E9 mov al, [esi+1]
.text:004013EC add esp, 8
.text:004013EF inc esi
.text:004013F0 test al, al
.text:004013F2 jnz short loc_4013D6
.text:004013F4
.text:004013F4 loc_4013F4: ; CODE XREF: OnCheck+29Dj
.text:004013F4 lea edx, [esp+968h+hash_out]
.text:004013F8 lea eax, [esp+968h+sha_ctx]
.text:004013FF push edx
.text:00401400 push eax
.text:00401401 call _shs_hash
.text:00401406 mov ecx, [esp+970h+ba]
.text:0040140A lea edx, [esp+970h+hash_out]
.text:0040140E push ecx
.text:0040140F push edx
.text:00401410 push 10
.text:00401412 call _bytes_to_big
.text:00401417 lea eax, [esp+97Ch+Serial_1]
.text:0040141E push eax
.text:0040141F push ebp
.text:00401420 call _cinstr
.text:00401425 mov esi, [esp+984h+bc]
.text:00401429 lea ecx, [esp+984h+Serial_2]
.text:00401430 push ecx
.text:00401431 push esi
.text:00401432 call _cinstr
.text:00401437 push offset aE97e36f9426708 ; "E97E36F9426708D10516A001FC358367B8ECBB7"...
.text:0040143C push ebx
.text:0040143D call _cinstr
.text:00401442 mov edi, [esp+994h+be]
.text:00401446 push offset aD9bc54b68e7f0c ; "D9BC54B68E7F0CC76BD6BEB333AA09CCE9162FA"...
.text:0040144B push edi
.text:0040144C call _cinstr
.text:00401451 push ebp
.text:00401452 push ebp
.text:00401453 push 2
.text:00401455 push ebp
.text:00401456 call _power
.text:0040145B add esp, 44h
.text:0040145E push esi
.text:0040145F push esi
.text:00401460 push 2
.text:00401462 push esi
.text:00401463 call _power
.text:00401468 push edi
.text:00401469 push edi
.text:0040146A call _negify
.text:0040146F push ebp
.text:00401470 push ebx
.text:00401471 push ebx
.text:00401472 push ebp
.text:00401473 push esi
.text:00401474 push edi
.text:00401475 call _mad
.text:0040147A push ebp
.text:0040147B push ebx
.text:0040147C push ebp
.text:0040147D call _add
.text:00401482 push ebx
.text:00401483 push ebx
.text:00401484 push ebp
.text:00401485 call _divide
.text:0040148A mov esi, [esp+9B0h+ba]
.text:0040148E add esp, 48h
.text:00401491 push ebx
.text:00401492 push ebx
.text:00401493 push esi
.text:00401494 call _divide
.text:00401499 push ebp
.text:0040149A push esi
.text:0040149B call _compare ; 关键比较
.text:004014A0 add esp, 14h
.text:004014A3 neg eax
.text:004014A5 pop edi
.text:004014A6 pop esi
.text:004014A7 sbb eax, eax
.text:004014A9 pop ebp
.text:004014AA inc eax
.text:004014AB pop ebx
.text:004014AC add esp, 958h
.text:004014B2 retn
.text:004014B3 ; ---------------------------------------------------------------------------
.text:004014B3
.text:004014B3 to_exit: ; CODE XREF: OnCheck+101j
.text:004014B3 ; OnCheck+12Aj ...
.text:004014B3 pop edi
.text:004014B4 pop esi
.text:004014B5 pop ebp
.text:004014B6 xor eax, eax
.text:004014B8 pop ebx
.text:004014B9 add esp, 958h
.text:004014BF retn
.text:004014BF OnCheck endp
.text:004014BF
该CrackMe使用了Miracl大数库，除大数运算以外，还使用了其中的SHA1算法。
注册验证过程：
1、对用户名和注册码进行检查，用户名长度至少2个字符，注册码必须是这样的：
xxxxxx-xxxxxxx，它是用'-'连起来的字符串，前后两个子串都必须由16进制字符组成，
且长度都不能为0。
2、将注册码中'-'前的子串转化为大数s1，将后面的子串转化为大数s2。将用户名与字符串
"&PEdiy"连接起来，进行SHA1运算，将结果的前10个字节转化为大数h。
3、另给定了两个大数：
n = E97E36F9426708D10516A001FC358367B8ECBB7210388B971C886AA4A44845F1
d = D9BC54B68E7F0CC76BD6BEB333AA09CCE9162FA9DF22989EC049D5BCD34981FE
4、验证 h ?= s1^2 - d * s2^2 mod n ，如果相等则注册成功，否则失败。
为生成注册码，需要求解方程 h = s1^2 - d * s2^2 mod n。该方程还有两个未知数s1和s2，
因此是一个不定方程。我们给以将该方程改写为这样：
s1^2 = h + d * s2^2 mod n
其中s2可以任意给定（取一个随机数即可），然后关于s1的方程就变成了一个二次剩余方程。
由于大数n可以分解为两个大数的乘积: n = p * q
p = EB8D197C10BA775BA2A785085C44A0C3
q = FDC35FF9D4A7BBCAD7577E99D8C8533B
故由定理可知，在有限域Zn*内大约2^-2=1/4的元素都是模n的二次剩余。这个比例还是很大的。
任取随机数s2，验证 a = h + d * s2^2 mod n 是否是模n的二次剩余，如果不是则重新选择s2。
经过多次重复以后，总可以得到一个模n的二次剩余 a 。
然后求解二次剩余方程 s1^2 = a mod n，这个可以用中国剩余定理来求。
故生成注册码的过程：
1、将用户名与字符串"&PEdiy"连接起来，进行SHA1运算，将结果的前10个字节转化为大数h。
2、另给定了两个大数：
n = E97E36F9426708D10516A001FC358367B8ECBB7210388B971C886AA4A44845F1
d = D9BC54B68E7F0CC76BD6BEB333AA09CCE9162FA9DF22989EC049D5BCD34981FE
其中 n = p * q
p = EB8D197C10BA775BA2A785085C44A0C3
q = FDC35FF9D4A7BBCAD7577E99D8C8533B
3、取随机数s2，计算 a = h + d * s2^2 mod n ，并验证a是否是模n的二次剩余，
如果不是则重新选择s2，直到a是模n的二次剩余为止。
4、用中国剩余定理求解二次剩余方程 s1^2 = a mod n，得到大数s1。
5、将s1和s2转化成字符串，并用字符'-'连接起来，即为注册码。
感谢jB,bLaCk_eYe等人的精彩教程！
源码及keygen见附件。
[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法
上传的附件：
