N =e =c =m =ZmodN = Zmod(N)P. = PolynomialRing(ZmodN)f = (m + x)^e - cx0 = f.small_roots(X=2^kbits, beta=1)[0]# 这里的X选取不像上文用的是临界值 ， 而是选了一个我们未知的x的最大可能值 。 X的选取并非严格 ， 但至少得保证比临界值小 。 print("m:", m + x0)BTW ， 这里泄露的是明文的高位 ， 其实还有泄露低位、泄露高低位的情况 。 但换汤不换药 ， 无非是由m+x变成了 m_high +x * 2^k + m_low 。
第二关：Factoring with high bits known已知n,e,c ， n=pq且已知p的高位
[+]Generating challenge 2[+]n=0x5fe2743ec99568d645943147498849643932486590fb101f41c93ad7247161bc035d75dfb9e4b25209e26913098ecc1b7c4a92a47fb28452465d8b94e31844c4624da870140a48a28a0e6a3c6d9731b8488a63fd8ab9f5fe1ae86513c7444bb0aa39d44416b9cfa83c370f50c7a5a148a36823f0ddeed66ecf99117378c0640fL[+]e=65537[+]m=random.getrandbits(512)[+]c=pow(m,e,n)=0x2639582bf7b22fd52a7a519673574e1212b675c9c10763ffcbcf5a86b61f07c4ea536e48dfbd4f3201cb2e18f2a0946959223b3f32bd5b3166d6cdd185ad946e543504dcc42ac9a24c03343bc8e4379997c722b12c66acaed6ad64d35f2fbcc8f4d899c1081d4211987841d1be082801a07014de89050b71e584827020934755L[+]((p>>128)<<128)=0xe4f16417011e6cc5ced2aad00d5865a0530f37c078dd22d942d0d0811c7053d973b621c4768a2a87a6d233be10db8e1a00000000000000000000000000000000L[-]long_to_bytes(m).encode('hex')=这一关我们需要引入一个新的定理
Theorem 3
这里我就不再给出令人头大的证明了 。 直接给出一个例子 ， 但是显然 ， 由于条件的改变 ， 这个格子的构造也会与之前的格子不同 。
example 4设N=16803551 ， p’=2830，X=10
我们设F(x)=(x+p’) ， 并且考虑多项式：N, F(x) ， xF(x)=(x^2 + p’x) ， x^2F(x) 。 然后构造格
LLL规约后得到第一行的SVP为（105 ， -1200 ， 800 ， 1000） ， 去除X可以得到
G(x) = x^3 + 8x^2 – 120*x + 105；解方程可以得到x = 7 ， 检查一下确实 2387|N
【这里的N也许显得突兀 ， 把它看作是k * p也许会好理解些：所选取的多项式带入正解x时均在模p下与0同余 。 】
除了这样构造格子 ， 通过查阅网上关于这道题的题解可以发现另一种格子的构造 。 我们这里是“x-shift”了三次 ， 另外那种是先提升次数 ， 然后再“x-shift” ， 具体用了这八个多项式：
格子的样式：
之所以这么选也是这里新引入了两个参数 ， 一个是beta ， 一个是t ， beta是未知p与已知N指数关系 ， 这里就是0.4 ， 因为p ≈ N^0.4 ， 【其实可以是0.5 ， 但我们并不确定p, q的大小关系 ， 保险起见用0.4】t的具体取值与beta相关 ， 另外这里的h的取值也与beta有关 ， X的取值也与上面的定理所述不同 。
exp
# 展示格的样式def matrix_overview(B, bound):for ii in range(B.dimensions()[0]):a = ('%02d ' % ii)for jj in range(B.dimensions()[1]):a += '0' if B[ii,jj] == 0 else 'X'a += ' 'if B[ii, ii] >= bound:a += '~'print (a)def coppersmith(pol, modulus, beta, h, t, X):# 计算矩阵维度n = d * h + t# 将多项式转到整数环上polZ = pol.change_ring(ZZ)x = polZ.parent().gen()# 构造上文所述lattice ， polZ(x * X) 就是环上的多项式f(X * x) ， 所以这里与上文不同的点就在于引入了变量x ， 但变量x在后面的矩阵构造中会被抹掉 。g = []for i in range(h):for j in range(d):g.append((x * X)**j * modulus**(h - i) * polZ(x * X)**i)for i in range(t):g.append((x * X)**i * polZ(x * X)**h)# 构造格BB = Matrix(ZZ, n)for i in range(n):for j in range(i+1):B[i, j] = g[i][j]# 展示格的样式matrix_overview(B, modulus^h)# LLLB = B.LLL()# 将最短向量转化为多项式 ， 并且去除相应的Xnew_pol = 0for i in range(n):new_pol += x**i * B[0, i] / X**i# 解方程potential_roots = new_pol.roots()# 检查根roots = []for root in potential_roots:if root[0].is_integer():result = polZ(ZZ(root[0]))if gcd(modulus, result) >= modulus^beta:print("p: ",(gcd(modulus, result)))roots.append(ZZ(root[0]))return rootsN = ZmodN = Zmod(N)P.