RSAで一部の値がわかっている時

参考文献

Recovering cryptographic keys from partial information, by example

eが小さく、mの大部分がわかっている時

$m_{pad} = 0x1FFFFFF..0000 + m$

$c = m_{pad}^e \mod N$

のようなとき。

$a = 0x1FFFFFF...0000$ とおいて

$f(x) = (a+x)^e - c$ について

$f(m) \equiv 0 \mod N$ だから、この $f$ のsmall rootsを求めれば良い

pの上位半分がわかっているとき

$p = 2^la + r$ と表して、 $a$ 既知、 $r$ 未知のとき

$f(x) = 2^la + x$ について

$f(r) = p \equiv 0 \mod p$ なので、適当なBound $R = 2^l$ をおいて、small root $r \lt R$ を探す

このsmall rootを探すには

$\begin{pmatrix} R^2 & R2^la & 0 \\ 0 & R & 2^la \\ 0 & 0 & N \end{pmatrix} = \begin{pmatrix}x(2^la + x) \\ 2^la + x \\ N \end{pmatrix}$

をLLLして出る $v = (f_2R^2, f_1R, f_0)$ から $f' = f_2x^2 + f_1x + f_0$ とサイズを小さくした方程式をつくって、これの small rootを探せば良い

どうしてmod pの方程式の解がNを使って求められるんですか？

May先生がそういうcoppersmith's methodの拡張をやってくれたから
上記の行列のそれぞれの行が $x = r$ のときに $\mod p$ で0になるから（多分）

PRIME_SIZE = 512
KNOWN_SIZE = 270

p = random_prime(1<<PRIME_SIZE)
q = random_prime(1<<PRIME_SIZE)
n = p * q

high_p = p >> (PRIME_SIZE - KNOWN_SIZE) << (PRIME_SIZE - KNOWN_SIZE)
PR.<x> = PolynomialRing(Zmod(n))
f = high_p + x

set_verbose(2)
r = f.small_roots(X=2^(PRIME_SIZE - KNOWN_SIZE), beta=0.25, epsilon=0.005)

p_ = int(r[0] + high_p)
assert p == p_

pの下位半分がわかっている時

$p = 2^lr + a$ で $a$ 既知、 $r$ 未知のとき

同様に

$f(x) = 2^lx + a$ として解くだけ

PRIME_SIZE = 512
KNOWN_SIZE = 270

p = random_prime(1<<PRIME_SIZE)
q = random_prime(1<<PRIME_SIZE)
n = p * q

MOD = 1<<KNOWN_SIZE
low_p = p % MOD
PR.<x> = PolynomialRing(Zmod(n))
f = low_p + x*MOD
f = f.monic()

set_verbose(2)
r = f.small_roots(X=2^(PRIME_SIZE - KNOWN_SIZE), beta=0.25, epsilon=0.005)

p_ = int(low_p + r[0]*MOD)
assert p == p_