武汉大学应用密码学RSA加密解密大作业

1对RSA算法的理解RSA加密算法是一种非对称加密算法，它基于一个非常简单的数论思想：“将两个素数乘起来是很容易的，但是分解该乘积是非常困难的”。1.1加解密步骤(1)生成公钥和私钥a)随机生成两个不相等的大素数p和q，计算N=p*q;b)根据欧拉函数，求出φ=(p-1)*(q-1);c)选择一个小于r的整数e，求e关于r的模反元素d使得e*dmodφ=1得到公钥N，e，私钥N，d(2)加密给定明文m，公钥N，e，计算密文c=me(N)。(3)解密给定密文c，私钥N，d，计算明文m’=cd(N)。1.2素性检验RSA算法的实现难点之一是生成大素数，这就需要生成一个大数并对其进行素性检验。素性检验有很多种方法。其中包括确定性方法和随机方法。确定性方法有试除法(埃拉托斯特尼筛法)，卢卡斯-莱默检验法和AKS素数测试。常见的随机方法有费马素性检验，米勒-拉宾检验和欧拉-雅科比测试。本次作业采用就是米勒-拉宾检验方法。米勒-拉宾(MillerRabin)算法原理：要测试N是否为素数，首先将N-1分解为2sd。在每次测试开始时，先随机选一个介于[1,N-1]的整数a，之后如果对所有的r∈[0,s-1]，若admodN≠1且a2^rdmodN≠1，则N是合数。否则，N有3/4的概率为素数。1.3安全问题（1）公共模数攻击。每个人具有相同的r，但有不同的指数e和d，这是不安全的。（2）低加密指数攻击。如果选择了较低的e值，虽然可以加快计算速度，但存在不安全性。（3）低解密指数攻击。如果选择了较低的d值，也是不安全的。（4）选择密文攻击。如A想让T对一个T不愿意签名的消息m’签名，A首先选择一个任意值x，计算y=xe（modr），然后要求T对m=ym’签名，A最后计算(mdmodr)x-1modr=(ym’)dx-1modr=m’dmodr。还有一些不是直接对RSA的算法本身进行的攻击，如中间人攻击、时间攻击、边信道攻击等。2.具体实现2.1函数说明voidProducePrime(JTextFieldprime)：使用JAVA的Biginteger生成512位的大数，再用MillerRobin算法检验是否是素数。参数prime即为生成的大素数。booleanMillerRobin(BigIntegern)：用MillerRobin检验判断大数n是否是素数。BigIntegermodex(BigIntegera,BigIntegerb,BigIntegern)：模幂运算，计算abmodnBigIntegerinverse(BigIntegera,BigIntegerb)：求逆运算，计算a-1(b)StringEncode(StringPlaintext,BigIntegern,intnLen,intm,JTextFielde)：加密，用公钥（n，e）对明文Plaintext加密。StringDecode(StringCiphertext,BigIntegern,intm,JTextFieldd)：解密，用私钥d对密文Ciphertext解密。2.2JAVA代码importjava.math.BigInteger;importjava.util.Random;importjava.util.Scanner;importjavax.swing.JTextField;publicclassRSA{publicstaticvoidmain(String[]args){Strings;JTextFieldp=newJTextField(35);JTextFieldq=newJTextField(35);JTextFielde=newJTextField(35);JTextFieldd=newJTextField(35);ProducePrime(p);ProducePrime(q);BigIntegerpp=newBigInteger(p.getText());BigIntegerqq=newBigInteger(q.getText());BigIntegeroo=(pp.subtract(newBigInteger(1))).multiply(qq.subtract(newBigInteger(1)));BigIntegeree;do{ee=newBigInteger(100,newRandom()).mod(oo);}while(MillerRobin(ee)==false);e.setText(ee.toString());d.setText(inverse(ee,oo).toString());BigIntegern=pp.multiply(qq);intnLen=n.bitLength();intm=(int)(Math.ceil((double)(nLen)/16.0));nLen=(nLen-1)/16;StringCiphertext=newString();StringPlaintext=newString();System.out.println(P：+p.getText());System.out.println(Q：+q.getText());System.out.println(公钥：+e.getText());System.out.println(私钥：+d.getText());Scannerscanner=newScanner(System.in);System.out.println(输入要加密字符串：);s=scanner.nextLine();Ciphertext=Encode(s,n,nLen,m,e);System.out.println(加密结果：+Ciphertext);Plaintext=Decode(Ciphertext,n,m,d);System.out.println(解密结果：+Plaintext);}//产生大素数publicstaticvoidProducePrime(JTextFieldprime){BigIntegern=newBigInteger(0);Randomr=newRandom();do{n=newBigInteger(512,5,r);prime.setText(n.toString());}while(MillerRobin(n)==false);}//MillerRobin素性检验publicstaticbooleanMillerRobin(BigIntegern){inttime=1000;BigIntegerm=n.mod(newBigInteger(2));if(m.equals(newBigInteger(0))){returnfalse;}ints=0;intk=0;BigIntegert=n.subtract(newBigInteger(1));while(t.mod(newBigInteger(2)).equals(0)){t.divide(newBigInteger(2));++s;}for(inti=0;itime;++i){BigIntegera=newBigInteger(100,newRandom()).mod(n.subtract(newBigInteger(3))).add(newBigInteger(2));BigIntegerb=modex(a,t,n);if(b.equals(newBigInteger(1))==false&&b.equals(n.subtract(newBigInteger(1)))==false){k=1;while(k==s&&b.equals(n.subtract(newBigInteger(1)))==false){b=b.multiply(b).mod(n);if(b.equals(newBigInteger(1))){returnfalse;}++k;}if(b.equals(n.subtract(newBigInteger(1)))==false){returnfalse;}}}returntrue;}//模幂运算publicstaticBigIntegermodex(BigIntegera,BigIntegerb,BigIntegern){BigIntegerm=newBigInteger(1);while(b.equals(newBigInteger(0))==false){if(b.mod(newBigInteger(2)).equals(newBigInteger(1))){m=m.multiply(a).mod(n);}a=a.multiply(a).mod(n);b=b.divide(newBigInteger(2));}returnm;}//求逆运算publicstaticBigIntegerinverse(BigIntegera,BigIntegerb){BigIntegern1,n2,n3,m,t,b1;n1=newBigInteger(1);n2=newBigInteger(0);b1=b;while(b.equals(newBigInteger(0))==false){m=a.divide(b);n3=n1.subtract(m.multiply(n2));if(n3.compareTo(newBigInteger(0))!=-1){n3=n3.mod(b1);}else{n3=b1.subtract(n3.multiply(newBigInteger(-1)).mod(b1));}n1=n2;n2=n3;t=b;b=a.mod(b);a=t;}if(a.equals(newBigInteger(1))){returnn1;}else{returnnewBigInteger(0);}}//加密publicstaticStringEncode(StringPlaintext,BigIntegern,intnLen,intm,JTextFielde){BigIntegerr=newBigInteger(0);StringBufferoutBuf=newStringBuffer();inti,j,k;for(i=0;iPlaintext.length();i=j){BigIntegert=newBigInteger(0);for(j=i;ji+nLen&&jPlaintext.length();j++){t=t.shiftLeft(16);longnum=Plaintext.charAt(j);t=t.add(BigInteger.valueOf(num));}r=modex(t,newBigInteger(e.getText()),n);Stringbuf=newString();for(k=0;km;++k){longnum=(r.and(BigInteger.valueOf(65535))).longValue();r=r.shiftRight(16);buf=(char)(num)+buf;}outBuf=outBuf.append(buf);}returnoutBuf.toString();}//解密publicstaticStringDecode(StringCiphertext,BigIntegern,intm,JTextFieldd){StringBufferoutBuf=newStringBuffer();BigIntegerr=newBigInteger(0);inti,j;for(i=0;iCiphertext.length();i+=j){BigIntegert=newBigInteger(0);for(j=0;jm&&j+iCiphertext.length();j++){t=t.shiftLeft(16);longnum=(long)(Ciphertext.charAt(j+i));t=t.add(BigInte