RSA加密是非对称加密，由瑞弗斯特(Ron Rivest)，沙米尔(Adi Shamir)和阿德来门(Len Adleeman)于1978年提出的，它的基础是欧拉定理，安全性依赖于大数因子分解的困难性。整个RSA加密运算，要了解一点数论的基础。下面在讲解的时候，需要用到的数学知识，我都会在一旁做简单标注。此文主要包括：
-
RSA加密算法 -
RSA加解密举例 -
RSA加密的安全性 -
RSA加密算法的正确性证明
RSA加密算法
取两个大素数
p和q(p ≠ q)，记n = pq，ϕ(n) = (p-1)(q-1)。选择正整数
w，w与ϕ(n)互素，设d是w的模ϕ(n)逆，即dw ≡ 1(mod ϕ(n))。
RSA密码算法如下：首先将明文数字化，后把明文分成若干段，每一个明文段的值小于n，对每一个明文段m，
加密算法c = E(m) = m^w mod n
解密算法D(c) = c^d mod n
其中加密密钥w和n是公开的pqϕ(n)和d是保密的。
- 素数：只能被
±1和±自己整除的数，比如2, 3, 5, 7, 11... - 两数互素：除
±1之外，没有其他的公因子，比如2 ~ 3，7 ~ 11... -
ϕ(n)：这个是欧拉函数，是指小于n且与n互素的正整数的个数，习惯上ϕ(1) = 1。算法中用到的ϕ(n) = (p-1)(q-1)，p和q为素数，是欧拉函数的一个特殊情况。特殊情况还有n为素数时，ϕ(n) = n - 1。 - 模
n同余：形如a ≡ b(mod n)这样的算式称为a b模n同余，即a % n = b % n - 模逆：如果
ab ≡ 1(mod m)，即ab % m = 1，则称b是a的模m逆；由定义可知，a的模m逆就是方程ax ≡ 1(mod m)的解，其中形如ax ≡ c(mod m)的方程称一次同余方程。
RSA加解密举例
A B 两人通信，A要传递信息给 B，这时 B 公布出来加密的公钥，A 以此将信息加密，B收到密文以后用私钥解密，比如：
公钥：w = 13, n = 2537
私钥：p = 43, q = 59, ϕ(n) = 2436, d = 937(根据 w 和 ϕ(n) 求出)
A 要传递的明文信息数字化之后为：m = 2106，用公钥加密为密文：c = 2106^13 % 2537 = 2321
B 收到密文 c = 2321 后，用私钥解密为明文：m = 2321^937 % 2537 = 2106
上面加解密都要涉及到模幂乘运算形如：a^b(mod n)。这儿可以利用模运算的一个性质：(a*b) % n = [(a % n) * (b % n)] % n
比如2106^13 % 2537 = [(2106 % 2537)(2106^4 % 2537)(2106^8 % 2537)] % 2537 = [(-431) * (-988) * (-601) % 2537] = 2321
求解过程可以使用递归求解的方式，2106^2 % 2537 可以根据 2106 % 2537 来求，2106^4 % 2537 可以根据 2106^2 % 2537 来求。比如 2106^4 % 2537 = [(2106^2 % 2537)(2106^2 % 2537)] % 2537 = (560 * 560) % 2537 = -988
RSA加密的安全性
开头提到，RSA加密的安全性依赖于大数因子分解的困难性。因为 n 是公钥公布出来的，如上例中 n = 2537 很容易就可以因为分解，求得 p = 43 q = 59，继而求出 ϕ(n) = 2436, d = 937，这样就攻破了。但是在实际中，n 选的值一般为 1024位 的二进制整数，这么大的一个整数因式分解以目前的技术水平是不可能因式分解的，对加密要求更高的行为，n 则选为2048位的二进制整数。
RSA加密算法的正确性证明
正确性证明需要用到费马小定理和欧拉定理，表述如下
- 费马小定理：若
a p互素，则a^(p-1) ≡ 1(mod p)。另一种表示形式a^p ≡ a(mod p)，这种形式则不要求a p互素。
- 欧拉定理：若
a n互素，则a^ϕ(n) ≡ 1(mod n)。另一种表示形式a^ϕ(n) ≡ a(mod n)，这种形式则不要求a n互素。
因为m < n，故解密算法 D(c) = c^d mod n ⇔ c^d ≡ m(mod n)，又因为加密算法 c = m^w mod n，故 c^d ≡ m(mod n) ⇔ m^dw ≡ m(mod n)。又因为 dw ≡ 1(mod ϕ(n))，所以存在整数 k 使得 dw = kϕ(n) + 1。最终转换为证明：m^(kϕ(n) + 1) ≡ m(mod n)，其中k为整数。关于此证明可以分两种情况讨论：
m 与 n 互素
由欧拉定理 m^ϕ(n) ≡ 1(mod n) ⇒ m^kϕ(n) ≡ 1(mod n) ⇒ m^(kϕ(n) + 1) ≡ m(mod n) 命题得证
m 与 n 不互素
由于 m < n，n = pq，p 和 q 是素数且 p ≠ q，故 m 必含 p 和 q 中的一个为因子，且只含其中的一个为因子。设 m = cp，由费马小定理 m^(q - 1) ≡ 1(mod q) ⇒ m^kϕ(n) ≡ m^(k(p-1)(q-1)) ≡ 1^k(p-1) ≡ 1(mod q)，从而存在整数 h 使得 m^kϕ(n) = hq + 1，两边同乘于 m 得，m^(kϕ(n) + 1) = mhq + m = cphq + m = hcn + m ⇒ m^(kϕ(n) + 1) ≡ m(mod n) 命题得证
总结
RSA加密，整个过程的计算量是很大的，只有特别敏感的信息才使用RSA加密。此文牵扯很多的数论的知识，也没有讲解的很详细，只是用到的地方，直接给出了结论，其他一些，比如欧拉函数的通用公式，一次同余方程求解方法，费马小定理和欧拉定理的证明过程，计算模幂乘运算的通用公式，都没有做过多的详解，因为这些不是此文的重点，如果你对这些感兴趣，可以参考下面我列出来的这本参考书，或者和我交流沟通。这是一系列文章的其中一篇，你可以在这儿Encode & Decode集序找到他其他的兄弟。
参考
- 屈婉玲,耿素云,张立昂. 离散数学:高等教育出版社
网友评论