Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
2  
Very nice question, that stands not fully answered!! An observation: leaking 1 more bit can only help any well-tuned algorithm by a factor of at most 2 (otherwise, we could use that to construct a better algorithm). Therefore, for N of a size making it borderline factorisable (or equivalently, low k), the optimal solution can not be hinting a mediocre algorithm (like any improvement of Fermat factoring). The problem may have different solutions depending on how much N is above the state of the factoring art. –  fgrieu May 7 '13 at 6:16

5 Answers 5

up vote 8 down vote accepted

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$). These attacks work 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).

share|improve this answer
    
Ah I see! Thanks for pointing out that paper. Seems like a very good summary of what you can do with RSA. It appears that $n/4$ (or $k/2$ for $k$ bit $p,q$) is the best bound out there then. –  javic May 6 '13 at 21:04

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
1  
Are you thinking at hinting an Elliptic Curve factoring algorithm? Seems promising, for EC factoring is very near the best factorization algorithm around. Could you elaborate? –  fgrieu May 7 '13 at 6:10
3  
The problem requires that there has to be a PPT algorithm to compute these leaked bits (presumably, given $N,p,q$ as inputs). Do you have a plan for how to do that? –  D.W. May 7 '13 at 6:35
    
You'd have to look at semismoothness probabilities in the vicinity of p and q to see if you could just search. I believe my idea is likely to win because there's the opportunity to do work on the sending side to encode the information and then more work on the receiving side whereas just leaking bits from $p$ requires the receiver to do all the work. If you could allow the primes to be not chosen uniformly at random but at random from a particular distribution which should have no effect on security then coming up with a suitable curve should be easy using complex multiplication. –  Barack Obama May 9 '13 at 1:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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