|
ElGamal算法既能用于数据加密也能用于数字签名,其安全性依赖于计算有限域上离散对数这一难题。 % ^7 z% g: Z% W! @% ?% O2 c3 w( _
密钥对产生办法。首先选择一个素数p,两个随机数, g 和x,g, x < p, 计算 y = g^x ( mod p ),则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。 / M& H! L' m) F
ElGamal用于数字签名。被签信息为M,首先选择一个随机数k, k与 p - 1互质,计算 5 Q" ?8 W7 g6 D8 [6 `" n( i0 j
+ w* z6 `, B( x* [3 q, H
a = g^k ( mod p )
% x- t# p, }6 n" n6 p' w. b再用扩展 Euclidean 算法对下面方程求解b:
" g4 S3 ]0 q3 b+ q2 Q9 i! S
3 \8 _0 E: \+ `$ q' h( k: zM = xa + kb ( mod p - 1 ) ( ]' d# K" `: r
' @3 a2 A+ P, K( H
签名就是( a, b )。随机数k须丢弃。
/ k8 V' t# P' K1 F( Q1 s" ?验证时要验证下式: 1 k. x( j0 O, h O& o$ Q
1 N2 }0 I0 @7 S$ {( i: _& Y- Y
y^a * a^b ( mod p ) = g^M ( mod p ) 1 J: u' h: f1 i( r% K/ K" ~
8 p: @$ l0 Y4 L1 J9 }5 U( S* R同时一定要检验是否满足1<= a < p。否则签名容易伪造。 0 N' R7 l) Q. y$ W
ElGamal用于加密。被加密信息为M,首先选择一个随机数k,k与 p - 1互质,计算 % ?# a8 h1 G, s* S
* m' ~% \# O2 {4 U6 J4 @
a = g^k ( mod p ) 9 J$ k; G V u1 p* b
b = y^k M ( mod p ) 6 P% y+ d1 U; ^' i2 b5 ?
9 r! N, Y3 c& a$ o0 H+ K: W2 A/ B $ e7 K9 @- F- ^3 s4 }; Q8 x/ l
( a, b )为密文,是明文的两倍长。解密时计算 ( Q! L, I" f# b/ E
a9 a" m/ q' j" {" R% D$ ?M = b / a^x ( mod p ) " j8 b M1 l5 `( }
5 V/ T! D; i0 X8 B
ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大,且p-1至少包含一个大素数
% e6 |6 ~, |- F4 t" \+ X) A+ b# `8 l因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g,若选取不当则签名容易伪造,应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。 9 C: r% u, d% G3 T" l( P3 S' [
9 g( v/ y2 n( Q1 q% M! n5 n) L% C
美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
: A3 v6 W* I- I8 s/ M变而来。 |
|