elgamal.java

ElGamal算法的Java实现

/**
 * author:zmhu
 * MSN:[e-mail]
 * Email:[e-mail]
 * QQ:4328335
 */
package elgamar;
import java.math.BigInteger;
import java.util.Random;
import java.io.*;
/**
 * @author zmhu
 */
 /**
  *ElGamal算法原理
  *ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。
  *密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
  *ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算
  *a = g^k ( mod p )
  *再用扩展 Euclidean 算法对下面方程求解b：
  *M = xa + kb ( mod p - 1 )
  *签名就是( a, b )。随机数k须丢弃。
  *验证时要验证下式：
  *y^a * a^b ( mod p ) = g^M ( mod p )
  *同时一定要检验是否满足1<= a < p。否则签名容易伪造。
  **/

public class ElGamal
{
 /**
  * 加密一个消息m(m为BigInteger类型) 并返回加密结果为一个BigInteger数组
  * @param m  明文
  * @param p  
  * @param b  公钥
  * @param g  
  * @return
  */
 public static BigInteger [] encrypt(BigInteger m,BigInteger p,BigInteger b,BigInteger g)
 {
  //随机选取一个k gcd(k,p-1)=1 0<=k<p          //即k与p-1要互质，0<=k<p
  BigInteger [] rtn = {null,null};//定义一个BigInteger数组,存贮返回的加密对象C1,C2
  BigInteger k = ElGamal.getRandomk(p); //随机取满足条件的k
  //计算密文C1,C1   C1=g^k(mod p);用g.modPow(k,p)表示
  BigInteger C1 = g.modPow(k, p);
  BigInteger C2 = m.multiply(b.modPow(k, p)).mod(p);///////C2=m*(b^k(mod p))(mod p)
  //保存密文到对象中
  rtn[0] = C1;
  rtn[1] = C2;
  return rtn;
 }
 /**
  * 取随机数k
  * @param p
  * @return
  */
 public static BigInteger getRandomk(BigInteger p)
 {
  ///随机取一个与p-1互质的数k & 0<=k<p-1
  Random r = new Random();
  BigInteger k = null;
  while(true)
  {
   k = new BigInteger(p.bitLength()-1,r);//产生一0<=k<p-1的随机数
   if(k.gcd(p.subtract(BigInteger.ONE)).equals(BigInteger.ONE))
   {//如果随机数与p-1互质 则选取成功,返回随机数k
    break;
   }
  }
  return k;
 }
 /**
  * 取一个大的随机素数P,和P的生成元a
  * @param alpha 为该素数的比特位数
  * @return
  */
 public static BigInteger [] getRandomP(int alpha)
 {
  BigInteger rtn [] = {null,null};
  Random r = new Random();
  BigInteger p = null;
  BigInteger q = null;
  //选取一个安全素数Q, p = 2q+1 如果P为素数,选定成功
  while(true)
  {
   q = BigInteger.probablePrime(alpha, r);//new BigInteger(alpha,r); 
   //取一个随机数q, r为随机数发生器  alpha 为想要得到随机数大小   [2^alpha]p = 2^alpha
   if(q.bitLength() != alpha)  //判断生成的随机数q<2^alpha 如果q<2^alpha 重新再生成一个随机数直到q>2^alpha
    continue;
   if(q.isProbablePrime(10))    //如果q为素数则再进一步计算生成元   ////////isProbablePrime(10)判断是否为素数的方法
   {
    p = q.multiply(new BigInteger("2")).add(BigInteger.ONE); // 选取一个安全素数P=2*Q+1 
    //////这个应该是BigInteger型数的计算方法，乘以2应该表示成multiply(new BigInteger("2")),即2也要变成BigInteger型的数据
    //////故add(BigInteger.ONE)应该是加一的意思，合起来就是p=2q+1
    if(p.isProbablePrime(10)) //如果P为素数则选取成功 否则继续第一步
     break;
   }
  }
  //计算p 的乘法群 用Zp表示
  //在Zp中选择一个g != 1
  BigInteger g = null;
  while(true)
  {
   g = BigInteger.probablePrime(p.bitLength()-1, r);//new BigInteger(p.bitLength()-1,r);//从Zp*中随机取出一个元
   ////////同q的生成方法一样，probablePrime为BigInteger的一个方法，有两个参数，一个是长度，另一个是用来产生随机数
   if(!g.modPow(BigInteger.ONE, p).equals(BigInteger.ONE) && !g.modPow(q, p).equals(BigInteger.ONE)) 
   {////在Z*p中任选一元素g!=1,计算g^2 mod P 和g^Q mod P ,如它们都不等于1,则g是生成元,否则继续选取
    break;
   }
  }
  rtn[0] = p;
  rtn[1] = g;
  return rtn;
 }
 /**
  * 取随机数a
  * @param p
  * @return
  */
 public static BigInteger getRandoma(BigInteger p)
 {
  BigInteger a = null;
  Random r = new Random();
  a = new BigInteger(p.bitLength()-1,r);
  return a;
 }
 /**
  * 计算b的值
  * @param g
  * @param a
  * @param p
  * @return
  */
 public static BigInteger calculateb(BigInteger g,BigInteger a,BigInteger p)
 {
  BigInteger b = null;
  b = g.modPow(a, p);
  /////b=g^a(mod p)
  return b;
 }
 /**
  * 解密一个串返回值为一个BigInteger对象
  * @param C1
  * @param C2
  * @param a
  * @param p
  * @return
  */
 public static BigInteger decrypt(BigInteger C1,BigInteger C2,BigInteger a,BigInteger p)
 {
  BigInteger m = null;
  m = C2.multiply(C1.modPow(a.negate(), p)).mod(p);
  return m;
 }
 /**
  * 加密一个数字签名,其实就是加密一个字符串,消息m为一个字串,程序中是把消息m(String)转成一个byte数组,
  * 然后再把byte类型的数组再构造成一个BigInteger对象,使用encrypt方法加密
  * @param m
  * @param p
  * @param b
  * @param g
  * @return
  */
 public static BigInteger [] encryptSignature(String m,BigInteger p,BigInteger b,BigInteger g)
 {
  BigInteger [] rtn = {null,null};//定义一个BigInteger数组,存贮返回的加密对象C1,C2
  BigInteger message = new BigInteger(m.getBytes());//把字串转成一个BigInteger对象
  rtn = ElGamal.encrypt(message, p, b, g);//调用加密方法encrypt加密
  return rtn;
 }
 /**
  * 解密一个数字签名,传入先前加密结果,两个BigInteger的对象C1,C2
  * 程序使用先前的decrypt方法进行解密,把解密得到的结果(BigInteger对象),转化为一个byte的数组
  * 再把byte类型的数组还原为一个字串
  * @param C1
  * @param C2
  * @param a
  * @param p
  * @return
  */
 public static String decryptSignature(BigInteger C1,BigInteger C2,BigInteger a,BigInteger p)
 {
  BigInteger rtn = ElGamal.decrypt(C1, C2, a, p);//调用decrypt方法解密
  String str = new String(rtn.toByteArray());//把返回的结果还原成一个字串
  return str;
 }
 public static void main(String [] args)
 {
  BigInteger p = null; //随机数 P
  BigInteger g = null; //P的生成元
  //BigInteger m = new BigInteger("11111111111111"); // 明文M 0<=m<p
  //System.out.println("明文:"+m);//输出
  BigInteger b = null; // 公钥<b,g,p>
  BigInteger a = null;//私钥<a> 0<a<p
  BigInteger [] rtn = {null,null}; 
  
  String signm = "";
  System.out.println("请输入消息M:");
  InputStream clav= System.in;
  BufferedReader rd = new BufferedReader(new InputStreamReader(clav));
  try {signm = rd.readLine();}
  catch(IOException e) {System.out.println(e.getMessage());}
  //System.out.println(new BigInteger(signm.getBytes()).bitLength());
  //System.exit(0);
  rtn = ElGamal.getRandomP(new BigInteger(signm.getBytes()).bitLength());//取得随机数P,和P的生成元g
  
  p = rtn[0];
  g = rtn[1];
  a = ElGamal.getRandoma(p);
  b = ElGamal.calculateb(g, a, p);
  //rtn = ElGamal.encrypt(m, p, b, g);
  //System.out.println("密文:"+rtn[0]+","+rtn[1]);
  //BigInteger dm = ElGamal.decrypt(rtn[0], rtn[1], a, p);
  //System.out.println("解密:"+dm);
  /////数字签名
  
 
  System.out.println("原文:"+signm);
  byte[] mb = signm.getBytes();
  System.out.println("字节码构造的超大整数:"+new BigInteger(mb).toString());
  System.out.println("素数P:"+p);
  System.out.println("生成元:"+g);
  System.out.println("随机数a(私钥):"+a);
  System.out.println("b(公钥):"+b);
  //rtn = ElGamal.getRandomP(100);//取得随机数P,和P的生成元g
  //p = rtn[0];
  //g = rtn[1];
  a = ElGamal.getRandoma(p);
  b = ElGamal.calculateb(g, a, p);
  rtn = ElGamal.encryptSignature(signm, p, b, g);
  System.out.println("密文:"+rtn[0]+","+rtn[1]);
  String designm = ElGamal.decryptSignature(rtn[0], rtn[1], a, p);
  mb = designm.getBytes();
  System.out.println("解密后的超大整数:"+new BigInteger(mb));
  System.out.println("解密:"+designm);
  
 }
}