密钥产生

ElGamal算法首先选择大素数$q$及其原根$\alpha$

其公私钥产生过程如下

  1. 选择随机整数$1<X_A<q-1$
  2. 计算$Y_A=\alpha^{X_A}\mod q$

则用户的私钥为$X_A$，公钥为${q,\alpha, Y_A}$

ElGamal加密/解密

首先将消息M分组，每块长度不小于$q$

发送方选择任意整数$k$使得$1\leq k\leq q-1$，并计算一次性密钥$K=(Y_A)^k\mod q$
按公式$C_1=\alpha^k\mod q, C_2=KM\mod q$加密，则密文为$(C_1,C_2)$

接收方计算$K=(C_1)^{X_A}\mod q$恢复密钥
按公式$M=C_2K^{-1}\mod q$即可恢复明文

注意每个消息分块都要有随机且唯一的$k$

椭圆曲线密码下的ElGamal

此处以域$Z_p$上的椭圆曲线为例

在$E_p(a,b)$中挑选基点$G$满足$G$的阶很大，其中$G$的阶$n$定义为使得$nG=O$的最小正整数

首先A选择一个整数$n_A<n$作为私钥，然后计算公钥$P_A=n_A\times G$

B要给A发送消息时，先将明文消息$m$编码为$E_p(a,b)$上的点$P_m$
之后随机选择整数$k<n$，计算$C_1=kG,C_2=P_m+kP_A$，则密文为$(C_1,C_2)$

A收到消息后计算$P_m=C_2-n_AC_1$即可解密

ElGamal数字签名

可参考博客 经典数字签名算法概述