1
$\begingroup$

I require help with the following assignment.

The Assignment

A company by the name "Secure Keys" is very good at creating random prime numbers, however a new CEO decides to cut costs and use random numbers more than once in generating RSA key pairs.

100 messages from this company were intercepted, all messages contain the cyphertext and the modulo used for decryption, we also know that their RSA encryption uses e = 65537 (2^16 + 1)

You are to decrypt the files and find the message containing the flag.

I'm lost in how to approach this problem, since I know that having the n,e isn't enough to decrypt a single message and I failed to connect the repetition on prime numbers used part.

|improve this question
$\endgroup$
  • $\begingroup$ It sounds like there's not just one $(n, e)$ public key, but multiple $(n_i, e_i)$ public keys. What do you know about the corresponding private keys? What are the private keys and how are they related to the public keys? $\endgroup$ – Squeamish Ossifrage Dec 23 '17 at 0:22
  • $\begingroup$ the public keys are (ni,e) where e = 65537 always, the only thing I know about private keys and public keys is that they are generated by the prime numbers p,q that might be used for more than 1 message. $\endgroup$ – Ali.B Dec 23 '17 at 0:26
  • $\begingroup$ How is $n_i$ related to $p_i$ and $q_i$? How might $p_i$ and $p_j$ or $q_j$ for $i \ne j$ be related? $\endgroup$ – Squeamish Ossifrage Dec 23 '17 at 0:31
  • $\begingroup$ The question doesn't specify $\endgroup$ – Ali.B Dec 23 '17 at 0:36
  • 1
    $\begingroup$ Knowing $p\cdot q_0$ alone doesn't help you to find $p$ or $q_0$. Knowing $p\cdot q_1$ alone doesn't help you to find $p$ or $q_1$. Does knowing $p\cdot q_0$ and $p\cdot q_1$ help you to find $p$, $q_0$, or $q_1$? $\endgroup$ – Squeamish Ossifrage Dec 23 '17 at 2:07
2
$\begingroup$

The assignment, or at least the part of it that you've quoted, seems somewhat ambiguous, but I'm going to assume that it means that among the RSA moduli there are pairs $(n_A, n_B)$ that share a common prime factor $p$ (i.e. $n_A = p \cdot q_A$, $n_B = p \cdot q_B$, with $q_A \ne q_B$).

In that case, you can trivially find the shared prime factor by calculating the greatest common divisor of the two moduli $n_A$ and $n_B$, e.g. using the Euclidean algorithm. Even if you don't know in advance which moduli share a common factor, you can simply test each pair of moduli: the GCD of any two numbers is always, by definition, a divisor of both of them, so if you find any two RSA moduli whose GCD isn't 1, you've just factored both of them.

Note that this is not just an artificial exercise, but a practical attack against poor quality RSA key generation implementations found in the wild. For a demonstration of this attack (and more details on how to efficiently carry it out in practice), see e.g. the paper "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices" by Heninger, Durumeric, Wustrow and Halderman (2012).

Ps. See also this related question from a few years ago.

|improve this answer
$\endgroup$
  • $\begingroup$ That is correct, thanks for writing the answer, with the help of @SqueamishOssifrage I was able to get to this conclusion last night. $\endgroup$ – Ali.B Dec 23 '17 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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