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.

I am researching vulnerable RSA moduli which are composed of primes generated with poor entropy. Having a list of these primes I searched for variable sized repeated patterns among them and I noticed the following:

DD93536E58A60B0F56BF95FAEDC7CA42A9C9809A0AAE2FC971C3D9963587ABCEAF2BAB479A68DDC9EFF0E98F0F5FD488A9DD08CC51C01E9A3CFE46CA10BF6AB5 DD93536E58A60B0F56BF95FAEDC7CA42A9C9809A2CF5B9957C2E6FD04E817F03D2E174BB79364A0FC0BF365807A1F9E3286A04EB90FBE9DD52B0A2F12222AB51 DD93536E58A60B0F56BF95FAEDC7CA42A9C9809ABB02D6D274A02869AF059E586EED6DC634FCC33C455504DD40FC43D23544AC4E8F2C5E5C64E3E7530C7EDB07 DD93536E58A60B0F56BF95FAEDC7CA42A9C9809ACEF6287DF02847947530B8CA9A125ACCB53EC922D6E9775A3B0169894ED5A46B281C17AF4583874B715B07BB

Four distinct primes have in common their first 160 bits. Apart from being obvious that these primes have been generated by a weak random number generator how can they be used to derive some other primes generated from the same RNG that are potential factors of other moduli?

share|improve this question
    
What is this question in mathematician's speech? –  Hans Stricker Aug 29 '13 at 14:35
    
@Hans Stricker: knowing integer $n$, that $n=p\cdot q$ with $p$ and $q$ unknown primes in range$[2^{1023/2}\dots2^{1024/2}]$, and the integer $\bar p=\lfloor p/2^{512-160}\rfloor$, find $p$. Perhaps it is possible to assume that $\lfloor p/2^{512-320}\rfloor$ falls into a relatively short list of known possible values; that could help tremendously. –  fgrieu Aug 29 '13 at 17:28
    
If the answers to this question are correct, asymptotically, one cannot efficiently factor an RSA modulus $N$ from knowledge of less than $1/4\cdot\log_2(N)$ of extra bits. Sounds like rather bad news for the problem in the question, where the proportion of known bits is $160/1024=5/32\ll1/4$; we need some more bits, or lots of effort. –  fgrieu Aug 30 '13 at 17:54
    
@fgrieu the primes that I present here are non random but valid factors of some existing RSA moduli. The objective is, given those factors, look for repeated patterns and try generate somehow some new factors that can factorise some other moduli. Presumably these factors are generated from a poorly seeded PRNG –  hask Aug 30 '13 at 19:02
1  
@hask: My understanding/assumption is that the only known pattern occurs for the 160 first bits of one prime (likely, the first generated) in a given modulus, and you have nothing exploitable about the remaining bits in the primes. That would be consistent with a RNG based on SHA-1, poorly seeded, and that you have not analyzed beyond that observation. My former remark shows that you need a better analysis of the RNG, or progress towards improving the bound in the answers to the linked question, or a lot of computational power. –  fgrieu Aug 30 '13 at 19:31
add comment

1 Answer

up vote 3 down vote accepted

Theorem 1 of "Implicit Factoring with Shared Most Significant and Middle_Bits" by Jean-Charles Faugère, Raphaël Marinier, Guénaël Renault from 2010 deals with factoring products of two primes where some fraction of the MSBs are common to one of the primes in each of the composites. If I read their bounds correctly, their method must only be useful for quite unbalanced primes.

"Let $N_1=p_1*q_1,N_2=p_2*q_2$ be two n-bit RSA moduli, where the $q_i$s are $\alpha$-bit primes and the $p_i$s are primes that share the $t$-most significant bits, If $t>2*\alpha+3$ then $N_1$ and $N_2$ can be factored in time quadratic in $n$"

share|improve this answer
    
Similar work has been done also by May and Maitre. It should be highlighted, as you correctly said, that the two composites of the moduli have to be unbalanced. –  hask Aug 31 '13 at 14:06
    
In the question, I guess the moduli are 1024-bit and balanced; and we have examples of output of the badly seeded RNG, thus it is not far fetched to say that we know (with non-negligible probability) the top 160 bits in one of the factors of the public modulus to be factorized, something not considered in the paper referenced. Problem is, there are not enough known bits (160 out of 1024; there is no reason to believe that both primes in a modulus are generated from poor seed) for any known attack, and a better analysis of the RNG seems necessary. –  fgrieu Aug 31 '13 at 16:30
add comment

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.