一、基本概念
- 基于离散对数问题
- 非对称加密算法(公钥加密、私钥解密)
- 乘法同态算法
- 生成的密文长度是明文的两倍,且每次加密后都会在密文中生成一个随机数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实现)