1、准备步骤
1)取大素数 p 和 g(g < p，g 最好是 p 的素根)
注解：若 a 是素数 p 的一个素根，则 a mod p, a^2 mod p , …, a^p-1 mod p 是 1 到 p - 1 的排列
2)随机选取一整数 x (1 <= x <= (p - 2)，(p，g，x) 是私钥)
3)计算 y = g^x (mod p) ( (p，g，y) 是公钥)
2、加密过程
1)随机选取一整数 k (1 <= k <= (p - 2) 且 k 与 (p - 1) 互素)
2)计算 a = g^k mod p，b = m*y^k mod p(m 为要加密的明文)
3)密文 C = (a, b)
3、解密过程
1)m = b * a^(-x) mod p
注解：ba^(-x) mod p Ξ m * y^k * g^(-xk) Ξ m * g^(xk) * g^(-xk) Ξ m
加密及解密的实现：
1 importjava.util.ArrayList;2
3 public classMain {4 static ArrayList suArr = new ArrayList<>();5 public static voidmain(String[] args) {6 int max = 8096, p, g, x, y, k, a, b;7 doublebuff;8 char[] m = "ABC".toCharArray(); //加密字符串"ABC"
9 ArrayList C = new ArrayList<>(); //存取加密后的密文
10 intsize1;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 (charc : 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(intnum) {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(intsize) {66 return suArr.get((int) (Math.random() *(size)));67 }68
69 //在素数数组中的(left, arr.size())之间随机取一个数
70 public static int getRanNum(int size, intleft) {71 return suArr.get((int) (Math.random() * (size)) +left);72 }73
74 //判断两个数是否互质
75 public static int isHuZhi(int a, intb) {76 return b == 0 ? a : isHuZhi(b, a %b);77 }78
79 public static int myPow(int a, int b, intm) {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 returnres;89 }90
91 public static int getSuGen(intp) {92 booleanisSuGen;93 for (intg : 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) returng;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的选取：/qq_34490018/article/details/79758620
108 */
原文：/GjqDream/p/11543367.html
如果觉得《elgamal java_ElGamal算法的基本原理及实现》对你有帮助，请点赞、收藏，并留下你的观点哦！
