密码学攻击之RSA:初见

admin 2024年9月28日11:55:37评论14 views字数 5450阅读18分10秒阅读模式

[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的小屋

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2024年9月28日11:55:37
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   密码学攻击之RSA:初见https://cn-sec.com/archives/3093682.html

发表评论

匿名网友 填写信息