|
|
ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。
8 W& o, S+ V- o/ A
密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
/ Z# P0 U( G9 I$ \ H$ QElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算
# S% ]! g. u. c1 L
( i+ q2 Z+ y3 H9 r$ ~a = g^k ( mod p )
- k% }( s7 H1 p8 y9 R2 t# ^再用扩展 Euclidean 算法对下面方程求解b：
* v/ u$ m" |" s* b$ x' d
6 V6 m( L% S! F3 H; | w$ UM = xa + kb ( mod p - 1 )
! p& ~2 Q& ~3 d8 x- L, g" q5 b
' p5 X' x, }) S
签名就是( a, b )。随机数k须丢弃。
4 {' q8 H6 i) l验证时要验证下式：
8 r n' O/ a8 l6 i) r
* O5 c3 ^* o& _0 f7 X9 |( [
y^a * a^b ( mod p ) = g^M ( mod p )
+ ~5 A2 L) g3 h$ h3 Z8 v
; a2 D) x. L0 I1 ?) S同时一定要检验是否满足1<= a < p。否则签名容易伪造。
, \. x3 W8 L( L3 lElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算
9 u7 m9 F i, n) K D8 o$ X3 G/ U
6 K' d( z$ Z7 n2 @5 H" N# u- |
a = g^k ( mod p )
3 X' f T7 G" c8 `3 Yb = y^k M ( mod p )
2 q) S7 q) O+ W3 X6 C8 O( p5 c' s
5 q7 q5 j8 x. r
u! I& M! i0 O' L7 [1 n3 f
( a, b )为密文，是明文的两倍长。解密时计算
0 q6 ^+ b7 |, S2 W1 `, H+ g0 U
- X7 m* X) `% O6 X" Q( xM = b / a^x ( mod p )
9 `, a4 W$ e) ]; D8 K
R4 p7 c6 v( @
ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数
' }5 g C3 K" \2 ?, Q# Y
因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。
; n+ M/ U: c' v' @
* R+ ]! ~3 j0 M( w X s
美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
- T, Y3 a( C8 w/ _
变而来。 |
|
IP卡
狗仔卡
发表于 2004-11-26 20:04:40
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡