內蒙古java團隊

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