RSA指南

基本的RSA算法和一些攻击方法 ## RSA算法原理

1. 随机选择两个素数 \(p\) 和 \(q\) 并且计算 \(n=pq\) 。

2. 根据欧拉函数，求得 \(\varphi (n)=\varphi(p)\varphi (q)=(p-1)(q-1)\)

3. 设 $ e $ ，使得 \(\gcd \big( e, \varphi(n) \big) = 1\) 并且 \(e < \varphi(n)\)。

4. 计算 $ d $ 的值，使得 \(de \equiv 1 \pmod{\varphi(n)}\) 。

5. 我们的公钥是一对 \((n, e)\) 并且我们的私钥是三部分 \((p,q,d)\) 。

6. 对于任何非零整数 \(m < n\) ，用 \(c \equiv m^e \pmod{n}\) 进行加密。

7. 用 \(m \equiv c^d \pmod{n}\) 进行解密。

• 正确性证明
• Sagemath官方文档

根据解密公式有： \[ \begin{aligned}m & \equiv c^d \\& \equiv\left(m^e\right)^d \\& \equiv m^{e d} \pmod n\end{aligned} \]

即我们要证 \(m^{ed} \equiv m \pmod{n}\) ，已知 \(e*d \equiv 1 \bmod{\varphi(n)}\) ，那么 \(ed=k\varphi(n)+1\) ，即需要证明 \[ m^{k\varphi(n)+1} \equiv m \bmod n \] 这里我们分两种情况证明 第一种情况 \(gcd(m,n)=1\) ，也就是说 \(m\) 和 \(n\) 是互素的则： \[ \begin{aligned}m^{e d} & \equiv m^{k\varphi(n)+1} \quad(\bmod n) \\& \equiv m^{k\varphi(n)} * m \quad(\bmod n) \\& \equiv m \quad(\bmod n)\end{aligned} \] 根据欧拉定理，因为 \(gcd(m,n)=1\) 所以有：\((m^{\varphi(n)})^{k} \equiv 1 \pmod{n}\)

第二种情况 \(gcd(m, n) \neq 1\) , 因为 \(n=pq\), 所以 \(gcd(m, n)\) 必含有 \(p\) 和 \(q\) 之一, 设 \(gcd(m, n)=p\), 有 \(m=s * p\) : 我们先推导这样的一个式子: \[ \begin{aligned} m^{\varphi(q)} & \equiv 1 \quad(\bmod q) \\ m^{k * \varphi(q)} & \equiv 1 \quad(\bmod q) \\ m^{k * \varphi(q) * \varphi(q)} & \equiv 1^{\varphi(q)} \equiv 1 \quad(\bmod q) \\ m^{k * \varphi(q) * \varphi(q)} & =1+t * q \end{aligned} \]

再进行推导 \[ \begin{aligned} m^{e d} & \equiv m^{k \varphi(n)+1} \quad(\bmod n) \\ & \equiv m^{k \varphi(n)} * m \quad(\bmod n) \\ & \equiv(1+t * q) * m \quad(\bmod n) \\ & \equiv m+t * q * s * p \quad(\bmod n) \\ & \equiv m \quad(\bmod n) \end{aligned} \]

常规RSA出题脚本：

加密RSA

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
flag = 'flag{this_is_flag}'
def get_key(bit):
    while 1:
        p = getPrime(bit)
        q = getPrime(bit)
        assert p > 0
        assert q > 0
        assert p != q
        assert p.bit_length() == bit
        assert q.bit_length() == bit
        assert isPrime(p)
        assert isPrime(q)
        n = p * q
        e = getPrime(16)
        assert p % e != 1
        assert q % e != 1
        d = int(pow(e,-1 ,(p-1)*(q-1)))
        assert GCD(d,n) == 1
        print(f'p={p}\nq={q}\nn={n}\ne={e}')
        return n,e,d,p,q
n,e,d,p,q = get_key(512)
m = int.from_bytes(flag.encode(), 'big')
assert m < n
c = pow(m,e,n)
print(f'c={c}')
try:
    key = RSA.construct([n,e,d,p,q])
    print("This is not a bad RSA keypair.")
except KeyboardInterrupt:
    print("Hacker detected.")

可以用 Crypto.PublicKey.RSA 里的函数 construct 来判断获取的值是否正确

测试RSA

from Crypto.PublicKey import RSA
n,e,d,p,q = get_key(512)
try:
    key = RSA.construct([n,e,d,p,q])
    print("This is not a bad RSA keypair.")
except KeyboardInterrupt:
    print("Hacker detected.")

常规解题脚本：

解密RSA

p =  
q =  
e =  
c =  
n = p*q
phi = (p-1)*(q-1)
d = int(pow(e,-1,phi))
m = pow(c,d,n)
print(m)
print((bytes.fromhex(hex(m)[2:])).decode('utf-8'))

生成公钥和私钥

\(M_m = 2^m - 1\) 形式的正整数称为梅森数。 如果 \(p\) 是素数且 \(M_p = 2^p - 1\) 也是素数，则 \(M_p\) 称为梅森素数。 可以使用命令 is_prime(p) 进行验证。

测试

sage: p = (2^31) - 1
sage: is_prime(p)
True
sage: q = (2^61) - 1
sage: is_prime(q)
True
sage: n = p * q ; n
4951760154835678088235319297

对于步骤 2，我们需要找到一个与 \(\varphi(n)\) 互质的正整数。 整数集在 Sage 模块 sage.rings.integer_ring 中实现。 可以通过 ZZ.* 系列函数访问对整数的各种操作。 例如，命令 ZZ.random_element(n) 返回一个在闭区间 \([0, n-1]\) 内均匀分布的伪随机整数。 我们可以通过调用 sage 函数 euler_phi(n) 来计算值 \(\varphi(n)\) ，但对于任意大的素数 \(p\) 和 \(q\) ，这可能需要大量时间。 事实上，一旦知道 \(\varphi(n)\) 就可以很快地从公钥中推导出私钥，因此 \(\varphi(n)\) 无法在短时间内计算出来，这是 RSA 密码系统安全性的重要组成部分，如果只是 \(n\) 是已知的。 另一方面，如果私钥可用，我们可以在很短的时间内计算出 \(\varphi(n)=(p-1)(q-1)\) 。

测试

sage: p = (2^31) - 1
sage: q = (2^61) - 1
sage: n = p * q
sage: phi = (p - 1)*(q - 1); phi
sage: e = ZZ.random_element(phi)
sage: while gcd(e, phi) != 1:
....:    e = ZZ.random_element(phi)
...
sage: e  # random
1850567623300615966303954877
sage: e < n
True

由于 e 是伪随机整数，因此每次执行 e = ZZ.random_element(phi) 后其数值都会发生变化。 为了计算 RSA 算法步骤 3 中的 d 值，我们使用扩展欧几里得算法。 根据同余的定义， \(de \equiv 1 \pmod{\varphi(n)}\) 等价于 \[ de - k \cdot \varphi(n) = 1 \]

其中 \(k \in Z\) 。 从步骤 1 和步骤 2 中，我们已经知道 \(e\) 和 \(\varphi(n)\) 的数值。 扩展欧几里得算法允许我们计算 \(d\) 和 \(-k\) 。 在 Sage 中，这可以通过命令 xgcd 来完成。 给定两个整数 \(x\) 和 \(y\) ， xgcd(x, y) 返回满足 Bézout 恒等式 \(g = \gcd(x,y) = sx + ty\) 的 3 元组 (g, s, t) 。 计算出 \(d\) 的值后，我们使用命令 mod(d*e, phi) 来检查 d*e 是否确实与 1 模 \(\varphi(n)\) 一致。

测试

sage: n = 4951760154835678088235319297
sage: e = 1850567623300615966303954877
sage: phi = 4951760152529835076874141700
sage: bezout = xgcd(e, phi); bezout  
(1, 4460824882019967172592779313, -1667095708515377925087033035)
sage: d = Integer(mod(bezout[1], phi)) ; d  # random
4460824882019967172592779313
sage: mod(d * e, phi)
1

因此，我们的 RSA 公钥是 \[ (n, e) = (4951760154835678088235319297,\, 1850567623300615966303954877) \]

而我们对应的私钥是

\[ (p, q, d) = (2147483647,\, 2305843009213693951,\, 4460824882019967172592779313) \]

加密和解密

假设我们要使用 RSA 加密对消息 HELLOWORLD 进行加扰。 从上面的 ASCII 表中，我们的消息映射到 ASCII 编码的整数，如下所示。

测试

+----------------------------------------+
| H   E   L   L   O   W   O   R   L   D  |
| 72  69  76  76  79  87  79  82  76  68 |
+----------------------------------------+

连接最后一个表中的所有整数 ，我们的消息可以用整数表示 \[ m = 72697676798779827668 \] 还有其他更加密安全的方法可以将我们的消息表示为整数。 上述过程仅用于演示目的，我们强烈建议不要在实践中使用它。 在 Sage 中，我们可以获得消息的整数表示形式，如下所示：

测试

sage: m = "HELLOWORLD"
sage: m = [ord(x) for x in m]; m
[72, 69, 76, 76, 79, 87, 79, 82, 76, 68]
sage: m = ZZ(list(reversed(m)), 100) ; m
72697676798779827668

为了加密我们的消息，我们计算 \(m\) 的 \(e\) 次方并以 \(n\) 为模减少结果。 命令 mod(a^b, n) 首先计算 a^b，然后对结果取模 \(n\) 进行减少。 如果指数 b 是一个“大”整数，比如超过 20 位数字，那么以这种简单的方式执行模幂运算需要相当长的时间。 强力（或简单）模幂运算效率低下，并且在使用计算机执行时会快速消耗大量计算机内存或导致消息溢出。 有一个技巧可以有效地执行模幂运算，称为重复平方方法，参见。 [CormenEtAl2001] 第 879 页。 假设我们要计算 \(a^b \mod n\) 。 首先，令 \(d \mathrel{\mathop:}= 1\) 并获得 \(b\) 的二进制表示，例如 \((b_1, b_2, \dots, b_k)\) ，其中每个 \(b_i \in Z/2Z\) 。 对于 \(i \mathrel{\mathop:}= 1, \dots, k\) ，设 \(d \mathrel{\mathop:}= d^2 \mod n\) ，如果 \(b_i = 1\) 则设 \(d \mathrel{\mathop:}= da \mod n\) 。 该算法在函数 power_mod 中实现。 我们现在使用函数 power_mod 来加密我们的消息：

测试

sage: m = 72697676798779827668
sage: e = 1850567623300615966303954877
sage: n = 4951760154835678088235319297
sage: c = power_mod(m, e, n); c
630913632577520058415521090

因此 \(c = 630913632577520058415521090\) 是密文。 为了恢复我们的明文，我们计算 \(c\) 的 \(d\) 次方并以 \(n\) 为模减少结果。 同样，我们在解密过程中通过重复平方来使用模幂：

测试

sage: m = 72697676798779827668
sage: c = 630913632577520058415521090
sage: e = 1850567623300615966303954877
sage: n = 4951760154835678088235319297
sage: power_mod(c, d, n)
72697676798779827668
sage: power_mod(c, d, n) == m
True

请注意，在最后一个输出中，值 72697676798779827668 与表示原始消息的整数相同。 因此我们已经恢复了明文。

针对模数 \(n\) 的攻击

1.直接分解模数 \(n\)

• factordb.com

• sagemath里面的函数 divisors(n) ，factor(n)

• cado-nfs: https://github.com/sethtroisi/cado-nfs

• yafu 分解，下载链接: https://sourceforge.net/projects/yafu/

使用 cmd 进入到 yafu所在目录下，或将目录加入到系统环境 PATH变量，或打开目录文件夹后 shift+右键 选择在此处打开powershell。 假如要分解因数 6，输入命令：.\yafu-x64.exe "factor(6)"。

如果因数过长，将 因数 用文本文件存放在 yafu目录下，例如：data.txt。文件最后一行一定要换行，否则eof; done processingbatchfile。

运行命令：.\yafu-x64.exe "factor(@)" -batchfile data.txt

2.\(\lvert p-q\rvert\) 较小

费马分解 我们首先计算这样一个式子

\[ \frac{(p+q)^2}{4}-n=\frac{(p+q)^2}{4}-pq=\frac{(p+q)^2}{4}-\frac{4pq}{4}=\frac{(p-q)^2}{4} \]

既然 \(\lvert p-q \rvert\) 较小，那么 \(\frac{(p-q)^2}{4}\) 也较小，所以我们有 \(\frac{(p+q)^2}{4}\) 只是比 \(n\) 稍微大一点 ，所以 \(\frac{p+q}{2}\) 与 \(\sqrt{n}\) 相近。那么我们可以按照如下方法来分解

farmat

import gmpy2
def factor(n):
    a = gmpy2.iroot(n, 2)[0]
    while 1:
        B2 = pow(a, 2) - n
        if gmpy2.is_square(B2):
            b = gmpy2.iroot(B2, 2)[0]
            p = a + b
            q = a - b
            return p, q
        a += 1  # 千万别忘了a的自增步长为1

p,q=factor(n)