RuCTF 2013 Quals - Crypto 200 - [Team xbios]

Well, this was not the busiest of weekends but still we didn't have much time for the CTF. Here is a small write up on crypto 200 challenge that we solved. A python source code was given which had the key generation and crypt algorithm. Below is the encryption algorithm

def crypt(open_text, public_key):
    bts = []
    [bts.extend([int(b) for b in '00000000'[len(bin(ord(c))[2:]):] + bin(ord(c))[2:]]) for c in open_text]
    return [sum(map(lambda x: x[0] * x[1] ,zip(blk, public_key))) for blk in [bts[i * 128:(i+1) * 128] for i in range(len(open_text) // 16)]] 

Algorithm performs the following operations:

[*] Creates a 8 bitstring of each character in the plain text
[*] Splits the bitsring into blocks of 128 bits
[*] Pair the bitstring list with the 128 element public key list
[*] sum(map(lambda x: x[0] * x[1] ,zip(blk, public_key))) performs multiplication operation on each tuple pair and then adds them together

We were given a cipher text list with 10 elements ie. from the algorithm we can interpret that the plain text is 160 characters, 16 chars per block. Though we understood the code, we failed to recognize the crypto system until our teammate Aghosh figured out that its knapsack public key cryptosystem. First we looked at cryptanalysis of the system, this didn't work out. Later we figured out that the generated public_key is not random and can be used to retrieve the private key.

Key Generation Algorithm:

def generate_public_key(private_key): 
    n = 199285318978668966527551342512997250816637709274749259983292077699440369
    t = 32416190071
    return list(map(lambda x: (t * x) % n, private_key))

This is what we got when analysing the public_key list:

sage: factor(1050809378719198985041)
32416190071^2
sage: factor(2101618757438397970082)
2 * 32416190071^2
sage: factor(6304856272315193910246)
2 * 3 * 32416190071^2
sage: factor(18914568816945581730738)
2 * 3^2 * 32416190071^2
sage: factor(56743706450836745192214)
2 * 3^3 * 32416190071^2
sage: factor(170231119352510235576642)
2 * 3^4 * 32416190071^2

Looks like the private_key is generated based on the given 't' value. This is how we generated the private_key list

private_key = [t]
for i in range(0,127):
    private_key.append(2 * 3**i * t)

The generated private keys can be verified using the given generate_public_key() function. We got a match. Then we wrote the routine for inverse knapsack sum to get the flag. Here is the final code:

#!/usr/bin/env python

import sys

n = 199285318978668966527551342512997250816637709274749259983292077699440369
t = 32416190071
t_inv = 3607086840002694423309872675805192458275553329397325526691156370525160 #sage: inverse_mod(t,n)

private_key = [t]
for i in range(0,127):
    private_key.append(2 * 3**i * t)

cipher_text = [
  1387977778999926469357780220487630125151962348185941993910077394771302677,
  1192236960845781949613172279312582839292898077268409678421304772227241438,
  1295152741157953792099179799985052248167548374589648818528421499250916999,
  828724787424187908000366458781164595076558885463707900320215679908512646,
  1179926879709109047038661681316962368287877340885819899201698611790531134,
  965171312356484716595815857561729919489896088681139239093293829323154838,
  1099367377207651843612375443021502714028353049437532392256489525051038347,
  1374891605015623267623322424512489936836885983493815443812918444687247914,
  1152880248428103510879661300981452627677389745079857275081612568623556291,
  962409003220820525413536841942678826309419979028794415812582008820263317
       ]

def decrypt(cipher, private_key):   # inverse knapsack
    
    bts = ['0']*128                 # generate bit string
    for i in range(len(private_key) - 1, -1, -1): 
        if cipher >= private_key[i]:
            bts[i] = '1'
            cipher = cipher - private_key[i]

    for j in range(0,128,8):        # generate chars out of every 8-bits
        sys.stdout.write(chr(int(''.join(bts[j:j+8]),2)))

for c in cipher_text:               # iterate through 10 blocks
    decrypt((c * t_inv) % n,private_key)
print ''

Running the code, we got the flag: bf145f32d9637c37de3cb5b470b2c44f8e466bc26e06725ac1517006ab70eac23907a37da8715981c7de813dc03f8104381eadf57d50dc4841d7956fffcd22eefe8ec62e9dea680f78d18352b4bb3ec2