|
|
ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。
, K. p2 t" \9 }" |+ b5 w2 q+ D# `4 K密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
( k6 m& O o: H) V3 n: K# R
ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算
3 N" q `2 F: c1 \1 T/ G# a; [. I
+ k' I5 C5 Q& ^+ A# la = g^k ( mod p )
2 D# V3 l1 z* M0 k) T" T: \再用扩展 Euclidean 算法对下面方程求解b：
9 z4 m! j5 L: h5 G
+ A6 k7 S' ?/ Q1 {8 e7 f* ]M = xa + kb ( mod p - 1 )
0 [, {$ V% Y( }0 ], y9 q( r
, @1 `9 g0 O) b5 I/ R$ s
签名就是( a, b )。随机数k须丢弃。
. q8 K7 t1 D- S" B+ {验证时要验证下式：
7 p' q, G: I' I7 |: ]' C7 Z
0 f, c9 Z& V# G8 u& a) N- i8 O
y^a * a^b ( mod p ) = g^M ( mod p )
6 Q+ B* h0 O0 U( Q5 R% p8 J8 T- C
. U/ y" q. r/ ]( S同时一定要检验是否满足1<= a < p。否则签名容易伪造。
- F- r& n* y' M7 @ElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算
( X2 b+ u. B8 ]2 Z$ G4 q; \
* U) N% G: O: O; Q
a = g^k ( mod p )
5 V! C* N0 x! ~/ X( m% z0 p" k+ {b = y^k M ( mod p )
) n4 a) i) O) B m8 i
$ W+ C3 S3 Y/ _/ l* J8 h( W
3 N4 I' c. g4 \2 X1 V$ [( a, b )为密文，是明文的两倍长。解密时计算
! H" \4 q$ C3 z2 v$ S3 L
( C3 F8 L" K; sM = b / a^x ( mod p )
3 r& z7 i, H: e5 c
3 _* l7 g8 M) o3 t; x6 Q! n1 n' g
ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数
. V& k) j0 b: m8 b; T" y$ c( S因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。
! j7 o& I( R$ h9 X" n7 c# w( N
) O! N5 {7 `$ K% u0 {5 |# d0 I \
美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
# G- @+ T9 o @4 ^! j变而来。 |
|
IP卡
狗仔卡
发表于 2004-11-26 20:04:40
收藏
分享
淘帖
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡