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!
[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法
上传的附件：
