rsa加密算法
简介：
RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
RSA算法是现今使用最广泛的公钥密码算法，也是号称地球上最安全的加密算法。在了解RSA算法之前，先熟悉下几个术语
根据密钥的使用方法，可以将密码分为对称密码和公钥密码
对称密码：加密和解密使用同一种密钥的方式
公钥密码：加密和解密使用不同的密码的方式，因此公钥密码通常也称为非对称密码。
一、加密算法概述
二、算法原理图解
流程图
RSA中涉及到的数论知识
质数：
又称素数，一个大于1的正整数，除了1和它自身外，不能被其他整数整除。
互质关系：
如果两个正整数，除了1以外没有其他公因子，就称这两个数是互质关系。
推论：
任意两个质数构成互质关系。
大数是质数的两个数一定是互质关系。
同余：
给定一个正整数m，若存在两个整数a和b满足a-b能被m整除，即(a-b) mod m = 0, 那么就称整数a与b对模m同余，记作 ：a≡b(mod m) , 同3时又成立：a mod m = b
欧拉函数：
- 定义： 对于给定正整数n，计算在小于等于n的正整数中，有多少个数与n构成互质关系。如：φ(8) = 4 .
推论：
- 若n可以拆成两个互质的正整数之积，如 n = p × q ，则有：φ(n) = φ(pq) = φ§φ(q)
- 对质数m ， 有：φ(m) = m-1 .
- 若n可以拆解成两个质数p和q的积，则：φ(n) = (p-1)(q-1) .
- 欧拉定理：如果两个正整数a和n互质，则n的欧拉函数φ(n)有：
φ ( n ) = φ ( p q ) = φ § φ ( q ) φ(n) = φ(pq) = φ§φ(q)φ(n)=φ(pq)=φ§φ(q)
对质数m ， 有：φ(m) = m-1 .
若n可以拆解成两个质数p和q的积，则：φ(n) = (p-1)(q-1) .
欧拉定理：如果两个正整数a和n互质，则n的欧拉函数φ(n)有：
a φ ( n ) ≡ 1 ( m o d n ) a φ (n)≡1(modn)aφ(n)≡1(modn)
意味着 a的φ(n)次方被n除的余数为1.
模反元素
如果两个正整数a和n互质，则一定有整数b，使得：ab-1能被n整除，或者说ab被n整除的余数是1，记作：ab≡1(mod n)
原理：
加密过程：
- 选取两个不同的大质数p和q，计算它们的乘积n=pq，并求出欧拉函数φ(n)=(p-1)(q-1)。
- 选择一个小于φ(n)且与φ(n)互质的整数e作为公钥，即公钥为(n,e)。
- 求出与e模φ(n)同余的整数d，即d*e=1 mod φ(n)，d为私钥，私钥为(n,d)。
- 将明文M转换成整数m，使得m<n。
- 对明文进行加密，计算密文C=m^e mod n。
- 发送密文C。
解密过程：
伪代码：
// 生成公钥和私钥 int p = 61; int q = 53; int n = p * q; int phi = (p - 1) * (q - 1); int e; do { e = random(2, phi - 1); // 生成一个与phi互质的整数e } while (gcd(e, phi) != 1); // 判断e与phi是否互质 int d = modInverse(e, phi); // 加密过程 int m = 123; int c = modPow(m, e, n); // 计算密文 // 解密过程 int m2 = modPow(c, d, n); // 计算明文 // 辅助函数 int gcd(int a, int b) { if (b == 0) { return a; } else { return gcd(b, a % b); } } int modInverse(int a, int m) { int m0 = m; int y = 0, x = 1; if (m == 1) { return 0; } while (a > 1) { int q = a / m; int t = m; m = a % m; a = t; t = y; y = x - q * y; x = t; } if (x < 0) { x += m0; } return x; } int modPow(int a, int b, int m) { int res = 1; while (b > 0) { if ((b & 1) == 1) { res = (res * a) % m; } a = (a * a) % m; b >>= 1; } return res; }
