ElGamal
文章给出了ElGamal加密算法的一个实现。未做任何优化，仅供学习参考，计算速度跟专业的库相比应该有很大差距。虽然密码学算法是安全的，但是工程实现中可能存在其他攻击，没有足够的信心，不要使用自己写的加密算法做加密。
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
/**
* @author miracle
* @date 2022/9/21 19:06
* @description: <br/>
*/
public class Main
{
// --------------------------------------------------- 工具函数 -------------------------------------------------------------------
/**
* 大整数的大整数幂对一个大整数求幂的结果(Big Integer Power Modulus)
*
* @param base 底数
* @param exponent 指数
* @param n 模数
* @return base的exponent次幂模n
*/
public static BigInteger BigIntegerPM(BigInteger base,BigInteger exponent,BigInteger n){
// 保证底数大于模数
if(base.compareTo(n) == -1){
base = base.mod(n);
}
BigInteger res = solvePM(base,exponent,n);
return res;
}
/**
* 1、数论中有如下结论
* (a + b) % p = (a % p + b % p) % p
* (a - b) % p = (a % p - b % p) % p
* (a * b) % p = (a % p * b % p) % p
* (a ^ b) % p = ((a % p) ^ b) % p
* (a ^ b) % p = ((a % p) ^ b) % p
* <p>
* 2、分治法求解
* (1) 若 exponent 为奇数： 令 exponent = 2k+1, k 为非负整数 , 则
* a^(2k+1) = (a^k)^2 *a ; a^(2k+1) % n = ((a^k % n)^2 % n * a % n) % n = [ (a^k % n)^2 * a ] % n
* (2) 若power 为偶数: 令 power = 2k, k为非负整数， 则
* a^(2k) = (a^k)^2 ; a^(2k) % n = (a^k % n)^2 % n
* (3) 若 power == 0: 返回 1。
* <p>
* 3、算法分析
* 时间复杂度 T(n) = O( log(n) ) (这里的n指的是 exponent)
* 空间复杂度 T(n) = O( lon(n) ) (递归函数的空间开销)
*
* @param base 底数
* @param exponent 指数
* @param n 模数
* @return base的exponent次幂模n
*/
public static BigInteger solvePM(BigInteger base,BigInteger exponent,BigInteger n){
if(exponent == BigInteger.ZERO){
return new BigInteger("1");
}
if(exponent.mod(new BigInteger("2")) == BigInteger.ZERO){
BigInteger two = new BigInteger("2");
base = solvePM(base,exponent.divide(two),n).pow(2);
return base.mod(n);
}
else{
BigInteger two = new BigInteger("2");
base = solvePM(base,exponent.divide(two),n).pow(2)
.multiply(base);
return base.mod(n);
}
}
/**
* 产生一个范围在 [start,end]之间的随机大整数
*
* @param start 随机数的最小值
* @param end 随机数的最大值
* @return 返回一个范围在[start,end]之间的随机大整数,如果start<end ， 返回null
*/
public static BigInteger random(BigInteger start,BigInteger end){
if(start.compareTo(end) > 0){
return null;
}
if(start.compareTo(end) == 0){
return end;
}
BigInteger a;
do{
a = new BigInteger((end.subtract(start)).bitLength(),new Random());
}
while(a.compareTo(end.subtract(start)) > 0);
a = a.add(start);
return a;
}
/**
* 针对大整数的扩展的欧几里得算法
* 时间复杂度T(n) = O(log n)
*
* @param a 任意长度的整数
* @param b 任意长度的整数
* @return a 和 b 的最大公约数以及 s 和 t组成的map,其中 key = "gcd" 的 value 是 gcd(a,b)
*/
public static Map<String,BigInteger> gcdExtend(BigInteger a,BigInteger b){
Map<String,BigInteger> res = new HashMap<>();
BigInteger r, r0 = a, r1 = b;
BigInteger s0 = BigInteger.ONE;
BigInteger t0 = BigInteger.ZERO;
BigInteger s1 = BigInteger.ZERO;
BigInteger t1 = BigInteger.ONE;
BigInteger s = BigInteger.ONE;
BigInteger t = BigInteger.ZERO;
// 如果 a < b; 交换 a,b ; 保证 a >= b
if(a.compareTo(b) == -1){
r0 = b;
r1 = a;
s0 = BigInteger.ZERO;
t0 = BigInteger.ONE;
s1 = BigInteger.ONE;
t1 = BigInteger.ZERO;
}
// 以下两种特殊情况处理
if(r1 == BigInteger.ZERO){
res.put("gcd",r0);
res.put("s",BigInteger.ONE);
res.put("t",BigInteger.ZERO);
return res;
}
if(a.mod(b) == BigInteger.ZERO){
res.put("gcd",r1);
res.put("s",BigInteger.ZERO);
res.put("t",BigInteger.ONE);
return res;
}
// 迭代求解 s和t 使得 as + bt = gcd(a,b)
BigInteger qi = BigInteger.ZERO;
while(r0.mod(r1) != BigInteger.ZERO){
qi = r0.divide(r1);
s = s0.subtract(s1.multiply(qi));
t = t0.subtract(t1.multiply(qi));
s0 = s1;
t0 = t1;
s1 = s;
t1 = t;
r = r0.mod(r1);
r0 = r1;
r1 = r;
}
// 找到相应的 s和t 后 , 返回结果
BigInteger as = a.multiply(s);
BigInteger bt = b.multiply(t);
res.put("gcd",as.add(bt));
res.put("s",s);
res.put("t",t);
return res;
}
/**
* 求 a 在 模n 下的乘法逆元（扩展的欧几里得算法）
* 这里 a 和 n 都是 BigInteger 类型的
*
* @param a 求a的乘法逆元
* @param n 模数
* @return 存在乘法逆元时，返回 a 在 模n 下的乘法逆元。否则返回 -1
*/
public static BigInteger getMultiplicativeInverse(BigInteger a,BigInteger n){
Map<String,BigInteger> map = gcdExtend(a,n);
if(map.get("gcd")
.compareTo(BigInteger.ONE) == 0){
BigInteger s = map.get("s");
while(s.compareTo(BigInteger.ZERO) == -1){
s = s.add(n);
}
while(s.compareTo(n) == 1){
s = s.subtract(n);
}
return s;
}
else{
System.out.println("getMultiplicativeInverse()提示您: " + a + "在模" + n + "下没有乘法逆元！");
return new BigInteger("-1");
}
}
/**
* 返回int型数据的位数
*
* @param number 数据
* @return 数据的位数
*/
public static int bitOfInt(int number){
if(number < 0){
number = -number;
}
int[] sizeTable = {9,99,999,9999,99999,999999,9999999,99999999,999999999,Integer.MAX_VALUE};
int i = 0;
while(number > sizeTable[i++])
;
return i;
}
/**
* Miller-Rabin素性判定
* 算法思路
* 设n是一个奇数，n-1 = 2^t * m,其中m是一个奇数。要测试n是否为素数，
* ① 先随机选择一个介于 [2,n-2]区间内的整数a,如果a^m ≠ 1 且
* ② 对所有的满足 r ∈ [0,k-1] 的整数有，a^(2^r * m) ≠ -1 ， 则有n一定是合数。否则，n有很大可能是素数。
* (目前可以在数学上证明，Miller-Rabin将合数判定为素数的概率小于1/4，而事实上经验告诉我们，概率比1/4小得多)
* <p>
* 时间复杂度： T(n) = O(log n)
*
* @param n 待判定数字
* @param k 迭代的轮数，迭代k次后，将合数判定为素数的概率为 1/4^k
* @return 是素数返回true,是合数返回false。注意返回false一定是合数，返回true，有1/4^k 的概率是合数
*/
public static boolean isPrime_Miller_Rabin(BigInteger n,int k){
if(n.compareTo(BigInteger.ONE) <= 0){
return false;
}
// 特殊情况，n为2或3时，MyTools.random返回为null
if(n.compareTo(new BigInteger("2")) == 0 || n.compareTo(new BigInteger("3")) == 0){
return true;
}
// Miller-Rabin素性判定
BigInteger two = new BigInteger("2");
BigInteger m = n.subtract(BigInteger.ONE);
int t = 0;
while(m.mod(two) == BigInteger.ZERO){
m = m.divide(two);
t++;
}
for(int i = 0; i < k; i++){
BigInteger a = random(two,n.subtract(two));
if(BigIntegerPM(a,m,n)
.compareTo(BigInteger.ONE) != 0){
int r;
for(r = 0; r <= t - 1; r++){
if(BigIntegerPM(a,two.pow(r)
.multiply(m),n)
.subtract(n)
.compareTo(new BigInteger("-1")) == 0){
break;
}
}
if(r == t){
return false;
}
}
}
return true;
}
// 获得Miller-Rabin素数检测的检测次数
private static int getTryTime(BigInteger n){
//copy自jdk源码, n的bit数越多, 需要的Miller-Rabin检测次数就越少
int sizeInBits = n.bitLength();
int tryTime = 0;
if(sizeInBits < 100){
tryTime = 50;
}
else if(sizeInBits < 256){
tryTime = 27;
}
else if(sizeInBits < 512){
tryTime = 15;
}
else if(sizeInBits < 768){
tryTime = 8;
}
else if(sizeInBits < 1024){
tryTime = 4;
}
else{
tryTime = 2;
}
return tryTime;
}
/**
* 判断一个数是否是素数
* 当 num 较小时，使用查询素数表和查看num是不是小素数的倍数的方法对num进行素性判定
* 当 使用上述方法无法判断 num 的素性时，采用 Miller-Rabin进行k轮素性判定，其中k的值根据num的大小不同而动态求出。
*
* @param num 待判断的数
* @return 素数返回true，合数返回false
*/
public static boolean isPrime(BigInteger num){
// # 创建小素数的列表,可以大幅加快速度
int[] small_primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
if(num.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) < 0){
long n = num.longValue();
// # 如果是小素数,那么直接返回true
for(int i = 0; i < small_primes.length; i++){
if(n == small_primes[i]){
return true;
}
}
// #如果大数是这些小素数的倍数,那么就是合数,返回false
for(int i = 0; i < small_primes.length; i++){
if(n % small_primes[i] == 0){
return false;
}
}
}
// #如果这样没有分辨出来,就一定是大整数,那么就调用rabin算法
return isPrime_Miller_Rabin(num,getTryTime(num));
}
/**
* 牛顿下降法对大整数开根号
* 由于开根号结果不一定是整数，这里的结果使用的直接抹掉小数部分，效果即为 floor(根号F7)
*
* @param F7 待开放的整数
* @return 对F7开放后，结果的整数部分
*/
public static BigInteger sqrt(BigInteger F7){
// 牛顿法求解平方根, 求解a的平方根
// x为a的平方根，x的初始值为1， 按x = (x+a/x)/2迭代， 误差为error，事实上，当error < 1时即可求出x平方根的整数部分
BigDecimal x = BigDecimal.ONE;
BigDecimal a = new BigDecimal(F7.toString());
BigDecimal eps = new BigDecimal("1");
final BigDecimal error = new BigDecimal("1E-10");
int scale = 100;
// 进入循环
while(eps.compareTo(error) > 0){ // eps > error是执行循环
x = x.add(a.divide(x,scale,BigDecimal.ROUND_HALF_UP))
.divide(new BigDecimal("2.0"),scale,BigDecimal.ROUND_HALF_UP);
eps = x.multiply(x)
.subtract(a)
.abs();
}
BigInteger sqrt = x.toBigInteger(); // 求平方根的整数部分
return sqrt;
}
// --------------------------------------------------- 加解密函数 -------------------------------------------------------------------
/**
* ElGamal加密
*
* @param m 密文
* @param p 随机选择的大素数
* @param alpha p的一个本原根
* @param beta 公钥
* @return 返回加密后的密文
*/
private static Map<String,BigInteger> encryptCore(BigInteger m,BigInteger p,BigInteger alpha,BigInteger beta){
HashMap<String,BigInteger> res = new HashMap<>();
BigInteger two = new BigInteger("2");
// 1. 产生随机数k
BigInteger gcd, k;
while(true){
k = random(two,p.subtract(two));
gcd = gcdExtend(k,p.subtract(BigInteger.ONE))
.get("gcd");
if(gcd.equals(BigInteger.ONE)){
break;
}
}
// BigInteger k = new BigInteger("853");// 书上的例子选用的随机数
BigInteger r = BigIntegerPM(alpha,k,p);
BigInteger t = (BigIntegerPM(beta,k,p)).multiply(m)
.mod(p);
res.put("r",r);
res.put("t",t);
return res;
}
/**
* ElGamal解密
*
* @param r 密文
* @param t 密文
* @param x 私钥
* @param p 大素数p(公钥)
* @return 返回解密后的明文
*/
private static BigInteger decryptCore(BigInteger r,BigInteger t,BigInteger x,BigInteger p){
BigInteger m;
BigInteger r_ = getMultiplicativeInverse(r,p);
m = (t.multiply(BigIntegerPM(r_,x,p))).mod(p);
return m;
}
// --------------------------------------------------- DSA签名 -------------------------------------------------------------------
// --------------------------------------------------- 加密解密函数 -------------------------------------------------------------------
/**
* 加密字符串
* 可以将字符换转化为byte数组。将byte数组的数字划为三位数，不够三位的，首位补 9(这样可以恢复) ，将byte拼接为字符串，转化为BigInteger
* 随机生成一个数k，且k一与n-1互素
* 计算 r = alpha^k (mod p) , t = beta^k * m
* 密文为 c = (r,t)
* <p>
* 注意：
* - 这里的字符串长度不能太长，必须保证字符串转化为的byte数组组成的BigInteger 小于 p ， 否则无法解密
*
* @param plaintext 明文字符串
* @param p 公钥：模数
* @param alpha 公钥：本原根
* @param beta 公钥
* @return 加密后的字符串，r和t之间使用 "\n" 隔开，以便于解密时解析
*/
private static String encrypt(String plaintext,String p,String alpha,String beta){
byte[] bytes = plaintext.getBytes();
int[] ints = new int[bytes.length];
int i;
for(i = 0; i < bytes.length; i++){
ints[i] = bytes[i];
}
StringBuilder builder = new StringBuilder();
// 目前只能小于 1024
i = 0;
while(i < ints.length){
if(bitOfInt(ints[i]) == 2){
ints[i] += 900;
}
builder.append(ints[i++]);
}
// System.out.println("plain = " + builder.toString());
BigInteger m = new BigInteger(builder.toString());
Map<String,BigInteger> cipher = encryptCore(m,new BigInteger(p),new BigInteger(alpha),new BigInteger(beta));
return cipher.get("r")
.toString() + "\n" + cipher.get("t")
.toString();
}
/**
* ElGamal解密
* 先解析加密后的字符串,分离 r,t 然后求 p = t*r^(-x) (mod p)恢复明文的BigInteger。
* 然后将解析p，即每三位作为一个十进制的数字，如果第一位为9，则将其去掉，否则这三位不做改变。
* 将上述数字转化为字符，然后拼接成字符串即可恢复明文
*
* @param ciphertext 密文
* @param x 私钥 p
* @param p 私钥 q
* @return 解密后的明文字符串
*/
private static String decrypt(String ciphertext,String x,String p){
StringBuilder res = new StringBuilder();
StringBuilder t = new StringBuilder();
StringBuilder r = new StringBuilder();
int i;
for(i = 0; i < ciphertext.length(); i++){
if(ciphertext.charAt(i) == '\n'){
for(int j = i + 1; j < ciphertext.length(); j++){
t.append(ciphertext.charAt(j));
}
break;
}
r.append(ciphertext.charAt(i));
}
BigInteger rr = new BigInteger(r.toString());
BigInteger tt = new BigInteger(t.toString());
BigInteger xx = new BigInteger(x);
BigInteger pp = new BigInteger(p);
String plaintext = decryptCore(rr,tt,xx,pp).toString();
for(i = 0; i < plaintext.length(); i = i + 3){
StringBuilder builder = new StringBuilder();
builder.append(plaintext.charAt(i));
builder.append(plaintext.charAt(i + 1));
builder.append(plaintext.charAt(i + 2));
int integer = new Integer(builder.toString());
if(integer / 100 == 9){
integer -= 900;
}
char temp = (char) integer;
res.append(temp);
}
return res.toString();
}
// --------------------------------------------------- 测试函数 -------------------------------------------------------------------
private void testElGamalCore(){
System.out.println("----------------------- 测试ElGamal算法的核心加密函数 ----------------------------");
BigInteger m = new BigInteger("2199");
BigInteger p = new BigInteger("2579");
BigInteger alpha = new BigInteger("2");
BigInteger x = new BigInteger("765");
BigInteger beta = BigIntegerPM(alpha,x,p);
Map<String,BigInteger> cipher = encryptCore(m,p,alpha,beta);
System.out.println(cipher);
BigInteger plaintext = decryptCore(cipher.get("r"),cipher.get("t"),x,p);
System.out.println(plaintext);
}
private void testElgamal(){
System.out.println("----------------------- 测试ElGamal算法加密字符串 ----------------------------");
String plain = "I love you!";
Map<String,BigInteger> key = getKey(35,new BigInteger("521"));
BigInteger p = key.get("p");
BigInteger alpha = key.get("alpha");
BigInteger x = key.get("x");
BigInteger beta = key.get("beta");
String encrypt = encrypt(plain,p.toString(),alpha.toString(),beta.toString());
System.out.println("encrypt = " + encrypt);
String decrypt = decrypt(encrypt,x.toString(),p.toString());
System.out.println("decrypt = " + decrypt);
}
private void testGenerateKey(){
System.out.println("----------------------- 测试密钥生成算法 ----------------------------");
BigInteger x = new BigInteger("521");
Map<String,BigInteger> key = getKey(4,x);
System.out.println(key);
System.out.println("----------------------- 测试指定位数的素数生成器 ----------------------------");
for(int i = 0; i < 10; i++){
System.out.print(getPrime(4) + ",");
}
System.out.println();
}
// --------------------------------------------------- 密钥生成 -------------------------------------------------------------------
/**
* 随机大素数的生成
* 生成一个随机的 bitCount位的大素数
* 注意：可使用 BigInteger.probablePrime() 方法生成大素数，速度比这个函数速度快10倍以上
*
* @param bitCount 生成素数的在十进制下占的位数
* @return 随机的bitCount位的大素数
*/
private static BigInteger getPrime(int bitCount){
//随机生成一个n bit的大整数
BigInteger start = BigInteger.TEN.pow(bitCount - 1);
BigInteger end = BigInteger.TEN.pow(bitCount)
.subtract(BigInteger.ONE);
BigInteger init = random(start,end);
//如果n为偶数, 则加一变为奇数
if(!init.testBit(0)){
init = init.setBit(0);
}
//基于素数定理, 平均只需要不到n次搜索, 就能找到一个素数
while(!isPrime(init)){
init = init.add(BigInteger.valueOf(2));
}
return init;
}
/**
* 生成ElGamal算法中的公钥
* 1. 步骤：
* 第一步：取一个随机的素数q，并且这个素数满足p = 2q + 1也是一个素数
* 第二步：随机取一个数g(在[2,p - 2]之间）,判断g^2 mod p 与 g ^q mod p是否为1；只要有一个为1，说明g不是p的原根，就重新取随机数
* <p>
* 2. 参考文献：
* https://blog.csdn.net/yibaobao2019/article/details/110429353
*
* @param bitCount 公钥中，大素数p的十进制位数
* @param x 私钥
* @return 返回一个map{ "p",大素数p; "alpha",p的一个原根; "beta",alpha^x(mod p) 其中x为私钥; "x",私钥 }
*/
private static Map<String,BigInteger> getKey(int bitCount,BigInteger x){
HashMap<String,BigInteger> res = new HashMap<>();
BigInteger p;
BigInteger two = new BigInteger("2");
while(true){
BigInteger q = getPrime(bitCount);
p = q.multiply(two)
.add(BigInteger.ONE);
if(!isPrime(p)){
continue;
}
BigInteger alpha = random(two,p.subtract(two));
if(BigIntegerPM(alpha,two,p)
.equals(BigInteger.ONE) || BigIntegerPM(alpha,q,p)
.equals(BigInteger.ONE)){
continue;
}
else{
res.put("p",p);
res.put("alpha",alpha);
res.put("beta",BigIntegerPM(alpha,x,p));
res.put("x",x);
return res;
}
}
}
// --------------------------------------------------- DSA攻击 -------------------------------------------------------------------
/**
* 大步小步算法(Shank算法, Baby-Step Giant-Step Algorithm)
* 给出ElGamal算法的公钥，求解私钥 x
* ① BabyStep 中存储的是 ( beta * alpha^r , r )
* ② GiantStep 中存储的是 ( alpha^(t*s) , t )
* 当第一个左边相同时，即 beta * alpha^r = alpha^(t*s)
* 将 beta = alpha^x 代入得到： alpha^(x+r) = alpha^(t*s)
* 即 x + r = t * s
* 所以 x = t*s - r
* <p>
* 时间复杂度 T(n) = O(n^0.5) (事实上求解大的整数幂复杂度为log n，因此T(n)实际大概为 O( n^0.5 * log n^0.5 ) )
* 空间复杂度 S(n) 大概为 O( n^0.5 * log n^0.5 )
*
* @param alpha 公钥
* @param beta 公钥
* @param p 公钥
* @return 私钥
*/
private BigInteger Shanks(BigInteger alpha,BigInteger beta,BigInteger p){
HashMap<BigInteger,BigInteger> BabyStep = new HashMap<>();
HashMap<BigInteger,BigInteger> GiantStep = new HashMap<>();
BigInteger s = sqrt(p);
// 计算大步小步的值
for(BigInteger r = BigInteger.ZERO; r.compareTo(s.subtract(BigInteger.ONE)) <= 0; r = r.add(BigInteger.ONE)){
BigInteger babyKey = beta.multiply(BigIntegerPM(alpha,r,p))
.mod(p);
BabyStep.put(babyKey,r);
BigInteger t = r.add(BigInteger.ONE);
BigInteger giantKey = BigIntegerPM(alpha,t.multiply(s),p);
GiantStep.put(giantKey,t);
}
// System.out.println(BabyStep);
// System.out.println(GiantStep);
// 找出键相同的值
for(BigInteger babyKey : BabyStep.keySet()){
if(GiantStep.containsKey(babyKey)){
BigInteger t = GiantStep.get(babyKey);
BigInteger r = BabyStep.get(babyKey);
return t.multiply(s)
.subtract(r);
}
}
return null;
}
public static void main(String[] args){
Main elGamal = new Main();
// elGamal.testElGamalCore();
elGamal.testElgamal();
// elGamal.testGenerateKey();
// System.out.println(elGamal.Shanks(new BigInteger("7190183321"),new BigInteger("1333381262"),new BigInteger("7788872843")));
}
}