# Finding prime factors of non-random key generator

I have been working on a challenge i found on the internet. It is as follows:

You've stumbled onto a significant vulnerability in a commonly used cryptographic library. It turns out that the random number generator it uses frequently produces the same primes when it is generating keys.

Exploit this knowledge to factor the (hexadecimal) keys below, and enter your answer as the last six digits of the largest factor you find (in decimal).

Key 1: 1c7bb1ae67670f7e6769b515c174414278e16c27e95b43a789099a1c7d55c717b2f0a0442a7d49503ee09552588ed9bb6eda4af738a02fb31576d78ff72b2499b347e49fef1028182f158182a0ba504902996ea161311fe62b86e6ccb02a9307d932f7fa94cde410619927677f94c571ea39c7f4105fae00415dd7d

Key 2: 2710e45014ed7d2550aac9887cc18b6858b978c2409e86f80bad4b59ebcbd90ed18790fc56f53ffabc0e4a021da2e906072404a8b3c5555f64f279a21ebb60655e4d61f4a18be9ad389d8ff05b994bb4c194d8803537ac6cd9f708e0dd12d1857554e41c9cbef98f61c5751b796e5b37d338f5d9b3ec3202b37a32f

These seem to be common RSA 1024-bit keys.

My approach to the problem was to implement Pollard's rho algorithm to find factors, then once a factor is found, try dividing the decimal form of the keys by that factor until it is not divisible anymore. Iterate.

Now, i used Pollard's rho and tried to divide until the key is not divided anymore because of the information the problem gave: the keys are not completely random.

But here comes the question: assuming the algorithm generates two primes and multiplies them to get a co-prime, which is the key, the low randomness doesn't help much, does it? I mean, even if both keys share a common factor, finding it the first time would take the regular-impractical-exponential time.

That seems to be the case, as my Python algorithm is running for about 5 hours now and has not found any factor to the second key, which i decided to start with.

As it is a challenge, i assume there is a practical way of finding the answer. So what im i doing wrong? Is just the algorithm choice wrong, as Pollard's rho is intended mainly for integer with small factors? Is my assumption that i can only use the lack of randomness after i find the first of the four factor, to then try to break the other key with the same factor, wrong?

I would like if someone could just point me in right direction, instead of just giving the answer. Thank you.

## 1 Answer

So you have two numbers that:

1. both have two prime factors, and
2. you strongly suspect that they share a factor.

So one is $n_{1}=pq_{1}$ the other $n_{2}=pq_{2}$. What is their GCD?

What happens when you apply Euclid' algorithm?

• When a related problem was reported on the internet, a similar question came up: Assume you have a billion such keys, and some of them have common factors. How do you find them without calculating 1 billion x 1 billion GCDs? (Which I read is possible in reasonable time using some clever maths). – gnasher729 Nov 19 '16 at 20:01