Suppose you randomly generate large primes p and q as in RSA, and then tell me 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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.