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.
Encrypts a message using super secure, NP-hard graph stuff.
Encryption works like this: take a graph, split your message up into
N numbers, such that the sum of all the numbers is equal to your message.
Assign each vertex to one of these N numbers.
Then ciphertext[v] is the sum of v's N, and all of the N's from v's neighborsThis challenge provides a .tar.bz2 including the ciphertext (encrypted flag), pubkey ("GRAPHCRYPT PUBLIC KEY"), and genkey.py (implementing the graphcrypt cryptosystem described above). The encryption/decryption routines looked interesting, but nothing immediately stuck out about them:
def encrypt(self,message): t = message/self.keylen vals = [int(random.gauss(t,t)) for _ in xrange(self.keylen-1)] missing = message - reduce(lambda a,b:a+b, vals) vals.append(missing) assert(reduce(lambda a,b:a+b, vals) == message) ctext = [0] * self.keylen for v in xrange(self.keylen): ctext[v] = vals[v] for n in self.pubkey[v]: ctext[v] += vals[n] return zlib.compress(pickle.dumps(ctext),9).encode("base64") def decrypt(self,ct): ct = pickle.loads(zlib.decompress(ct.decode("base64"))) return reduce(lambda a,b:a+b,[ct[i] for i in self.privkey])
The much more interesting data came about from testing the key generation algorithm, a common source of crypto-woes. The PRNG was seeded with 128-bytes of pretty random data, so I expected to see meaningless data... but a low key length showed some magical patterns.
>>> genkey.Graphcrypt(keylen=16*1) private_key [3] public_key [[3], [3, 7, 11], [3], [2, 5, 12, 0, 8, 10, 11, 14, 7, 6, 15, 1, 9, 4, 13], [3, 12, 15], [3], [3, 12], [3, 1], [3], [3], [3], [3, 1, 14], [3, 4, 6], [3], [3, 11], [3, 4]] >>> genkey.Graphcrypt(keylen=16*1) private_key [6] public_key [[6], [6], [6], [6], [6], [6], [4, 2, 9, 5, 12, 8, 14, 7, 0, 10, 3, 11, 1, 15, 13], [6], [6], [6], [6, 13], [6], [6], [6, 10], [6, 15], [6, 14]] >>> genkey.Graphcrypt(keylen=16*2) private_key [4, 3] public_key [[4, 1], [3, 0, 20, 28], [4], [30, 27, 20, 17, 31, 16, 19, 9, 28, 18, 8, 1, 23, 26], [22, 10, 21, 6, 24, 0, 14, 7, 15, 12, 13, 11, 25, 5, 2, 29], [4, 5, 5, 15], [4, 15], [4, 16, 30], [3, 27, 28], [3, 30], [4, 13, 19, 23], [4, 23, 28], [4, 14], [4, 10, 16], [4, 12, 23, 30], [4, 5, 6], [3, 7, 13, 19], [3], [3, 25], [3, 10, 16, 31], [3, 1], [4], [4], [3, 11, 14, 10], [4, 29], [4, 18], [3], [3, 8], [3, 1, 8, 11], [4, 24], [3, 7, 9, 14], [3, 19, 31, 31]] >>> genkey.Graphcrypt(keylen=16*2) private_key [3, 13] public_key [[3], [3, 28], [13, 31], [9, 25, 27, 31, 8, 1, 0, 4, 15, 17, 19, 26], [3], [13, 17, 18], [13, 17, 20], [13, 17, 21, 26], [3, 9, 20], [3, 8, 22], [13, 31], [13, 21, 24], [13, 26], [30, 18, 20, 24, 29, 28, 10, 7, 14, 16, 22, 12, 23, 5, 21, 2, 11, 6], [13, 14, 14, 28], [3, 19, 30, 21, 27], [13], [3, 5, 6, 7, 18], [13, 5, 17], [3, 15], [13, 8, 6, 24, 27], [13, 11, 7, 15, 23], [13, 9, 29], [13, 21], [13, 11, 20, 25, 30], [3, 24], [3, 12, 7, 28], [3, 20, 15, 29], [13, 1, 14, 26], [13, 22, 27, 30], [13, 15, 24, 29], [3, 10, 2]] >>> genkey.Graphcrypt(keylen=16*2) private_key [11, 30] public_key [[30, 8, 17, 26], [11], [11, 31, 7], [11, 19, 28, 31], [30, 12, 14], [30, 16], [30, 17], [30, 2, 19, 25], [11, 0, 19, 22, 9], [30, 8], [11], [1, 28, 19, 3, 16, 2, 10, 13, 8], [30, 4, 22], [11, 27, 17, 20], [30, 4, 26, 17], [30, 17], [11, 5], [30, 0, 15, 6, 13, 14], [30], [11, 3, 7, 8, 24], [30, 13], [30, 21, 21, 26], [30, 8, 12], [30, 29], [30, 19, 25], [30, 7, 24], [30, 14, 21, 0], [30, 13], [11, 3], [30, 23], [12, 15, 22, 23, 5, 31, 6, 18, 29, 4, 20, 0, 25, 7, 27, 26, 21, 17, 24, 14, 9], [30, 2, 3]]
The first thing to notice is that elements of the private key disproportionately appear as the first element of public_key groupings. The second thing is that elements of the private_key don't appear in their respective public key indexes. Thirdly, public_key indexes which appear in the private key (ie, 3) are substantially longer than those which don't. So in the first example, public_key[3] is the longest sublist and doesn't contain number 3. Any one of these 3 issues may be sufficient to recover elements of the private key, but the 1st and 3rd will also provide positioning. Upon recovering the private key, just decrypt using the provided code.
import genkey target = genkey.Graphcrypt('pubkey') lookups= sorted([(len(lookup),i) for i,lookup in enumerate(target.pubkey)],reverse=True) target.privkey = [lookup[1] for lookup in lookups][:len(lookups)/16] ptext = target.decrypt(open('ciphertext').read()) print ptext
Successful Execution
$ python recoverPrivKey.py 10741481577014830904303555552655870683543835028106003993397553121202030