PACTF_2018: Siblings

Category: Lovelace Points: 120 Description:

One 4096-bit RSA key is impossible to break, so 20 must be even better! By chaining each encryption together, surely it’s impossible for you to figure out what the message is? Everything you’ll need (except the private keys, you’re on your own for that!)

Write-up

Upon extracting our file, we get a folder static/. In it, we find the encrypted file as well as 20 public keys. The key to this challenge lies in prime factor reuse where a public key may share either p or q with another public key.

In the case of two public keys sharing p, as shown below,

n1 = p1 * q1
n2 = p1 * q2

The easiest way to retrieve p1, is to get the greatest common divisor of n1 and n2. With p1, you can simply divide from n1 or n2 to get q1 and q2 respectively.

To expedite the process, we can code that in Python,

# ./solve.py
t00 many c00ks sp0il the br0th

Therefore, the flag is t00 many c00ks sp0il the br0th.

results matching ""

    No results matching ""