1RSA算法的原理如下：
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(modm)
其中Public_key，n是公匙，private_key是密匙
1.2.4
加密信息text时，利用公式secretword=text^Public_key(modn)得到密文secretword
1.2.5
解密时利用公式word=text^private_key(modn)得到原文word=text.。
2程序
本算法用JAVA编程语言实现，开发环境为Eclipse
//BJTU软件0404
importjava.io.*;
publicclassRsa
{
privateintp=0;
privateintq=0;
privatelongn=0;
privatelongm=0;
privatelongpublic_key=0;//公匙
privatelongprivate_key=0;//密匙
privatelongtext=0;//明文
privatelongsecretword=0;//密文
privatelongword=0;//解密后明文
//判断是否为素数
publicbooleanprimenumber(longt)
{
longk=0;
k=(long)Math.sqrt((double)t);
booleanflag=true;
outer:for(inti=2;i<=k;i++)
{
if((t%i)==0)
{
flag=false;
breakouter;
}
}
returnflag;
}
//输入PQ
publicvoidinputPQ()throwsException
{
do{
System.out.println("请输入素数p:");
BufferedReaderstdin=newBufferedReader(newInputStreamReader(System.in));
Stringbr=stdin.readLine();
this.p=Integer.parseInt(br);
}
while(!primenumber(this.p));
do{
System.out.println("请输入素数q:");
BufferedReaderstdin=newBufferedReader(newInputStreamReader(System.in));
Stringbr=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);
}
//求最大公约数
publiclonggcd(longa,longb)
{
longgcd;
if(b==0)
gcd=a;
else
gcd=gcd(b,a%b);
System.out.println("gcd:"+gcd);
returngcd;
}
//输入公匙
publicvoidgetPublic_key()throwsException
{
do{
System.out.println("请输入一个公钥的值，这个值要求小于m并且和m互质：");
BufferedReaderstdin=newBufferedReader(newInputStreamReader(System.in));
Stringbr=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);
}
//计算得到密匙
publicvoidgetPrivate_key()
{
longvalue=1;
outer:for(longi=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;
breakouter;
}
}
System.out.println("产生的一个私钥为："+this.private_key);
}
//输入明文
publicvoidgetText()throwsException
{
System.out.println("请输入明文：");
BufferedReaderstdin=newBufferedReader(newInputStreamReader(System.in));
Stringbr=stdin.readLine();
this.text=Long.parseLong(br);
}
//加密、解密计算
publiclongcolum(longy,longn,longkey)
{
longmul;
if(key==1)
mul=y%n;
else
mul=y*this.colum(y,n,key-1)%n;
returnmul;
}
//加密后解密
publicvoidpascolum()throwsException
{
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);
}
publicstaticvoidmain(String[]args)throwsException
{
Rsat=newRsa();
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
