中国安防论坛

 找回密码
 注册
查看: 5017|回复: 0

ElGamal加密算法

[复制链接]

安防中学生

Rank: 2

积分
147
发表于 2004-11-26 20:04:40 | 显示全部楼层 |阅读模式
ElGamal算法既能用于数据加密也能用于数字签名,其安全性依赖于计算有限域上离散对数这一难题。
% ^7 z% g: Z% W! @% ?% O2 c3 w( _ 密钥对产生办法。首先选择一个素数p,两个随机数, g 和x,g, x < p, 计算 y = g^x ( mod p ),则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
/ M& H! L' m) F ElGamal用于数字签名。被签信息为M,首先选择一个随机数k, k与 p - 1互质,计算
5 Q" ?8 W7 g6 D8 [6 `" n( i0 j
+ w* z6 `, B( x* [3 q, H a = g^k ( mod p )
% x- t# p, }6 n" n6 p' w. b再用扩展 Euclidean 算法对下面方程求解b:
" g4 S3 ]0 q3 b+ q2 Q9 i! S
3 \8 _0 E: \+ `$ q' h( k: zM = xa + kb ( mod p - 1 )
( ]' d# K" `: r
' @3 a2 A+ P, K( H 签名就是( a, b )。随机数k须丢弃。
/ k8 V' t# P' K1 F( Q1 s" ?验证时要验证下式:
1 k. x( j0 O, h O& o$ Q
1 N2 }0 I0 @7 S$ {( i: _& Y- Y y^a * a^b ( mod p ) = g^M ( mod p )
1 J: u' h: f1 i( r% K/ K" ~
8 p: @$ l0 Y4 L1 J9 }5 U( S* R同时一定要检验是否满足1<= a < p。否则签名容易伪造。
0 N' R7 l) Q. y$ W ElGamal用于加密。被加密信息为M,首先选择一个随机数k,k与 p - 1互质,计算
% ?# a8 h1 G, s* S
* m' ~% \# O2 {4 U6 J4 @ a = g^k ( mod p )
9 J$ k; G V u1 p* b b = y^k M ( mod p )
6 P% y+ d1 U; ^' i2 b5 ?
9 r! N, Y3 c& a$ o0 H+ K: W2 A/ B
$ e7 K9 @- F- ^3 s4 }; Q8 x/ l ( a, b )为密文,是明文的两倍长。解密时计算
( Q! L, I" f# b/ E
a9 a" m/ q' j" {" R% D$ ?M = b / a^x ( mod p )
" j8 b M1 l5 `( }
5 V/ T! D; i0 X8 B   ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大,且p-1至少包含一个大素数
% e6 |6 ~, |- F4 t" \+ X) A+ b# `8 l因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g,若选取不当则签名容易伪造,应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。
9 C: r% u, d% G3 T" l( P3 S' [
9 g( v/ y2 n( Q1 q% M! n5 n) L% C   美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
: A3 v6 W* I- I8 s/ M变而来。
不在競爭中變坏,就在沉默中變態
您需要登录后才可以回帖 登录 | 注册

本版积分规则

安豆网|Archiver|手机版|中国安防论坛 ( 粤ICP备09063021号 )

GMT+8, 2025-9-16 13:17 , Processed in 0.070995 second(s), 18 queries .

Powered by Discuz! X3.4 Licensed

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表