大致学习下，收集佬们的脚本，帮助理解。
Coppersmith定理指出在一个e阶的mod n多项式f(x)中，如果有一个根小于$n^{\frac{1}{e}}$，就可以运用一个O(log n)的算法求出这些根。
或者，给定$\beta$，快速求出模某个b意义下较小的根，其中，$b \geq n^{\beta} (0 < \beta \leq 1)$。
Coppersmith在RSA中运用的比较多的是已知部分二进制位，通过Coppersmith来求得剩余的位数。遇到其它方面的再补充。
知道p的高位
知道p的高位位p的位数的约$\frac {1}{2}$即可。
#sage
n = ...
e = ...
p4 = ...#p的高位部分
pbits = ...#p的初始位数
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
#经过以上一些函数处理后，n和p已经被转化为10进制
if roots:
p = p4+int(roots[0])
print("n: "+str(n))
print("p: "+str(p))
print("q: "+str(n//p))
知道m的高位
设m的高位部分为$m_{0}$，低位部分为x，故$m = m_{0} + x$
#Sage
n = ...
e = ...
c = ...
mbar = ...#m的高位部分
kbits = ...#低位位数
#有mbar = (m >> kbits) << kbits
beta = 1
nbits = n.nbits()
print("upper {} bits of {} bits is given".format(nbits - kbits, nbits))
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
#c = m^e = (mbar + x)^e
x0 = f.small_roots(X=2^kbits, beta=1)[0]
# find root < 2^kbits with factor = n
print("m:", mbar + x0)
知道d的低位
知道的低位约为n的位数的$\frac{1}{4}(\frac{n.nbits()}{4})$就可以恢复d。
#Sage
def partial_p(p0, kbits, n):
PR.<x> = PolynomialRing(Zmod(n))
nbits = n.nbits()
f = 2^kbits*x + p0
f = f.monic()
roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.4) # find root < 2^(nbits//2-kbits) with factor >= n^0.4
if roots:
x0 = roots[0]
p = gcd(2^kbits*x0 + p0, n)
return ZZ(p)
def find_p(d0, kbits, e, n):
X = var('X')
for k in range(1, e+1):
results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
for x in results:
p0 = ZZ(x[0])
p = partial_p(p0, kbits, n)
if p and p != 1:
return p
if __name__ == '__main__':
n =
e =
c =
d0 =
beta = 0.5
nbits = n.nbits()
kbits = d0.nbits()
print("lower %d bits (of %d bits) is given" % (kbits, nbits))
p = int(find_p(d0, kbits, e, n))
print("found p: %d" % p)
q = n//int(p)
print("d:", inverse_mod(e, (p-1)*(q-1)))
暂时先放这三种比较常用的。
方法解释：small_root(x = ,beta = )。
x表示解根的上限，过大会解不出来，需要调试，看题目环境确定。
beta的取值：当p，q位数相同时，一般只能取0.4。如果p，q位数不同，需要具体分析。
使用条件：未知位数 / 总位数 $\leq$ 0.44。
如当p、q位数为1024是，未知的位数不能超过454位过多，略微超过几位可以爆破出来。
参考：
https://lazzzaro.github.io/2020/05/06/crypto-RSA/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com