CTFshow供题 unusualrsa系列

other 评论

​

看到CTFshow上新上的easyrsa及funnyrsa系列题，手痒出了5道比较高阶的unusualrsa系列题。

在此仅提供思路以辅助，代码实现由读者自行查找/学习/完成/致用。如有疑问，欢迎留言。

​

unusualrsa1

明文 $m$ 高位泄露，泄露部分位数为 $2044-315=1729$，前部分添加 $208$ 位随机字符做padding以防止直接从 $c$ 还原出部分 $m$ 中的字符。可采用Coppersmith攻击中已知明文高位攻击方法。

  • 算法说明

    假设我们首先加密了消息 $m$，如下

    $C\equiv m^e \bmod N$

    并且我们假设我们知道消息 $m$ 的很大的一部分 $m_0$，即 $m=m_0+x$，但是我们不知道 $x$。那么我们就有可能通过该方法进行恢复消息。这里我们不知道的 $x$ 其实就是多项式的根，需要满足 Coppersmith 的约束。

    当 $e$ 足够小，且部分明文泄露时，可以采用Coppersmith单变量模等式的攻击，如下：

    $c=m^{e}\bmod n=(mbar+x_{0})^{e}\bmod n$，其中 $mbar = (m >> kbits) << kbits$

    当 $\vert x_{0}\vert\leq N^{\frac{1}{e}}$ 时，可以在 $\log N$ 和 $e$ 的多项式时间内求出 $x_0$。

​

unusualrsa2

Related Message Attack

正确理解lambda函数及reduce函数的概念，发现reduce(lambda xxx,[yyy,zzz])实际就是对list参数从头元素至尾元素应用一遍lambda匿名函数的操作，得到最终结果。

第一步，assert函数用于确定x及y两个list的值（解一元二次方程），勿与匿名函数的参数名混淆；

第二步，pow(2*m+3,17,n)及pow(4*m+11,17,n)对应输出结果：

$c_1=(2m+3)^{17} \pmod n \\ c_2=(4m+11)^{17} \pmod n$

第三步，采用Coppersmith’s Short-pad Attack & Related Message Attack（又称Franklin-Reiter攻击），其中此题的 $4m+11$ 可以等价构造为： $4m+11=2\cdot(2m+3)+5$。

  • 算法说明

    目前在大部分消息加密之前都会进行 padding，但是如果 padding 的长度过短（$m \in (0,\lfloor\frac{n.nbits()}{e^2}\rfloor]$），也有可能被很容易地攻击。

    这里所谓 padding 过短，其实就是对应的多项式的根会过小。

    当 Alice 使用同一公钥对两个具有某种线性关系的消息 $M_1$ 与 $M_2$ 进行加密，并将加密后的消息 $C_1$，$C_2$ 发送给了 Bob 时，我们就可能可以获得对应的消息 $M_1$ 与 $M_2$ 。这里我们假设模数为 $N$，两者之间的线性关系如下：

    $M_1 \equiv f(M_2) \bmod N$

    其中 $f$ 为一个线性函数，比如说 $f=ax+b$。

    在具有较小错误概率下的情况下，其复杂度为 $O(e\log^2N)$。

    这一攻击由 Franklin与Reiter 提出。

​

unusualrsa3

多项式RSA，整数RSA的变种，借助Sage工具求解。

  • 定义与原理

    在有限域上选取两个不可约多项式 $g(p),g(q)$，$g(n)=g(p) \cdot g(q)$，计算出 $g(n)$ 的欧拉函数 $\varphi(g(n))=\varphi$，

    选取一个整数 $e$ 作为公钥，$e$ 与 $\varphi$ 是互素的，那么对于明文 $g(m)$，加密过程为 $g(m)^e \equiv g(c) \pmod {g(n)}$，

    计算私钥 $d$ 满足 $ed \equiv 1 \pmod \varphi$，则 $g(c)^d \equiv (g(m)^e)^d \equiv g(m)^{ed} \equiv g(m)^{\varphi+1} \pmod {g(n)}$，

    同样考虑 $g(n)$ 与 $g(m)$ 互素，欧拉定理对于多项式亦成立，

    得到 $g(m)^{\varphi+1} \equiv g(m) \pmod {g(n)}$，所以 $g(c)^d \equiv g(m) \pmod {g(n)}$。

    显然RSA对于整数的体制可以适用于有限域上的多项式。

    注意

    对于素数 $x$，$\varphi(x)=x-1$，但是对于不可约多项式 $g(x)$，$\varphi(g(x))=p^n-1$。（此 $p$ 为 $GF(p)$ 的模，此 $n$ 为多项式最高项次数）

    原因：

    由欧拉函数定义本身，欧拉函数是小于 $n$ 的所有与 $n$ 互质的数的个数。

    多项式的欧拉函数则类似，表示不高于 $g(x)$ 幂级的环内所有多项式中，与 $g(x)$ 无公因式（非1）的其他多项式的个数，所以每一个不高于 $g(x)$ 幂级的环内多项式（除了它自己）均满足此条件。

​

unusualrsa4

Hint1:

ed=1+kφ

  1. 比较e与k比特位数
  2. 联立两式，尝试化简 (inv(q,p)·φ) mod p

Hint2:

  1. 费马小定理
  2. 对于任意 r,k1,k2，当 k2 为 k1 因子时，r mod k2=(r mod k1) mod k2

已知 $e,d,inv(q,p),c$，且 $p,q$ 同比特位数。

令 $cf=q^{-1} \bmod p$，有 $q\cdot cf=1 \pmod p$。

  • $ed=1+k(p-1)(q-1)$，

    比较比特位数，$k$ 与 $e$ 同长，可爆破 $k$，得 $\varphi(n)=(p-1)(q-1)=\cfrac{ed-1}{k}$；

  • 上式 $\varphi(n) =(p-1)(q-1) \pmod p=-(q-1) \pmod p$，

    结合 $q\cdot cf=1 \pmod p$，即 $q\cdot cf-1=0 \pmod p$，

    联立：

    $\begin{eqnarray} \varphi(n)&=&(p-1)(q-1)\\&=&pq-p-q+1\\&=&n-p-q+1 \end{eqnarray}$

    $\begin{eqnarray} cf\cdot \varphi(n)&=&cf\cdot(n-p-q+1)\\&=&cf\cdot n-cf\cdot p-cf\cdot q+cf \end{eqnarray}$

    $\begin{eqnarray} cf\cdot \varphi(n) \bmod p&=&(cf\cdot n-cf\cdot p-cf\cdot q+cf) \bmod p\\&=&0-0-(cf\cdot q)+cf \bmod p\\&=&-1+cf \bmod p \end{eqnarray}$

    有 $1+cf\cdot \varphi(n)-cf=0\pmod p$，

    即$x=1+cf\cdot \varphi(n)-cf$ 能被 $p$ 整除；

  • 由费马小定理，存在 $r$ 满足 $r^{p-1}=1 \pmod p$，

    $\begin{eqnarray}r^{\varphi(n)}&=&(r^{(p-1)})^{(q-1)}\\&=&1^{(q-1)} \pmod p\\&=&1 \pmod p \end{eqnarray}$，

    因对于任意 $r,k_1,k_2$，当 $k_2$ 为 $k_1$ 因子时，$r \bmod k_2=(r \bmod k_1) \bmod k_2$，

    故 $r^{\varphi(n)} \bmod p=(r^{\varphi(n)} \bmod x) \bmod p=1 \bmod p=kp$，

    已知 $\varphi(n)$，由 $(r^{\varphi(n)} \bmod x) \bmod p=kp$ 可得到多组 $p$ 的乘积，计算 $\gcd$ 可得到 $p$；

  • 由 $q\cdot cf=1 \pmod p$ 求模逆可得 $q$，再用 $c$ 计算出 $m$。

​

unusualrsa5

有限域 n-th root

发现 $\gcd(e,\varphi) =e$ 且 $e\mid (p-1),e\mid (q-1)$。

解题思路即求解 $m \bmod p$ 和 $m \bmod q$ ，再通过CRT还原 $m \bmod n$。

这里 $e$ 与 $p-1$ 和 $q-1$ 都不互素，不能简单地求个逆元就完事，主要难点则是在有限域 $GF(p)$ 上求 $e$ 次根。

在有限域上求r-th root有两个常见算法：Adleman-Manders-Miller algorithm (AMM) 和Cipolla-Lehmer algorithm (CL)，这里采用AMM算法（paper）。

这个算法只能开出一个根，实际上开 $e$ 次方，最多会有 $e$ 个根（这题的情况下有0x1337个根）。

如何找到其他根？

StackOverflow – Cube root modulo P 给出了方法。

如何找到所有的primitive n-th root of 1?

StackExchange – Finding the n-th root of unity in a finite field 给出了方法。

以 e=0x1337​ 为例：

  • 先用Adleman-Manders-Miller rth Root Extraction Method在 $GF(p)$ 和 $GF(q)$ 上对 $c$ 开 $e$ 次方根，分别得到一个解。大概不到10秒。
  • 然后去找到所有的0x1336个primitive nth root of 1，乘以上面那个解，得到所有的0x1337个解。大概1分钟。
  • 再用CRT对 $GF(p)$ 和 $GF(q)$ 上的两组0x1337个解组合成 $\bmod n$ 下的解，可以得到0x1337**2=24196561个 $\bmod n$ 的解。最后能通过check()的即为flag。大概十几分钟。

此题可根据上述算法或利用Sage自带函数实现计算。