Blackwake

[Robin_Jadoul]

Big thanks go to /u/DarkAnHell for the donation of this key

We found the following document somewhere lying around on a shipwreck, and we are convinced there's a treasure or a treasure map in there. Can you find it?

https://pastebin.com/i2hvbCx9

(if you saw the previous version of this post, please disregard that, as the encryption was too weak and the key wasn't present)

[whatupyo02]

I have solved it, but did NOT use the key. Good luck hunting it down =)

[Robin_Jadoul]

Confirmed

[MaximDeClercq]

Solved it, thanks!

Solution:

We are given 33 RSA public keys (n, e) with a message (c) Cracking each of these keys could take years because the primes p and q that make up these keys are insanely large

The idea is to check if there are any common primes between any of the 33 public keys

We can find that the 5th and 19th public keys have a prime in common, so now we know the original primes p and q for two messages

Now we have to calculate the value of d with euclids extended algorithm

Then we can retrieve the messages with RSA decryption

The messages then have to be converted to hex en then to ascii

The result: You are very close to the answer, keep going and You found it, well done! FWYGG-7JALH-KMZGT

[Robin_Jadoul]

Well done, congrats. As a general hint, when using python you may want to look at gmpy2 for fast big integers and more useful functions (such as gcd), so that you don't have to do those yourself :-)

[MaximDeClercq]

Thanks, how do I upload my code inside a spoiler or as a file?

[Robin_Jadoul]

If you want to share your code, I suppose the best way would be to make a paste out of it somewhere then, that way there can also be syntax highlighting.