RSA 算法学习记录

博主： Richard
发布时间：2019 年 10 月 27 日
804 次浏览
暂无评论
9436字数
分类：数据结构与算法 Crypto

历史

1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。

这种新的加密模式被称为"非对称加密算法"。

非对称加密传输的大致流程如下:
A 生成一对密钥 (公钥和私钥)，然后将公钥公开出去，私钥自己保存。
B 获取 A 的公钥，用它加密一段信息，再发送给 A。
A 收到 B 发送的信息，再用自己的私钥解密。

1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。

准备

在开始 RSA 算法原理之前，我们先来看一点数论的知识：

1. 互质关系

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（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构成互质关系？）

计算这个值的方法就叫做欧拉函数，以 $\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$ 。

这一条的证明要用到"中国剩余定理"，这里就不展开了，只简单说一下思路：如果 $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) $$

这就是著名的费马小定理。它是欧拉定理的特例。

4. 模反元素

如果两个正整数 $a$ 和 $n$ 互质，那么一定可以找到整数 $b$ ，使得 $ab-1$ 被 $n$ 整除，或者说 $ab$ 被 $n$ 除的余数是1。
$$ ab \equiv 1(mod \; n) $$
这时，$b$ 就叫做 $a$ 的"模反元素"。

比如，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. 生成密钥

假设爱丽丝要与鲍勃进行加密通信，她该怎么生成公钥和私钥呢？

第一步，随机选择两个不相等的质数 $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$。

所谓"模反元素"就是指有一个整数 $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 $$

这个方程可以用"扩展欧几里得算法"求解，此处省略具体过程。总之，爱丽丝算出一组整数解为 $(x,y)=(2753,-15)$，即 $d=2753$。

至此所有计算完成。

第六步，将 $n$ 和 $e$ 封装成公钥，$n$ 和 $d$ 封装成私钥。

在爱丽丝的例子中，$n=3233$，$e=17$，$d=2753$，所以公钥就是 $(3233,17)$，私钥就是 $(3233, 2753)$ 。

实际应用中，公钥和私钥的数据都采用ASN.1格式表达（实例）。

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) $$

因为，根据加密规则

$$ ｍ^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

# 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

# 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

# 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 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

[每日一题] 216.组合总和III - Richardの小小杂货铺
[...]};时间复杂度 $O(M \times 2^M)$ ...
fa
最新的版本无法登陆，能否指导一下。多谢
rantrism
您好～我是腾讯云开发者社区运营，关注了您分享的技术文章，觉得内...
examine
Richard什么时候带我
https://telegra.ph/Technology-A-linchpin-To-Maintain-Businesses-Handle-Remote-Workforce-Amid-Pandemic---Technology-02-16
You actually expressed this ade...

RSA 算法学习记录

Richard • 2019 年 10 月 27 日

<h2>历史</h2>1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为<a class="no-external-link" href="http://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange" target="_blank">"Diffie-Hellman密钥交换算法"</a>。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。这种新的加密模式被称为"非对称加密算法"。<blockquote>非对称加密传输的大致流程如下:<ol><li>A 生成一对密钥 (公钥和私钥)，然后将公钥公开出去，私钥自己保存。</li><li>B 获取 A 的公钥，用它加密一段信息，再发送给 A。</li><li>A 收到 B 发送的信息，再用自己的私钥解密。</li></ol></blockquote>1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做<a class="no-external-link" href="http://zh.wikipedia.org/zh-cn/RSA加密算法" target="_blank">RSA算法</a>。<h2>准备</h2>在开始 RSA 算法原理之前，我们先来看一点数论的知识：<h3>1. 互质关系</h3>如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是<a class="no-external-link" href="http://zh.wikipedia.org/zh-cn/互素" target="_blank">互质关系</a>（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。 关于互质关系，不难得到以下结论：<blockquote>　　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。</blockquote><h3>2. 欧拉函数</h3>在看欧拉函数之前我们先看一个问题:<blockquote>任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）</blockquote>计算这个值的方法就叫做<a class="no-external-link" href="https://en.wikipedia.org/wiki/Eulers_totient_function" target="_blank">欧拉函数</a>，以 $\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$ 。这一条的证明要用到<a class="no-external-link" href="http://en.wikipedia.org/wiki/Chinese_remainder_theorem" target="_blank">"中国剩余定理"</a>，这里就不展开了，只简单说一下思路：如果 $a$ 与 $p1$ 互质 $(a&lt;p1)$ ，$b$ 与 $p2$ 互质 $(b&lt;p2)$ ，$c$ 与 $p1p2$ 互质 $(c&lt;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
$$<h3>3. 欧拉定理</h3>欧拉函数的作用，在于欧拉定理:<blockquote>如果两个正整数 $a$ 和 $n$ 互质，则n的欧拉函数 $\phi(n)$ 可以让下面的等式成立 : $$
 a ^ {\phi_{(n)}} \equiv 1 (mod \; n)
 $$</blockquote>也就是说，$a$ 的 $\phi(n)$ 次方被 $n$ 除的余数为1。或者说，$a$ 的 $\phi(n)$ 次方减去1，可以被 $n$ 整除。比如，3和7互质，而7的欧拉函数 $\phi(7)$ 等于6，所以3的6次方 (729) 减去1，可以被7整除 (728/7=104)。欧拉定理有一个特殊情况。<blockquote>假设正整数 $a$ 与质数 $p$ 互质，因为质数 $p$ 的 $\phi(p)$ 等于 $p-1$ ，则欧拉定理可以写成$$
a^{p-1} \equiv 1 (mod \; p)
$$</blockquote>这就是著名的<a class="no-external-link" href="http://zh.wikipedia.org/wiki/费马小定理" target="_blank">费马小定理</a>。它是欧拉定理的特例。<h3>4. 模反元素</h3><blockquote>如果两个正整数 $a$ 和 $n$ 互质，那么一定可以找到整数 $b$ ，使得 $ab-1$ 被 $n$ 整除，或者说 $ab$ 被 $n$ 除的余数是1。$$
ab \equiv 1(mod \; n)
$$这时，$b$ 就叫做 $a$ 的<a class="no-external-link" href="http://zh.wikipedia.org/wiki/模反元素" target="_blank">"模反元素"</a>。</blockquote>比如，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$ 的模反元素。<h2>算法流程</h2>看完这些数论的知识后，我们就可以理解 RSA 的算法原理了。首先我们先来看一下 RSA 的算法流程:<h3>1. 生成密钥</h3>假设<a class="no-external-link" href="http://zh.wikipedia.org/wiki/爱丽丝与鲍伯" target="_blank">爱丽丝</a>要与鲍勃进行加密通信，她该怎么生成公钥和私钥呢？第一步，随机选择两个不相等的质数 $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&lt; e &lt; \phi(n)$，且 $e$ 与 $\phi(n)$ 互质。爱丽丝就在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）第五步，计算 $e$ 对于 $\phi(n)$ 的模反元素 $d$。所谓<a class="no-external-link" href="http://zh.wikipedia.org/wiki/模反元素" target="_blank">"模反元素"</a>就是指有一个整数 $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
$$这个方程可以用<a class="no-external-link" href="http://zh.wikipedia.org/wiki/扩展欧几里得算法" target="_blank">"扩展欧几里得算法"</a>求解，此处省略具体过程。总之，爱丽丝算出一组整数解为 $(x,y)=(2753,-15)$，即 $d=2753$。至此所有计算完成。第六步，将 $n$ 和 $e$ 封装成公钥，$n$ 和 $d$ 封装成私钥。在爱丽丝的例子中，$n=3233$，$e=17$，$d=2753$，所以公钥就是 $(3233,17)$，私钥就是 $(3233, 2753)$ 。实际应用中，公钥和私钥的数据都采用<a class="no-external-link" href="http://zh.wikipedia.org/zh-cn/ASN.1" target="_blank">ASN.1</a>格式表达（<a class="no-external-link" href="http://hi.baidu.com/mathack/item/d0ad4cc1514a3663f7c95da2" target="_blank">实例</a>）。<h3>2. 加密与解密</h3>有了公钥和密钥，就能进行加密和解密了。（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。至此，"加密--解密"的整个过程全部完成。<h2>算法安全性</h2>由上面的流程可以知道，我们总共用了 6 个数字: $ p, q, n, \phi(n), e, d $ 。其中 $n$ 和 $e$ 组成了公钥，其他的四个数字都是不公开的。四个数字中最关键的就是 $d$ 。因为私钥是由 $n, d$ 组成的，所以 $d$ 泄露就相当于私钥泄露。那么，有无可能在已知 $n$ 和 $e$ 的情况下，推导出 $d$ ？<blockquote>　　（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$ 。</blockquote>结论：如果 $n$ 可以被因数分解，$d$ 就可以算出，也就意味着私钥被破解。可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基百科这样写道：<blockquote>　　"对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。　　假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。　　只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。"</blockquote><h2>证明</h2>最后，我们来证明，为什么用私钥解密，一定可以正确地得到 $m$ 。也就是证明下面这个式子：$$
c^d ≡ m (mod \; n)
$$因为，根据加密规则$$
ｍ^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)
$$原式得到证明。<h2>代码实现</h2><h3>Python 代码实现</h3><blockquote>Miller_Rabin.py</blockquote><pre><code class="lang-python"># encoding: utf-8

import random

def MillerRabin(num, times):
    if num == 2:
        return True

if num &lt; 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&lt;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__ == &quot;__main__&quot;:
 res = generateLargePrime()
 print (res)</code></pre><blockquote>cryptomath.py</blockquote><pre><code class="lang-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 &amp; 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</code></pre><blockquote>RSA.py</blockquote><pre><code class="lang-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(&quot;public key: &quot;, publicKey)
    print(&quot;private key: &quot;, privateKey)

text = &quot;hello world!&quot;

cipher = encrypt(text, publicKey)
    plain = decrypt(cipher, privateKey)

print (&quot;cipher = &quot;, cipher)
 print (&quot;plain = &quot;, plain)</code></pre><h2>Referrer</h2><a class="no-external-link" href="http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html" target="_blank">http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html</a> <a class="no-external-link" href="http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html" target="_blank">http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html</a>

RSA 算法学习记录

历史

准备

1. 互质关系

2. 欧拉函数

3. 欧拉定理

4. 模反元素

算法流程

1. 生成密钥

2. 加密与解密

算法安全性

证明

代码实现

Python 代码实现

Referrer

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【转】提问的智慧

【枫燃异闻录】利用python爬取Bangumi评分

BUUCTF-web writeup (更新中)

Typecho附件上传大小限制修改

记录一道卡了我好几天的题目

实验二分治法求最近点对问题

实验一排序算法性能分析

主定理 (Master Theorem)

[PHP] eval函数

Hadoop2.4.1安装与配置

RSA 算法学习记录

历史

准备

1. 互质关系

2. 欧拉函数

3. 欧拉定理

4. 模反元素

算法流程

1. 生成密钥

2. 加密与解密

算法安全性

证明

代码实现

Python 代码实现

Referrer

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

RSA 算法学习记录

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款