[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,我们只需要一行代码即可完成计算
1
|
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 语言)
1234 |
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$,下面我们给出一个例子。
第一颗🌰:
1234567891011121314151617 |
import gmpy2from Crypto.Util import numberFLAG = "************************************"mybytes = FLAG.encode('utf-8')flag = int.from_bytes(mybytes, 'little')e = 65537p = number.getPrime(2048)q = number.getPrime(2048)r = 663111019425944540514080507309phi = (p-1)*(q-1)d = gmpy2.invert(e, phi)k = (p-r)*denc = 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,核心代码也只需要一行
1
|
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 代码实现
123456789101112131415 |
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 代码实现
123456 |
def exgcd(a, b):if (b == 0):return 1, 0, ax, y, g = exgcd(b, a % b)x, y = y, x - a // b * yreturn x, y, g |
另外,也可以直接调包
1
|
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,也可以邮件至 [email protected] - source:Van1sh的小屋
- 左青龙
- 微信扫一扫
- 右白虎
- 微信扫一扫
评论