plaidCTF 2014 - graphs (crypto200)

For PlaidCTF2014, Eindbazen and fail0verflow joined forces as 0xffa, the Final Fail Alliance.
Don't miss out on other write-ups at Eindbazen's site!

This challenge was about breaking a custom public key encryption system.

Cryptography (200 pts)
In this era, block ciphers hadn't even been invented. The Plague created this
system based on problems he knew to be NP hard, but there must be something you
can do to decode his messages.

We were given a python implementation of the system, the Plague’s public key and an encrypted message. The implementation includes encryption, decryption (given a private key) and key generation.