7
$\begingroup$

Given two unknown large primes $p$ and $q$, can we efficiently factor $n=pq$ if we additionally know $p \oplus q$ (bitwise XOR of the primes)?

EDIT: I have implemented the algorithm described in poncho's answer in this Python code.

$\endgroup$
0

1 Answer 1

9
$\begingroup$

I believe that we can indeed factor efficiently.

Consider this factoring algorithm; we track the set of $k$ bit values $p_k, q_k$ that satisfy $p_k \times q_k \equiv n \bmod 2^k$; for each iteration, we attempt to extend $p_k, q_k$ by one bit, generating 0-4 possible solutions $p_{k+1}, q_{k+1}$ that satisfy $p_{k+1} \times q_{k+1} \equiv n \bmod 2^{k+1}$.

Now, when we apply this approach to the standard factorization method, it fails miserable; it turns out there will always be 2 solutions at step $k+1$ for every solution at step $k$ (and hence we have an exponential time solution).

However, if we add the additional constraint that $p_k \oplus q_k = m$ (where $m$ is the known value of $p \oplus q$, this drastically reduces the number of intermediate solutions. I believe what will happen is that, when we are at a specific $p_k, q_k$, half the time, there will be 0 solutions for step $k+1$ (and hence we can eliminate that branch of the tree), and half the time, there will be 2 solutions. What this gives us is a fairly slowly growing number of solutions overall as we increase $k$; this makes it totally feasible to get to $k = \log_2{n}$ (and, at which point, we can check the intermediate solutions directly)

$\endgroup$
7
  • 2
    $\begingroup$ Isn't it still exponential though? If you only branch half the time on average, then you square-root the size of the search space as far as I know, so I don't see how it is feasible to get to $k = \log_2 n$. $\endgroup$
    – Thomas
    Jan 7, 2017 at 15:01
  • $\begingroup$ @Thomas: I've done this sort of state scanning attack before in other contexts; for an expected branch factor of 1, the amount of state tends to grow slowly. Think about this way; if the number of possible solutions at step k in $z$, half of those solutions will die (have 0 solutions) at step k+1, and the other half will have 2 solutions, and so at step k+1, you'll still have approximately $z$ solutions. $\endgroup$
    – poncho
    Jan 7, 2017 at 16:07
  • $\begingroup$ I agree with @Thomas, if you write the update equations, you see that there are either 2 or zero solutions, but for sizeable $n$ by chernoff bound you will have 2 solutions at least $(v-\sqrt{v})/2\sim v/2$ times with probability approaching one, where $v=\log_2 n$, so overall number of solutions surviving at the end is $\approx 2^{v/2}=\sqrt{n}$ which is exponential in the bit size $v.$ $\endgroup$
    – kodlu
    Jan 8, 2017 at 0:09
  • $\begingroup$ Ok, I wrote a Python implementation to test this, and it indeed works: Given $pq$ and $p \oplus q$ where $p$ and $q$ are 1024-bit primes, I can factor $pq$. The size of the tracked set seems to generally be in the hundreds-to-thousands range. $\endgroup$ Jan 8, 2017 at 12:28
  • 1
    $\begingroup$ @SamiLiedes: cool; I was about to do that myself; you beat me to it. And, "hundreds to thousands" is consistent with my experience with this sort of algorithm applied to other scenarios with the same branching factors $\endgroup$
    – poncho
    Jan 8, 2017 at 15:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .