ElGamal算法的基本原理及实现

  1 import java.util.ArrayList;
  2 
  3 public class Main {
  4     static ArrayList<Integer> suArr = new ArrayList<>();
  5     public static void main(String[] args) {
  6         int max = 8096, p, g, x, y, k, a, b;
  7         double buff;
  8         char[] m = "ABC".toCharArray(); // 加密字符串"ABC"
  9         ArrayList<Integer> C = new ArrayList<>();   // 存取加密后的密文
 10         int size1;
 11         suArr.add(2);
 12 
 13         // 随机取一个小于2048的素数g
 14         for (int i = 3; i <= 2048; i++) {
 15             if (isSuShu(i)) suArr.add(i);
 16         }
 17         size1 = suArr.size();
 18         g = getRanNum(size1);
 19 
 20         // 随机取一个大素数p
 21         for (int i = 2049; i <= max; i++) {
 22             if (isSuShu(i)) suArr.add(i);
 23         }
 24         p = getRanNum(suArr.size() - size1, size1);
 25 
 26         // x是1~(p-2)中的一个数
 27         x = (int)(Math.random() * (p-2) + 1);
 28         // k是1~(p-2)中的一个数且k与p-1互素
 29         k = (int)(Math.random() * (p-2) + 1);
 30         while (isHuZhi(k, p-1) != 1) {
 31             k = (int)(Math.random() * (p-2));
 32         }
 33 
 34         // y = g^x mod p
 35         y = myPow(g, x, p);
 36 
 37         // a = g^k mod p
 38         a = myPow(g, k, p);
 39         C.add(a);
 40 
 41         // 加密过程，即计算b = m*y^k mod p (m是明文)
 42         for (char c : m) {
 43             C.add((int)c*myPow(y, k, p));
 44         }
 45 
 46         buff = myPow(a, x, p);
 47         // 将解密后的明文输出
 48         for (int i = 1; i < C.size(); i++) {
 49             System.out.print((char)(C.get(i) * (1/buff)));
 50         }
 51 
 52     }
 53 
 54     // 判断一个数是否为素数
 55     public static boolean isSuShu(int num) {
 56         int max = (int) Math.sqrt(num);
 57         for (int i = 2; i <= max; i++) {
 58             if (num % i == 0)
 59                 return false;
 60         }
 61         return true;
 62     }
 63 
 64     // 在素数数组中随机取一个数
 65     public static int getRanNum(int size) {
 66         return suArr.get((int) (Math.random() * (size)));
 67     }
 68 
 69     // 在素数数组中的(left, arr.size())之间随机取一个数
 70     public static int getRanNum(int size, int left) {
 71         return suArr.get((int) (Math.random() * (size)) + left);
 72     }
 73 
 74     // 判断两个数是否互质
 75     public static int isHuZhi(int a, int b) {
 76         return b == 0 ? a : isHuZhi(b, a % b);
 77     }
 78 
 79     public static int myPow(int a, int b, int m) {
 80         int res = 1;
 81         a %= m;
 82         while (b != 0) {
 83             if ((b & 1) == 1)
 84                 res = (res * a) % m;
 85             a = (a * a) % m;
 86             b >>= 1;
 87         }
 88         return res;
 89     }
 90 
 91     public static int getSuGen(int p) {
 92         boolean isSuGen;
 93         for (int g : suArr) {
 94             isSuGen = true;
 95             for (int i = 1; i < p; i++) {
 96                 if (myPow(g, i, p) != i) isSuGen = false;
 97             }
 98             if (isSuGen) return g;
 99         }
100         return 2; // 如果在素数数组中找不到p的素根，则返回一个默认值
101     }
102 }
103 
104 /*
105  * 参考：
106  * 素根的定义：a是素数p 的一个素根，如果a mod p, a^2 mod p , …, a^p-1 mod p 是1到p-1的排列，称a是P的一个素根
107  * 加密时x和k的选取：https://blog.csdn.net/qq_34490018/article/details/79758620
108  */