一、基本概念
- 基于离散对数问题
- 非对称加密算法（公钥加密、私钥解密）
- 乘法同态算法
- 生成的密文长度是明文的两倍，且每次加密后都会在密文中生成一个随机数K
1、离散对数问题
一种基于同余运算和原根的一种对数运算
原根：设素数$p$，若存在一个正整数$α$，使得$α,α^2,...,α^{p-1}$关于模$p$互斥（不同余），则称$α$为模$p$的一个原根。
于是有如下运算：
$α$的幂乘运算：
$$ y = α^x(mod\ p), 1\le x\le p-1 $$
$α$的对数运算：
$$ x=log_α y,1 \le y \le p-1 $$
只要$p$足够大，求解离散对数问题是相当复杂的。离散对数问题具有较好的单向性。
单向函数 是一种具有下述特点的单射函数：对于每一个输入，函数值都容易计算（多项式时间），但是给出一个随机输入的函数值，算出原始输入却比较困难（无法在多项式时间内使用确定性图灵机计算）。 单向函数是否存在仍然是计算机科学中的一个开放性问题。事实上，如果单向函数存在，将证明复杂性类P/NP问题中，P不等于NP。
2、ELGamal加解密算法
0x01 准备公钥和私钥
- 随机地选择一个大素数$p$，且要求$p-1$有大素数因子，$p$公开。
- 选择一个模$p$的原根$α$，$α$公开。
- 随机选择一个整数$d\ (1\lt d\lt p-1)$作为私钥，$d$保密。
- 计算$y=α^d(mod\ p)$作为公钥，$y$公开。
|符号|含义|是否公开|
|-|-|-|
|$p$|大素数（$p-1$有大素数因子）|公开|
|$α$|$p$的原根|公开|
|$d$|私钥$(1\lt d\lt p-1)$|保密|
|$y$|公钥 $y=α^d(mod\ p)$|公开|
0x02 加密
对明文 $M$ 进行加密
- 随机地选取一个整数$k（1＜k＜p-1）$。
- 计算$U=y^k(mod\ p)、C1=α^k(mod\ p)、C2=MU(mod\ p)$。
- 取$(C1,C2)$作为密文。
0x03 解密
$M= C_2/C_1^d\ (mod\ p)=C_2{C_1^d}^{-1}(mod\ p)$。
3、实例
选取素数$p=150001$，原根$α=7$，私钥$d = 113$
=> $y = α^d\ \% p = 66436$
加密：
随机数$k = 1000$，明文$M = 809$。
=> $C_1 = α^k\ (mod\ p) = 90429$
=> $C_2 = MU = M·y^k\ \%p = 15061$
=> $(c1,c2)=(90429,15061)$
解密：
${C_1^d} = 4654$
${C_1^d}^{-1} = 4654^{-1} = 80802 (mod\ p)$
=> 得出： $M = C_2{C_1^d}^{-1} (mod\ p) = 15061 * 80802 mod\ p = 809$
4、安全性问题
由于ELGamal密码的安全性建立在GF(p)上离散对数的困难性之上，而目前尚无求解GF(p)上离散对数的有效算法，所以在$p$足够大时ELGamal密码是安全的。理想情况下p为强素数，$p-1=2q$，$q$为大素数。
为了安全加密所使用的k必须是一次性的。如果长期使用同一个$k$加密的话，就可能被攻击者获取，从而根据$V=U=y^k(mod\ p)$，$M=C_2V^{-1}(mod\ p)$而得到明文。另外，使用同一个$k$加密不同的明文$M$和$M'$，则由于$\frac{C_2}{C_2'} = \frac{M}{M'}$，如果攻击者知道$M$，则很容易求出$M'$。此外，$k$选取时还要保证$U=y^k(mod\ p)≠1$。
二、算法实现
1、算法细节
0x01 判断原根
已知$a$和$m$互素，如果$d$是满足$a^d=1(mod\ m)$的最小正整数，则称$d$为$a$模$m$的阶，记为$d=σ_m(a)$。由于$a$和$m$互素，根据欧拉定理$a^{φ(m)}=1(mod\ m)$，由此可以得到$σ_m(a) | φ(m)$。
若$a$是$m$的原根，则$σ_m(a)=φ(m)$。
根据上述两点，推出逆否命题：如果$∃\ d≠φ(m)$，使得$a^d=1(mod\ m)$，则$a$不是模$m$的原根。
所以判断$a$是否为模$m$的原根，最快的方法就是判断$φ(m)$的每一个因子$d$是否使得$a^d=1(mod\ m)$。如果不存在这样的$d$，则$a$是模$m$的原根。
0x02 实例：判断2是不是模11的原根
$φ(11)=10$，$10$的因子有$1、2、5、10$，
$2^1(mod\ 11)=2$、$2^2(mod\ 11)=4$、$2^5(mod\ 11)=10$、$2^{10}(mod\ 11)=1$
因此，$2$是模$11$的原根。
2、Java实现
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Random;
public class ELGamal {
static BigInteger p, alpha, d, y;
public static void main(String[] args) {
init();
BigInteger M = new BigInteger("809");
BigInteger[] C = encrypt(M);
System.out.println(Arrays.toString(C));
BigInteger M2 = decrypt(C);
System.out.println(M2);
}
/**
* 初始化参数：素数p、原根α、私钥d，公钥y
*/
private static void init(){
do {
p = BigInteger.probablePrime(10, new Random());
} while (p.subtract(BigInteger.ONE).divide(new BigInteger("2")).isProbablePrime(100)); // (p-1)/2可能是个素数
do {
alpha = new BigInteger(10, new Random());
} while (! isOrigin(alpha, p)); // 判断是否是原根
do {
d = new BigInteger(10, new Random()); // 私钥
} while (d.compareTo(BigInteger.ONE) <= 0 || d.compareTo(p.subtract(BigInteger.ONE)) >= 0);
//p = BigInteger.valueOf(150001); alpha = BigInteger.valueOf(7); d = BigInteger.valueOf(113);
y = alpha.modPow(d, p); // 公钥y = alpha^d %p
System.out.println("p = " + p + ", alpha = " + alpha + ", d = " + d + ", y = " + y);
}
/**
* 加密
* @return (C0, C1)
*/
private static BigInteger[] encrypt(BigInteger M) {
BigInteger[] C = new BigInteger[2]; // C0 C1
BigInteger k, U;
do {
do {
k = new BigInteger(10, new Random());
} while (k.compareTo(BigInteger.ONE) <= 0 || k.compareTo(p.subtract(BigInteger.ONE)) >= 0); // 必须保证 k > 1 && k < p - 1
U = y.modPow(k, p);
} while (U.intValue() == 1);
//k = BigInteger.valueOf(1000);
System.out.println("k = " + k);
C[0] = alpha.modPow(k, p); // C0 = α^k
C[1] = U.multiply(M).mod(p); // C1 = MU %p
return C;
}
/**
* 解密
*/
private static BigInteger decrypt(BigInteger[] C) {
BigInteger V = C[0].modPow(d, p); // C0^d
BigInteger M = C[1].multiply(V.modPow(new BigInteger("-1"), p)).mod(p); // C1 * C0^-1 mod p
return M;
}
/**
* 判断a是否为模m的原根，其中m为素数
*
* **判断$φ(m)$的每一个因子$d$是否使得$a^d=1(mod\ m)$。如果不存在这样的$d$，则$a$是模$m$的原根。**
*/
private static boolean isOrigin(BigInteger a, BigInteger m) {
if (a.gcd(m).intValue() != 1) return false;
BigInteger i = new BigInteger("2");
while (i.compareTo(m.subtract(BigInteger.ONE)) < 0) {
if (m.mod(i).intValue() == 0) { // 判断因子
if (a.modPow(i, m).intValue() == 1)
return false; // 如果 a^因子 == 1，说明不是原根
while (m.mod(i).intValue() == 0)
m = m.divide(i); // 把因子除尽
}
i = i.add(BigInteger.ONE); // i++
}
return true;
}
}
三、ELGamal数字签名
整数模 n 乘法群：在同余理论中，模 $**n**$ 的互质同余类成一个乘法群，称为整数模 n 乘法群翻译成人话就是：在$[1,n-1]$区间内互质的数组成例如：模$4$的乘法群 $\{1, 3\}$、模$8$的乘法群 $\{1, 3, 5, 7\}$、模 $16$ 乘法群$\{1,3,5,7,9,11,13,15\}$
0x01 系统初始化
选取一个大的素数$p$，$g$是GF(p)的生成元，$p,g$公开
0x02 数字签名
假定要发送消息$m \in [1, p-1]$
- 随机选取整数$x$，$1≤x≤p-2$，计算$y=g^x(mod p)$，$y$是公开密钥，而$x$是保密密钥。
- 随机选取 $k \in [1, p-1]$，且$gcd(k, p-1) = 1$，即$k,p$互质
- 计算$r,s$，$r = g^k\ mod \ p$，$s = k^{-1}(m-xr)\ mod\ p$
- $(m,rs)$即为对消息$m$的数字签名
0x03 签名验证
公开的变量有$p, g, y$
- 计算$left$, $left = g^m\ mod\ p$
- 计算$right$, $right = y^rr^s\ mod\ p$
- 比较$left$和$right$，相等则验证通过。
参考资料：
ELGamal详解（Java实现）