# RSA: If the least significant bits of the factors are leaked, what advantage is there in factoring N?

For $$N=pq$$, if the first $$x$$ least significant bits of both $$p$$ and $$q$$ are leaked.

• what is the advantage in factoring $$N$$?

• Does this give an advantage beyond simply lowering the number of bits we have to guess for the smaller factor?

• Note: the "both $p$ and $q$" part of the question is pointless: when the low-order $x$ bits $p_{[x]}$ of $p$ leak, we can find the low-order $x$ bits $q_{[x]}$ of $q$ as ${p_{[x]}}^{-1}N\bmod2^x=q_{[x]}$.
– fgrieu
Jan 4 '20 at 16:21

if $$\delta = .57$$ fraction of the bits of $$p$$ and $$q$$ is randomly is given they can construct them.
Theorem 1: Let $$N = pq$$, when $$p, q$$ are primes of same bit size. Let $$S = \{0,\ldots, l_{N /4}\}$$. Consider $$U \subseteq S$$ and $$V = S \backslash U$$. Assume that p[i]’s for $$i \in U$$ and $$q[j]$$’s for $$j \in V$$ are known. Then one can factor $$N$$ in $$poly(\log N)$$-time.
• $$l_N$$ the bit size of $$N$$, i.e, $$l_N = \lceil log_2 N\rceil$$.