# How can I take advantage of repeated patterns in non random RSA prime factors?

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?

• What is this question in mathematician's speech? – Hans-Peter 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 – alexandros Aug 30 '13 at 19:02
• @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

"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$"