用java实现RSA算法

用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(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软件0404importjava.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;}//输入PQpublicvoidinputPQ()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;elsegcd=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_keythis.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;elsemul=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、n3.2输入公匙，产生密匙3.3输入明文，产生密文，并解密此处时间限制，明文暂时用个数字代替，有兴趣的可以改变程序，变成一段数字。请输入素数p：23请输入素数q：29这两个素数的乘积为p*q：667所得的小于N并且与N互素的整数的个数为m=(p-1)(q-1)：616请输入一个公钥的值，这个值要求小于m并且和m互质：611gcd：1gcd：1gcd：1gcd：1公钥为：611产生的一个私钥为：123请输入明文：311输入明文为:311所得的密文为：653解密后所得的明文为：311