RSA浅析

2023-04-16

字数统计: 5.9k | 阅读时长≈ 23 分钟

什么是RSA

简单地说，RSA就是一种非对称加密算法，它组成了今天计算机网络安全的基石。每个人的浏览、消息、支付等背后，都有RSA的身影。虽然其有很多竞争者，但直到如今，RSA依然是主流的非对称加密方式。比如B站的证书就是基于RSA的。

本文旨在让已经对非对称加密有一定了解的朋友了解RSA所使用的算法。如果你不了解非对称加密，本文并不能作为非对称加密的科普，可以去网上搜索看看其他的非对称加密相关的介绍。

RSA中使用到了许多定理与一些为被证明的假设，本文仅使用这些定理与假设，不深究其具体细节与证明。

函数与运算符号

部分函数虽然小学就学过了，但我们可能对它们的名字比较陌生，先看看这些函数的名字。

$gcd(m, n) $：计算m与n的最大公因数。
$lcm(m, n) $：计算m与n的最小公倍数。
$m \mod n$ 或 $m % n$：计算m除n的余数，也称作m模n，前者在数学中出现，后者在计算机程序中出现。
$a ≡ b (\mod c)$： a除c的余数等于b除c的余数，也被称作a与b模c同余。其中恒等号可换为等号。

如何生成一个RSA密钥？

生成两个质数 p 和 q。

p和q应该是随机的，并且差距应该足够大。
计算 $N=pq$
计算 $λ(N)$，$λ(N) = lcm(λ(p),λ(q)) = lcm(φ(p),φ(q)) = lcm(p-1, q-1)$
选择一个数e，使得e与λ(n)互质。这里e是公钥指数。
根据e与λ(n)，计算私钥指数d，满足 $ed \equiv 1\mod N$。

经历过这些步骤，我们得到了RSA加解密所需要的全部信息，将(N, d)作为私钥保存，而(N, e)作为公钥发布，而其中的p、q、λ(n) 均无需保留，可以抛弃。不过在大多数的RSA实现中，p和q都被保留在私钥文件中。

算法演示

我们使用一个较小的数来演示生成RSA密钥的方式。按照上面提到的方法生成一个演示密钥。

选择p=257，q=379.
N = 257 * 379 = 97403.
λ(N) = lcm(256, 378) = 48384.
选择e = 5.
计算得到d = 9677.

可以验证，(5*9677) mod 48384 = 1.

其实这里我想选e=3，发现3居然是48384的因子，遂选择5作为公钥指数。

组装公钥E为(N = 97403, e = 5)，而私钥D为(N = 97403, d = 9677)。

公钥加密

当Bob持有Alice的公钥E时，如果它想给Alice发送一个秘密消息msg，需要先将m转换为一个不大于N的数字m，加密方法为计算 $c = m^e \mod N$，此时c就是密文，可以通过不安全的信道传送给Alice。

假设Bob要发送“hi”，那么可以将“hi”两个字母中的ASCII编码，计算可得“hi” = 104*256+105*1 = 26729，接下来算$26729^5 \mod 97403 = 46004$，此时49388即可发送给Alice。

私钥解密

当Alice接收到Bob的密文c时，Alice可以使用他的私钥解密。解密方法为计算$m = c^d \mod N$。

计算得到 $46004^{9677} \mod 97403 = 26729$，按照拼接ASCII的反向算法就可以得到消息msg为“hi”了。

解决消息过长

上面的例子中，Bob给Alice发送的消息仅有两个ascii字符，如果有三个，那计算得到的结果会超出N，虽然依然可以算，但是解密后的消息就不是原消息M了。比如Bob发送了消息“ack”，编码后为“ack” = 97*256**2+99*256+107 = 6382443. 继续计算密文得到c=6473，而解密后得到m为51248，和原消息不同。

解决方案非常简单：将消息分段，使每段可以满足m<N，再将分段一起发送或保存即可。

而实际应用中，非对称加密常被用于传递对称加密的密钥。RSA密钥中的N往往有2048bits或者更高的值，使用它来传递一个通常只有256bits的对称密钥是无需分段的。

密钥长度

密钥长度就是平时所谓的密钥的位数，比如256位AES就是说AES的密钥长度是256位。而RSA的密钥长度指的就是N的长度，即N有多少比特，或者说是N在二进制下的位数。

比如上文演示用的密钥N为97403，二进制为“10111110001111011”，即该密钥的位数为17位。目前被认为较为安全的是2048位及以上的密钥长度。

安全性

实践中保证RSA的安全性，需要很多细节工作。这里我们只讨论理想条件下，增加密钥长度是如何增加安全性的。从上面算法演示的过程中，我们知道，如果分解了N=p*q，那么相当于破解者也可以从第一步开始算得私钥指数d，此时该密钥对也就被破解了。目前，最行之有效的分解大数的方式是 Pollard rho算法，对于一个合数M，若其因子包括$m_1,m_2,…,m_k$，那么其期望的时间复杂度为$O(\sqrt{min(m_1,m_2,…,m_k)}$，而在实际的分解中，其时间复杂度往往能达到$O(\sqrt[4]{min(m_1,m_2,…,m_k)}$. 对于大数N=p*q 而言，其期望的时间复杂度为$O(\sqrt[2]{min(p,q)}) \leqslant O(\sqrt[4]{N})$。对于2048bits的RSA密钥来说，其消耗时间依然高达$t\cdot 2^{512}$，底线在$t\cdot 2^{256}$上，t为一个常数，所以目前在传统计算领域是安全的。

要注意的是，p与q不能过于接近，否则可以先计算$n = \sqrt{N}$，然后从n开始做减法计算因子。这种分解方法叫做费马因式分解。从上面的时间复杂度分析上我们可以知道，只要保证$|p-q|>\sqrt[4]{N}$即可让费马因式分解的期望时间长于Pollard rho算法。

量子安全性

秀尔算法（Shor’s algorithm）和量子计算机的出现似乎打破了RSA的安全神话。这项技术为因数分解提供了指数级加速，足以在多项式时间内分解N，然而其需要量子计算机有与RSA密钥位数相当的量子比特，而量子比特的增加是非常困难的。目前已知的具有最多量子比特的量子计算机为IBM Eagle（2021年），其拥有127个量子比特。

目前公开的对RSA的最佳量子破解也来自IBM，他们使用量子计算机成功分解了15=5×3.

不能被证明的安全性

事实上，RSA安全性的核心，也就是因数分解的困难性，并没有被证明。该问题是一个NP问题，可以在多项式时间内验证p*q=N，但不能在多项式时间内算出N的两个因子p和q.

P=NP这个问题至今没有答案，但RSA等非对称加密手段都是建立在P!=NP的基础之上的，由于没有人能拿出一个行之有效的破解方式，所以大家相信破解RSA是不可能的. 值得一提的是，一个调查显示，知道NP问题的人中，多数人相信P!=NP.

当然，即使哪天证明了P=NP，如果只有证明而拿不出有效的算法的话，我们或许依然可以焦虑地使用RSA等非对称加密手段.

工程实现

RSA生成的5个步骤中，第2，3，4步都很简单，然而第1步和第5步则需要特殊的算法实现。

本文会提供切实可行的实现方式，要求如下。

Windows 10及以上操作系统，Python >= 3.7，Python无需安装第三方库。

选择Python是因为其原生提供无限长度的整数运算，无需额外关注具体的大整数运算实现，同时具有较好的可读性。

对不了解Python的朋友，我在下方简单的介绍一下下文中使用的功能。

a ** b：计算a的b次方，等于$a^b$.
pow(a, b, m)：计算a的b次方模m，等于$a^b \mod m$.
public_key = N, e：将N和e”打包“进变量public_key中。
N, e = public_key：将N和e从变量”public_key“中解包出来。
for var in range(n)：循环n次，var会从0赋值到n-1，不关心var的值时可以使用 _代替。
random.randint(m, n)：生成从m到n的整数，包括m和n.

Miller-Rabin 算法

演示中使用了两个小质数257和379，这两个数即使是使用纸笔的人类也能验证其并非合数。然而在实际应用中，我们面对的是$10^{308}$这种数量级的质数，仅凭试除法肯定是是不能判断其是否为质数的。此时就需要一个多项式时间的算法来判断该数是否为质数，也就是米勒-拉宾素性检验算法(Miller-Rabin primality test)。

米勒拉宾算法是一种概率性的检验算法，其并不能绝对判断某数是否为质数。但是在合理选择迭代次数的情况下，其错误率是可接受的。下面给出Miller-Rabin算法的Python实现。

def miller_rabin(n, k):
    # n必须为一个奇数
    if n % 2 == 0:
        return "composite"
    s = 0
    m = n - 1
    if m % 2 == 0:
        s += 1
        m //= 2
    d = (n - 1) // (2 ** s)
    # 找到 s > 0, d > 0 且 d 为奇数, 使得 2 ** s * d = n - 1
    # 由于 n 为奇数，所以 s 至少为 1，同时当 s 足够大时总能找到一个奇数 d 满足上面等式
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)  # 快速幂取余，相当于 (a ** d) % n
        # 定理1. 如果 n 是一个质数，对任意整数 x，当且仅当 x = 1或x = -1时，(x ** 2) % n = 1
        # 定理2. 如果 n 是一个质数，对任意整数 a，总有 a ** ((2 ** s) * d) = 1  (mod n)

        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == 1:
                return "composite"
            if x == n - 1:
                break
        if x != n - 1:
            return "composite"
    return "probably prime"

Miller-Rabin 算法给出了一个时间复杂度为$O(k\cdot \log^3n)$的算法，它能有效的检查一个数是否为质数，其中k为循环次数，log来自于快速幂取余的时间复杂度。而其将一个合数误报为质数的概率为$4^{-k}$，因此很容易将在线性时间内以足够高的准确度预测n是否为一个质数。OpenSSL中，k默认为20.

质数分布与大质数生成

一个显而易见的事实是，除了2和3，质数n必然满足 $n = 6k + 1$或$n = 6k-1$，其中k为正整数。

当生成一个n bits的质数时，实际上是在$[2^{n-1}, 2^n)$中找一个整数，验证是否为质数。

由于质数分布规律较为复杂，其生成时间具有较大的不确定性。不过，根据质数定理，对于一个自然数N，其前面的质数大约有 $\frac{N}{\ln N}$个。

那么，如果生成1024bits的质数，我们可以算得在$2^{1023}-2^{1024}$质数的密度如下。
$$
\frac{\frac{2^n}{\ln {(2^n)}}-\frac{2^{n-1}}{\ln (2^{n-1})}}{2^n-2^{n-1}} = \frac{2-\ln 2}{n\ln2} = 1.841 \times 10^{-3} = 543.12^{-1}
$$
可以看到，平均而言，每543.12个数中有一个质数。这个数字不是很大，所以即使暴力搜索也能比较快的搜索到。下面是具体的实现代码。

def gen_prime(n):
    # n为要生成质数的位数
    num = random.randint(2 ** (n - 1), (2 ** n) - 1)
    num = ((num // 6) * 6) + 1  # 6n+1 模式
    # 这里设置为5，速度会快很多，安全性上应该设置为较大的值，比如15以上
    while miller_rabin(num, 5) != "probably prime":
        # 如果不是质数，那就再生成一个
        num += 4  # 6n + 5 模式
        if miller_rabin(num, 5) == "probably prime":
            break
        num += 2  # 6(n+1) + 1 模式
    return num

测试CPU为i7-7700HQ，生成1024bits的质数，测试20次，平均消耗31.14秒。实际平均约10000个奇数遇到一个质数。和上面的计算相差较大，暂未知原因。

扩展欧几里得算法

第五步中，要求计算 de = 1 (mod λ(N)). 即计算e模λ(n)的乘法逆元。

变形这个算式，可以得到 $de = kλ(N) + 1$，其中d, e, k 均为正整数，e为已知数。

当然，可以从k=1开始，一个个计算符合的d，不过有更快的算法，也就是标题提到的扩展欧几里得算法。

扩展欧几里得算法，顾名思义，其由欧几里得算法扩展而来，而欧几里得算法就是辗转相除法。
$$
gcd(a, b) = gcd(b, a \mod b)
$$
而扩展欧几里得算法，则可以求解裴蜀等式（或贝祖等式）
$$
ax+by = gcd(a,b)
$$
求解裴蜀等式就是当 a, b 已知时，求解一对可以使等式成立的x, y.

我们将求解乘法逆元的算式代入，得到下面的式子。
$$
de-λ(N)\cdot k = 1
$$
接下来就可以使用扩展欧几里得算法求解d了。

def ex_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = ex_gcd(b % a, a)
        return gcd, y - (b // a) * x, x

简单地说，ex_gcd返回的第二个值就是要求的私钥指数d.

自己生成一个密钥对

上文中给出了生成一个密钥对所需的全部算法。接下来我们可以自己生成一个可以使用的密钥对了。

def fmt_big_int(name, num):
    max_len = 30
    name += " = "
    indent = len(name)
    num = str(num)
    if len(num) <= max_len:
        return f"{name}{num}"
    num_l = []
    for idx in range(0, len(num), max_len):
        num_l.append(num[idx:idx + max_len])
    return name + " \\\n{}".format(' ' * indent).join(num_l)


def generate_key_pair():
    bits = 1024
    p = gen_prime(bits)
    q = gen_prime(bits)
    N = p * q
    lambda_N = math.lcm(p - 1, q - 1)
    e = 65537  # 通常e会选择65537，这几乎不会和lambda_N有公因数
    gcd_e = math.gcd(e, lambda_N)
    if gcd_e != 1:
        print(f"真不巧e和λ(n)有公因数{gcd_e}")
        return
    _, d, _ = ex_gcd(e, lambda_N)
    if d < 0:  # 可能算出负数来，算出来了就加上，避免私钥指数为负数。
        d += lambda_N

    print(fmt_big_int("N", N))
    print(fmt_big_int("p", p))
    print(fmt_big_int("q", q))
    print(fmt_big_int("e", e))
    print(fmt_big_int("d", d))

下面是我生成的密钥对。

N = 227442712852228682420414779319 \
    562687651643739341662796692929 \
    163922400267934787590621116694 \
    891760619327203004901144906832 \
    800095526049668470542778999323 \
    651897322671119077281968001372 \
    446392959926682893287212273771 \
    241722129942437331580897662308 \
    578666249068303886306662169412 \
    193217352311366461532975812852 \
    124193228404641158708725065274 \
    708644109118939811612576529812 \
    846988041909580026981490541567 \
    445743128463667379869830312310 \
    386152013370124058632684548068 \
    516907871220638110433917758192 \
    056516147025352893608425414982 \
    659378237947057838512573683719 \
    656010305302908753593858876575 \
    962355149895528849120178912224 \
    35170357514424413
p = 145051038077958860693796012628 \
    625876634665931949940050370449 \
    387104965384223153152471552741 \
    833745166885914511061893077670 \
    464028682608703752485689595048 \
    619321249150617970591218334362 \
    527527974241212468108567074763 \
    798879903619803151999405468786 \
    884736416473525334019578812862 \
    866293752484163777592143766285 \
    811404063
q = 156801851173231690833526980220 \
    070443094216022723233530479768 \
    612945390163310468787991953168 \
    708616715527769639602060536294 \
    556776062794179272183786104176 \
    586288917546573301530873029141 \
    344273752018571280068748133198 \
    532396742562461156175632492260 \
    503161905280147990066527029768 \
    573516310751136244023374550179 \
    197384451
e = 65537
d = 190701085970214780948194029687 \
    199134633227390280671539409439 \
    821132122232067634742277345047 \
    596048736317344478986189673473 \
    951588402832434845298468132701 \
    140909072444237503954165458831 \
    132479258250625219130145024089 \
    136405862952788979818580748948 \
    783095204026783321674032778570 \
    883886865579895128877382561243 \
    636791701404807498474376829463 \
    986075399201337437286982733483 \
    883375774171899112093369852188 \
    022751835849225142095728136344 \
    556634868177611264216881972938 \
    769052035843741360883732498917 \
    623652545912814027557437888976 \
    645651446879691031770018258055 \
    933872022471957950567451266956 \
    588963326221579878715175692341 \
    743003401618123

在实践中，不要使用文章里的方式生成密钥，这只是作为演示使用。虽然文章完整的复现了RSA的生成算法，但是很多地方并没有考虑。比如没有检查p和q是否过分相近，Miller-Rabin检查次数过少，没有使用安全的随机数生成器等等，它虽然是一个可用的RSA密钥对，但是并不具有足够的安全性。

尝试使用自制的密钥对进行加解密

现在我们已经具备生成一个RSA密钥对的能力了，可以尝试使用生成的密钥对进行数据的加解密。

注意：这种加解密方式是不安全的，不要在实践中使用这种方式。

def big_int_to_bytes(num):
    out = []
    while num > 0:
        out.append(num % 256)
        num //= 256
    return bytes(out)


def bytes_to_big_int(content: bytes):
    s = 0
    for i, byte in enumerate(content):
        s += byte * (256 ** i)
    return s


def encrypt(public_key, msg: bytes):
    N, e = public_key
    msg = bytes_to_big_int(msg)
    if msg > N:
        raise ValueError("msg过长，无法编码")
    cipher_text = pow(msg, e, N)
    return big_int_to_bytes(cipher_text)


def decrypt(private_key, cipher_text: bytes):
    N, d = private_key
    cipher_text = bytes_to_big_int(cipher_text)
    if cipher_text > N:
        raise ValueError("密文过长，无法解密，可能不是密文。")
    plain_text = pow(cipher_text, d, N)
    return big_int_to_bytes(plain_text)


def test_rsa():
    N = 227442...4413 # 真实数字在上面，这里太长就不放了
    e = 65537
    d = 1907...123
    msg = b"Hello, I'm Bob."
    print("msg = ", msg)
    cipher_text = encrypt((N, e), msg)
    print("cipher_text = ", cipher_text)
    decrypted_text = decrypt((N, d), cipher_text)
    print("decrypted_text = ", decrypted_text)

加密与解密的结果

msg =  b"Hello, I'm Bob."
cipher_text =  b'\x0f\x9b\t...@\xc5\xadc\x97\x9a' 
# 加密的密文比较长，就不全写了，可以自己复制测试
decrypted_text =  b"Hello, I'm Bob."

RSA特性

从上面的算法讲解，可以发现RSA有很多特性。

公钥与私钥的对称性

上文中，我们并没有对公钥指数e做出什么特殊要求，仅仅是看似随机的选取了65537这个数，它并没有成为公钥指数的必然性。而在加密和解密章节中，这种对称性则更加明显，除了变量名和报错信息有区别，它们完全是一样的。

任何与λ(n)互质的数都可以作为公钥e。而解密密钥d则是使用扩展欧几里得算法得到的。回到求解私钥的要求中。
$$
ed ≡ 1 (\mod λ(N))
$$
可以看到公钥与私钥时对称的，当把选取的数字作为私钥指数时，那么计算得到的就是公钥指数了。事实上，RSA三人组最初的论文中，选取的数字就是作为私钥指数，而计算得到的则为公钥指数。

但是，将选取的数字作为公钥具有一定的好处。选择一个很小的数字作为公钥指数，私钥指数就会非常大，这为破解增加了难度。

交换公私钥的安全问题

假如以d作为公钥指数，那么私钥指数e就只有65537了，此时如果知道d和N，就可以对e进行暴力破解。下面是对交换公私钥后成功的暴力破解。

def crack_unsafe_private_key(public_key, cipher_text):
    # 假设 Alice 加密的是以ASCII编码的明文
    N, e = public_key
    cipher_text = bytes_to_big_int(cipher_text)
    for d in range(3, 100000):
        probably_plain_text = pow(cipher_text, d, N)
        probably_plain_text = big_int_to_bytes(probably_plain_text)
        if probably_plain_text.isascii():
            print("破解出明文可能是: ", probably_plain_text, "d = ", d)
            return


def test_crack():
    # 对当前的公钥选择策略而言，交换公私钥后，其不能保证安全
    N = 227442...4413
    e = 65537  # e仅作为展示，此处假设它是隐藏的私钥指数
    d = 190...123 #让算出来的d作为公钥，此时不仅加密速度变慢，而且会不安全
    # 这里反向利用，将计算出来的d作为公钥指数，而e作为私钥指数
    cipher_text = encrypt((N, d), b"Hello, I'm Alice.")
    crack_unsafe_private_key((N, d), cipher_text)

运行结果如下

1	破解出明文可能是: b"Hello, I'm Alice." d = 65537

可以看到，2048bits的密钥很容易就被破解了。所以虽然公私钥具有对称性，但是并不能真的将随便一个数作为私钥指数。使用私钥加密，公钥解密并不能保证秘密消息的安全性。

数字签名

然而私钥加密依然有其用武之地。只有使用私钥加密的信息，其他人才可以使用公钥解密。利用这个特性，Alice可以将其要公布的明文信息与该信息被私钥加密的密文一起公布，这样任何持有Alice公钥的人都可以验证消息来自Alice。Alice的动作叫做签名(Sign)，而验证者Bob的动作叫做验正(Verify)。

def sign_and_verify():
    N = 2274427...413
    e = 65537
    d = 190...123
    msg = b"Hello, I'm Alice"
    cipher_text = encrypt((N, d), msg)
    print("msg = ", msg, "cipher_text = ", cipher_text[:10] + b"...")
    # 验证签名
    decrypted = decrypt((N, e), cipher_text)
    print("decrypted = ", decrypted)
    print("is decrypted == msg :", decrypted == msg)

函数输出如下。

1
2
3

msg =  b"Hello, I'm Alice" cipher_text =  b'\xd0@;2\x995X\x7f\x1e\x94...'
decrypted =  b"Hello, I'm Alice"
is decrypted == msg : True

而如果有人篡改了明文或者篡改了密文，那么解密后的密文与明文会不同，也就验证消息没有来自Alice。

在实际应用中，文件通常很大，通常总会超过密钥能加密的最长长度。而分段虽然可以，但是需要下载两个内容完全一样的文件，消耗一倍的流量。所以实践中，会先对文件求一个加密哈希（如SHA-256），然后对哈希值做加密，这样签名的体积就会小很多。验证者只要解密出哈希后，再对原文件做哈希，比对两个哈希值是否相等即可

明文填充

可以看到，如果我们把RSA明文转换为正整数加密，那么1显然是无法被加密的。为了避免这种情况以及增加安全性，出现了明文填充 (Padding)。Padding 的目的为尽可能提高安全性，以及提供验证消息是否被正确解密的方法。选择一个好的Padding可以增强RSA的安全性。

比如在交换公私钥的安全问题提到的暴力破解中，其实只要解码出任意一个字符是非ASCII字符即可跳过，这提高了破解速度，而一个好的Padding，必须要解码全部消息才能够验证消息是否被正确解密。

不过Padding不在本文的讨论范围内。

实践中使用RSA

这篇文章主要介绍RSA的实现及其算法，不会对如何使用RSA工具做赘述。但本文可以提供一些工具的简单介绍。

下面这些工具很多不止提供基于RSA的非对称加密，也有基于其他算法的非对称加密。

OpenSSL

这是世界上最主流的非对称加密软件，内置在许多操作系统中，Chrome浏览器完成HTTPS使用的也是OpenSSL的一个分支版本BoringSSL。

下面的命令可以在Windows上使用(PowerShell)，应该也适用于Linux及Mac。

# 生成一个1024bits的质数
openssl prime -generate -bits 1024
# 生成一个2048bits(3.1.10 默认)的RSA密钥
openssl genrsa 2048
# 生成一个2048bits rsa密钥，并以人类可理解的方式打印
openssl genrsa 2048 | openssl rsa -text

可以看到第三个命令打印了了 exponent1 和 exponent2，以及coefficient三个本文没有介绍过的值。

这三个值是从私钥计算而来，目的是加快私钥解密速度，并不对RSA算法起实际作用，删去它们不会对算法的正确执行造成任何影响，只是会慢一些。

PGP

PGP原本是一个使用非对称加密的商业应用程序，但随着时间进展，其已经变成了一套标准，被称作OpenPGP，有很多符合该标准的开源软件。

Windows平台有Gpg4win，这是一套软件，可以提供邮件、文件的加密与验证。

Android有OpenKeyChain，也可以较为简单的使用。

在线版本

也有一些网页提供了网页版RSA加解密，比如这个网站就提供了RSA生成与加解密的功能。

版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！