2
$\begingroup$

Let's say we have a certain amount of LSB bits of P and Q and we want to fully reconstruct them given N=P*Q. I know this problem was studied in literature by Coppersmith and that Lattice methods are pretty efficient but I would like a numerical / sagemath code example.

If we have for example N=23767*17191=408578497

and we know LSB P=67 LSB Q=91

How can we efficiently reconstruct P and Q without "brute-force", in the smartest way that would works for large N too? (ex. 512 bit,1024 bit,..)

New contributor
gram is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
0

1 Answer 1

3
$\begingroup$

The title of the question is about bits, but the example in the body gives decimal digits. I'll note $b$ for the base we are given digits, and I'll assume $b$ is even and coprime with $N$. I'll note $k$ for the number of digits of $P$ given. Thus in the question $b=10$, $k=2$.

From $N$ and the low-order $k$ digits of $P$, we can find the low-order $k$ digits of $Q$ by computing $P^{-1}N\bmod b^k$. Thus, the only useful hint we are given on top of $N$ is the $k$ low-order digits of $P$. The low-order digits of $Q$ are implied, or just a confirmation. Further, since $b$ is even, our hints are even. Thus by an entropy argument, the hints can make the task of factoring $N$ at most about $b^k/2$ times easier on average. Further, for $b=10$, the low-order digit of a hint can only be in $\{1,3,7,9\}$, thus the speedup can't exceed a factor of $40$ on average.


I'll propose a method that boils down to Fermat factorization aided by the given hint. It will allow factorization with pen and paper for the values in the question. But it's inadequate for large $N$ as used in RSA, including with half of the lower digits of the smallest factor disclosed.

Recall Fermat factorization: if we define the (unknown) $U=(P+Q)/2$ and $V=|P-Q|/2$, then $N=(U+V)(U-V)=U^2-V^2$, and if we find $U$ or $V$ the factorization of $N$ follows. Fermat scans candidates $U$ incrementally starting from $\left\lceil\,\sqrt N\,\right\rceil$, until $W=U^2-N$ is found to be a square. Notice that thanks to the hint we know $P+Q\bmod b^k$, thus $(P+Q)/2\bmod(b^k/2)$, that is $U\bmod(b^k/2)$. This allows to test only one candidate $U$ in $b^k/2$, hence a large speedup.

Here $P+Q\bmod100=58$, thus $U\bmod50=29$. The search for $U$ in standard Fermat factoring starts at $\left\lceil\,\sqrt{408578497}\,\right\rceil=20214$, so the first $U$ we need to consider is $U_0=20229$ (the first value at least $20214$ equal to $29$ modulo $50$). For this, $W_0=U_0^2-N=633944$ (which is not a square). Among various speedups:

  • We compute $\Delta_0=100U_0+50^2=2025400$, and then update $W_i$ and $\Delta_i$ as $W_{i+1}=W_i+\Delta_i$, and $\Delta_{i+1}=\Delta_i+5000$. We don't need to maintain $U$. Thus each $W$ tested requires two additions to produce $W$ and update $\Delta$, then a squareness test.
  • The last decimal digit of a square is never in $\{2,3,7,8\}$, but that's of no help here (contrary to standard Fermat): that optimization overlaps with the stepping of $U$ by $50$.
  • A square reduced modulo the prime $11$ is never in $\{2,6,7,8,10\}$; this allows to eliminate $\frac5{11}$ of the candidates. This generalizes to any prime $p$ not dividing $b$, and allows to eliminate $\frac{p-1}{2p}$ of the candidates. The prime $11$ is especially convenient, because it's easy to reduce modulo $11$ by alternately adding and subtracting the decimal digits starting from low-order, and performing a final reduction. $p=3$ also allows easy computation in decimal (casting out nines followed by final reduction modulo $3$), but eliminates 33% of candidate, versus 45% for $11$. The two combined eliminate next to 70%.

After testing a mere $6$ candidates (instead of $266$ without the hint about the low-order digits of $P$), we find $W_5=10810944$, which is the square of $V=3288$. We find $U=20479$ either as $(\Delta-50^2)/100$ or as $\sqrt{N+W}$, and get the factors as $U+V=23767$ and $U-V=17191$.


This is adequate for the question's $N$. But as $N$ grows, it has cost $\mathcal O(\sqrt N/b^k)$ (for constant ratio $p/q$, and discounting some $\log(N)$ and lower terms). That compares poorly in efficiency with the method in Gabrielle de Micheli and Nadia Heninger's Recovering cryptographic keys from partial information, by example. I won't dive into this, at least right now.


Meat for thought: I wonder if James McKee's improvement of Fermat, or Shank's SQUFOF, could be modified to take advantage of a hint. Since they are $\mathcal O(\sqrt[4]N)$ without hint, it's at least plausible they would be fast in the situation.

$\endgroup$
3
  • $\begingroup$ Thank you @fgrieu for your detailed answer. I really appreciated the speed-up tips as well, I am still studying the prime 11 method. It's curious we can't use information from the other prime number to speed up the calculation. I'm studying the paper you referenced, because without brute-force I was meaning something that could works in semi-real-world RSA scenarios (ex. N=512 or 1024 bits). Thanks again $\endgroup$
    – gram
    Aug 2 at 22:51
  • $\begingroup$ @gram: 11 is special only because there's a simple rule to reduce modulo 11. But any prime not a factor of $b$ is usable. Several can be used together. It's even possible to skip entirely (rather than test) the $\frac{p-1}{2p}$ of candidates a small prime $p$ allows to eliminate, and to do this for several small primes (severely limited by memory). But no mater what, Fermat remains hopeless against semi-real-world RSA scenarios. That's even with half of the bits of one prime available. I was not quite sure about that last point when I started this answer! $\endgroup$
    – fgrieu
    Aug 3 at 6:40
  • $\begingroup$ Thanks again for the reply. The only problem with the Fermat factorization is that the idea is to find a number U between P and Q (the middle) and an offset V that is the distance |U-P| or |U-Q|. It works well when P and Q are close so the search space is small. In our case the center is (23767+17191)/2=20479 and the offset V=3288 so primes are relatively very close and the search process (that try to guess the center) starts from 20214, so very close to the center. I'm having a look at lattice-based methods and they looks promising. $\endgroup$
    – gram
    Aug 3 at 16:38

Your Answer

gram is a new contributor. Be nice, and check out our Code of Conduct.

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.