Elgamal数字签名

package com.javase.ElGamalSignature; import java.util.Scanner; public class ElGamal { /** * 1.素数判定 * * 在2到根号p之间没有p的因子即可说明p是一个素数 */ public static boolean isPrime(long p){ for(long i = 2; i <= Math.sqrt(p); i++){ if(p % i == 0){ return false; } } return true; } /** * 2.欧几里德算法 * * 判断两个数是否互素 */ public static long gcd(long k,long l) { if(l != 0) return gcd(l, k % l); return k; } /** * 3.扩展的欧几里德算法 * * 求模p乘法逆元 */ public static long extendEuclid(long e, long f) { long x2 = 0, x3 = f, y2 = 1, y3 = e, q, t2, t3; while (true) { if (y3 == 0) return 0; if (y3 == 1) { if (y2 < 0) y2 += f; return y2; } q = x3 / y3; t2 = x2 - q * y2; t3 = x3 - q * y3; x2 = y2; x3 = y3; y2 = t2; y3 = t3; } } /** * 4.计算公钥：y=g^x mod p * @param p * @param g * @param x * @return * * 私钥，公钥生成： * 1、选取一个随机数x，1<x<p-1 * 2、计算y=g^x%p * (g, p, y)为公钥，x为私钥。 */ public static long publicKey(long p,long g,long x){ long y = 1; for(int i = 1; i <= x; i++){ y = y * g; if(y > p){ y = y % p; } } return y; } /** * 5.ElGamal签名算法 * @param p：公开值 * @param g：公开 * @param x：私密 * @param k：随机值 * @param m：一个整数 * @return * * 1、选取一个随机数k，1<k<p-1，且k和p-1互素 * 2、计算r，r满足：r≡g^k (mod p) * 3、计算s，s满足：s≡(m-xr)*(k^(-1)) (mod p-1) * m为待签名信息。 *（r，s）构成对m的签名 */ public static long[] signature(long p,long g,long x,long k,long m){ //1.判断k和p-1是否互素 if(gcd(k, p-1) != 1){ System.out.println("随机数k输入错误！"); return null; }else{ //2、计算r，r满足：r≡g^k (mod p) long r = 1; for(int i = 1; i <= k; i++){ r = r * g; if(r > p){ r = r % p; } } //3、计算s，s满足：s≡(m-xr)*(k^(-1)) (mod p-1) long s; ///(1.)k^(-1) long niyuan_k = extendEuclid(k, p-1); ///(2.)s long xr = x * r; long s1 = (m - xr); while(s1 < 0){ s1 += (p-1); } if(s1 > (p - 1)){ s1 = s1 % (p - 1); } s = s1 * niyuan_k; if(s > (p - 1)){ s = s % (p - 1); } //3.计算签名 long [] sign = {r, s}; return sign; } } /** * 6.ElGamal验证算法 * @param p:公开 * @param y:公开 * @param m:消息 * @param r:签名1 * @param s:签名2 * @return * * 用公钥验证签名： * 1、验证：0<r<p，0<s<p-1 * 2、验证：g^(m)≡(y^r)*(r^s) (mod p) * 签名算法正确性证明： * 由签名过程得：m≡s*k+x*r (mod p-1) */ public static boolean Verify(long p,long y,long g,long m,long r,long s){ //1.计算g^(m) = par1 long par1 = 1; for(long i = 1; i <= m; i++){ par1 = par1 * g; if(par1 > p){ par1 = par1 % p; } } //2.计算y^r = par2 long par2 = 1; for(int i = 1; i <= r; i++){ par2 = par2 * y; if(par2 > p){ par2 = par2 % p; } } //3.计算r^s = par3 long par3 = 1; for(int i = 1; i <= s; i++){ par3 = par3 * r; if(par3 > p){ par3 = par3 % p; } } //4.验证签名 long par = par2 * par3; if(par > p){ par = par % p; } return par1 == par; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("输入一个素数："); long p = scanner.nextLong(); boolean f = isPrime(p); if(f){ System.out.println(p+"是素数。"); }else{ System.out.println("不是素数，请重新输入！"); } System.out.println("输入g,x，都小于p:"); long g = scanner.nextLong(); long x = scanner.nextLong(); //计算公钥y long y = publicKey(p, g, x); // System.out.println(y); System.out.print("选择随机数k(小于p)："); long k = scanner.nextLong(); System.out.println("公钥为：p=" + p + ", g=" + g + ", y=" + y); System.out.println("私钥为：x=" + x); System.out.println("随机数：k=" + k); System.out.println(); System.out.print("请输入一个消息m："); long m = scanner.nextLong(); //签名 System.out.println(); System.out.println("明文 m="+m); long[] sign = signature(p, g, x, k, m); System.out.println("消息m = " + m +",签名(r,s) = " + "(" + sign[0] + "," + sign[1] + ")"); //验证 long r = sign[0]; long s = sign[1]; System.out.println(); boolean verify = Verify(p, y, g, m, r, s); if(verify){ System.out.println("签名验证成功"); }else{ System.out.println("签名验证失败"); } } }