开云手机版登录入口
标题: ElGamal加密算法 [打印本页]
作者: 乐乐天 时间: 2004-11-26 20:04
标题: ElGamal加密算法
ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。
' r, j5 D% k E3 K; u" x
密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
+ Q: F4 [5 s9 Q9 k+ F
ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算
! _* X0 z4 N. L5 b$ S2 n
9 P* ~* }! ]% ]( L
a = g^k ( mod p )
$ r! F' i- A( o( x
再用扩展 Euclidean 算法对下面方程求解b：
7 \/ b' d4 N8 t5 y5 u9 Z
! O7 W1 Z1 l0 \0 C' a5 p5 Q
M = xa + kb ( mod p - 1 )
. E5 u# ?3 P' o" {' m
$ s) R* @0 j5 p6 Q/ b) p7 I签名就是( a, b )。随机数k须丢弃。
& ^; I( a. T8 p$ ~3 [' @验证时要验证下式：
; L. q' F C+ F
D9 G- U. [$ {( K) `( K" gy^a * a^b ( mod p ) = g^M ( mod p )
; U0 W; Y) N) n; R. I' ^
' F" A% H4 E+ j
同时一定要检验是否满足1<= a < p。否则签名容易伪造。
3 j9 [5 ], H. r% X% ~
ElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算
1 }3 }" G) \, _2 V; Q! T( Z) w
3 M8 x. l/ L5 {2 d- g
a = g^k ( mod p )
! [% l2 O H0 F3 K5 y
b = y^k M ( mod p )
" a( I- o6 Z/ {4 V9 \
: ?9 _& \% n! J; m
. Z* {( H5 x% E) w
( a, b )为密文，是明文的两倍长。解密时计算
% k- H/ X0 u' S, H' |
7 M5 K. {2 C2 t1 ~; R* AM = b / a^x ( mod p )
: [$ T) H2 D- d
4 e: M8 P1 c2 j' T: n ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数
7 y3 R3 X' b7 U7 g0 e: Y w因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。
3 o( K! Y% k( S0 \- k; X- j
9 y0 W* U) ]* w
美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
7 ~2 u4 V0 B6 j% u* V5 q- S; T0 i变而来。
| 欢迎光临 开云手机版登录入口 (/) |
Powered by Discuz! X3.4 |