本文的概要旨在说明RSA加密算法的原理和实现，相关数学部分的证明不是本文的内容。
说明著作权归作者所有。
商业转载请联系作者取得许可。 非商业转载请注明出处。
作者： Coding-Naga
发布日期： 2016年2月29日
本文链接： http://blog.csdn.net/lemon _ tree 12138/article/details/50696926
来源： CSDN
详细信息：分类数据加密和信息安全
RSA简介1977年，三位数学家Rivest、Shamir、Adleman设计了实现非对称加密的算法。 该算法以三个人的名字命名，称为RSA算法。 从那时到现在，RSA算法是应用最广泛的“非对称加密算法”。 毫不夸张地说，有计算机网络的地方就有RSA算法。
-摘自网络
数学背景这部分旨在补充本文的完整性。 如果你说你已经知道或者不想知道这部分的内容。 那么，你可以直接跳过这个部分的读法。
虽说只是补充说明，但博客的数学也是-_-!!!，但这部分的内容相当重要。 博主希望你再读一遍这个部分。
1 .互质从小学开始就知道什么是质数。 互质是对多个数字说的，是两个正整数，如果除了1以外没有其他的公因子，那两个数就称为互质关系。 (请注意，在此，并没有表示这两个数必须是素数，或者其中一个是素数。 例如15和4是相互质量的关系)。 关于质数和互质有几个性质：
如果质数为1和能被其自身整除的任意两个质数互为质的关系的两个数中，较大的一个数为质数，则两者互为质的关系
两个数中，如果小的一方的数为素数，大的一方的数不是小的一方的整数倍，则两者互为质的关系
1和任何自然数都是互相质量的关系
如果p是大于1的整数，p和p-1构成相互质量关系
如果p是大于1的奇数，则p和p-2互为质的关系
2 .欧拉函数
欧拉函数是不足x且求出与x互质数的个数。 其通式为(x) = x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)
其中p1, p2……pn是x的所有质因数，x是非0的整数。 看到这里你就头疼吗？ 过于理论化的东西确实不是具体的。 我们无视后面公式的计算和论证。 因为已经超出了正文的范围。 谈谈前面的句子吧。 欧拉函数求小于x且与x互有质量的数的个数。 在这里举个例子：
如果x=16，则x的所有质因数必须与(16) = 16 * (1 - 1/2) = 8
我们还可以列举所有小于16、与16互质的数。1, 3, 5, 7, 9, 11, 13, 15
现在，欧拉函数的一部分性质也被给出：
这是因为，如果n是素数p的k次幂，则p的倍数以外的数都与n互为要素
欧拉函数是积性函数——若m，n互为素，
在n为奇数情况下，
p为素数，(p )为p的欧拉值
有关Euler函数的详细信息，请参见此处的链接。
3 .模逆元素的定义：在两个正整数a和n相互为素数的情况下，一定能够找到整数b，使得ab-1能够被n整除，或者ab能够被n整除的馀数为1。
对于模反因素的求解，采用了朴素的解法。 读者如果想了解更多，请自己搜索其他解法。 例如，辗转相除、cqdzxc算法等。
RSA原理在RSA原理之前，我认为还是有必要了解不对称密码算法的加密和解密过程。 以下是非对称加密算法的流程图。
如您所见，非对称加密通过两个密钥(公钥-私钥)来加密和解密数据。 公钥用于加密，私钥用于解密。 为什么可以用不同的密钥进行不对称的加密和解密，这些是数学问题。 不同的不对称加密算法也适用于不同的数学知识。 上面也稍微介绍了一下RSA中使用的数学问题。 让我们看看RSA算法是如何加密数据的。 以下是RSA加密算法的流程和加密过程的图示。
RSA应用1 .以实例模型上图的Bob和落后的毛豆为例。
当前，延迟的枝豆由密钥生成器生成了一对密钥(公钥-私钥)。 只公开了公开密钥。 并且，如果有什么想对我说的话，请用模幂运算和公钥加密后发送。
这时，鲍勃已经得到了迟来的毛豆的宣布
公钥。使用模幂运算对明文进行了加密，就把加密后的密文发送给了落后的毛豆。落后的毛豆获得Bob发来的密文并没有使用公钥对密文进行解密，并获得了明文。因为解密过程需要使用的密钥是私钥。
下面的代码只是根据RSA算法的定义，使用Java开发语言实现。且这里只是展示了一些关键步骤，完整过程可以参见下面的源码下载文档。
public class RSA { /** * 获得(公/私)密钥 */ public final Map<String, RSAKey> getCipherKeys() { ... int[] primes = getRandomPrimes(2); int modulus = modulus(primes[0], primes[1]); int euler = euler(primes[0], primes[1]); int e = cipherExponent(euler); int inverse = inverse(euler, e); publicKey.setExponent(e); publicKey.setModulus(modulus); privateKey.setExponent(inverse); privateKey.setModulus(modulus); ... } /** * 加密 */ public int encode(int plaintext, RSAPublicKey key) { return modularPower2(plaintext, key.getExponent(), key.getModulus()); } /** * 解密 */ public int decode(int chipertext, RSAPrivateKey key) { return modularPower2(chipertext, key.getExponent(), key.getModulus()); } // 随机生成count个素数 private final int[] getRandomPrimes(int count) { ... try { primeLabels = FileReadUtils.readLines("./data/prime_table"); } catch (IOException e) { e.printStackTrace(); } for (int i = 0; i < primes.length; i++) { primes[i] = Integer.parseInt(primeLabels.get(indexs.get(i))); } return primes; } // 计算公共模数 private final int modulus(int p, int q) { return p * q; } // 计算欧拉数 private final int euler(int p, int q) { return (p - 1) * (q - 1); } // 计算加密指数 private final int cipherExponent(int euler) { Random random = new Random(); int e = 7; do { e = random.nextInt(euler - 1); } while (!isCoprime(e, euler) || e <= 1); return e; } // 判断两个数互素 private final boolean isCoprime(int number1, int number2) { int sqrt = (int) Math.sqrt(Math.max(number1, number2)); for (int i = 2; i <= sqrt; i++) { if (number1 % i == 0 && number2 % 2 == 0) { return false; } } return true; } // 计算“模的逆元” // (d * e) ≡ 1 mod euler private final int inverse(int euler, int e) { ... while (flag) { q = m[2] / n[2]; for (int i = 0; i < 3; i++) { temp[i] = m[i] - q * n[i]; m[i] = n[i]; n[i] = temp[i]; } if (n[2] == 1) { if (n[1] < 0) { n[1] = n[1] + euler; } return n[1]; } if (n[2] == 0) { flag = false; } } return 0; } // 模幂运算 private final int modularPower(int base, int e, int modular) { int result = 1; do { if (isOdd(e)) { result = (result * (base % modular)) % modular; e -= 1; } else { base = (base * base) % modular; e /= 2; } } while (e > 0); result %= modular; return result; }}RSA算法判别 RSA算法优点
不需要进行密钥传递，提高了安全性可以进行数字签名认证
RSA算法缺点
加密解密效率不高，一般只适用于处理小量数据（如：密钥）容易遭受小指数攻击
《算法导论》《算法的乐趣》《深入浅出密码学》RSA算法原理（一） -- 阮一峰RSA算法原理（二） -- 阮一峰逆元详解 -- ACdreamers
JAVA实现扩展cqdzxc算法求乘法逆元
http://download.csdn.net/detail/u013761665/9439852
转载于:https://www.cnblogs.com/fengju/p/6336011.html