RSA leak bits to factor N

Question

Suppose you randomly generate large primes p and q as in RSA, and then tell me N=pq but not p or q.

Then, you would like to actually let me factor N, except you should tell me as few bits of information as possible. Say p and q are 4096 bits, then how many bits do you need to tell me in order for me to factor N in feasible amount of time?

Note that you can arbitrarily design how these bits are derived, as long as there is a PPT algorithm to compute these bits and there is a PPT algorithm to use these bits to factor N.

Answer 1

I don't believe a lower bound has ever been proven for the "fewest" number of bits needed. Coppersmith showed, however, how given either the $n/4$ least or $n/4$ most significant bits of $p$ where $n$ is the size of the modulus $N=pq$, $N$ can be efficiently factored. Additionally, given the $n/4$ least significant bits of $d$, one can reconstruct $d$ (and therefore factor $N$), if $e<\sqrt{N}$. See Boneh's 20 year survey of attacks on RSA. See that paper and the reference within for the algorithms, etc.

Since then, the bounds for $e$ have been update somewhat, but still requires leaking the same number of bits. Also, random subsets of bits are sufficient to factor where $(1-\frac{H_r}{r})\log{N}$ bits of $p$ are known ($H_r$ is the r-th harmonic number).

Answer 2

Late reply but hope it helps.

You could also see this paper: "A Coding-Theoretic Approach to Recovering Noisy RSA Keys" by Kenneth G. Paterson and Antigoni Polychroniadou and Dale L. Sibborn.

They provide many attack, however answer that they give is that the bound is more or less the same as Coppermith's logN/4 bits. The nice thing is that the bound remains even for the case of random bits. A nice thing about the algorithm is that you can retrieve the correct factorization even if sometimes you are given the wrong bit value (allows error correction). However, it can go even lower.

Answer 3

I imagine that it would be most efficient to leak bits of an appropriate sigma which describes an elliptic curve of smooth order which would lead to a factorization after a tolerable amount of work

Answer 4

If you want to deliberately leak information, so that specific entities can factor N, but it is generally secure, because this is what I can understand from your next post the you have to look into SETUPs (Secretly Embedded Trapdoor with Universal Protection). The original work is from Young & Yung see this: http://dl.acm.org/citation.cfm?id=706030

Answer 5

This is a very interesting question from a number-theoretic and computer scientific point-of-view.

However if you were thinking about practical ways one could 'backdoor' a system and have the backdoor transmit as little information back to the implanter, so as to allow factorization, there might be another way to look at it though. You could generate p,q using a PRNG seeded with, say, 256-bits. Then you could leak the 256-bits or some subset thereof. Or you could avoid leaking at all: Having generated the entropy of seeding the PRNG, you could replace some of the bits (say all except for 64 bits) with a hardcoded value or something that could be inferred in an attack scenario (derived from user-id, hardware serial numbers etc). Run that through a hash (probably not necessary if the PRNG is secure) and use that as the seed for the PRNG for generating p,q. Then you would be able to brute-force your way to p,q using only 2^64 operations even though the system seemingly has a much higher level of security. If this was embedded in hardware (i.e. a hardware RNG) where the hardcoded value could not be extracted, you would have this advantage to yourself - for everyone else it truly would require 2^256 operations.

Discovering the backdoor by others, would be possible by essentially 'brute-forcing' the RNG, exhausting the subspace it maps into and notice that you get duplicates more often than expected. You could try circumventions against that. So the attack works best if you have a much higher capacity for brute-force than is available to those who would audit the system.