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
所得的小于N并且與N互素的整數的個數為m=(p-1)(q-1)：616
請輸入一個公鑰的值，這個值要求小于m并且和m互質：
611
gcd：1
gcd：1
gcd：1
gcd：1
公鑰為：611
產生的一個私鑰為：123
請輸入明文：
311
輸入明文為: 311
所得的密文為：653
解密后所得的明文為：311