连分数
形如：$a1+\frac{b1}{a2+\frac{b2}{a3+\frac{b3}{a4+…}}}$，$a_{n}$和$b_{n}$可取任意实数、复数。如果项数有限，则可以写成[$a_{1}$,$a_{2}$,$a_{3}$,$a_{4}$,…$a_{n}$]。
举例说明：把$\frac{61}{21}$写成连分数形式：
$2+\frac{1}{1+\frac{1}{9+\frac{1}{2}}}$ = [2,1,9,2]
大致内容
如果满足：d<$\frac{1}{3}n^{\frac{1}{4}}$，那么一种基于连分数(一个数论当中的问题)的特殊攻击类型就可以危害 RSA 的安全。此时需要满足：q<p<2q。
思路
在rsa加密里头，有ed $\equiv $ 1mod$\varphi (n)$，进一步有ed = 1+k*$\varphi (n)$，两边同除以d*$\varphi (n)$，并进行移位得到：
$\frac{e}{\varphi(n)} - \frac{k}{d} = \frac{1}{d\varphi(n)}$
又$\varphi (n)$ = p*q - p - q + 1 = n - (p+q) + 1$\approx$n（因为p、q非常大，n>>(p+q)）
$\frac{e}{\varphi(n)} - \frac{k}{d} = \frac{1}{d\varphi(n)} \approx $$\frac{e}{n} - \frac{k}{d} = \frac{1}{d\varphi(n)}$
$d\varphi(n)$很大，倒数就非常小，故$\frac{e}{n}和\frac{k}{d}$相差很小，$\frac{e}{n}比\frac{k}{d}稍大些$，因为e和n是给出的，故我们可以通过计算，$\frac{e}{n}$的连分数展开，依次算出每一个渐进分数。$\frac{e}{n}比\frac{k}{d}大$，所以$\frac{e}{n}$的渐进分数覆盖了$\frac{k}{d}$。说明$\frac{e}{n}$的渐进分数里有等于$\frac{k}{d}$的分数。
举例说明：假设某个渐进分数$\frac{a}{b}$成立，则k=a，d=b，代回ed = 1+k$\varphi (n)$，就能够解出$\varphi (n)$来（设为y），可以列出一个表达式：n - (p+q) + 1 = y，n是已知的，把(p+q)当整体。所以(p+q)就能解出来，又n = pq也是已知的，通过韦达定理，有方程：$x^{2}$ - (p+q)*x+pq = 0，解方程就得到了p和q。
难点在于用脚本实现求解连分数，借鉴代码(doge)
例题：
n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793
e很大，这是关键特征，解密脚本：
from gmpy2 import *
from Crypto.Util.number import *
# numerator(n):分子, denominator(d)：分母
def t_cf(n, d): # 将分数 x/y 转为连分数的形式
res = []
while d:
res.append(n // d)
n, d = d, n % d
return res
def cf(sub_res): # 得到渐进分数的分母和分子
n, d = 1, 0
for i in sub_res[::-1]: # 从后面往前循环
d, n = n, i * n + d
return d, n
def list_fraction(x, y): # 列出每个渐进分数
res = t_cf(x, y)
res = list(map(cf, (res[0:i] for i in range(1, len(res))))) # 将连分数的结果逐一截取以求渐进分数
return res
def get_pq(a, b, c): # 由p+q和pq的值通过维达定理来求解p和q(解二元一次方程)
par = isqrt(b * b - 4 * a * c) # 由上述可得，开根号一定是整数，因为有解
x1, x2 = (-b + par) // (2 * a), (-b - par) // (2 * a)
return x1, x2
def wienerAttack(e, n):
for (d, k) in list_fraction(e, n): # 用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
if k == 0: # 可能会出现连分数的第一个为0的情况，排除
continue
if (e * d - 1) % k != 0: # ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
continue
phi = (e * d - 1) // k # 这个结果就是 φ(n)
px, qy = get_pq(1, n - phi + 1, n)
if px * qy == n:
p, q = abs(int(px)), abs(int(qy)) # 可能会得到两个负数，负负得正未尝不会出现
d = invert(e, (p - 1) * (q - 1)) # 求ed=1 (mod φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
return d
print("求解d失败")
n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793
d = wienerAttack(e, n)
print(long_to_bytes(pow(c,d,n)))
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com