新手加密算法入门(二)--ElGamal手记

中国IT动力,最新最全的IT技术教程

最新100篇 | 推荐100篇 | 专题100篇 | 排行榜 | 搜索 | 在线API文档

当前位置：> 看雪学院专区 > CrackMe

新手加密算法入门(二)--ElGamal手记

作者:佚名时间:2006-12-15 10:37 出处:pediy.com 责编:月夜寒箫

摘要：新手加密算法入门(二)--ElGamal手记

【作者】ryOsUkE(QQ:448089717)
转载请注明出处来自看雪论坛，以及本文的完整性，谢谢！

ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算

r = g^k ( mod p )
s=k^-1*(M-x*r) ( mod p - 1 )

签名就是( r, s )。随机数k须丢弃。
验证时要验证下式：

y^r * r^s ( mod p ) = g^M ( mod p )

同时一定要检验是否满足1<= r < p。否则签名容易伪造。ElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算

a = g^k ( mod p )
b = y^k M ( mod p )

( a, b )为密文，是明文的两倍长。解密时计算

M = b / a^x ( mod p )

　　ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。

=======================================================================================
keygenme在附件中，采用miracl编程。
【分析】
根据提示来到：
00401272   > \68 20D84000   push    0040D820      ;  ASCII "12345678"
00401277   .  55            push    ebp           ;  r 开始是60进制
00401278   .  E8 A32F0000   call    00404220           ;  cinstr
0040127D   .  8B5424 34     mov     edx, [esp+34]
00401281   .  68 A0D74000   push    0040D7A0      ;  ASCII "87654321"
00401286   .  52            push    edx           ;  s
00401287   .  E8 942F0000   call    00404220         ;  cinstr
0040128C   .  8B4424 28     mov     eax, [esp+28]
00401290   .  8B4C24 2C     mov     ecx, [esp+2C]
00401294   .  53            push    ebx  ;M 用name+*填充一个30Byte
00401295   .  68 20D74000   push    0040D720     ;  ASCII "night*************************"
0040129A   .  51            push    ecx      ;  30
0040129B   .  C780 38020000>mov     dword ptr [eax+238], 10
004012A5   .  E8 062E0000   call    004040B0       ;  bytes_to_big
004012AA   .  68 18C14000   push    0040C118    ;  ASCII "AC2DB4FEC8C62992DB4F"
004012AF   .  56            push    esi       ;  N
004012B0   .  E8 6B2F0000   call    00404220  ;cinstr
004012B5   .  53            push    ebx
004012B6   .  56            push    esi                                ;  N
004012B7   .  6A 02         push    2
004012B9   .  53            push    ebx         ;  M
004012BA   .  E8 F1260000   call    004039B0     ;  power M=M^2 mod n 计算M
004012BF   .  68 00C14000   push    0040C100       ;  ASCII "B54F430648C6B2A10FFB"
004012C4   .  56            push    esi        ;  P
004012C5   .  E8 562F0000   call    00404220        ;  cinstr
004012CA   .  8B5424 50     mov     edx, [esp+50]
004012CE   .  68 E8C04000   push    0040C0E8      ;  ASCII "2E0C2DB4FEC8C6299A0C"
004012D3   .  52            push    edx           ;  G
004012D4   .  E8 472F0000   call    00404220           ;  cinstr
004012D9   .  8B7C24 64     mov     edi, [esp+64]
004012DD   .  83C4 44       add     esp, 44
004012E0   .  68 D0C04000   push    0040C0D0   ;  ASCII "4E0F2ACAD51C4CCDFB51"
004012E5   .  57            push    edi              ;  Y
004012E6   .  E8 352F0000   call    00404220      ;  cinstr
用Pollard-Rho算法计算 X=3F6536A02CD18F3B67D3 满足Y=G^X mod P
004012EB   .  8B4424 18     mov     eax, [esp+18]
004012EF   .  8B4C24 1C     mov     ecx, [esp+1C]
004012F3   .  50            push    eax      ;  v2
004012F4   .  56            push    esi      ;  p
004012F5   .  53            push    ebx      ;  M
004012F6   .  51            push    ecx      ;  g
004012F7   .  E8 54220000   call    00403550   ;  powmod
004012FC   .  8B5424 48     mov     edx, [esp+48]
00401300   .  8B4424 44     mov     eax, [esp+44]
00401304   .  52            push    edx      ;  v1
00401305      56            push    esi      ;  p
00401306   .  50            push    eax      ;  s
00401307   .  55            push    ebp      ;  r
00401308   .  55            push    ebp      ;  r
00401309   .  57            push    edi      ;  y
0040130A   .  E8 A1210000   call    004034B0 ;  powmod2
0040130F   .  8B4C24 60     mov     ecx, [esp+60]
00401313   .  8B5424 40     mov     edx, [esp+40]
00401317   .  51            push    ecx
00401318   .  52            push    edx
00401319   .  E8 D2120000   call    004025F0    ;  compare(v1,v2)
很明显的看出上面是ElGamal的验证过程。
0040131E   .  83C4 38       add     esp, 38
00401321   .  85C0          test    eax, eax
00401323   .  6A 00         push    0
00401325   .  75 11         jnz     short 00401338
00401327   .  8B4424 2C     mov     eax, [esp+2C]
0040132B   .  68 C4C04000   push 0040C0C4  ;  ASCII "GOOOD!!!"
00401330   .  68 B0C04000   push 0040C0B0  ;  ASCII "Your key is good."
00401335   .  50            push    eax
00401336   .  EB 0F         jmp     short 00401347
00401338   >  8B4C24 2C     mov     ecx, [esp+2C]                      ; |
0040133C   .  68 A8C04000   push    0040C0A8                           ; |Title = "Faild"
00401341   .  68 88C04000   push    0040C088                           ; |Text = ".... Better luck next time .."
00401346   .  51            push    ecx                                ; |hOwner
00401347   >  FF15 ACB04000 call    [<&USER32.MessageBoxA>]            ; \MessageBoxA
0040134D   .  8B5424 2C     mov     edx, [esp+2C]
00401351   .  52            push    edx
00401352   .  E8 F90C0000   call    00402050
00401357   .  55            push    ebp
00401358   .  E8 F30C0000   call    00402050
0040135D   .  8B4424 38     mov     eax, [esp+38]
00401361   .  50            push    eax
00401362   .  E8 E90C0000   call    00402050
00401367   .  8B4C24 1C     mov     ecx, [esp+1C]
0040136B   .  51            push    ecx
0040136C   .  E8 DF0C0000   call    00402050
00401371   .  53            push    ebx
00401372   .  E8 D90C0000   call    00402050
00401377   .  56            push    esi
00401378   .  E8 D30C0000   call    00402050
0040137D   .  8B5424 2C     mov     edx, [esp+2C]
00401381   .  52            push    edx
00401382   .  E8 C90C0000   call    00402050
00401387   .  57            push    edi
00401388   .  E8 C30C0000   call    00402050
0040138D   .  83C4 20       add     esp, 20
00401390   .  E8 DB0C0000   call    00402070
00401395   .  5F            pop     edi
00401396   .  5E            pop     esi
00401397   .  5D            pop     ebp
00401398   .  33C0          xor     eax, eax
0040139A   .  5B            pop     ebx
0040139B   .  83C4 14       add     esp, 14
0040139E   .  C2 1000       retn    10

可以看出，这个Keygenme用到了ElGamal的验证过程，那么注册机就严格按照签名过程来写，其中M的产生是由name填充'*'到30个字节，转成一个big数,平方mod N得出来的，具体程序见注册机。

谢谢你看到这里，今天就到这里，未完待续。。。

所上传文件

keygenme3_and_注册机.rar (上传时间2006-06-10,05:02,215.1 KB,74 次点击)

关闭本页