Coppersmith's Theorem - crypto-writeup-public

多項式 $f$ の $\mod N$ 上の小さい根または $\mod p$ 上の小さい根 $x$ を多項式時間で求めるアルゴリズム。つまり $f(x) \equiv 0 \mod N$ または $f(x) \equiv 0 \mod p$ となるような $x$ を求めるということ。Sagemathではsmall_roots というメソッドが生えている。

$\beta, \epsilon$ というパラメータがあり、 $\beta$ は $N$ と多項式 $f$ の剰余の関係。例えば $f \equiv 0 \mod N$ を解くときは $\beta = 1$ だけど、 $f \equiv 0 \mod p$ を解くときは（ $N = pq$ でp, qが同じくらいの大きさなら） $\beta = 0.5$ ということになる

$\epsilon$ は $d = \deg f$ として $|x| < N^{\frac{\beta^2}{d} - \epsilon}$ が成立するように決める。この値が小さいほど大きい行列を内部で使うようになり、実行に時間がかかる。

原理

Coppersmith's methodのお気持ちと実装

応用

特殊な設定下での素因数分解などで利用できる

pの上位bit/下位bitがわかっている時

原理的には $p$ の半分くらいのbit数が判明しているとき、残りのbitを求められる。実践的には6割〜判明していないと安定しない

size = 128
p = random_prime(1 << (size + 1), lbound=1<<(size))
q = random_prime(1 << (size + 1), lbound=1<<(size))
N = p*q;

# qbar is q + [hidden_size_random]
hidden = 80
# diff = ZZ.random_element(0, 2^hidden-1)
# qbar = q + diff
qbar = (q >> hidden) << hidden
# qbar = qbar | (q & ((1 << 64) - 1))

low_size = 24
q_low = q & ((1<<low_size)-1)

PR.<x> = PolynomialRing(Zmod(N), implementation='NTL')
f = qbar + x*2**low_size + q_low
f = f.monic()
set_verbose(2)
r = f.small_roots(X=2**(hidden + 1 - low_size), beta=0.25, epsilon=0.01)

print(r)
print(q, qbar)
print(N)