|
|
ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。
, V: F1 C: k2 N9 P7 S! w! x密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
- Y$ k4 ^; j! bElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算
2 q% x* A5 F$ z3 n: O% u
0 K' T3 d* b: p- g9 s& k. C' o* za = g^k ( mod p )
7 y7 k+ Z5 v: `: E* D! w再用扩展 Euclidean 算法对下面方程求解b：
$ f7 i$ n3 B+ v$ q% E Z
( w. J+ i' s% ]! U2 X$ _6 bM = xa + kb ( mod p - 1 )
4 G# L1 J! w3 ]: _" g8 {
8 K' ]9 P3 Z+ y/ M5 l; ~# S8 f5 H签名就是( a, b )。随机数k须丢弃。
" W x) R. k9 }, A* \验证时要验证下式：
- R* P& {- \1 y7 M L* X
+ L, _: s. r/ e' F2 h
y^a * a^b ( mod p ) = g^M ( mod p )
: H; B% z# ^' U: e
+ q+ v' M( B9 p J9 h+ J同时一定要检验是否满足1<= a < p。否则签名容易伪造。
, U) x6 k2 d6 L% e: QElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算
5 |3 w: {% y/ |7 F
, U2 u u$ F9 Fa = g^k ( mod p )
3 \7 m. S: T& X
b = y^k M ( mod p )
1 s# U% ]' Y3 w9 `- ]7 m# m7 f
- D9 i5 I+ ~3 G0 |: [; r( n' D
* x8 F1 p3 `) f- ~1 _5 {1 |
( a, b )为密文，是明文的两倍长。解密时计算
, x# m+ ]# g0 P- t# c
5 J4 S8 _" k: Q: E4 w) e' MM = b / a^x ( mod p )
# G$ [0 L% n2 B) C# D2 P
) p' }6 k7 d; J& `+ l: i
ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数
( p0 W: z& c8 [ X G
因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。
$ p/ [, m) @9 B* F3 `
7 n" r! e/ y* j4 B 美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
3 m+ y @* n$ r- y. r变而来。 |
|
IP卡
狗仔卡
发表于 2004-11-26 20:04:40
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡