1、准备步骤
1)随机选取大素数 p 和 g
2)随机选取整数 x，x∈[1, p-2]，计算 y=g^x(mod p)。
3)设 m∈Z 是待签名的消息，秘密随机选取一个整数 k，k∈[1, p-2]，且 k 与 p-1 互质
2、签名过程
1)计算 r 和 s：
r=g^k(mod p)
s=k^-1(m-rx)(mod p-1)(k^-1 表示 k mod p-1 的逆元)
2)(m, r, s)为对消息 m 的数字签名。
3、验证签名
1)对方收到对消息 m 的数字签名(m, r, s)后，利用签名者的公开密钥(y, g, p)对签名进行以下验证：
(y^r)(r^s) mod p=g^m(mod p)(左式计算时可以使用快速幂取模)
如果上式成立，则接受该签名，否则拒绝该签名。
4、签名过程实现(测试对消息 'A' 进行签名)：
importjava.util.ArrayList;public classMain {private static ArrayList suArr = new ArrayList<>();private static int[] xy = new int[2];//定义素数的范围为 8-bit
private static int MAX = 255;public static voidmain(String[] args) {intp, g, x, y, k, r, s;int m = (int)'A';//初始化素数数组
initSuArr();//取一个素数 p
p = suArr.get((int) (Math.random() *(suArr.size())));//g 是 p 的一个本原元
g = 2;//x >= 1 && x <= p-2
x = (int)(Math.random() * (p-2))+1;//y = g^x mod p
y = myPow(g, x, p); //y是公开密钥//k >= 1 && k <= p-2 且 k 与 (p-1) 互质
k = (int)(Math.random() * (p-2))+1;while (isHuZhi(k, p-1) != 1) {
k= (int)(Math.random() * (p-2));
}//r = g^k mod p
r =myPow(g, k, p);//计算k^-1 mod p-1
exGcd(k, (p-1));
k= xy[0];if(k < 0) k += (p-1);//s = k^(-1)*(m-rx)(mod p-1)
s = (k*(m-r*x)) % (p-1); //(m,r,s)为对消息m的数字签名//s可能为负值，所以要将其转化为正数，利用a%b=(a%b+b)%b
if(s < 0) s = (s + p-1) % (p-1);if ((myPow(y, r, p) * myPow(r, s, p))%p ==myPow(g, m, p)) {
System.out.println("接受该签名");
}else{
System.out.println("拒绝该签名");
}
}//判断一个数是否为素数
public static boolean isSuShu(intnum) {int max = (int) Math.sqrt(num);for (int i = 2; i <= max; i++) {if (num % i == 0)return false;
}return true;
}//初始化素数数组
public static voidinitSuArr() {
suArr.add(2);for (int i = 3; i <= MAX; i++) {if(isSuShu(i))
suArr.add(i);
}
}//判断两个数是否互质
public static int isHuZhi(int a, intb) {return b == 0 ? a : isHuZhi(b, a %b);
}public static int myPow(int a, int b, intm) {int res = 1;
a%=m;while (b != 0) {if ((b & 1) == 1)
res= (res * a) %m;
a= (a * a) %m;
b>>= 1;
}returnres;
}//求 a mod b 的逆元
public static void exGcd(int a, intb) {if (b == 0) {
xy[0] = 1;
xy[1] = 0;
}else{
exGcd(b, a%b);int x = xy[0];
xy[0] = xy[1];
xy[1] = x - (a / b) * xy[1];
}
}
}
参考文档：
1)/qq_34490018/article/details/79758620
如果觉得《elgamal签名java_ElGamal算法的数字签名》对你有帮助，请点赞、收藏，并留下你的观点哦！
