HappyTowns 39th CrackMe 算法分析及注册机

这个CrackMe有点麻烦，前一阵我已经投降过了，后来有人提醒是DSA变形算法，我重试了下确实如此。
不过这个DSA变形算法要求解一个离散对数问题，由于数比较大，试了几种工具都没有求出来。
最后我只好来一个折中，写了个Loader将其中一个关键大数替换，这样就能求解出离散对数问题。

虽然仍然不是完美解决方案，但相比以前已经有了很大的进步，至少算法已经都弄清楚了。
期望有朝一日谁能求解出其中的离散对数问题，这样才算最完美。

用PEiD查壳，显示
Microsoft Visual C++ 6.0
经验证，确实没有加壳。

用PEiD的Krypto ANAlyzer插件检查，结果如下：
List of Primes
MPI
big number

用IDA载入，并加载常用的sig。找到注册验证的关键函数，初步分析的结果如下：

.text:00401000 ; int __cdecl OnCheck(HWND hDlg)
.text:00401000 OnCheck         proc near               ; CODE XREF: DialogFunc+55p
.text:00401000
.text:00401000 var_1264        = dword ptr -1264h
.text:00401000 var_125F        = dword ptr -125Fh
.text:00401000 var_125B        = dword ptr -125Bh
.text:00401000 var_1257        = word ptr -1257h
.text:00401000 var_1255        = byte ptr -1255h
.text:00401000 bn7             = dword ptr -1254h
.text:00401000 bn1             = dword ptr -1244h
.text:00401000 bn0             = dword ptr -1234h
.text:00401000 bn9             = dword ptr -1224h
.text:00401000 bn8             = dword ptr -1214h
.text:00401000 bn6             = dword ptr -1204h
.text:00401000 bn5             = dword ptr -11F4h
.text:00401000 bn2             = dword ptr -11E4h
.text:00401000 bn3             = dword ptr -11D4h
.text:00401000 bn4             = dword ptr -11C4h
.text:00401000 _ctx            = dword ptr -11B4h
.text:00401000 Magic           = dword ptr -1194h
.text:00401000 Serial          = dword ptr -0FA0h
.text:00401000 Name            = byte ptr -0DACh
.text:00401000 var_BB8         = dword ptr -0BB8h
.text:00401000 var_9C4         = dword ptr -9C4h
.text:00401000 var_7D0         = dword ptr -7D0h
.text:00401000 var_79F         = dword ptr -79Fh
.text:00401000 var_5DC         = dword ptr -5DCh
.text:00401000 var_5AB         = dword ptr -5ABh
.text:00401000 var_3E8         = dword ptr -3E8h
.text:00401000 var_3CB         = dword ptr -3CBh
.text:00401000 var_1F4         = dword ptr -1F4h
.text:00401000 var_1C3         = dword ptr -1C3h
.text:00401000 hDlg            = dword ptr  4
.text:00401000
.text:00401000                 mov     eax, 1264h
.text:00401005                 call    __alloca_probe
.text:0040100A                 push    ebx
.text:0040100B                 push    esi
.text:0040100C                 push    edi
.text:0040100D                 xor     ebx, ebx
.text:0040100F                 mov     ecx, 124
.text:00401014                 xor     eax, eax
.text:00401016                 lea     edi, [esp+4C5h]
.text:0040101D                 mov     [esp+1270h+Name], bl
.text:00401024                 rep stosd
.text:00401026                 stosw
.text:00401028                 stosb
.text:00401029                 mov     ecx, 7Ch
.text:0040102E                 xor     eax, eax
.text:00401030                 lea     edi, [esp+1270h+var_BB8+1]
.text:00401037                 mov     byte ptr [esp+1270h+var_BB8], bl
.text:0040103E                 rep stosd
.text:00401040                 stosw
.text:00401042                 stosb
.text:00401043                 mov     ecx, 7Ch
.text:00401048                 xor     eax, eax
.text:0040104A                 lea     edi, [esp+1270h+Magic+1]
.text:00401051                 mov     byte ptr [esp+1270h+Magic], bl
.text:00401058                 rep stosd
.text:0040105A                 stosw
.text:0040105C                 stosb
.text:0040105D                 mov     ecx, 7Ch
.text:00401062                 xor     eax, eax
.text:00401064                 lea     edi, [esp+1270h+var_9C4+1]
.text:0040106B                 mov     byte ptr [esp+1270h+var_9C4], bl
.text:00401072                 rep stosd
.text:00401074                 stosw
.text:00401076                 stosb
.text:00401077                 mov     ecx, 7Ch
.text:0040107C                 xor     eax, eax
.text:0040107E                 lea     edi, [esp+1270h+Serial+1]
.text:00401085                 mov     byte ptr [esp+1270h+Serial], bl
.text:0040108C                 rep stosd
.text:0040108E                 stosw
.text:00401090                 stosb
.text:00401091                 mov     ecx, 0Ch
.text:00401096                 mov     esi, offset aC9c794ff125dc1 ; "C9C794FF125DC1CA546E797E9486F62D78D83A8"...
.text:0040109B                 lea     edi, [esp+1270h+var_7D0]
.text:004010A2                 xor     eax, eax
.text:004010A4                 rep movsd
.text:004010A6                 mov     [esp+1270h+var_1264+1], eax
.text:004010AA                 mov     ecx, 70h
.text:004010AF                 mov     [esp+1270h+var_125F], eax
.text:004010B3                 mov     byte ptr [esp+1270h+var_1264], bl
.text:004010B7                 mov     [esp+1270h+var_125B], eax
.text:004010BB                 movsb
.text:004010BC                 mov     [esp+1270h+var_1257], ax
.text:004010C1                 lea     edi, [esp+1270h+var_79F]
.text:004010C8                 mov     [esp+1270h+var_1255], al
.text:004010CC                 mov     esi, offset aD96f7b8483e94d ; "D96F7B8483E94DC1F6291AB7395B"
.text:004010D1                 rep stosd
.text:004010D3                 stosw
.text:004010D5                 stosb
.text:004010D6                 mov     ecx, 7
.text:004010DB                 lea     edi, [esp+1270h+var_3E8]
.text:004010E2                 rep movsd
.text:004010E4                 movsb
.text:004010E5                 mov     ecx, 75h
.text:004010EA                 xor     eax, eax
.text:004010EC                 lea     edi, [esp+1270h+var_3CB]
.text:004010F3                 mov     esi, offset a3faf2653287153 ; "3FAF265328715370501B09597543BAF1B42455D"...
.text:004010F8                 rep stosd
.text:004010FA                 stosw
.text:004010FC                 stosb
.text:004010FD                 mov     ecx, 0Ch
.text:00401102                 lea     edi, [esp+1270h+var_5DC]
.text:00401109                 rep movsd
.text:0040110B                 movsb
.text:0040110C                 mov     ecx, 70h
.text:00401111                 xor     eax, eax
.text:00401113                 lea     edi, [esp+1270h+var_5AB]
.text:0040111A                 rep stosd
.text:0040111C                 stosw
.text:0040111E                 stosb
.text:0040111F                 mov     ecx, 0Ch
.text:00401124                 mov     esi, offset a6edd84f08b6c30 ; "6EDD84F08B6C308F5727EEC13F5D87AC03D3FB7"...
.text:00401129                 lea     edi, [esp+1270h+var_1F4]
.text:00401130                 rep movsd
.text:00401132                 movsb
.text:00401133                 mov     ecx, 70h
.text:00401138                 xor     eax, eax
.text:0040113A                 lea     edi, [esp+1270h+var_1C3]
.text:00401141                 rep stosd
.text:00401143                 stosw
.text:00401145                 lea     ecx, [esp+1270h+bn0]
.text:00401149                 push    ecx
.text:0040114A                 stosb
.text:0040114B                 call    _mp_init
.text:00401150                 lea     edx, [esp+1274h+bn2]
.text:00401157                 push    edx
.text:00401158                 call    _mp_init
.text:0040115D                 lea     eax, [esp+1278h+bn3]
.text:00401164                 push    eax
.text:00401165                 call    _mp_init
.text:0040116A                 lea     ecx, [esp+127Ch+bn1]
.text:0040116E                 push    ecx
.text:0040116F                 call    _mp_init
.text:00401174                 lea     edx, [esp+1280h+bn5]
.text:0040117B                 push    edx
.text:0040117C                 call    _mp_init
.text:00401181                 lea     eax, [esp+1284h+bn6]
.text:00401188                 push    eax
.text:00401189                 call    _mp_init
.text:0040118E                 lea     ecx, [esp+1288h+bn4]
.text:00401195                 push    ecx
.text:00401196                 call    _mp_init
.text:0040119B                 lea     edx, [esp+128Ch+bn7]
.text:0040119F                 push    edx
.text:004011A0                 call    _mp_init
.text:004011A5                 lea     eax, [esp+1290h+bn8]
.text:004011A9                 push    eax
.text:004011AA                 call    _mp_init
.text:004011AF                 lea     ecx, [esp+1294h+bn9]
.text:004011B3                 push    ecx
.text:004011B4                 call    _mp_init
.text:004011B9                 lea     edx, [esp+1298h+var_7D0]
.text:004011C0                 push    10h
.text:004011C2                 lea     eax, [esp+129Ch+bn0]
.text:004011C6                 push    edx
.text:004011C7                 push    eax
.text:004011C8                 call    _mp_read_radix
.text:004011CD                 lea     ecx, [esp+12A4h+var_3E8]
.text:004011D4                 push    10h
.text:004011D6                 lea     edx, [esp+12A8h+bn1]
.text:004011DA                 push    ecx
.text:004011DB                 push    edx
.text:004011DC                 call    _mp_read_radix
.text:004011E1                 add     esp, 40h
.text:004011E4                 lea     eax, [esp+1270h+var_5DC]
.text:004011EB                 lea     ecx, [esp+1270h+bn2]
.text:004011F2                 push    10h
.text:004011F4                 push    eax
.text:004011F5                 push    ecx
.text:004011F6                 call    _mp_read_radix
.text:004011FB                 lea     edx, [esp+127Ch+var_1F4]
.text:00401202                 push    10h
.text:00401204                 lea     eax, [esp+1280h+bn3]
.text:0040120B                 push    edx
.text:0040120C                 push    eax
.text:0040120D                 call    _mp_read_radix
.text:00401212                 mov     esi, [esp+1288h+hDlg]
.text:00401219                 mov     edi, ds:GetDlgItemTextA
.text:0040121F                 add     esp, 18h
.text:00401222                 lea     ecx, [esp+1270h+Name]
.text:00401229                 push    501             ; nMaxCount
.text:0040122E                 push    ecx             ; lpString
.text:0040122F                 push    3EDh            ; nIDDlgItem
.text:00401234                 push    esi             ; hDlg
.text:00401235                 call    edi ; GetDlgItemTextA
.text:00401237                 cmp     eax, 2
.text:0040123A                 jnb     short loc_401248
.text:0040123C                 pop     edi
.text:0040123D                 pop     esi
.text:0040123E                 xor     eax, eax
.text:00401240                 pop     ebx
.text:00401241                 add     esp, 1264h
.text:00401247                 retn
.text:00401248 ; ---------------------------------------------------------------------------
.text:00401248
.text:00401248 loc_401248:                             ; CODE XREF: OnCheck+23Aj
.text:00401248                 lea     edx, [esp+1270h+Magic]
.text:0040124F                 push    501             ; nMaxCount
.text:00401254                 push    edx             ; lpString
.text:00401255                 push    3EEh            ; nIDDlgItem
.text:0040125A                 push    esi             ; hDlg
.text:0040125B                 call    edi ; GetDlgItemTextA
.text:0040125D                 cmp     eax, 1
.text:00401260                 jnb     short loc_40126E
.text:00401262                 pop     edi
.text:00401263                 pop     esi
.text:00401264                 xor     eax, eax
.text:00401266                 pop     ebx
.text:00401267                 add     esp, 1264h
.text:0040126D                 retn
.text:0040126E ; ---------------------------------------------------------------------------
.text:0040126E
.text:0040126E loc_40126E:                             ; CODE XREF: OnCheck+260j
.text:0040126E                 lea     eax, [esp+1270h+Serial]
.text:00401275                 push    501             ; nMaxCount
.text:0040127A                 push    eax             ; lpString
.text:0040127B                 push    3EFh            ; nIDDlgItem
.text:00401280                 push    esi             ; hDlg
.text:00401281                 call    edi ; GetDlgItemTextA
.text:00401283                 test    eax, eax
.text:00401285                 jnz     short loc_401291
.text:00401287                 pop     edi
.text:00401288                 pop     esi
.text:00401289                 pop     ebx
.text:0040128A                 add     esp, 1264h
.text:00401290                 retn
.text:00401291 ; ---------------------------------------------------------------------------
.text:00401291
.text:00401291 loc_401291:                             ; CODE XREF: OnCheck+285j
.text:00401291                 lea     ecx, [esp+1270h+var_BB8]
.text:00401298                 lea     edi, [esp+1270h+Magic]
.text:0040129F                 push    ecx
.text:004012A0                 or      ecx, 0FFFFFFFFh
.text:004012A3                 xor     eax, eax
.text:004012A5                 lea     edx, [esp+1274h+Magic]
.text:004012AC                 repne scasb
.text:004012AE                 not     ecx
.text:004012B0                 dec     ecx
.text:004012B1                 push    ecx
.text:004012B2                 push    edx
.text:004012B3                 call    str2bytes
.text:004012B8                 add     esp, 0Ch
.text:004012BB                 test    eax, eax
.text:004012BD                 jnz     short loc_4012C9
.text:004012BF                 pop     edi
.text:004012C0                 pop     esi
.text:004012C1                 pop     ebx
.text:004012C2                 add     esp, 1264h
.text:004012C8                 retn
.text:004012C9 ; ---------------------------------------------------------------------------
.text:004012C9
.text:004012C9 loc_4012C9:                             ; CODE XREF: OnCheck+2BDj
.text:004012C9                 lea     eax, [esp+1270h+var_9C4]
.text:004012D0                 lea     edi, [esp+1270h+Serial]
.text:004012D7                 push    eax
.text:004012D8                 or      ecx, 0FFFFFFFFh
.text:004012DB                 xor     eax, eax
.text:004012DD                 repne scasb
.text:004012DF                 not     ecx
.text:004012E1                 dec     ecx
.text:004012E2                 push    ecx
.text:004012E3                 lea     ecx, [esp+1278h+Serial]
.text:004012EA                 push    ecx
.text:004012EB                 call    str2bytes
.text:004012F0                 add     esp, 0Ch
.text:004012F3                 test    eax, eax
.text:004012F5                 jnz     short loc_401301
.text:004012F7                 pop     edi
.text:004012F8                 pop     esi
.text:004012F9                 pop     ebx
.text:004012FA                 add     esp, 1264h
.text:00401300                 retn
.text:00401301 ; ---------------------------------------------------------------------------
.text:00401301
.text:00401301 loc_401301:                             ; CODE XREF: OnCheck+2F5j
.text:00401301                 lea     edx, [esp+1270h+_ctx]
.text:00401308                 push    edx
.text:00401309                 call    hash_init
.text:0040130E                 lea     edi, [esp+1274h+Name]
.text:00401315                 or      ecx, 0FFFFFFFFh
.text:00401318                 xor     eax, eax
.text:0040131A                 repne scasb
.text:0040131C                 not     ecx
.text:0040131E                 dec     ecx
.text:0040131F                 lea     eax, [esp+1274h+Name]
.text:00401326                 push    ecx
.text:00401327                 lea     ecx, [esp+1278h+_ctx]
.text:0040132E                 push    eax
.text:0040132F                 push    ecx
.text:00401330                 call    hash_update
.text:00401335                 lea     edx, [esp+1280h+_ctx]
.text:0040133C                 lea     eax, [esp+1280h+var_1264]
.text:00401340                 push    edx
.text:00401341                 push    eax
.text:00401342                 call    hash_final
.text:00401347                 lea     ecx, [esp+1288h+var_1264]
.text:0040134B                 push    10
.text:0040134D                 lea     edx, [esp+128Ch+bn4]
.text:00401354                 push    ecx
.text:00401355                 push    edx
.text:00401356                 call    _mp_read_unsigned_bin
.text:0040135B                 lea     edi, [esp+1294h+Magic]
.text:00401362                 or      ecx, 0FFFFFFFFh
.text:00401365                 xor     eax, eax
.text:00401367                 repne scasb
.text:00401369                 not     ecx
.text:0040136B                 dec     ecx
.text:0040136C                 lea     eax, [esp+1294h+var_BB8]
.text:00401373                 shr     ecx, 1
.text:00401375                 push    ecx
.text:00401376                 lea     ecx, [esp+1298h+bn5]
.text:0040137D                 push    eax
.text:0040137E                 push    ecx
.text:0040137F                 call    _mp_read_unsigned_bin
.text:00401384                 lea     edi, [esp+12A0h+Serial]
.text:0040138B                 or      ecx, 0FFFFFFFFh
.text:0040138E                 xor     eax, eax
.text:00401390                 lea     edx, [esp+12A0h+var_9C4]
.text:00401397                 repne scasb
.text:00401399                 not     ecx
.text:0040139B                 dec     ecx
.text:0040139C                 lea     eax, [esp+12A0h+bn6]
.text:004013A3                 shr     ecx, 1
.text:004013A5                 push    ecx
.text:004013A6                 push    edx
.text:004013A7                 push    eax
.text:004013A8                 call    _mp_read_unsigned_bin
.text:004013AD                 lea     ecx, [esp+12ACh+bn7]
.text:004013B1                 lea     edx, [esp+12ACh+bn1]
.text:004013B5                 push    ecx
.text:004013B6                 lea     eax, [esp+12B0h+bn6]
.text:004013BD                 push    edx
.text:004013BE                 lea     ecx, [esp+12B4h+bn4]
.text:004013C5                 push    eax
.text:004013C6                 push    ecx
.text:004013C7                 call    _mp_mulmod
.text:004013CC                 add     esp, 4Ch
.text:004013CF                 lea     edx, [esp+1270h+bn8]
.text:004013D3                 lea     eax, [esp+1270h+bn1]
.text:004013D7                 lea     ecx, [esp+1270h+bn5]
.text:004013DB                 push    edx
.text:004013DC                 push    eax
.text:004013DD                 lea     edx, [esp+1278h+bn6]
.text:004013E1                 push    ecx
.text:004013E2                 push    edx
.text:004013E3                 call    _mp_mulmod
.text:004013E8                 lea     eax, [esp+1280h+bn7]
.text:004013EC                 lea     ecx, [esp+1280h+bn0]
.text:004013F0                 push    eax
.text:004013F1                 lea     edx, [esp+1284h+bn7]
.text:004013F5                 push    ecx
.text:004013F6                 lea     eax, [esp+1288h+bn2]
.text:004013FD                 push    edx
.text:004013FE                 push    eax
.text:004013FF                 call    _mp_exptmod
.text:00401404                 lea     ecx, [esp+1290h+bn8]
.text:00401408                 lea     edx, [esp+1290h+bn0]
.text:0040140C                 push    ecx
.text:0040140D                 lea     eax, [esp+1294h+bn8]
.text:00401414                 push    edx
.text:00401415                 lea     ecx, [esp+1298h+bn3]
.text:0040141C                 push    eax
.text:0040141D                 push    ecx
.text:0040141E                 call    _mp_exptmod
.text:00401423                 lea     edx, [esp+12A0h+bn9]
.text:00401427                 lea     eax, [esp+12A0h+bn0]
.text:0040142B                 push    edx
.text:0040142C                 lea     ecx, [esp+12A4h+bn8]
.text:00401433                 push    eax
.text:00401434                 lea     edx, [esp+12A8h+bn7]
.text:00401438                 push    ecx
.text:00401439                 push    edx
.text:0040143A                 call    _mp_mulmod
.text:0040143F                 add     esp, 40h
.text:00401442                 lea     eax, [esp+1270h+bn9]
.text:00401446                 lea     ecx, [esp+1270h+bn1]
.text:0040144A                 lea     edx, [esp+1270h+bn9]
.text:0040144E                 push    eax
.text:0040144F                 push    ecx
.text:00401450                 push    edx
.text:00401451                 call    _mp_mod
.text:00401456                 lea     eax, [esp+127Ch+bn9]
.text:0040145A                 lea     ecx, [esp+127Ch+bn5]
.text:00401461                 push    eax
.text:00401462                 push    ecx
.text:00401463                 call    _mp_cmp
.text:00401468                 mov     esi, eax
.text:0040146A                 lea     edx, [esp+1284h+bn9]
.text:0040146E                 push    ebx
.text:0040146F                 lea     eax, [esp+1288h+bn8]
.text:00401473                 push    edx
.text:00401474                 lea     ecx, [esp+128Ch+bn7]
.text:00401478                 push    eax
.text:00401479                 lea     edx, [esp+1290h+bn4]
.text:00401480                 push    ecx
.text:00401481                 lea     eax, [esp+1294h+bn6]
.text:00401488                 push    edx
.text:00401489                 lea     ecx, [esp+1298h+bn5]
.text:00401490                 push    eax
.text:00401491                 lea     edx, [esp+129Ch+bn1]
.text:00401495                 push    ecx
.text:00401496                 lea     eax, [esp+12A0h+bn3]
.text:0040149D                 push    edx
.text:0040149E                 lea     ecx, [esp+12A4h+bn2]
.text:004014A5                 push    eax
.text:004014A6                 lea     edx, [esp+12A8h+bn0]
.text:004014AA                 push    ecx
.text:004014AB                 push    edx
.text:004014AC                 call    _mp_clear_multi
.text:004014B1                 add     esp, 40h
.text:004014B4                 xor     eax, eax
.text:004014B6                 cmp     esi, ebx
.text:004014B8                 pop     edi
.text:004014B9                 pop     esi
.text:004014BA                 setz    al
.text:004014BD                 pop     ebx
.text:004014BE                 add     esp, 1264h
.text:004014C4                 retn
.text:004014C4 OnCheck         endp
.text:004014C4

该CrackMe使用了MPI大数运算库。

该CrackMe的关键函数的逆向代码如下：

#include "..//hash.h"
extern "C" {
#include "..//mpi.h"
}

#pragma comment ( lib, "mpi.lib" )

void str2bytes( const unsigned char *in, unsigned int len, unsigned char out[] )
{
        unsigned int i;
        unsigned char x, y;
        len >>= 1;
        for( i=0; i<len; i++ )
        {
                y = in[ ( i  << 1 ) + 1 ];
                if( isalpha(y) )  y = toupper(y);
                y -= 0x30;
                if( y > 9 )  y -= 7;
                x = in[ ( i  << 1 ) ];
                if( isalpha(x) )  x = toupper(x);
                x -= 0x30;
                if( x > 9 )  x -= 7;
                y = y | (x << 4);
                out[i] = (unsigned char)y;
        }
}

void CCrackMeDlg::OnCheck()
{
        char szName[500] = {0};
        char szMagic[500] = {0};
        char szSerial[500] = {0};
        int  i, len;
        unsigned char buf[256];

        len = GetDlgItemText( IDC_NAME, szName, 501 );
        if( len < 2 )  return;
        len = GetDlgItemText( IDC_MAGIC, szMagic, 501 );
        if( len < 1 || len % 2 ==1 )  return;
        len = GetDlgItemText( IDC_SERIAL, szSerial, 501 );
        if( len == 0 || len % 2 ==1 )  return;

        mp_err  res;
        mp_int  bn[10];
        mp_init_array( bn, 10 );

        res = mp_read_radix( &bn[0], (unsigned char *)"C9C794FF125DC1CA546E797E9486F62D78D83A8E2A6D8D4B", 16);
        res = mp_read_radix( &bn[1], (unsigned char *)"D96F7B8483E94DC1F6291AB7395B", 16);
        res = mp_read_radix( &bn[2], (unsigned char *)"3FAF265328715370501B09597543BAF1B42455D283DEC78B", 16);
        res = mp_read_radix( &bn[3], (unsigned char *)"6EDD84F08B6C308F5727EEC13F5D87AC03D3FB7476654D2F", 16);

        hash_context _ctx;
        unsigned char hash_out[20];
        hash_init( &_ctx );
        hash_update( &_ctx, (unsigned char *)szName, strlen(szName) );
        hash_final( hash_out, &_ctx );
        res = mp_read_unsigned_bin( &bn[4], hash_out, 10 );

        len = strlen( szMagic );
        i = 0;
        while( i < len )
        {
                if( isxdigit( szMagic[i] ) == 0 )  return;
                i++;
        }
        str2bytes( (unsigned char *)szMagic, len, buf );
        res = mp_read_unsigned_bin( &bn[5], buf, len>>1 );

        len = strlen( szSerial );
        i = 0;
        while( i < len )
        {
                if( isxdigit( szSerial[i] ) == 0 )  return;
                i++;
        }
        str2bytes( (unsigned char *)szSerial, len, buf );
        res = mp_read_unsigned_bin( &bn[6], buf, len>>1 );

        res = mp_mulmod( &bn[4], &bn[6], &bn[1], &bn[7] );
        res = mp_mulmod( &bn[6], &bn[5], &bn[1], &bn[8] );

        res = mp_exptmod( &bn[2], &bn[7], &bn[0], &bn[7] );
        res = mp_exptmod( &bn[3], &bn[8], &bn[0], &bn[8] );

        res = mp_mulmod( &bn[7], &bn[8], &bn[0], &bn[9] );
        res = mp_mod( &bn[9], &bn[1], &bn[9] );

        if( mp_cmp( &bn[5], &bn[9] ) == 0 )
                MessageBox( "Congratulations!\nYou have done a good work.", "Good!", MB_OK | MB_ICONINFORMATION);
        else
                MessageBox( "Sorry!\nGo on, and never give up ...", "Error!", MB_OK | MB_ICONERROR );

        mp_clear_array( bn, 10 );
}

上述代码中的hash函数是经过修改的sha1函数，直接从CrackMe中提取汇编代码即可，无须自己编写。

注册验证过程如下：
1、给定4个大数bn0,bn1,bn2,bn3。
2、读取用户名，至少2个字符。对用户名进行修改过的sha1运算，将结果的前10个字节转化为大数bn4。
读取Magic码，至少1个字符，转化为大数bn5。读取注册码，注册码不能为空，转化为大数bn6。
3、进行以下运算：
( bn4 * bn6 ) mod bn1 => bn7
( bn5 * bn6 ) mod bn1 => bn8
( bn2 ^ bn7 ) mod bn0 => bn7
( bn3 ^ bn8 ) mod bn0 => bn8
( bn7 * bn8 ) mod bn0 => bn9
  bn9 mod bn1 => bn9
  检查bn9和bn5，如果二者相同则注册成功，否则失败。

其中的已知大数：
bn0: C9C794FF125DC1CA546E797E9486F62D78D83A8E2A6D8D4B
bn1: D96F7B8483E94DC1F6291AB7395B
bn2: 3FAF265328715370501B09597543BAF1B42455D283DEC78B
bn3: 6EDD84F08B6C308F5727EEC13F5D87AC03D3FB7476654D2F
bn4: 可从用户名计算得到。

模bn0和bn1都是素数。bn0-1分解的结果如下：
bn0-1 : C9C794FF125DC1CA546E797E9486F62D78D83A8E2A6D8D4A
2
3
5
D
D3
A1F
12B18DDE3094A9
D96F7B8483E94DC1F6291AB7395B
可知bn1是bn0-1的一个因子。

经人提醒，这是一个DSA变形算法，其中各参数分别是：
p = bn0
q = bn1
g = bn2
y = bn3
H(m) = bn4
r = bn5
s = bn6
验证过程：
u1 = (H(m) * s) mod q
u2 = (r * s) mod q
如果 r == ((g^u1 * y^u2) mod p) mod q, 那么验证通过。
相应的签名过程：
任取随机大数k，使得0<k<q，计算
r = (g^k mod p) mod q
s = k * (H(m) + xr)^-1 mod q
其中的x需要通过求解离散对数问题 y = g^x mod p 得到。

那么由此可知，我们生成注册码的过程就是：
1、求解离散对数问题 y = g^x mod p，得到大数 x 。
2、任取随机大数k，使得0<k<q，计算 r = (g^k mod p) mod q ，输出r的16进制字符串即为 Magic 码。
3、计算 s = k * (H(m) + xr)^-1 mod q ，输出r的16进制字符串即为注册码。

关于DSA变形算法的更详细的信息，请参考这本密码学经典著作中的相关章节，这里不再赘述。
Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

由于q是p的素因子，这是一个比较大的素数，使得离散对数问题 y = g^x mod p 的求解相当困难。
我试了好几种工具，花了很长时间都没有能解出来。
最后我想了一个折中的办法，就是令 y = g, 也就是让 bn3 = bn2, 这样离散对数问题 y = g^x mod p 的解就是 x = 1 了。
经过这样修改以后，就可以写出keygen，算出一系列的注册码。
为了让修改更容易一些，我另外编写了一个Loader，它可以加载并修改这个 CrackMe 中的参数 bn3 。

测试的时候先运行Loader或者先运行CrackMe都可以。
但是如果先运行Loader的话，CrackMe不能更改文件名，且要和Loader在同一个目录内。
否则Loader将找不到CrackMe。

逆向代码、注册机代码、以及Loader的代码见附件。

just for fun!

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课