短文|一元Coppersmith参数详解

简介

Coppersmith ：有一个 $e$ 阶（度）的（首一）多项式 $f$：
● 在模 $n$ 意义下，可快速求出 $n^{1/e}$ 以内的根（e为多项式f的最高次）
● 给定参数 $\beta$，可快速求出模某个 $b$（$b \geq n^\beta$） 意义下较小的根，$b$是 $n$ 的因数，注意这里并不是指小根的范围。

small_roots参数问题（X, beta, epsilon）

$X$:小根的上界，$X=\frac{1}{2} N^{\frac{\beta^{2}}{d}-\epsilon}$，sagemath可自定义上界，理论上小根满足$|x_0|\leq\frac{1}{2}N^{\frac{\beta^2}{\delta}-\epsilon}$
$\beta$:$N$有一个因子$b \geq N^{\beta}$，默认为1
$\epsilon$:默认为$\frac{1}{8} \beta$，越小机会越大，但内部构造的矩阵规模也越大，导致LLL运算时间更长

上述Latex语法转换后

例子

from enc import flag
from Crypto.Util.number import *
import gmpy2
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
c = pow(m,e,n)
leak1 = p>>924
leak2 = p%(2**500)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"leak1 = {leak1}")
print(f"leak2 = {leak2}")

EXP:

p高924位泄露，低500位泄露，还有中间424位未知，构造多项式打中间copper。

# sage
n = 
e = 65537
c = 
leak1 = 
leak2 = 
R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
ph=leak1<<924
f = ph+x*2^500+leak2
r=f.monic().small_roots(X=2^424,beta=0.48)
p = int(f(r[0]))
q = n//p
d = inverse_mod(e,(p-1)*(q-1))
m = power_mod(c,d,n)
print(bytes.fromhex(hex(m)[2:]))