testrsa.java

个人编的rsa的源代码

/*
 *RSA encryption/decryption;RSA digital signature
 *Millar Rabin Test; Euclid & Extend Euclid Algorithm
 *
 **/

import java.util.*;
import java.math.*;
import java.security.*;
import java.io.*;

public class TestRsa
{
private BigInteger p, q;
private BigInteger n;
private BigInteger PhiN;
private BigInteger e, d;
private static final Random random = new Random();
private static BigInteger ZERO= BigInteger.valueOf(0); 
private static BigInteger ONE= BigInteger.valueOf(1); 
private static BigInteger TWO= BigInteger.valueOf(2);
private static BigInteger THREE= BigInteger.valueOf(3); 
private static BigInteger FOUR= BigInteger.valueOf(4);

/*Miller Rabin Test
 *If nn is prime,return true; otherwise, return false
 *iterations defines number of times to test it
*/
public static boolean MillerRabin(BigInteger nn,int iterations){
    Random rnd=new Random();
    for(int i=0;i<iterations;i++)
    {
        BigInteger a;
        do{
            a=new BigInteger(nn.bitLength(),rnd);
        } while(a.equals(ZERO));
        if(!MillerRabinPass(a,nn)) return false;
   	}
   	return true;
}
	private static boolean MillerRabinPass(BigInteger a, BigInteger nn) {
	    BigInteger n_minus_one = nn.subtract(BigInteger.ONE);
	    
	    BigInteger mm = n_minus_one;
		int s = mm.getLowestSetBit();
		mm = mm.shiftRight(s);
	
	    BigInteger a_to_power = a.modPow(mm, nn);
	    if (a_to_power.equals(BigInteger.ONE)) return true;
	    for (int i = 0; i < s-1; i++) {
	        if (a_to_power.equals(n_minus_one)) return true;
	        a_to_power = a_to_power.multiply(a_to_power).mod(nn);
	    }
	    if (a_to_power.equals(n_minus_one)) return true;
	    else return false;
	}

//Euclid's algorithm
public BigInteger Gcd(BigInteger i,BigInteger j){
	 BigInteger r;
	 if(j.equals(ZERO)) r=i;
	 else r=Gcd(j,i.remainder(j));
	 return r;
}

//EEA to calculate d
public BigInteger[] EEuclid(BigInteger x, BigInteger y) {
    int n = 2;
    BigInteger r[] = new BigInteger[3];
    BigInteger q[] = new BigInteger[3];
    BigInteger u[] = new BigInteger[3];
    BigInteger v[] = new BigInteger[3];

    r[0] = x;
    r[1] = y;
    u[0] = new BigInteger("1");
    v[0] = new BigInteger("0");
    u[1] = new BigInteger("0");
    v[1] = new BigInteger("1");
    while (!r[(n-1)%3].equals(ZERO)) {
        q[n%3] = r[(n-2)%3].divide(r[(n-1)%3]);
        r[n%3] = r[(n-2)%3].remainder(r[(n-1)%3]);
        // Un = Un-2 - QnUn-1
        u[n%3] = u[(n-2)%3].subtract(q[n%3].multiply(u[(n-1)%3]));
        // Vn = Vn-2 - QnVn-1
        v[n%3] = v[(n-2)%3].subtract(q[n%3].multiply(v[(n-1)%3]));

        n++;
    }
    BigInteger result[] = new BigInteger[2];
    result[0] = u[(n-2)%3];
    result[1] = v[(n-2)%3];
    return result;
}

public TestRsa()
{
Initialize();
}

public void Initialize()
{
    int Size=128;//Key size in bits

	/*Step 1: Select two large prime numbers, p and q.
	 *Pass Millar-Rabin test
	*/
   do{
   		do{p = new BigInteger(Size/2, random);}
   		while(p.equals(ZERO));
    }
    while(!MillerRabin(p,20));
    do{
    	do{q = new BigInteger(Size/2, random);}
   		while(q.equals(ZERO));
    }
    while(!MillerRabin(q,20));

    System.out.println("p: "+p);
    System.out.println("q: "+q);

	/* Step 2: Calculate n = p*q */
    n = p.multiply(q);
    System.out.println("n: "+n);

	/* Step 3: Calculate Phi(n) = (p - 1)*(q - 1) */
    PhiN = p.subtract(BigInteger.valueOf(1));
    PhiN = PhiN.multiply( q.subtract( BigInteger.valueOf(1)));
    System.out.println("PhiN: "+PhiN);

	/* Step 4: Find e such that gcd(e, Phi(n)) = 1 ; 1 < e < Phi(n) */
    do
    {
        e = new BigInteger(Size, random);
    }
    while((e.compareTo(PhiN)!=1)||Gcd(e,PhiN).compareTo(ONE)!=0);
    System.out.println("e: "+e);

	/* Step 5: Calculate d such that d*e mod m = 1 */
    BigInteger tmp[]=EEuclid(e,PhiN);
    d=tmp[0];
    System.out.println("d: "+d);
    System.out.println();
    
}//Calculate p,q,n,e,d  

//Encrypt message
public BigInteger encrypt(BigInteger plaintext)
{
    return plaintext.modPow(e, n);
}

//Decrypt message
public BigInteger decrypt(BigInteger ciphertext)
{
    return ciphertext.modPow(d, n);
}
   
//main()
public static void main(String[] args) throws IOException
{
    System.out.println("******RSA Encryption/Decryption******");
    TestRsa app = new TestRsa();
    
    String sou = "RSA";//The message.
    System.out.println("Input is: " +  sou);
    
    byte[] bytes=sou.getBytes();  
    BigInteger m=new BigInteger(bytes);
    System.out.println("Plain: " +  m.toString());
    
    /*RSA encryption/decryption
     *A use B's public key to encrypt
     *B use B's secret key to decrypt
     */
    BigInteger mcipher,mdecypt;   
    mcipher = app.encrypt(m);
    System.out.println("Encrypt: " +  mcipher.toString());
    mdecypt = app.decrypt(mcipher);
    System.out.println("Decrypt: " +  mdecypt.toString());
    String des = new String(mdecypt.toByteArray());
    System.out.println("Orign is: " +  des);
    
    System.out.println();
    
    /*RSA digital signature
     *A use A's secret key to sign
     *B use A's public key to verify
     */
    System.out.println("******RSA Signature******");

    System.out.println("Hash value: " +  m.toString(16)+" (pretend it's MD5)");
    //pretend it's MD5.
    BigInteger sign,check;
    sign=app.decrypt(m);
    System.out.println("Signing: "+ sign.toString());
    check=app.encrypt(sign);
    System.out.println("Check: "+ check.toString(16));
    if(check.equals(m)) System.out.println("Verified");
    else System.out.println("Hacked");

    System.out.println();
}

}