|
|
ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。
/ l" c7 h+ ]1 w/ O* Y: d密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
3 N4 z0 Q/ z4 g9 VElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算
) R7 D# T7 n5 e9 i) i2 K2 ?
0 d- [* a1 N8 f: _/ u% ha = g^k ( mod p )
* s9 ?9 k' w: h/ P$ D6 i: ^* S" l& \# z再用扩展 Euclidean 算法对下面方程求解b：
' L# Y7 V9 @* T: t
( z$ U0 N& d# ]7 [2 JM = xa + kb ( mod p - 1 )
) `7 _4 q$ H; a4 l
* K: f; Z) `: v. G- j
签名就是( a, b )。随机数k须丢弃。
/ G" f; \; Y/ m/ a. o4 h
验证时要验证下式：
# H& z' t/ b4 z R7 T4 ]# I6 N
; I9 z! O1 a& E9 W% d
y^a * a^b ( mod p ) = g^M ( mod p )
6 F/ l- V. b { N: F$ D
: |+ e2 x W3 f; t# S% A2 ~2 O3 q) m同时一定要检验是否满足1<= a < p。否则签名容易伪造。
- ~4 a- p ` A' A+ E/ ?
ElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算
B+ C) o3 K/ u, Y( G7 j% t9 C& ?
: w8 J% k# I5 c% u5 S# \
a = g^k ( mod p )
+ S3 |6 e6 C( c' a4 S$ E: ?' M" [b = y^k M ( mod p )
% b; z# r: r8 u# \
# E+ z L7 a) @& C. j
8 L$ s9 p0 [2 H1 I. v# R. E, {$ h
( a, b )为密文，是明文的两倍长。解密时计算
! G) t g( E4 G, s4 @ H/ L
8 o, e7 _- B% r8 L2 U8 [+ |M = b / a^x ( mod p )
2 C- H6 u+ t3 M5 Z( Z
) U: {, D) N8 b ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数
8 U/ l0 `9 n( i2 ]8 D因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。
: E7 O" w8 y% q+ m
: v) r: _8 G0 t& _ 美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
; H( m* d' j0 k变而来。 |
|
IP卡
狗仔卡
发表于 2004-11-26 20:04:40
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡