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?

  • 2
    $\begingroup$ 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]}$. $\endgroup$
    – fgrieu
    Jan 4 '20 at 16:21

This question looked due to the Cold boot attack, by Halderman et. al. Normally researchers look at some random known bit known due to the decaying of the memory.

The closest article is by Maira et. al.

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$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.