关于微信公众号

[TOC]

在了解了一些基础的抽象代数基础知识以及数论四大定理后，我们就能完成一些基础的 RSA 题目了，也能够通过公式推导去理解攻击手法背后的数学原理。

RSA 基础加解密

设有明文 $m$、公钥 $e$、私钥 $d$、密文 $c$、模数 $n=p \cdot q$，其中 $p,q$ 为两个大素数（大于512比特）

RSA 的加密公式为 $c \equiv m^e \pmod n$

RSA 的解密公式为 $d \equiv c^d \pmod n$

其中 $e,d$ 满足 $e \cdot d \equiv 1 \pmod {\varphi(n)}$ ，$\varphi(n)$ 表示为 $n$ 的欧拉函数，决定式为
$$
\varphi(n) = n \cdot \prod (1-\frac{1}{p_i})
$$
其中 $p_i$ 是 $n$ 的各个素因子（如果素因子重复也只计算一次）。这里由于 $n = p \cdot q$，因此 $\varphi(n) = n \cdot (1 - \frac{1}{p})(1-\frac{1}{q}) = (n-q)(1-\frac{1}{q})=n-p-q+1=(p-1)(q-1)$

另外根据欧拉函数的性质， $\varphi(n) = \varphi(p) \cdot \varphi(q)$，而 $p,q$ 而素数，因此 $\varphi(p)=p-1,\varphi(q) = q-1$ ，也能够得到 $\varphi(n) = (p-1)\cdot (q-1)$

关于解密公式的正确性验证需要用到欧拉定理，具体过程这里就不再赘述了，我们在上一篇《密码学基础之数论四大定理》中已经介绍过了。另外在其中我们还介绍了 RSA-CRT 签名算法，因此如果相关参数 $d_p,d_q$ 泄露，其造成的影响也不小于私钥 $d$ 泄露。

私钥 $d_p,d_q$ 泄露

根据 RSA-CRT 签名算法流程，如果我们已知 $d_p,d_q,p,q$，

我们可以先计算 $m_p \equiv c^{d_p} \pmod p;m_q \equiv c^{d_q} \pmod q$，

最后使用中国剩余定理即可计算得到 $m% n$。

使用 sagemath，我们只需要一行代码即可完成计算

m = crt([mp,mq],[p,q])

不过又要泄露 $d_p,d_q$，还得知道 $n$ 的分解 $p,q$，这个攻击的利用条件也过于严苛了。

问题不大， 我们有稍微普适一点的攻击手法。已知公钥对 $(e,n)$，只需要再加上一个 $d_p$ 或者 $d_q$ 就足够了。

已知 $e\cdot d \equiv 1 \pmod {\varphi(n)}$

所以有 $e\cdot d \equiv 1 \pmod{\varphi(p)}$

又因为 $d \equiv d_p \pmod{\varphi(p)}$

于是有 $e \cdot d_p \equiv 1 \pmod {\varphi(p)}$，化作等式则有 $e \cdot d_p = 1 + k \varphi(p)$

那么根据费马小定理，对于任意整数 $0 \lt a \lt p$ ，有 $a^{e\cdot d_p} = a^{1+k\varphi(p)} \equiv a \pmod p$

再将上面的同余式化成等式，就有 $a^{e\cdot d_p} -a = kp$

然后我们对 $kp$ 和 $n=pq$ 求一个最大公约数即可获得素数 $p$，从而分解了 $n$，也就能够完成任意由该模数生成的密文的解密了。

欧几里得算法

在上述攻击中我们构造出了 $kp$ ，然后和 $n$ 求最大公约数以分解出 $p$。那么如何求最大公约数呢？我们使用欧几里得算法（天呐，我们在用两千多年前的算法）。

设有两个整数 $a、b(a \ge b,a\neq 0,b \neq 0)$， $x$ 为 $a,b$ 的最大公约数，我们证明 $x | (a % b)$ （$\mid$ 为整除符号）

令 $r = a % b$

则有 $a = kb + r$

由于 $x \mid a,x \mid b$

因此 $x \mid r$

于是 $x = gcd(a,b) = gcd(b,a % b) = gcd(b,r)$

当 $ r = 0$ 时，我们定义 $gcd(x,0)=x$

于是我们构建欧几里得算法（使用 python 语言）

def gcd(a,b):
    while b != 0:
        a,b = b, a % b
    return a

欧几里得算法的时间复杂度非常低，只有 $\mathcal{O}(log\ n)$，是比线性复杂度还低的对数复杂度，因此即使 $n$ 和 $kp$ 很大，我们也能够在极短的时间内计算出他们的最大公约数 $p$。（不得不感叹一下两千年前古人的智慧）

RSA 额外相关参数

这种类型是简单 RSA 题目中出现比较多的，比较偏“数学题”。除了给出的基本 RSA 参数 $e,n,c$ 之外的额外参数就是我们需要关注的点。一般涉及到公式的推导，利用已知信息构造式子求出一个 $p$ （或者 $q$ ）的倍数 $kp$ （或者 $kq$） ，然后和 $n$ 求一个 GCD 以分解 $n$，下面我们给出一个例子。

第一颗🌰：

import gmpy2
from Crypto.Util import number
FLAG = "************************************"
mybytes = FLAG.encode('utf-8')
flag = int.from_bytes(mybytes, 'little')
e = 65537
p = number.getPrime(2048)
q = number.getPrime(2048)
r = 663111019425944540514080507309
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
k = (p-r)*d
enc = gmpy2.powmod(flag, e, p * q)
print("n", p*q)
print("e", e)
print("k", k)
print("enc", enc)

看到题目，除了常规参数 $e,n,c$ 外，我们还额外知道一个 $k = (p-r) \cdot d$，其中 $r$ 已知， $p,d$ 未知

由于 $e \cdot d \equiv 1 \pmod{\varphi(n)}$

即有 $e \cdot d \equiv 1 \pmod{\varphi(p)}$

这里我们并不知道 $d$ 或者 $d_p$，但是有 $k = (p-r) \cdot d$

于是 $e \cdot k = e \cdot d \cdot(p-r) \equiv p-r \pmod{\varphi(p)}$

我们考虑使用费马小定理，设一个整数 $a$ 满足 $1 \lt a \lt p$，

于是 $a^{ek} \cdot a^r \equiv a^{p-r+r} \equiv a^p \equiv a\pmod p $

因此有 $a^{ek+r} -a = kp$，和 $n$ 求一个 GCD 就能得到 $p$ 了。

使用 python，核心代码也只需要一行

p = gcd(pow(a,e*k+r,n)-a,n)

已知 $e\cdot d$，分解 $n$

如果我们知道额外参数 $e \cdot d$ 的值，我们也能够利用 GCD 来分解模数 $n$。

首先我们计算 $k=e\cdot d−1$。根据 $d$ 和 $e$ 的定义我们知道 $k$ 是 $\varphi(n)$ 的倍数。

由于 $\varphi(n)$ 是偶数，因此$k$ 可以表示为 $ k=2^tr $ 其中 $r$ 为奇数且 $t \ge 1$。

根据费马小定理，对于每个 $g\in \mathbb{Z}_n$ 都有 $g^k \equiv 1 \pmod n$，于是 $g^{\frac{k}{2}}$ 就是模 $n$ 下的一个二次根。

我们知道理论上一个数的二次根有两个，一正一负，而根据前面的知识（引理 3），我们有 $g^k \equiv 1 \pmod p,g^k \equiv 1 \pmod q$，所以开根后 $g^{\frac{k}{2}}$ 在模 $p$ 下和模 $q$ 下的子群中各有两个解（是分别在模 $p$ 和 模 $q$ 下的 $\pm1$）

然后我们使用中国剩余定理，于是表现出 1 在模 $n$ 下有四个平方根。其中两个平方根是 $±1$，另外两个是$±x$，其中 $x$ 满足 $x\equiv 1 \pmod p$ 和 $x\equiv −1 \pmod q$ （或者反一下）。

于是我们计算 $g^{\frac{k}{2^i}}$ ，当发现其值不为 $\pm 1 \pmod n$ 时，就可以通过计算 $gcd(x−1,n)$ 或者 $gcd(x+1,n)$ 将 $n$ 分解。

一个直截了当的论证表明，如果从$\mathbb{Z}_n$中随机选择 $g$，那么序列中的一个元素 $g^{\frac{k}{2}}，g^{\frac{k}{4}},\cdots ,g^{\frac{k}{2^t}} \pmod n$ 中是 $x$ 的概率至少为$\frac{1}{2}$，即随机选取一个 $g$ 就能分解 $n$ 的概率很高。（如果运气不好都没分解出来，那就再换一个 $g$）

python 代码实现

from Crypto.Util.number import *

def factor_n_with_ed(n,e,d):  
    p = 1  
    q = 1  
    while p==1 and q==1:  
        k = e * d - 1  
        g = getRandomRange(0,n)  
        while p==1 and q==1 and k % 2 == 0:  
            k //= 2  
            y = pow(g,k,n)  
            if y!=1 and GCD(y-1,n)>1:  
                p = GCD(y-1,n)  
                q = n//p  
                return p,q

前面我们提到了欧几里得算法，那就不得不再提一下欧几里得拓展算法了。

欧几里得拓展算法

设有整数 $a,b,x$，其中 $x = gcd(a,b)$，那么必然存在整数 $u,v$ 满足 $au + bv = x$，而使用欧几里得拓展算法就能够求出这样的 $u,v$

第二颗🌰：

设 $a=7,b=11$，我们知道 $x = gcd(a,b) = gcd(7,11)=1$，我们跟踪一下使用欧几里得算法求它们最大公约数的流程

$11 = 7 \cdot 1 + 4$

$7 = 4 \cdot 1 +3$

$4 = 3 \cdot 1 + 1$

$3 = 1 \cdot 3 + 0$

于是有 $gcd(a,b)=1$

现在我们反一下，$1 = 4 - 3\cdot 1$

将 $3$ 替换一下有，$1 = 4 - (7 - 4 \cdot 1)\cdot 1$， 整理一下 $1 = 4 \cdot 2 - 7 \cdot 1$

再将 $4$ 替换一下有， $1 = (11-7\cdot 1) \cdot 2 - 7 \cdot 1$， 整理一下 $1 = 11 \cdot 2 - 7 \cdot 3$

于是我们计算出来 $u=-3,v=2$

欧几里得拓展算法的 python 代码实现

def exgcd(a, b):
	if (b == 0):
		return 1, 0, a
	x, y, g = exgcd(b, a % b)
	x, y = y, x - a // b * y
	return x, y, g

另外，也可以直接调包

from gmpy2 import gcdext

那么，欧几里得拓展算法有啥用呢？

共模攻击

如果手中恰好有这么两条密文

$c_1 \equiv m^{e_1} \pmod n$

$c_2 \equiv m^{e_2} \pmod n$

并且运气不错，$gcd(e_1,e_2)=1$，那么我们就能够通过欧几里得拓展算法计算出 $u,v$ 满足 $u\cdot e_1 + v\cdot e_2 = 1$

这样我们再计算 $c_1^u \cdot c_2^v \equiv m^{u\cdot e_1+v\cdot e_2 } \equiv m ^1 \pmod n $，于是在不知道 $n$ 分解的情况下我们利用两条密文就成功解密出了明文 $m$ 。

但是这样的场景也不现实，因为加密使用的公钥是消息接收者，怎么会有两个接受者的公钥有一样的模数呢？

更现实的场景是消息发送者使用所有消息接受者的不同公钥对 $(e_i,n_i)$ 加密同一消息 $m$ 得到不同的密文 $c_i$ 并广播（也许会再给每一条密文加一个身份id表示）。消息接收者选择属于自己的那条密文，解密获得消息。

广播攻击

如果攻击者在信道中收集到了多条广播的密文

$c_1 \equiv m^{e_1} \pmod{n_1}$

$c_2 \equiv m^{e_2} \pmod{n_2}$

$c_3 \equiv m^{e_3} \pmod {n_3}$

$\vdots$

一般来说加密者喜欢选取的公钥指数是 $3,17,65537$ 这三个数（由于是 $2^i+1$ 的素数，加密计算效率高）。假设公钥指数都是是 $3$，那么我们搜集了 $3$ 条密文后，就可以通过中国剩余定理计算 crt([c1,c2,c3],[n1,n2,n3]) 得到 $m^3 \pmod{n_1\cdot n_2 \cdot n_3}$ ，由于加密时要求 $m\lt n$，所以得到的就是 $m^3$，我们直接对其开 $3$ 次根即可得到消息 $m$。

同理如果公钥是 $17$，那就搜集 $17$ 条，如果是 $65537$，则需要 $65537$ 条。 具体需要的条数为 $\lceil e \cdot \frac{m.bitlen}{n.bitlen}\rceil $，其中 $.bitlen$ 表示数据的比特长度。因此如果 $m$ 在加密前未经过数据填充的话，则可以少搜集一些。

例如我们有 $2048$ 比特的 $n$，$m$ 为 $400$ 比特的消息，公钥 $e$ 为 $65537$，那么需要的密文数为 $\lceil 65537 \cdot \frac{400}{2048}\rceil = 12801$ 条。

同理，如果 $e=3$，而 $m$ 的比特长度小于 $n$ 比特长度的 $1/3$，那么我们就只需要一条密文 $c$ ，直接对其开 $3$ 次根即可。

可以看到，RSA 的各类攻击真离不开欧拉定理、费马小定理和中国剩余定理。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com