前言
第一次认真看英文论文，也是第一次看论文。 这篇是 NSSCTF 中 Crypto 题的出题论文，题目非常简单，但是零解（） 后来在 Destog3 迎新赛的压轴题又看到了几乎一样的题，照着 NSSCTF 的 wp 改了下参数中跑出来了，既然在短时间内能碰见两次，也是缘分，就读读罢。
论文翻译
引言
论文中写到 （这个我没见过），然后 ，再然后由CRT给出 且 。 为了加速 RSA 的解密，有人想用小解密指数 ，然而 Wiener 先生指出 时可以在多项式时间内爆破出来。 虽然不能使用小解密指数 ，但还有一个方法，就是计算 和 是比较小的，这样一个 称为小CRT指数。为了对消息 进行签名，可以计算 和 ，在之前，由于 看起来是比较大的，所以也没法攻击（意思应该就是现在可以了）。 攻破这个系统的最优的算法的时间复杂度在 ，同时有趣的是， 和 不平衡时往往会降低 RSA 的安全性。 令 且 ，当满足 时可以在 复杂度内分解 ，显然，这个方法只能在 时有效。 关键部分来了，这里说到，文章中给出了一种构造任意维度的格的方法来将条件提升到 ，这个 是一个小错误的意思（我也不知道干嘛的）。因此只要 ，这个方法就是有效的，当 时是黄金比例的共轭（这一段我又不知道在干嘛了）。
准备工作
记模 环为 ，整数模 乘法群为
真相1（原文就叫Fact 1，随便翻译意思一下） 令 为一个由 张成的格，那么 -reduction 算法可以在多项式时间内输出一个以 为基的格且这组基满足
用 CRT 生成 Key
一个模 的方法
同余式改写等式过程如下：
下面假设 不整除 ，否则右式是 的倍数然后我们可以获得更强的结果（又是奇怪的翻译），等下再讨论这个。 此时有多项式
且该多项式有一根 构造时我们有 ，又 ，就有
定义两个上界 和 ，则模二元多项式方程 有一个小根 满足 且 ，这个模方程可以用 Howgrave_Grahm 定理转变为一个整数上的方程。
用格约化算法可以找到一个小欧里几得范数的多项式 ，第一个方法是构造一个二维的格，这时高斯约化算法可以找到一个最短向量。 我们选择 ，然后我们使用同样含根 的辅助多项式 ，因为 是 的倍数。 因此， 和 的每个整数线性组合都有根 。 此时构造一个由多项式 和 的系数向量张成的格 。这些系数向量是如下 格基矩阵 的行向量
然后找到一个向量 使其欧里几得范数小于 ，这个向量可以被转换成一个满足真相2的多项式 。
引理3 令 和 满足
则 有一个最小向量 满足 证明 由 Minkowski 定理，…呃先不说这个，能用就行（逃
通过引理3，我们知道，对每个固定的 ，条件 有适当的模量 （这里我感觉不应该是这么翻译，后面再改）。 假定我们通过格约化找到了一个 中的向量 ，其范数小于 ，令 为多项式 的系数向量，应用真相2，我们知道 在整数上有一根 ，下一个定理将表明这个根可以很容易被找到。
证明 略
总结如下结论就有如下定理：
定理5 给定一个 RSA 公钥对 ，令 且
则 可以在时间 内被分解。 证明 还是略（
在之前的分析中，我们假设 不整除 ，特殊情况下若 ( )，我们得到了类似于以下更强结果之前的推理（百度翻译的）
定理6 给定一个RSA公钥对，令且
则 可以在时间 内被分解。 证明 又双叒叕是略（
有趣的是，在定理 6 中选择 会有一个界 ，这与 Wiener 的界差不多。
将界提升到
这里将界提升到 。 上面我们使用真相2的时候选择 ，现在一般化方法到任意 。 定义 移位多项式（这个也是百度翻译）
注意到，每个多项式 的线性组合都有零点 。 确定一个格维数 ，然后用 的系数向量来构造一个 维格 ，其中 ， 。参数 是 的函数且须进行优化。 比如选取 ， ，格 由如下行向量张成
注意到，之前的 和这里的 是一样的。 为了满足真相2，我们一个满足范数小于 系数向量 ，如下引理给出了一个找这样一个向量的条件
引理7 对每个确定的 ，令 ， 满足
然后用 LLL 算法可以在 中找到一个向量 满足范数小于 。 证明 略（
现在我们可以用上面的引理7与真相2结合来构造一个次数为的双变量多项式 ，该多项式最多由 个单项式组成，有一根 ，现在问题来到如何提取根 。 与引理4类似，等下写这
证明 略（
总结这些结论，就有如下定理：
且
其中对于适当大的 （啥叫适当大）， 任意小，则我们可以在 确定的时间多项式内分解 。 证明 略（
一个模 的方法
好像没啥用？？？不写了
方法间的比较
懒得写了（逃
实现
Section3
#!sage
def attack(N, e, beta, delta):
N = int(N)
e = int(e)
if 3*beta+2*delta > 1-log(4, N):
print('[-] Attack failed')
return None
else:
X = int(pow(N, delta))
Y = int(pow(N, (beta+delta)))
Bp = matrix(ZZ, [[N*X, 0], [e*X, -Y]])
print('[+] LLL reduction...')
sv = Bp.LLL()[0]
c = sv*Bp ^ -1
c1 = -abs(c[0]) # k
c2 = abs(c[1]) # q*dp
q = abs((e*c2+c1*N)//(c1+1))
p = N//q
print('[+] Attack successed')
print('[+] p = {}'.format(p))
print('[+] q = {}'.format(q))
return p, q
if __name__ == '__main__':
# from random import *
# qbits = 900
# pbits = 3138
# dpbits = 66
# print('[+] Generating parameters...')
# p = random_prime(2 ^ pbits)
# q = random_prime(2 ^ qbits)
# dp = random_prime(2 ^ dpbits)
# while True:
# d = (p - 1) * (randint(1 << 895, 1 << 905)) + dp
# if GCD(d, (p - 1) * (q - 1)) == 1:
# break
# e = pow(d, -1, (p - 1) * (q - 1))
# N = p * q
# Nbits = int(N).bit_length()
# beta = qbits/Nbits
# delta = dpbits/Nbits
# print('[+] N = {}'.format(N))
# print('[+] e = {}'.format(e))
# print('[+] beta = {}'.format(beta))
# print('[+] delta = {}'.format(delta))
N = 634629908805216799355967956917035397016752766546070169887547308032924761760891699780399214796824214567267154390070522978483366198289411019582748412313710079216359358255867558259121819712947017660972562997658767364245468900343296627500215831311492976020519937654664907394551244233281196085084301881491720946011495516095312100438461444736650645875530160635314476776379821792685906378511085849924665878291761636238890281686290340422138558891124650561389417569572198766305774737557276999432569512459279457704718190818264594575715474945778743504600307881900481338218715405869829242732728780155929040869667117191128487515003629576385308251284254186650906711925117856043812344169291478611645877809590138625462171489233257786403238243625811812424843820945935661305236547254826569192218598933115538295435575896652227458056744204696170806637821332028265957534034435423213071725773547809761130059315592010070432661283749890121832768362711638162670468266766356808625866527581349441814512302739394082651200775637526523353517769267014266507198162521714133402947845712189448974860772495360651769766890958881349140536387282266034095164827944286428551415655867359896643466364963634800962833486281066681776967479689689507887525855059
e = 222449729494346666756992460607761795081627331408633195158207067801306565329147681510898658030387508242070227143765893175513890166451777866451978064721778354202341750518999213529606354327894502393449664534948211789294499720405305147950904692085956769722064799513485397504251091294784655828560748848569365844048162038115977508383792426755701835564072424447439243657439872604411430842404037279822672689499520052597008624952368711035998877339177834448061486065262519442303882787242038252503252910254536179033495248788991658972894666551977962064604651051056420818328840034050064445699641044377207422145434076180424757570241966515333860523020888095363402812210233331161015473008660090443148983742164413532587125663777942637230471840611787651285227528953723973668762432241634488008559578459289516131455221246160389933755148774233018937472092674461794244671504900737970090655485320247064558891268178725955788668940079001559604584196657982775865643371046971752485475409807795707098733502124948500727883742572495725371711913411783312068234668792482799143907403909681456144274826087394298716593721198894233809352032011315411881752188433540351647062223660868815946885574427181940281003433351179379410815810916817304563532735699
beta = 225/1009
delta = 33/2018
attack(N, e, beta, delta)