Sometimes We Need More Random

Computer Science Level 3

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

The answer is 616467.

5 solutions

Discussions for this problem are now closed

Aleksejs Popovs
Feb 9, 2014

Let's call the given keys $a$ and $b$ . Let's assume each key is a product of two primes (like it is in RSA), so $a = pq$ and $b = rs$ . Since we know the generator is flawed, both keys probably share at least one prime factor, so let's say $s = q$ , then $a = pq$ and $b = qr$ . If $p$ and $r$ are distinct primes, this means $gcd(a, b) = q$ .

We can easily calculate the GCD of a and b using Euclid's algorithm ( $a, b ← b, a \mod{b}$ until $b = 0$ , then $a$ is the GCD), and the answer is $847\dots616467$ . So we've only got to choose the biggest number between $q$ , $p$ and $r$ . $q = 847\dots616467$ , $r = \frac{a}{q} = 343\dots734127$ , $l = \frac{b}{q} = 461\dots616437$ . $q$ turns out to be the biggest number of them all, so $\boxed{61647}$ it is.

Zi Song Yeoh
Feb 8, 2014

Python code :

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

x =         int('1c7bb1ae67670f7e6769b515c174414278e16c27e95b43a789099a1c7d55c717b2f0a0442a7d49503ee09552588ed9bb6eda4af738a02fb31576d78ff72b2499b347e49fef1028182f158182a0ba504902996ea161311fe62b86e6ccb02a9307d932f7fa94cde410619927677f94c571ea39c7f4105fae00415dd7d', 16)
y = int('2710e45014ed7d2550aac9887cc18b6858b978c2409e86f80bad4b59ebcbd90ed18790fc56f53ffabc0e4a021da2e906072404a8b3c5555f64f279a21ebb60655e4d61f4a18be9ad389d8ff05b994bb4c194d8803537ac6cd9f708e0dd12d1857554e41c9cbef98f61c5751b796e5b37d338f5d9b3ec3202b37a32f', 16)
print (gcd(x, y))

which prints $84712455329458472210475092572678509526272708993404574231933262963274962364443789510742328496333782156398316832447160740326193165821341070265858616467$ . Thus, the answer is $\boxed{616467}$ .

Your solution is not quite complete: although the answer is right, you don't check the possibility that the largest factor (which is what you're asked to find) might not be the common one, but one of the others. This can be fixed by assigning gcd(x, y) to a variable, for example, g, and then printing max(g, x // g, y // g).

Aleksejs Popovs - 7 years, 4 months ago

Yes and no. You're right that it says "largest factor" not "largest common factor". But if you don't assume that "largest common factor" was meant, then wouldn't Key 2 itself be the "largest factor"?

Peter Byers - 7 years, 4 months ago

people, plz scroll towards right to see the full answer... and as the question says,
last 6 digits is the final answer.

Anand Narayan - 7 years, 4 months ago

Tanmay Meher
May 9, 2014

The solution using a built-in library

from fractions import gcd

k1 = int("1c7bb1ae67670f7e6769b515c174414278e16c27e95b43a789099a1c7d55c717b2f0a0442a7d49503ee09552588ed9bb6eda4af738a02fb31576d78ff72b2499b347e49fef1028182f158182a0ba504902996ea161311fe62b86e6ccb02a9307d932f7fa94cde410619927677f94c571ea39c7f4105fae00415dd7d",16)

k2 = int("2710e45014ed7d2550aac9887cc18b6858b978c2409e86f80bad4b59ebcbd90ed18790fc56f53ffabc0e4a021da2e906072404a8b3c5555f64f279a21ebb60655e4d61f4a18be9ad389d8ff05b994bb4c194d8803537ac6cd9f708e0dd12d1857554e41c9cbef98f61c5751b796e5b37d338f5d9b3ec3202b37a32f",16)

g = gcd(k1,k2)
print str(max(g, k1//g, k2//g))[-6:]

Adrian Iriciuc
May 2, 2014

Using the fact that key1 = a b and key2 = b c (one common prime factor) we need to find the last 6 digits of b. And b = gdc(key1, key2).

import java.math.BigInteger;

public class RSA {
    public static void main(String[] args) {
       BigInteger a = new BigInteger("1c7bb...", 16);
        BigInteger b = new BigInteger("2710e...", 16);

        System.out.println(a.gcd(b).mod(new BigInteger("1000000")));
    }
}

Amish Naidu
May 1, 2014

Here's the solution in C++ , the hint was that one of the factors of both numbers is same.

    #include <iostream>
    #include <gmpxx.h>
    int main()
    {
        mpz_class a,b,cf,f1,f2;
        a = "0x1c7bb1ae67...7f94c571ea39c7f4105fae00415dd7d";
        b = "0x2710e45014...796e5b37d338f5d9b3ec3202b37a32f";
        mpz_gcd(cf.get_mpz_t(),a.get_mpz_t(),b.get_mpz_t());
        f1 = a/cf;  //actually calculating f1 and f2 is unnecessary,
        f2 = b/cf;  //as it comes out cf is the largest factor any way.
        std::cout << std::max(cf,std::max(f1,f2))%1000000 << std::endl;
    }

Sometimes We Need More Random

The answer is 616467.

5 solutions

Discussions for this problem are now closed

0 pending reports