Loading... ## 历史 1976年,两位美国计算机学家Whitfield Diffie 和 Martin Hellman,提出了一种崭新构思,可以在不直接传递密钥的情况下,完成解密。这被称为["Diffie-Hellman密钥交换算法"](http://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange)。这个算法启发了其他科学家。人们认识到,加密和解密可以使用不同的规则,只要这两种规则之间存在某种对应关系即可,这样就避免了直接传递密钥。 这种新的加密模式被称为"非对称加密算法"。 > 非对称加密传输的大致流程如下: > > 1. A 生成一对密钥 (公钥和私钥),然后将公钥公开出去,私钥自己保存。 > 2. B 获取 A 的公钥,用它加密一段信息,再发送给 A。 > 3. A 收到 B 发送的信息,再用自己的私钥解密。 1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做[RSA算法](http://zh.wikipedia.org/zh-cn/RSA加密算法)。 ## 准备 在开始 RSA 算法原理之前,我们先来看一点数论的知识: ### 1. 互质关系 如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是[互质关系](http://zh.wikipedia.org/zh-cn/互素)(coprime)。比如,15和32没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。 关于互质关系,不难得到以下结论: > 1. 任意两个质数构成互质关系,比如13和61。 > > 2. 一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如3和10。 > > 3. 如果两个数之中,较大的那个数是质数,则两者构成互质关系,比如97和57。 > > 4. 1和任意一个自然数是都是互质关系,比如1和99。 > > 5. p是大于1的整数,则p和p-1构成互质关系,比如57和56。 > > 6. p是大于1的奇数,则p和p-2构成互质关系,比如17和15。 ### 2. 欧拉函数 在看欧拉函数之前我们先看一个问题: > 任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?) 计算这个值的方法就叫做[欧拉函数]( https://en.wikipedia.org/wiki/Euler's_totient_function),以 $\phi(n)$ 表示。 在 1 到 8 之中,与8形成互质关系的是 1、3、5、7,所以 $\phi(n) = 4$ 。 $ \phi(n) $ 的计算方法并不复杂,但是为了得到最后那个公式,需要一步步讨论。 **第一种情况** 如果 $n=1$ ,则 $\phi(1) = 1$ 。因为1与任何数(包括自身)都构成互质关系。 **第二种情况** 如果n是质数,则 $\phi(n)=n-1$ 。因为质数与小于它的每一个数,都构成互质关系。比如 5 与1、2、3、4都构成互质关系。 **第三种情况** 如果n是质数的某一个次方,即 $n = p^k (p为质数,k为大于等于1的整数)$,则 $$ φ(p^k) = p^k - p^{k-1} $$ 比如 $\phi(8) = \phi(2^3) =2^3 - 2^2 = 8 -4 = 4$。 这是因为只有当一个数不包含质数 $p$ ,才可能与 $n$ 互质。而包含质数 $p$ 的数一共有 $p^{(k-1)}$ 个,即 $1×p、2×p、3×p、...、p^{(k-1)}×p$ ,把它们去除,剩下的就是与 $n$ 互质的数。 上面的式子还可以写成下面的形式: $$ φ(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p}) $$ 可以看出,上面的第二种情况是 $k=1$ 时的特例。 **第四种情况** 如果 $n$ 可以分解成两个互质的整数之积, $$ n = p1 × p2 $$ 则 $$ φ(n) = φ(p1p2) = φ(p1)φ(p2) $$ 即积的欧拉函数等于各个因子的欧拉函数之积。比如,$\phi(56)=\phi(8×7)=\phi(8)×\phi(7)=4×6=24$ 。 这一条的证明要用到["中国剩余定理"](http://en.wikipedia.org/wiki/Chinese_remainder_theorem),这里就不展开了,只简单说一下思路:如果 $a$ 与 $p1$ 互质 $(a<p1)$ ,$b$ 与 $p2$ 互质 $(b<p2)$ ,$c$ 与 $p1p2$ 互质 $(c<p1p2)$ ,则 $c$ 与数对 $(a,b)$ 是一一对应关系。由于 $a$ 的值有 $\phi(p1)$ 种可能, $b$ 的值有 $\phi(p2)$ 种可能,则数对 $(a,b)$ 有 $\phi(p1)\phi(p2)$ 种可能,而 $c$ 的值有 $\phi(p1p2)$ 种可能,所以 $\phi(p1p2)$ 就等于 $\phi(p1)\phi(p2)$ 。 **第五种情况** 因为任意一个大于1的正整数,都可以写成一系列质数的积。 $$ n = p^{k1}_1p^{k2}_2...p^{kr}_r $$ 根据第4条的结论,得到 $$ φ(n) = φ(p^{k1}_1)φ(p^{k2}_2)...φ(p^{kr}_r) $$ 再根据第3条的结论,得到 $$ φ(n) = p^{k1}_1p^{k2}_2...p^{kr}_r(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_r}) $$ 也就等于 $$ φ(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_r}) $$ 这就是欧拉函数的通用计算公式。比如,1323的欧拉函数,计算过程如下: $$ φ(1323) = φ(3^3 \times 7^2) = 1323(1 - \frac{1}{3})(1 - \frac{1}{7}) = 756 $$ ### 3. 欧拉定理 欧拉函数的作用,在于欧拉定理: > 如果两个正整数 $a$ 和 $n$ 互质,则n的欧拉函数 $\phi(n)$ 可以让下面的等式成立 : > $$ > a ^ {\phi_{(n)}} \equiv 1 (mod \; n) > $$ 也就是说,$a$ 的 $\phi(n)$ 次方被 $n$ 除的余数为1。或者说,$a$ 的 $\phi(n)$ 次方减去1,可以被 $n$ 整除。比如,3和7互质,而7的欧拉函数 $\phi(7)$ 等于6,所以3的6次方 (729) 减去1,可以被7整除 (728/7=104)。 欧拉定理有一个特殊情况。 > 假设正整数 $a$ 与质数 $p$ 互质,因为质数 $p$ 的 $\phi(p)$ 等于 $p-1$ ,则欧拉定理可以写成 > $$ > a^{p-1} \equiv 1 (mod \; p) > $$ 这就是著名的[费马小定理](http://zh.wikipedia.org/wiki/费马小定理)。它是欧拉定理的特例。 ### 4. 模反元素 > 如果两个正整数 $a$ 和 $n$ 互质,那么一定可以找到整数 $b$ ,使得 $ab-1$ 被 $n$ 整除,或者说 $ab$ 被 $n$ 除的余数是1。 > $$ > ab \equiv 1(mod \; n) > $$ > 这时,$b$ 就叫做 $a$ 的["模反元素"](http://zh.wikipedia.org/wiki/模反元素)。 比如,3和11互质,那么3的模反元素就是4,因为 (3 × 4)-1 可以被11整除。显然,模反元素不止一个, 4加减11的整数倍都是3的模反元素 {...,-18,-7,4,15,26,...},即如果b是a的模反元素,则 $b+kn$ 都是a的模反元素。 欧拉定理可以用来证明模反元素必然存在。 $$ a^{\phi(n)} = a \times a^{\phi(n) - 1} \equiv 1(mod \; n) $$ 可以看到,$a$ 的 $\phi(n)-1$ 次方,就是 $a$ 的模反元素。 ## 算法流程 看完这些数论的知识后,我们就可以理解 RSA 的算法原理了。首先我们先来看一下 RSA 的算法流程: ### 1. 生成密钥 假设[爱丽丝](http://zh.wikipedia.org/wiki/爱丽丝与鲍伯)要与鲍勃进行加密通信,她该怎么生成公钥和私钥呢? **第一步,随机选择两个不相等的质数 $p$ 和 $q$ 。** 爱丽丝选择了61和53。(实际应用中,这两个质数越大,就越难破解。) **第二步,计算 $p$ 和 $q$ 的乘积 $n$ 。** 爱丽丝就把61和53相乘。 $$ n = 61×53 = 3233 $$ n的长度就是密钥长度。3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。 **第三步,计算 $n$ 的欧拉函数 $\phi(n)$ 。** 根据公式: $$ φ(n) = (p-1)(q-1) $$ 爱丽丝算出 $\phi(3233)$ 等于60×52,即3120。 **第四步,随机选择一个整数 $e$,条件是 $1< e < \phi(n)$,且 $e$ 与 $\phi(n)$ 互质。** 爱丽丝就在1到3120之间,随机选择了17。(实际应用中,常常选择65537。) **第五步,计算 $e$ 对于 $\phi(n)$ 的模反元素 $d$。** 所谓["模反元素"](http://zh.wikipedia.org/wiki/模反元素)就是指有一个整数 $d$,可以使得 $ed$ 被 $\phi(n)$ 除的余数为1。 $$ ed ≡ 1 (mod φ(n)) $$ 这个式子等价于 $$ ed - 1 = kφ(n) $$ 于是,找到模反元素 $d$ ,实质上就是对下面这个二元一次方程求解。 $$ ex + φ(n)y = 1 $$ 已知 $e=17, \phi(n)=3120$, $$ 17x + 3120y = 1 $$ 这个方程可以用["扩展欧几里得算法"](http://zh.wikipedia.org/wiki/扩展欧几里得算法)求解,此处省略具体过程。总之,爱丽丝算出一组整数解为 $(x,y)=(2753,-15)$,即 $d=2753$。 至此所有计算完成。 **第六步,将 $n$ 和 $e$ 封装成公钥,$n$ 和 $d$ 封装成私钥。** 在爱丽丝的例子中,$n=3233$,$e=17$,$d=2753$,所以公钥就是 $(3233,17)$,私钥就是 $(3233, 2753)$ 。 实际应用中,公钥和私钥的数据都采用[ASN.1](http://zh.wikipedia.org/zh-cn/ASN.1)格式表达([实例](http://hi.baidu.com/mathack/item/d0ad4cc1514a3663f7c95da2))。 ### 2. 加密与解密 有了公钥和密钥,就能进行加密和解密了。 **(1)加密要用公钥 $(n,e)$** 假设鲍勃要向爱丽丝发送加密信息 $m$,他就要用爱丽丝的公钥 $(n,e)$ 对 $m$ 进行加密。这里需要注意,$m$ 必须是整数(字符串可以取 ascii 值或 unicode 值),且 $m$ 必须小于 $n$。 所谓"加密",就是算出下式的 $c$ : $$ m^e ≡ c (mod \; n) $$ 爱丽丝的公钥是 $(3233, 17)$,鲍勃的 $m$ 假设是 65,那么可以算出下面的等式: $$ 65^{17} ≡ 2790 (mod \; 3233) $$ 于是,$c$ 等于2790,鲍勃就把 2790 发给了爱丽丝。 **(2)解密要用私钥(n,d)** 爱丽丝拿到鲍勃发来的 2790 以后,就用自己的私钥 $(3233, 2753)$ 进行解密。可以证明,下面的等式一定成立: $$ c^d ≡ m (mod \; n) $$ 也就是说,$c$ 的 $d$ 次方除以 $n$ 的余数为 $m$ 。现在,$c$ 等于 2790,私钥是 $(3233, 2753)$ ,那么,爱丽丝算出 $$ 2790^{2753} ≡ 65 (mod \; 3233) $$ 因此,爱丽丝知道了鲍勃加密前的原文就是65。 至此,"加密--解密"的整个过程全部完成。 ## 算法安全性 由上面的流程可以知道,我们总共用了 6 个数字: $ p, q, n, \phi(n), e, d $ 。 其中 $n$ 和 $e$ 组成了公钥,其他的四个数字都是不公开的。四个数字中最关键的就是 $d$ 。因为私钥是由 $n, d$ 组成的,所以 $d$ 泄露就相当于私钥泄露。 **那么,有无可能在已知 $n$ 和 $e$ 的情况下,推导出 $d$ ?** > (1)$e ^ d≡1 (mod \; \phi(n))$ 。只有知道 $e$ 和 $\phi(n)$ ,才能算出 $d$ 。 > > (2)$\phi(n)=(p-1)(q-1)$。只有知道 $p$ 和 $q$ ,才能算出 $\phi(n)$ 。 > > (3)$n=pq$ 。只有将 $n$ 因数分解,才能算出 $p$ 和 $q$ 。 **结论:如果 $n$ 可以被因数分解,$d$ 就可以算出,也就意味着私钥被破解。** 可是,大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。维基百科这样写道: > "对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。 > > 假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。 > > 只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。" ## 证明 最后,我们来证明,为什么用私钥解密,一定可以正确地得到 $m$ 。也就是证明下面这个式子: $$ c^d ≡ m (mod \; n) $$ 因为,根据加密规则 $$ m^e ≡ c (mod \; n) $$ 于是,$c$ 可以写成下面的形式: $$ c = m^e - kn $$ 将 $c$ 代入要我们要证明的那个解密规则: $$ (m^e - kn)^d ≡ m (mod n) $$ 它等同于求证 $$ m^{ed} ≡ m (mod \; n) $$ 由于 $$ ed ≡ 1 (mod \; φ(n)) $$ 所以 $$ ed = hφ(n)+1 $$ 将 $ed$ 代入: $$ m^{hφ(n)+1} ≡ m (mod \; n) $$ 接下来,分成两种情况证明上面这个式子。 **(1)m与n互质。** 根据欧拉定理,此时 $$ m^{φ(n)} ≡ 1 (mod \; n) $$ 得到 $$ (m^{φ(n)})^h × m ≡ m (mod \; n) $$ 原式得到证明。 **(2)m与n不是互质关系。** 此时,由于 $n$ 等于质数 $p$ 和 $q$ 的乘积,所以 $m$ 必然等于 $kp$ 或 $kq$ 。 以 $m = kp$为例,考虑到这时$k$与$q$必然互质,则根据欧拉定理,下面的式子成立: $$ (kp)^{q-1} ≡ 1 (mod \; q) $$ 进一步得到 $$ [(kp)^{q-1}]^{h(p-1)} × kp ≡ kp (mod \; q) $$ 即 $$ (kp)^{ed} ≡ kp (mod \; q) $$ 将它改写成下面的等式 $$ (kp)^{ed} = tq + kp $$ 这时t必然能被 $p$ 整除,即 $t=t'p$ $$ (kp)^{ed} = t'pq + kp $$ 因为 $m=kp,n=pq$ ,所以 $$ m^{ed} ≡ m (mod \; n) $$ 原式得到证明。 ## 代码实现 ### Python 代码实现 > Miller_Rabin.py ```python # encoding: utf-8 import random def MillerRabin(num, times): if num == 2: return True if num < 2 or num % 2 == 0: return False r = num - 1 k = 0 while r % 2 == 0: r //= 2 k += 1 for t in range(times): a = random.randrange(2, num - 1) x = pow(a, r, num) for i in range(1, k + 1): tmp = x * x % num if tmp == 1 and x != 1 and x != num - 1: return False x = tmp if x != 1: return False return True def isPrime(num, times): if num<2: return False lowPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997] if num in lowPrimes: return True for prime in lowPrimes: if num % prime==0: return False return MillerRabin(num, times) def generateLargePrime(keysize=1024): while True: num = random.randrange(2**(keysize-1), 2**keysize) if isPrime(num, 8): return num if __name__ == "__main__": res = generateLargePrime() print (res) ``` > cryptomath.py ```python # encoding: utf-8 def gcd(a, b): # Return the GCD of a and b using Euclid's Algorithm while a != 0: a, b = b % a, a return b def findModInverse(a, m): # Returns the modular inverse of a % m, which is # the number x such that a*x % m = 1 if gcd(a, m) != 1: return None # no mod inverse if a & m aren't relatively prime # Calculate using the Extended Euclidean Algorithm: u1, u2, u3 = 1, 0, a v1, v2, v3 = 0, 1, m while v3 != 0: q = u3 // v3 # // is the integer division operator v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3 return u1 % m ``` > RSA.py ```python # encoding: utf-8 import random import cryptomath from Miller_Rabin import generateLargePrime def generateRSAkey(keysize): p = generateLargePrime(keysize) q = generateLargePrime(keysize) n = p * q while True: e = random.randrange(2 ** (keysize - 1), 2 ** keysize) # e 和 \phi(n) 需互素 if cryptomath.gcd(e, (p - 1) * (q - 1)) == 1: break # 计算模反元素 d = cryptomath.findModInverse(e, (p - 1) * (q - 1)) publicKey = (n, e) privateKey =(n, d) return (publicKey, privateKey) def encrypt(plain, publicKey): plain = plain.encode('ascii') plain = list(plain) cipher = [] for e in plain: cipher.append(pow(e, publicKey[1], publicKey[0])) return cipher def decrypt(cipher, privateKey): plain = [] for c in cipher: plain.append(pow(c, privateKey[1], privateKey[0])) res = bytes(plain).decode('ascii') return res if __name__ == '__main__': publicKey, privateKey = generateRSAkey(32) print("public key: ", publicKey) print("private key: ", privateKey) text = "hello world!" cipher = encrypt(text, publicKey) plain = decrypt(cipher, privateKey) print ("cipher = ", cipher) print ("plain = ", plain) ``` ## Referrer http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html 最后修改:2019 年 11 月 18 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏