用java实现RSA算法

　　1  RSA算法的原理如下：
　　1.1原理
　　     假设我们需要将信息从机器A传到机器B，首先由机器B随机确定一个Key，我们称之为密匙private_key，将这个可KEY始终保存在机器B中而不发出来；然后，由这个private_key计算出另一个Key，我们称之为公匙Public_key。这个Public_key的特性是几乎不可能通过该Key计算生成它的private_key。接下来通过网络把这个Public_key传给机器A，
　　机器A受到Public_key后，利用该key，将信息加密，并把加密后的信息通过网络发送到机器B，最后机器B利用已知的private_key，就可以解开加密信息。
　　1.2步骤
　　RSA算法的安全性依靠于大数因数分解的困难性。公匙和私匙都是两个大素数的函数。
　　1.2.1
　　     首先选择两个大素数p、q,计算n=p*q; m=(p-1)*(q-1);
　　1.2.2
　　     而后随机选择加密密匙Public_key，要求和m互质，比如Public_key=m-1;
　　1.2.3
　　利用欧几里德算法计算解密密匙private_key，使private_key满足
　　Public_key*private_key三1(mod m)
　　其中Public_key，n是公匙，private_key是密匙
　　1.2.4
　　加密信息text时，利用公式secretWord=text^Public_key (mod n)得到密文secretword
　　1.2.5
　　解密时利用公式word=text^private_key(mod n)得到原文word=text.。
　　
　　2程序
　　本算法用Java编程语言实现，开发环境为Eclipse
　　//BJTU 软件0404  
　　import java.io.*;
　　
　　public class Rsa 
　　{
　　    private int p=0;
　　    private int q=0;
　　    private long n=0;
　　    private long m=0;
　　    
　　    private long public_key=0;//公匙
　　    private long private_key=0;//密匙
　　    
　　    private long text=0;//明文
　　    private long secretword=0;//密文
　　    private long word=0;//解密后明文
　　    
　　    //判定是否为素数
　　    public boolean primenumber(long t)
　　    {
　　        long k=0;
　　        k=(long)Math.sqrt((double)t);
　　        boolean flag=true;
　　        outer:for(int i=2;i<=k;i++)
　　        {
　　            if((t%i)==0)
　　            {
　　                flag = false;
　　                break outer;
　　
　　             }
　　        }
　　        return flag;
　　    }
　　    //输入PQ
　　    public void inputPQ()throws Exception
　　    {
　　        do{
　　                System.out.println("请输入素数p: ");
　　                BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
　　                String br=stdin.readLine();
　　                this.p=Integer.parseInt(br);
　　         }
　　        while(!primenumber(this.p));
　　        do{
　　            System.out.println("请输入素数q: ");
　　            BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
　　            String br=stdin.readLine();
　　            this.q=Integer.parseInt(br);
　　        }
　　        while(!primenumber(this.q));
　　        this.n=this.p*this.q;
　　        this.m=(p-1)*(q-1);
　　        System.out.println("这两个素数的乘积为p*q："+this.n);
　　        System.out.println("所得的小于Ｎ并且与Ｎ互素的整数的个数为m=(p-1)(q-1)："+this.m);
　　    }
　　    //求最大公约数
　　    public long gcd(long a,long b)
　　    {
　　        long gcd;
　　        if(b==0)
　　            gcd=a;
　　        else
　　            gcd=gcd(b,a%b);
　　        System.out.println("gcd:"+gcd);
　　        return gcd;
　　        
　　    }
　　
　　     //输入公匙
　　    public void getPublic_key()throws Exception
　　    {
　　        do{
　　            System.out.println("请输入一个公钥的值，这个值要求小于m并且和m互质： ");
　　            BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
　　            String br=stdin.readLine();
　　            this.public_key=Long.parseLong(br);
　　        }while((this.public_key >= this.m)  (this.gcd(this.m,this.public_key)!=1));
　　        System.out.println("公钥为："+this.public_key);
　　    }
　　    //计算得到密匙
　　    public void getPrivate_key()
　　    {
　　        long value=1;
　　        outer:for(long i=1;;i++)
　　        {
　　            value=i*this.m+1;
　　            System.out.println("value:  "+value);
　　            if((value%this.public_key==0)&& (value/this.public_key < this.m))
　　            {
　　                this.private_key=value/this.public_key;
　　                break outer;
　　            }
　　        }
　　        System.out.println("产生的一个私钥为："+this.private_key);
　　    }
　　    //输入明文
　　    public void getText()throws Exception
　　    {
　　        System.out.println("请输入明文：");
　　        BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
　　        String br=stdin.readLine();
　　        this.text=Long.parseLong(br);
　　    }
　　    //加密、解密计算
　　    public long colum(long y,long n,long key)
　　    {
　　
　　         long mul;
　　        if(key==1)
　　            mul=y%n;
　　        else 
　　            mul=y*this.colum(y,n,key-1)%n;
　　        return mul;
　　    }
　　    
　　    //加密后解密
　　    public void pascolum()throws Exception
　　    {
　　        this.getText();
　　        System.out.println("输入明文为: "+this.text);
　　        //加密
　　        this.secretword=this.colum(this.text,this.n,this.public_key);
　　        System.out.println("所得的密文为："+this.secretword);
　　        //解密
　　        this.word=this.colum(this.secretword,this.n,this.private_key);
　　        System.out.println("解密后所得的明文为："+this.word);
　　        
　　    }
　　    public static void main(String []args)throws Exception
　　    {
　　        Rsa t = new Rsa();
　　        t.inputPQ();
　　        t.getPublic_key();
　　        t.getPrivate_key();
　　        t.pascolum();
　　    }
　　
　　}
　　3试验介绍
　　2.1输入PQ，计算m、n
　　 
　　3.2输入公匙，产生密匙
　　 
　　3.3输入明文，产生密文，并解密
　　此处时间限制，明文暂时用个数字代替，有爱好的可以改变程序，变成一段数字
　　 
　　
　　请输入素数p: 
　　23
　　请输入素数q: 
　　29
　　这两个素数的乘积为p*q：667
　　所得的小于Ｎ并且与Ｎ互素的整数的个数为m=(p-1)(q-1)：616
　　请输入一个公钥的值，这个值要求小于m并且和m互质： 
　　611
　　gcd:1
　　gcd:1
　　gcd:1
　　gcd:1
　　公钥为：611
　　产生的一个私钥为：123
　　请输入明文：
　　311
　　输入明文为: 311
　　所得的密文为：653
　　解密后所得的明文为：311