连分式RSA攻击(Wiener攻击)

Question

我在网上发现了一篇关于RSA攻击的文章。

所列数字如下：

• $n =205320043521075746592613美元
• $e = 70760135995620281241019$
• $\frac{e}{n}=$

该方法指出，如果$d

在这些方法的示例中，它们采用$\frac{k}{d}=$。

他们说在5911之前停止连续分数，因为这是一个很大的数字。谁能解释一下为什么吗？

Answer 1

设$n=pq$是RSA模。设$e$也是公共指数，$d = e^{-1} \bmod (p-1)(q-1)$是匹配的私有指数。

从\frac{k}{d}\Bigl(\frac1{q}+\frac1{p}-\frac1{n}\Bigr) 1 pmod{(p-1)(q-1)}$存在一些整数$k$，使得$$ed =1+ k(p-1)(q-1) =1+ k(n-p-q+1) \当且仅当kn-ed=k(p+q-1)-1美元除以$dn$收益率$$\frac{k}{d}{n}{n}=$dn$-\ by 1{dn}$$。

此外，我们还有以下定理。

定理如果$|\frac{a}{b}-x| <\frac1 1{2b^2}$，则$\frac{a}{b}$是$x$的连续分数逼近。

因此，如果满足先前定理的条件，则$k/d$是$e/n$的连续逼近。由于$e/n$是公共的，并且连分式可以很容易地计算，所以可以找到秘密指数$d$ (同样，只要满足定理的条件)。

特别地，假设$p \sim q \sqrt{n}$和$e \sim n$，则该定理满足阶为$n^{1/4}$的私有指数$d$的条件。

证据。首先，我们注意到如果$e \sim n$那么$k \sim d$。此外，我们还有$$\Bigl|\frac{k}{d}-\frac{e}\Bigr\ \le -\frac \sim \frac1 1+\frac1 1{n} \sim \frac1 1{\sqrt{n}}$$。

因此，$|\frac{k}{d}-\frac{e}{n}\<\frac1 1{2d^2}$如果$d$最多为$n^{1/4}$。

回到您的示例，$e/n$的持续分数开发是$$。因此，$e/n$的逐次收敛剂是$$\frac{0}{1}、\frac{1}{2}、\frac{1}{3}、\frac{10}{29}、\frac{61}{177}、\frac{3304}{9587}、\frac{19530005}{56668934}、\frac{19530005}{56668934}、\frac{61}{177}。

只要满足Wiener攻击的条件(即$d$ of order至$n^{1/4}$)，我们就知道$k/d$是其中之一。实际上，您可以检查$d = 9587$是对应的私有指数。

在这个例子中，我们还有$n^{1/4} \约674144$和$56668934 \gg 674144$。