|
|
ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。
# L. h! A& }6 b3 Z0 R6 _/ Z密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
3 ]$ }+ ]9 c3 Y# j, F% B2 f
ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算
6 \4 ^, X) H: k4 a% K
5 h; i3 } s+ H9 @' V/ o4 Q9 E
a = g^k ( mod p )
2 @3 s6 N- U7 D" M再用扩展 Euclidean 算法对下面方程求解b：
2 }+ a* I4 N8 S- F- k: Y- q/ b
" T$ [5 s+ S; U8 _# k: B7 j) }/ uM = xa + kb ( mod p - 1 )
; o+ E' k& a$ z) A, w" ^% q4 b
+ o6 [6 K4 a( \签名就是( a, b )。随机数k须丢弃。
$ B0 K4 z2 u/ M; E9 Z+ E. \( X
验证时要验证下式：
! R, r) m& y% f8 H0 \) g; U
! J0 o' n- X( s8 q3 q' F
y^a * a^b ( mod p ) = g^M ( mod p )
% T' D9 L* u7 e, I8 C7 }4 `
" o4 z' q2 O- g3 m3 t# i2 r* |- |- {
同时一定要检验是否满足1<= a < p。否则签名容易伪造。
1 X Q6 Y" t+ s+ s2 ]1 TElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算
! N( C! ]' C2 x3 E& L
- ]8 w( w2 ?' }2 G% ?a = g^k ( mod p )
# y- N* ^% m) D# E6 a. h* |# W6 |" _b = y^k M ( mod p )
& g v# g0 {* p
. g0 }0 v3 T- K* h% t' Z2 z* Z
$ \/ f+ D7 P+ L$ z6 O9 p3 b" Z* r
( a, b )为密文，是明文的两倍长。解密时计算
0 } h# p+ i5 K& c" ^* b7 i9 E
9 Y6 I: J& Z. q1 u- V7 v& @# O/ @
M = b / a^x ( mod p )
% m9 F+ v/ {- q0 f; f3 c
( C4 C2 }$ z* J* Y" ~ ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数
% O# M( w" t; i8 _) p因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。
3 C6 x) z8 c& V) e$ A3 R2 q( Y
4 }2 }4 b2 l8 p( Q
美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
, m7 r. g5 G3 w; X7 k2 V* a变而来。 |
|
IP卡
狗仔卡
发表于 2004-11-26 20:04:40
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡