1
$\begingroup$

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.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
2
$\begingroup$

In such terms, I suppose you should to find GCD of two numbers Key1 and Key2. It seems that with big probability it will give to you one of the prime number which was generated by compromised generator. Pollard`s method is very hard, and I doubt, that you can successfully apply it in the case.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ This. You've apparently been given two keys $k_0$, $k_1$, and told that $k_0 = pq$ and $k_1 = pq'$ where $p$, $q$, and $q'$ are prime. Find $GCD(k_0, k_1) = p$. $\endgroup$
    – Stephen Touset
    Commented Mar 5, 2014 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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