RSA 的分析

使用连分数展开进行攻击

连分数

对于一个数 $\alpha$ 的展开，形如：

$$\alpha =c_0+\frac{1}{c_1+\frac{1}{c_2+\frac{1}{c_3+\cdots }}}$$

可以简记为：

$$[c_0;c_1,c_2,c_3,\dots ]$$

如何计算：

$$\begin{array}{rlr}{c}_0& =\lfloor \alpha \rfloor & {\epsilon }_0=\alpha -c_0\\ c_1& =\lfloor \frac{1}{{\epsilon }_0}\rfloor & {\epsilon }_1=\frac{1}{{\epsilon }_0}-c_1\\ c_2& =\lfloor \frac{1}{{\epsilon }_1}\rfloor & {\epsilon }_2=\frac{1}{{\epsilon }_1}-c_2\\ & ⋮& \end{array}$$

n-th convergent: (n次渐进分数)

对于 $\alpha =[c_0;c_1,c_2,\dots ]$，其 n-th convergent 定义为：

$$\frac{a_n}{b_n}=[c_0;c_1,c_2,\dots ,c_n]$$

计算如下：

$$\begin{array}{rl}\frac{a_0}{b_0}& =\frac{c_0}{1}\\ \frac{a_1}{b_1}& =\frac{c_0{c}_1+1}{c_1}\\ \cdots \\ \frac{a_n}{b_n}& =\frac{c_n{a}_{n-1}+a_{n-2}}{c_n{b}_{n-1}+b_{n-2}}(n\ge 2)\end{array}$$

e.g.

α = 45/89

$$\begin{array}{rl}\alpha & =\frac{45}{89},\\ c_0& =\lfloor \alpha \rfloor =\lfloor \frac{45}{89}\rfloor =0,& {\epsilon }_0& =\alpha -c_0=\frac{45}{89},\\ c_1& =\lfloor \frac{1}{{\epsilon }_0}\rfloor =\lfloor \frac{89}{45}\rfloor =1,& {\epsilon }_1& =\frac{1}{{\epsilon }_0}-c_1=\frac{89}{45}-1=\frac{44}{45},\\ c_2& =\lfloor \frac{1}{{\epsilon }_1}\rfloor =\lfloor \frac{45}{44}\rfloor =1,& {\epsilon }_2& =\frac{1}{{\epsilon }_1}-c_2=\frac{45}{44}-1=\frac{1}{44},\\ c_3& =\lfloor \frac{1}{{\epsilon }_2}\rfloor =\lfloor \frac{44}{1}\rfloor =44,& {\epsilon }_3& =\frac{1}{{\epsilon }_2}-c_3=\frac{44}{1}-44=0.\end{array}$$

因此连分数表示为：

$$\frac{45}{89}=[0;1,1,44]=0+\frac{1}{1+\frac{1}{1+\frac{1}{44}}}.$$

计算收敛分数：

$$\begin{array}{rl}\frac{a_0}{b_0}& =\frac{c_0}{1}=0,\\ \frac{a_1}{b_1}& =\frac{c_0{c}_1+1}{c_1}=\frac{1}{1}=1,\\ \frac{a_2}{b_2}& =\frac{c_2{a}_1+a_0}{c_2{b}_1+b_0}=\frac{1\cdot 1+0}{1\cdot 1+1}=\frac{1}{2},\\ \frac{a_3}{b_3}& =\frac{c_3{a}_2+a_1}{c_3{b}_2+b_1}=\frac{44\cdot 1+1}{44\cdot 2+1}=\frac{45}{89}.\end{array}$$

Lemma

如果 $|\alpha -\frac{a}{b}|<\frac{1}{2b^2}$,那么 $\frac{a}{b}$ 是 $\alpha$ 的某个收敛分数。

Wiener’s attack on RSA

如果满足：

• $p<q<2p$
• $e<(p-1)(q-1)$
• $d<\frac{1}{3}{n}^{\frac{1}{4}}$

则存在：

• $ed=1+k\varphi (N)$
• $\varphi (N)=N-(p+q)+1$
• $e<\varphi (N),k<d$
• 考虑：

$$\begin{array}{rl}\frac{e}{N}-\frac{k}{d}& =\frac{ed-kN}{dN}\\ & =\frac{1+k\varphi (N)-kN}{dN}\\ & =\frac{1-k(p+q-1)}{dN}\\ & <\frac{p+q-1}{N},\because k<d\\ & <\frac{3\sqrt{N}}{N}=\frac{3}{\sqrt{N}},\because q<2p\\ & <\frac{1}{3d^2},\because d<\frac{1}{3}{N}^{\frac{1}{4}}\\ & <\frac{1}{2d^2}\\ \text{QED}\end{array}$$

Code

Sage

from sage.all import *

n = 9449868410449
e = 6792605526025

test_message = 123456
enc_test_message = pow(test_message, e, n)

def weiner_atk(e,n):
    continued_fraction_expansion = continued_fraction(e/n)
    convergents = continued_fraction_expansion.convergents()
    print(convergents)

    for iter in convergents:
        k,d = iter.as_integer_ratio()
        if k == 0:
            continue
        if (e*d - 1) % k != 0:
            continue
        phi_n = (e*d - 1) // k
        s = n - phi_n + 1
        discriminant = s*s - 4*n
        if discriminant >= 0:
            t = isqrt(discriminant)
            if t*t == discriminant:
                dec_test_message = pow(enc_test_message, d, n)
                # print(dec_test_message)
                if dec_test_message == test_message:
                    return d
    return None

d = weiner_atk(e, n)
print(f"Found d: {d}")

[0, 1, 2/3, 3/4, 5/7, 18/25, 23/32, 409/569, 1659/2308, 2068/2877, 3727/5185, 76608/106577, 156943/218339, 1175209/1634950, 8383406/11662989, 34708833/48286906, 77801072/108236801]
123456
Found d: 569

Coppersmith

直觉

假设: $c=m^{e}modN,m=m_0+x_0$, 如果 $x_0$ 表示信息的低位，已知信息的高位 $m_0$，有方程如下:

$$f(x)=c-(m_0+x{)}^{e}modN$$

故而，当 $x_0$ 很小时，我们可以求解这个多项式来得到明文，特别是在 $e$ 也很小时。

同时，对于持有私钥，既拥有 $N$ 的分解， $p$, $q$ 时，求解 $f(x)$ 时更加容易的。但是对于攻击者来说这是不可能的。

但是我们可以通过一些转换，使得：

$$f(x)=0modN\to g(x)=0$$

既然 $f(x)$ 在模 $N$ 意义下有一个小根 $x_0$，那么我们可以构造一个整数多项式 $g(x)$，使得 $g(x)$ 在整数意义下也有一个小根 $x_0$，并且在 $\mathbb{Z}$ 上求解 $g(x)$ 是非常容易的。（牛顿法求根）

e.g.

• 令 $N=17\times 19=323$，并令$$f(x)=x^2+33x+215.$$
• 寻找满足 $f(x)\equiv 0(\mathrm{mod}N)$ 的解。
• $x_0=3$ 是一个解，但在整数域 $\mathbb{Z}$ 上有 $f(3)\ne 0$。
• 定义$$g(x)=9f(x)-N(x+6)=9x^2-26x-3.$$
• 若 $f(x_0)\equiv 0(\mathrm{mod}N)\Rightarrow g(x_0)\equiv 0(\mathrm{mod}N)\Rightarrow g(x_0)=0\text{ over }\mathbb{Z}$。
• $g(x)$ 的系数较小且满足 $g(3)=0$，其根可在实数域 $\mathbb{R}$ 上用牛顿法求出。

通过 格 找出多项式 gx

Coppersmith's method 的核心思想是通过构造一组多项式，并利用 LLL 算法 找出一个新的多项式 $g(x)$，使得 $g(x)$ 在整数域 $\mathbb{Z}$ 上有一个小根 $x_0$，从而可以通过牛顿法求出该根。

构造方法略

e.g.

令 $M=10001$ 并考虑多项式 (这里的$M$ 等同于模数 $N$)

$$F(x)=x^3+10x^2+5000x-222.$$

可以验证 $F(x)$ 是不可约的，并且 $F(x)$ 在模 $M$ 下有一个小解 $x_0=4$。注意 $|x_0|<M^{1/6}$，因此可以预期能够找到 $x_0$。假设 $X=10$ 是给定的 $x_0$ 大小的界限。考虑基矩阵

$$B=\left(\begin{array}{cccc}M& 0& 0& 0\\ 0& MX& 0& 0\\ 0& 0& M{X}^2& 0\\ -222& 5000X& 10X^2& X^3\end{array}\right).$$

对此矩阵运行 LLL 算法得到一个约化基，其第一行为

$$(444,10,-2000,-2000).$$

该向量对应的多项式为

$$G(x)=444+x-20x^2-2x^3.$$

在 $G(x)$ 上运行牛顿求根法得到解 $x_0=4$。