文章横幅PC版
文章横幅iPad版
文章横幅手机版

ElGamal数字签名

TIME:2019-03-21 13:39  click: 265 次 来源: 未知

ElGamal数字签名算法需要使用随机数,它是一种非确定性的签名方案,但它的运算过程并非是ElGamal加密算法的逆过程。

1.用户选择密钥

系统先选取一个大素数p及p的本原根a,用户A选择一个随机数x(1xp-1)作为自己的私钥,计算y=axmod p,将y作为自己的公钥。整个系统公开的参数有大素数p、本原根a以及每个用户的公钥;而每个用户的私钥x则严格保密。

2.签名过程

给定消息M,用户A进行下述计算来实现签名。

(1)选择随机数k∈Zp*,且k与p-1互素(注意:随机数k需要保密)。

(2)签名方A对消息M进行散列压缩后得到消息散列码H(M),再计算

r=ak mod p

s=(H(M)-xr)k-1mod(p-1)

将(r,s)作为用户A对消息M的数字签名,与消息M一起发送给接收方。

3.验证签名的过程

接收方B在收到消息M与数字签名(r,s)后,先计算消息M的散列码H(M)。然后计算

yrrs mod p=aH(M) mod p

如果上式成立,则可确信(r,s)为有效签名,否则认为签名是伪造的。

4.证明验证签名的正确性

若(r,s)为合法用户采用 ElGamal数字签名算法对消息M的签名,则

yrrs=(ax)r(ak)s=axr+ksmod p

又因为

s=(H(M)-xr)k-1mod(p-1)

两边乘k再移项得

ks+xr=H(M)mod(p-1)

根据模运算规则有

axr+ks=aH(M)mod pmod p

由费马定理的推论,ak=ak mod(p-1)mod p,将k替换成H(M),有

axr+ks=aH(M)mod p

因此有

yrrs=aH(M)mod p

 

上一篇:什么是虚拟专用网络 下一篇:IPSec的工作原理