|
|
ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。
+ M! B; y1 W/ j密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
, E9 ?0 {: D3 a5 q5 c, NElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算
( H8 d$ J6 L ]# m: p5 k
) W; H' A1 g3 l4 `6 ~! j% Na = g^k ( mod p )
, N* N$ h% J; I/ W
再用扩展 Euclidean 算法对下面方程求解b：
3 t |) e* _! ?1 M* T
! c. z' g& k9 ZM = xa + kb ( mod p - 1 )
; S* S: z# }4 U4 b
" I( d8 L! O w! c E; {' c签名就是( a, b )。随机数k须丢弃。
0 R. T/ z8 |! }7 v
验证时要验证下式：
6 w3 }( ]' P2 H$ v% C9 e! D
4 D1 ]# d2 _+ o0 ^
y^a * a^b ( mod p ) = g^M ( mod p )
$ }, K0 R* ~3 {& s8 a
1 D- M, x z' p5 T0 Z0 T同时一定要检验是否满足1<= a < p。否则签名容易伪造。
; g. ]3 h: B( c0 n% MElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算
$ ]! M# R- _. E4 ?4 B( q
( L( j# U) F& K( g3 ha = g^k ( mod p )
: e3 V3 z8 _3 Kb = y^k M ( mod p )
- v( C' R1 D" E w" X; ^# H$ x$ P- [
% j" N K3 J3 F6 A
& r0 R! b4 {( r5 d( a, b )为密文，是明文的两倍长。解密时计算
/ Z) c; ~5 r1 U" g$ _: _; \0 V' N
% L4 X( C. Y" Q
M = b / a^x ( mod p )
- D' r, a( {' |& [9 O
/ d# k8 {" f* K5 x
ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数
8 [* H* X( s- g9 z' o
因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。
. G: O* U* e2 p# n: V/ G3 M
$ s. m, P" i$ T' j' @- Q% _& n: ^" c 美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
/ p+ |; F' M" \
变而来。 |
|
IP卡
狗仔卡
发表于 2004-11-26 20:04:40
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡