Elgamal加密与签名算法简述

简述

ElGamal算法,是由T.Elgamal于1984年提出的公钥密码体制和椭圆曲线加密体系。既能用于数据加密也能用于数字签名,其安全性依赖于计算有限域上离散对数这一难题即CDH假设。在加密过程中,生成的密文长度是明文的两倍,且每次加密后都会在密文中生成一个随机数K,其实现依据是求解离散对数是困难的,而其逆运算指数运算可以应用快速幂的方法有效地计算。也就是说,在适当的群G中,指数函数是单向函数。

用于签名

  1. 生成密钥: 确定一个大素数$p$和它的一个原根$g$,在$Z_p$域上选择一个随机数$x$作为密钥,并计算$$y=g^x\ mod\ p$$ $(p,g,y)$作为公钥。
  2. 签名算法: 用$m$表示待签名信息,在$Z_p$域上选择一个与$p-1$互质的数$k$,并计算$$C_1=g^k\ mod\ p$$ 再运用Ext_Euclidean算法求出$C_2$,使其满足:$$m\equiv ax+C_2k\ \ mod\ p-1$$
  3. 输出签名: $(C_1,C_2)$.
  4. 验证签名: 验证下式$$y^{C_1}\cdot \ C_1^{C_2}\equiv\ g^m\ mod\ p$$ $$C_1\in Z_p$$
  5. 原理: 这里应用了欧拉定理。

用于加密

  1. 生成密钥:确定一个大素数$p$和它的一个原根$g$,在$Z_p$域上选择一个随机数$x$作为密钥,并计算$$y=g^x\ mod\ p$$
    $(p,g,y)$作为公钥。
  2. 加密算法:用$m$表示待加密信息,在$Z_p$域上选择一个与$p-1$互质的数$k$,并计算$$C_1=g^k\ mod\ p$$
    $$C_2=y^k\cdot m\ \ mod\ p$$
  3. 输出密文$(C_1,C_2)$
  4. 解密算法:计算下式$$m=C_2\cdot(C_1^x)^{-1}\ \ mod\  p$$
    这里需运用Ext_Euclidean算法求乘法逆元。