原了那个call是  两个64位数的相乘  哎 简单的问题复杂化了

Name:请哥慢捂
Code:00034KDD4H6XVQPMDHQ

先发一组，后面补分析

程序很小，结构很清晰，入口处：
004012D5 >/$  6A 00                  PUSH    0                                ; /lParam = NULL
004012D7  |.  68 8F104000            PUSH    0040108F                         ; |DlgProc = Keygenme.0040108F
004012DC  |.  6A 00                  PUSH    0                                ; |hOwner = NULL
004012DE  |.  6A 67                  PUSH    67                               ; |pTemplate = 67
004012E0  |.  6A 00                  PUSH    0                                ; |/pModule = NULL
004012E2  |.  FF15 00104000          CALL    NEAR DWORD PTR [<&KERNEL32.GetMo>; |\GetModuleHandleA
004012E8  |.  50                     PUSH    EAX                              ; |hInst
004012E9  |.  FF15 20104000          CALL    NEAR DWORD PTR [<&USER32.DialogB>; \DialogBoxParamA
004012EF  |.  6A 00                  PUSH    0                                ; /ExitCode = 0
004012F1  \.  FF15 04104000          CALL    NEAR DWORD PTR [<&KERNEL32.ExitP>; \ExitProcess

可以直接转到地址：DlgProc = Keygenme.0040108F
这里是处理消息循环的地方，case 111就是WM_COMMAND，处理按钮事件
接下来的
004010ED   .  FFD7                   CALL    NEAR EDI                         ; \GetWindowTextA

004010FC   .  FFD7                   CALL    NEAR EDI                         ; \GetWindowTextA

是分别获取用户名和注册码，往下来是初始化一个常数表，粗看不知所云，然而表格的大小以及后续的计算方式不免让人想起CRC32
回头仔细一看，这不就是CRC64嘛(不知道有没有这个名称)。

0040111D   .  33F6                   XOR     ESI, ESI
0040111F   >  8BC6                   MOV     EAX, ESI
00401121   .  99                     CDQ
00401122   .  C745 74 08000000       MOV     DWORD PTR [EBP+74], 8
00401129   >  8BC8                   MOV     ECX, EAX
0040112B   .  0FACD0 01              SHRD    EAX, EDX, 1
0040112F   .  83E1 01                AND     ECX, 1
00401132   .  33DB                   XOR     EBX, EBX
00401134   .  D1EA                   SHR     EDX, 1
00401136   .  0BCB                   OR      ECX, EBX
00401138   .  74 0B                  JE      SHORT 00401145
0040113A   .  35 B5C94BAC            XOR     EAX, AC4BC9B5
0040113F   .  81F2 2993AC95          XOR     EDX, 95AC9329
00401145   >  FF4D 74                DEC     DWORD PTR [EBP+74]
00401148   .^ 75 DF                  JNZ     SHORT 00401129
0040114A   .  8984F5 B0F7FFFF        MOV     DWORD PTR [EBP+ESI*8-850], EAX
00401151   .  8994F5 B4F7FFFF        MOV     DWORD PTR [EBP+ESI*8-84C], EDX
00401158   .  46                     INC     ESI
00401159   .  81FE 00010000          CMP     ESI, 100
0040115F   .^ 7C BE                  JL      SHORT 0040111F

初始化表格的代码如下：
procedure initTable;
var
  i, j: Integer;
  con, iv: Int64;
begin
  con := $95AC9329AC4BC9B5;
  for i:=0 to $FF do
  begin
    iv := i;
    for j:=1 to 8 do
    begin
      if iv and 1 = 1 then
        iv := (iv shr 1) xor con
      else
        iv := iv shr 1;
    end;
    crcTable[i] := iv;
  end;
end;

接下来就是计算用户名的CRC64校验值了：
00401165   > /8B4D 60                MOV     ECX, DWORD PTR [EBP+60]
00401168   . |8B55 64                MOV     EDX, DWORD PTR [EBP+64]
0040116B   . |3345 60                XOR     EAX, DWORD PTR [EBP+60]
0040116E   . |0FACD1 08              SHRD    ECX, EDX, 8
00401172   . |25 FF000000            AND     EAX, 0FF
00401177   . |338CC5 B0F7FFFF        XOR     ECX, DWORD PTR [EBP+EAX*8-850]
0040117E   . |C1EA 08                SHR     EDX, 8
00401181   . |3394C5 B4F7FFFF        XOR     EDX, DWORD PTR [EBP+EAX*8-84C]
00401188   . |47                     INC     EDI
00401189   . |8A07                   MOV     AL, BYTE PTR [EDI]
0040118B   . |84C0                   TEST    AL, AL
0040118D   . |894D 60                MOV     DWORD PTR [EBP+60], ECX
00401190   . |8955 64                MOV     DWORD PTR [EBP+64], EDX
00401193   .^\75 D0                  JNZ     SHORT 00401165

计算的代码如下：
function  calCRC64(s: string): Int64;
var
  i: Integer;
  iv: Int64;
begin
  iv := Int64(-1);
  for i:=1 to Length(s) do
  begin
    iv := (iv shr 8) xor crcTable[byte(iv and $FF) xor Ord(s[i])];
  end;
  Result := iv;
end;

再往下是处理注册码的地方，首先注册码要19位，否则错误：
004011A2   .  2BC2                   SUB     EAX, EDX
004011A4   .  83F8 13                CMP     EAX, 13
004011A7   .  0F85 B1000000          JNZ     0040125E

然后呢，有个查表的地方，[401028]=CDFHKMPQTVX23468
估计就是把注册码转换成这个字母表表示的16进制，跟踪一下即可确定这个猜测
004011B9   > /3A8B 28104000          CMP     CL, BYTE PTR [EBX+401028]
004011BF   . |74 08                  JE      SHORT 004011C9
004011C1   . |43                     INC     EBX
004011C2   . |83FB 11                CMP     EBX, 11
004011C5   .^\72 F2                  JB      SHORT 004011B9

到这里我们得到了2个Int64数字：
crcName = 用户名的CRC64校验值
crcCode = 注册码转换的类16进制值

然后进行下面的计算：
函数 00401070是典型的Int64乘法
004011E9   .  8B4D 60                MOV     ECX, DWORD PTR [EBP+60]          ; crcName的低位
004011EC   .  83E1 01                AND     ECX, 1
004011EF   .  33D2                   XOR     EDX, EDX
004011F1   .  56                     PUSH    ESI
004011F2   .  0BCA                   OR      ECX, EDX
004011F4   .  50                     PUSH    EAX                              ; push crcCode
004011F5   .  8BC8                   MOV     ECX, EAX
004011F7   .  8BD6                   MOV     EDX, ESI
004011F9   .  74 29                  JE      SHORT 00401224                   ; crcName的低位奇偶
004011FB   .  034D 60                ADD     ECX, DWORD PTR [EBP+60]          ; 奇数的时候
004011FE   .  1355 64                ADC     EDX, DWORD PTR [EBP+64]          ; crcName + crcCode
00401201   .  52                     PUSH    EDX                              ; /Arg4
00401202   .  51                     PUSH    ECX                              ; |Arg3 crcName + crcCode
00401203   .  56                     PUSH    ESI                              ; |Arg2
00401204   .  50                     PUSH    EAX                              ; |Arg1 crcCode
00401205   .  E8 66FEFFFF            CALL    00401070                         ; \Keygenme.00401070
0040120A   .  83C4 10                ADD     ESP, 10
0040120D   .  52                     PUSH    EDX                              ; |Arg2
0040120E   .  50                     PUSH    EAX                              ; |Arg1
0040120F   .  E8 5CFEFFFF            CALL    00401070                         ; \Keygenme.00401070
00401214   .  83C4 10                ADD     ESP, 10
00401217   .  05 420F87D7            ADD     EAX, D7870F42
0040121C   .  81D2 95576CC9          ADC     EDX, C96C5795                    ; 加上一个常数
00401222   .  EB 28                  JMP     SHORT 0040124C
00401224   >  81C1 B5C94BAC          ADD     ECX, AC4BC9B5                    ; 偶数的情况
0040122A   .  81D2 2993AC95          ADC     EDX, 95AC9329                    ; 加上一个常数
00401230   .  52                     PUSH    EDX                              ; /Arg4
00401231   .  51                     PUSH    ECX                              ; |Arg3
00401232   .  56                     PUSH    ESI                              ; |Arg2
00401233   .  50                     PUSH    EAX                              ; |Arg1 crcCode
00401234   .  E8 37FEFFFF            CALL    00401070                         ; \Keygenme.00401070
00401239   .  83C4 10                ADD     ESP, 10
0040123C   .  52                     PUSH    EDX                              ; |Arg2
0040123D   .  50                     PUSH    EAX                              ; |Arg1
0040123E   .  E8 2DFEFFFF            CALL    00401070                         ; \Keygenme.00401070
00401243   .  83C4 10                ADD     ESP, 10
00401246   .  0345 60                ADD     EAX, DWORD PTR [EBP+60]
00401249   .  1355 64                ADC     EDX, DWORD PTR [EBP+64]          ; 加上crcName

上面计算的代码总结下来就是：
if crcName and 1 = 0 then
    crcCode := (crcCode + $95AC9329AC4BC9B5) * crcCode * crcCode + crcName
else
    crcCode := (crcCode + crcName) * crcCode * crcCode + $C96C5795D7870F42;

最后就是判断了，需要 crcCode=0 才提示正确：
0040124C   > \0BC2                   OR      EAX, EDX                         ; 高低位或一下，等于0就通过了
0040124E   .  75 0E                  JNZ     SHORT 0040125E
00401250   .  6A 40                  PUSH    40
00401252   .  68 60104000            PUSH    00401060                         ;  ASCII "Congratulations"
00401257   .  68 54104000            PUSH    00401054                         ;  ASCII "Registered!"
0040125C   .  EB 0C                  JMP     SHORT 0040126A
0040125E   >  6A 10                  PUSH    10
00401260   .  68 48104000            PUSH    00401048                         ;  ASCII "Try again"
00401265   .  68 3C104000            PUSH    0040103C                         ;  ASCII "Wrong Key!"
0040126A   >  FF75 70                PUSH    DWORD PTR [EBP+70]               ; |hOwner
0040126D   .  FF15 14104000          CALL    NEAR DWORD PTR [<&USER32.Message>; \MessageBoxA

算法看完了，总结一下发现需要解下面的一元三次模方程：
if crcName and 1 = 0 then
    求解：(crcCode + $95AC9329AC4BC9B5) * crcCode * crcCode + crcName = 0
else
    求解：(crcCode + crcName) * crcCode * crcCode + $C96C5795D7870F42 = 0

或者使用碰撞技术来找这个crcCode。

经过大胆的假设，发现直接用上面的计算方法来做碰撞函数，效果奇佳(或者说一般性的CRC碰撞都可以用这个方式)。
每轮至少可以撞出一位结果，16轮后crcCode就计算出来了。

得到crcCode以后还需要把它再转换成类16进制的字符串才行，而且前面要记得补充3位哦

算法分析得不错，但碰撞的具体算法没有给出。碰撞需要多少时间？

碰撞算法就是用验证的算法，速度应该可以接受，这里有kg可以试试看

上传的附件：

• kg.rar （20.35kb，30次下载）

很不错的分析，强悍

我也顶一个!!
方程我没能解出来.
请哥慢捂  牛人  是马甲吗?

碰撞可以参考DonQuixote的文章。

被说中了，我就是在精华里面搜出来他的那篇文章的

这个解法不属于碰撞算法，而应该算是按位穷举。
不管怎么样，keygen是成功的。恭喜！请期待Keygenme II

不懂算法 。。。。

对哦，其实碰撞算法没有看懂，碰巧用了这个穷举的方式，循环16×16次，还算能对付自己了

飘飘而过～

从何处开始看算法？从何处开始看算法？从何处开始看算法？

Keygenme I,II,III实际上都是在探讨高次同余方程求解的问题。一次和二次的同余方程的求解早已被大家所熟识，而这三个Keygenme使用的都是大于二次的方程。这里先讲一下Keygenme I的相关问题。

Keygenme I使用的是高次同余方程的一个特例，即

f(x)=0 (mod p^n)

f(x)是任意的多项式。

有这么一个定理：

如果a是f(x)=0 (mod p^(n-1))的解，且p不能整除df(a)，那么同余方程只有一个解（其他的解情况这里就不讨论了），如下：

x= a - ( f(a) / df(a) ) (mod p^n)

其中df(x)是f(x)的导数。

因此只要求解出f(x)=0 (mod p)，即可以依次求解出 f(x)=0 (mod p^n)。另外，当x=a (mod p^n)，必有x=a (mod p^(n-1))，因此依次求解时都可以使用p^n作为模数。

现在就来看一下Keygenme I的实际情况：

Keygenme I使用的p是2，n是64，当c(c就是name的CRC64的值)是奇数时，需要求解的方程是：

f1(x)=x^3+c*x^2+0xC96C5795D7870F42

df1(x)=3*x^2+2*c*x

很显然 f1(x)=0 (mod 2)的解是1. 而2不整除df1(1)，因此同余方程有惟一解。按照上面的定理，就可以求解f1(x)=0 (mod 2^64)。

当c是偶数时，需要求解的方程是：

f2(x)=x^3+0x95AC9329AC4BC9B5*x^2+c

df2(x)=3*x^2+2*0x95AC9329AC4BC9B5*x

对于f2(x)=0 (mod 2^64)的求解和上面类似。

当然上面只是设计的解法，请哥慢捂的逐位穷举解法也是这个特殊同余方程当p较小时的有效解法，因为其计算量最大只有((p-1)*n)次f(x)模计算，当p=2时，比设计的解法还要快，因为不需要求逆。逐位穷举的解法依据一个简单的事实，f(x) (mod 2^n)的值低k位，只由x的低k位决定。