ElGamal加密算法|ElGamal签名算法|公钥密码|数字签名|密码学|信息安全

ElGamal签名算法

密钥产生

  • 确定一个大素数p
  • 取p的一个本原根g
  • 在Zp域上选择一个随机数x
  • y = gx%p
  • (y, g, p)为公钥,x为私钥

签名算法

设待签名的消息为m

  • C1=gk%p
  • C2=(H(m)-x*C_1) * k-1%(p-1)
  • 输出签名(C1,C2)和消息m

验证算法

  • y

    C

    1

    C

    1

    C

    2

    =

    H

    (

    m

    )

    y^{C_1}*C_1^{C_2}=H(m)

    yC1C1C2=H(m)

正确性证明

ElGamal加密算法

简单介绍

  • EIGamal密码是除了RSA密码之外最有代表性的公开密钥密码

  • EIGamal是建立在离散对数的困难问题上的一种公钥体制密码

密钥产生

  • 选一个素数p,以及小于p的两个随机数gx
  • 计算

    y

    =

    g

    x

    y = g^x

    y=gx%p

  • 公钥为(y, g, p),私钥为x

算法加密过程

M为明文

  • 选取一个与p-1互素的整数k
  • C

    1

    =

    g

    k

    C_1=g^k

    C1=gk%p

  • C

    2

    =

    y

    k

    M

    C_2=y^kM

    C2=ykM%p

  • (

    C

    1

    ,

    C

    2

    )

    (C_1,C_2)

    (C1,C2)即为密文

算法解密过程

解密方法:

C

2

C

1

x

frac{C_2}{C_1^x}

C1xC2%p

证明:

在这里插入图片描述

EIGamal 密码体制安全性

由于私钥x是通信双方共享的,别人不知道

所以,当加密完了以后的密文(y, g, p)被别人盗取后,想获取明文M,只能通过

C

2

=

y

k

M

C_2=y^kM

C2=ykM%p来获得,这里面只有kM是不知道的,所以只要获得了k就能获得M,而想获得k,只有通过

C

1

=

g

k

C_1=g^k

C1=gk%p来获取,这里面虽然只有k是未知数,但是求离散对数的过程是很困难的,尤其是对p很大的情,所以EIGamal密码体制很安全

举个例子

  • 取p=11, g=5, x=2
  • 则 y = g x%p = 3
  • 取 k 为 7, m为10
  • 则C1 = gk%p = 3
  • C2 = yk*m % p = 2
  • 则C1x%p= 9
  • 9在模11下的逆元为5
  • 所以

    C

    2

    C

    1

    x

    =

    2

    5

    frac{C_2}{C_1 ^x}=2 * 5

    C1xC2=25%10 =10,所以解密成功

ElGamal签名算法

密钥产生

  • 确定一个大素数p
  • 取p的一个本原根g
  • 在Zp域上选择一个随机数x
  • y = gx%p
  • (y, g, p)为公钥,x为私钥

签名算法

设待签名的消息为m

  • 取一个与p-1互质的k

  • C1=gk%p

  • C2=(H(m)-x*C1) * k-1%(p-1)

  • 输出签名(C1,C2)和消息m

验证算法

  • y

    C

    1

    C

    1

    C

    2

    =

    g

    H

    (

    m

    )

    y^{C_1}*C_1^{C_2}=g^{H(m)}

    yC1C1C2=gH(m)%p

正确性证明

在这里插入图片描述

举个例子

  • p = 11
  • g = 2,(注意必须取p的一个生成元)
  • x = 6
  • 计算y = gx%p = 9
  • 取 k = 7
  • 计算C1=gk%p = 7
  • 利用扩展欧几里得计算k在模p-1意义下的逆元k-1= 3
  • 假设需要验证的消息m经过哈希后的结果是H = 10
  • 则计算C2 = ((H - x * C1) * k-1 ) % (p-1) = 4
  • 验证:计算

    y

    C

    1

    C

    1

    C

    2

    y^{C_{1}} * C_{1}^{C_2}

    yC1C1C2%p = 1

  • 计算Hg%p=1
  • 所以验证成功
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>