近在学习PKI，顺便接触了一些加密算法。对RSA着重研究了一下，自己也写了一个简单的实现RSA算法的Demo，包括公、私钥生成，加解密的实现。虽然比较简单，但是也大概囊括了RSA加解密的核心思想与流程。这里写下来与大家分享一下。
RSA概述：
RSA是目前有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。 RSA的数学基础是大整数因子分解问题，其说明如下：
给定两个素数p、q，计算乘积pq=n很容易
给定整数n，求n的素因数p、q使得n=pq十分困难
RSA的密码体制:
设n=pq,其中p和q是大素数。设P=E=Zn，且定义K={（n,p,q,a,b）:ab≡1(modΦ(n)) }其中 Φ(n)=(p-1)(q-1)。对于K={(n,p,q,a,b)} 定义加密 E（x）=xb mod n; 解密D(y)=ya mod n;(x,y∈Zn),值n,b组成了公钥，p、q和a组成了私钥
代码如下：
首先，写出三个封装类，PrivateKey.java PublicKey.java RsaKeyPair.java (JDK中的实现高度抽象，这里我们就简单的封装一下)
View Code
View Code
View Code
生成大素数的方法没有自己实现，借用了BigInteger类中的probablePrime(int bitlength,SecureRandom random)方法
SecureRandom random=new SecureRandom(); random.setSeed(new Date().getTime()); BigInteger bigPrimep,bigPrimeq; while(!(bigPrimep=BigInteger.probablePrime(bitlength,random)).isProbablePrime(1)){ continue; }//生成大素数p while(!(bigPrimeq=BigInteger.probablePrime(bitlength,random)).isProbablePrime(1)){ continue; }//生成大素数q
计算k、n、b的值
1 BigInteger n=bigPrimep.multiply(bigPrimeq);//生成n 2 //生成k 3 BigInteger k=bigPrimep.subtract(BigInteger.ONE).multiply(bigPrimeq.subtract(BigInteger.ONE)); 4 //生成一个比k小的b,或者使用65537 5 BigInteger b=BigInteger.probablePrime(bitlength-1, random);
核心计算a的值，扩展欧几里得算法如下
注意第二个方法 cal 其实还可以传递第三个参数，模的值，但是我们这里省略了这个参数，因为在RSA中模是1
1 private static BigInteger x; //存储临时的位置变量x，y 用于递归 2 3 private static BigInteger y; 4 5 6 //欧几里得扩展算法 7 public static BigInteger ex_gcd(BigInteger a,BigInteger b){ 8 if(b.intValue()==0){ 9 x=new BigInteger("1"); 10 y=new BigInteger("0"); 11 return a; 12 } 13 BigInteger ans=ex_gcd(b,a.mod(b)); 14 BigInteger temp=x; 15 x=y; 16 y=temp.subtract(a.divide(b).multiply(y)); 17 return ans; 18 19 } 20 21 //求反模 22 public static BigInteger cal(BigInteger a,BigInteger k){ 23 BigInteger gcd=ex_gcd(a,k); 24 if(BigInteger.ONE.mod(gcd).intValue()!=0){ 25 return new BigInteger("-1"); 26 } 27 //由于我们只求乘法逆元 所以这里使用BigInteger.One,实际中如果需要更灵活可以多传递一个参数,表示模的值来代替这里 28 x=x.multiply(BigInteger.ONE.divide(gcd)); 29 k=k.abs(); 30 BigInteger ans=x.mod(k); 31 if(ans.compareTo(BigInteger.ZERO)<0) ans=ans.add(k); 32 return ans; 33 34 }
我们在生成中只需要
1 BigInteger a=cal(b,k);
就可以在Log级别的时间内计算出a的值
将以上代码结合包装成的 RSAGeneratorKey.java
View Code
编写一个简单的JUnit测试代码，没有把结果以字节流编码显示 ，比较懒。。。。
View Code
这样秘钥对的生成工作就完成了
加密与解密
加密与解密的根本就是使用E（x）=xb mod n D(y)=ya mod n这两个公式，所以我们首先要将数据转化为底层的二进制串，在转换为BigInteger进行计算，将结果做成Base64码
代码如下
View Code
很坑爹的一点是要记得BigInteger是有符号位的。重组String时要记得去除符号位，不然中文的时候会莫名其妙在位多出空格。
在编写一个测试代码就Ok了
View Code
测试结果。bingo。
本站文章版权归原作者及原出处所有 。内容为作者个人观点， 并不代表本站赞同其观点和对其真实性负责，本站只提供参考并不构成任何投资及应用建议。本站是一个个人学习交流的平台，网站上部分文章为转载，并不用于任何商业目的，我们已经尽可能的对作者和来源进行了通告，但是能力有限或疏忽，造成漏登，请及时联系我们，我们将根据著作权人的要求，立即更正或者删除有关内容。本站拥有对此声明的最终解释权。
