|
|
ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。
7 {0 E- w/ b- Q. M密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
! i- f. x2 L% g4 o! `0 |3 q, Y+ ~ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算
: }/ G. {$ U' R& D% Z; }
# i1 D D. C2 N6 ua = g^k ( mod p )
) S1 s/ D" _9 p6 E- B/ F
再用扩展 Euclidean 算法对下面方程求解b：
7 U* R6 |5 |& G# ]5 m2 N/ C
. f* r9 n; l( Y6 e& f& LM = xa + kb ( mod p - 1 )
6 b9 I. z* G* W. C+ D, ^
# K: x6 G9 `# q签名就是( a, b )。随机数k须丢弃。
: O; {. U5 m- Q; {" K' q. y
验证时要验证下式：
) V. Y, m6 V5 h1 K% n
4 K& m- d9 c4 r, u6 r
y^a * a^b ( mod p ) = g^M ( mod p )
G: N# |. [, H* x
& u# F$ ^+ G6 N! ^+ n- {( J5 a# `. K同时一定要检验是否满足1<= a < p。否则签名容易伪造。
2 Y5 s! J4 j EElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算
/ _$ z5 H, {: Y" }: Q
' ~0 ?% z0 V0 w" f
a = g^k ( mod p )
% U, V6 O+ s8 M9 Q+ xb = y^k M ( mod p )
% @1 c/ X3 j% P: Q
0 P! W3 z& _% D) t) s
p3 _2 q7 _3 f) h" p
( a, b )为密文，是明文的两倍长。解密时计算
+ f* v/ ~& B/ L, w
: m- W; f3 F/ ^% m ?( j! b0 F W
M = b / a^x ( mod p )
$ A( t( ~5 _* J3 X5 R
+ W" B! x! [ d! W' f' Z6 A! H
ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数
9 m4 \+ k7 Z- Y4 Z/ l
因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。
+ d# y( b- @" q- V
3 j1 A- h; c% F4 \
美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
9 ~' `" T4 @% T4 j* `) q5 y5 b$ S6 ^变而来。 |
|
IP卡
狗仔卡
发表于 2004-11-26 20:04:40
收藏
分享
淘帖
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡