0 - Slab of Platinium (CSAW Crypto 500).py

import os, random, struct
from Crypto.Cipher import AES

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def legendre_symbol(a, p):
    """
    Legendre symbol
    Define if a is a quadratic residue modulo odd prime
    http://en.wikipedia.org/wiki/Legendre_symbol
    """
    ls = pow(a, (p - 1)/2, p)
    if ls == p - 1:
        return -1
    return ls

def prime_mod_sqrt(a, p):
    """
    Square root modulo prime number
    Solve the equation
        x^2 = a mod p
    and return list of x solution
    http://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm
    """
    a %= p

    # Simple case
    if a == 0:
        return [0]
    if p == 2:
        return [a]

    # Check solution existence on odd prime
    if legendre_symbol(a, p) != 1:
        return []

    # Simple case
    if p % 4 == 3:
        x = pow(a, (p + 1)/4, p)
        return [x, p-x]

    # Factor p-1 on the form q * 2^s (with Q odd)
    q, s = p - 1, 0
    while q % 2 == 0:
        s += 1
        q //= 2

    # Select a z which is a quadratic non resudue modulo p
    z = 1
    while legendre_symbol(z, p) != -1:
        z += 1
    c = pow(z, q, p)

    # Search for a solution
    x = pow(a, (q + 1)/2, p)
    t = pow(a, q, p)
    m = s
    while t != 1:
        # Find the lowest i such that t^(2^i) = 1
        i, e = 0, 2
        for i in xrange(1, m):
            if pow(t, e, p) == 1:
                break
            e *= 2

        # Update next value to iterate
        b = pow(c, 2**(m - i - 1), p)
        x = (x * b) % p
        t = (t * b * b) % p
        c = (b * b) % p
        m = i

    return [x, p-x]

def extended_gcd(a, b):
    """Return (r, s, d) where a*r + b*s = d and d = gcd(a,b)"""
    x,y = 0, 1
    lastx, lasty = 1, 0

    while b:
        a, (q, b) = b, divmod(a,b)
        x, lastx = lastx-q*x, x
        y, lasty = lasty-q*y, y

    return (lastx, lasty, a)

def chinese_remainder_theorem(items):
  """Solve the chinese remainder theorem
  Given a list of items (a_i, n_i) solve for x such that x = a_i (mod n_i)
  such that 0 <= x < product(n_i)
  Assumes that n_i are pairwise co-prime.
  """

  # Determine N, the product of all n_i
  N = 1
  for a, n in items:
    N *= n

  # Find the solution (mod N)
  result = 0
  for a, n in items:
    m = N//n
    r, s, d = extended_gcd(n, m)
    if d != 1:
      raise "Input not pairwise co-prime"
    result += a*s*m

  # Make sure we return the canonical solution.
  return result % N

def xor(a, b):
	r = ""
	for i in range(len(a)):
		r += chr(ord(a[i]) ^ ord(b[i]))
	return r

def decrypt_file(key, in_filename, iv, out_filename="cashcat_dec.png", chunksize=16):
    if not out_filename:
        out_filename = os.path.splitext(in_filename)[0]

    with open(in_filename, 'rb') as infile:
        decryptor = AES.new(key, AES.MODE_CBC, iv)

        with open(out_filename, 'wb') as outfile:
            while True:
                chunk = infile.read(chunksize)
                if len(chunk) != 16:
                    break
                outfile.write(decryptor.decrypt(chunk))

# The first 2 primes where found by factorizing the N given in the file.
f1 = 123722643358410276082662590855480232574295214169
f2 = 164184701914508585475304431352949988726937945387
n = f1 * f2
phi = (f1 - 1) * (f2 - 1)

# This is the initial "e" used by the program
ei = 1404119484958500351776

# This is the ciphertext provided by the program
ciphertext = 4104314974842034312729644734009867622818315323910143873563666990448837112322264379294617825939

# The hard part of this challenge was that gcd(ei, phi) != 1
# This is an undesirable case when using RSA, because it means
# that for a given ciphertext "a", it either has no plaintext or
# it has many possible plaintext.
#
# For example, if we have are using RSA with the parameters N = 3*7 
# and e = 5 (Good case). We get the following value :
#  
# 0, 1,  2,  3,  4,  5, 6, 7, 8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
# 0, 1, 11, 12, 16, 17, 6, 7, 8, 18, 19,  2,  3, 13, 14, 15,  4,  5,  9, 10, 20
# 
# As we can see, every value comes up only once. However the case that 
# we have for the challenge is similar to having an e = 4 (Bad case). 
# We get the following value :
#
# 0, 1,  2,  3, 4,  5,  6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
# 0, 1, 16, 18, 4, 16, 15, 7, 1, 9,  4,  4,  9,  1,  7, 15, 16,  4, 18, 16,  1 
#
# As we can see, some value come up lots of times and some value never come up.
#
# So if we want to recover the original plaintext, we have to find all the 
# possible plaintext which gives the given ciphertext.

# This is where we store the found solutions so far
vv = []

for i in range(2**11):
	v = ciphertext
	e = ei

	try:
		# I observed that if we could divide the given "e" by 32,
		# the resulting "e" would have an inverse modulo "phi".
		# So we have to find all the possible results of :
		# sqrt(sqrt(sqrt(sqrt(sqrt(ciphertext)))))
		#
		# To compute the square root of the ciphertext we have to use
		# 2 algorithms. The first one is the "Tonelli-Shanks" algorithm
		# which allows us the find the square root of a number modulo a prime.
		# Since we are in a cases where it's modulo 2 primes, we have to split
		# the problem into 2 square root and combine the result using the
		# Chinese remainder theorem.
		#
		# Note : the bit shifting part is what allows us to iterate through all
		# the combination of the results.
		for j in range(5):
			v1 = prime_mod_sqrt(v, f1)
			v2 = prime_mod_sqrt(v, f2)
			
			v = chinese_remainder_theorem(
				[
					(v1[(i >> (j*2 + 0)) % 2], f1), 
					(v2[(i >> (j*2 + 1)) % 2], f2)
				]
			)
			e /= 2

		# For each distinct value that we found, we are now in a case
		# where the ciphertext is exponent e/32 instead of e. This means
		# that it's now possible to compute a "d" to decrypt it.
		#
		# This doesn't give a lot of different value and we can 
		# just look through the results to find the correct one.
		if not v in vv:
			vv.append(v)

			d = modinv(e, phi)
			ptxt = pow(v, d, n)
			test = pow(ptxt, ei, n)

			print(ptxt, test)
	except:
		continue

# This part was done after the previous results where known
# We got that the KEY was "mom_says_keys_are_secret".
#
# The initial code was really confusing for how to compute the
# IV. We could see the whole file except the first 16 bytes at
# this point, but since the first 16 bytes of a PNG file 
# pretty much never changes, we just manually replaced it in the
# output file.
IV = "\x00"*16
KEY = "mom_says_keys_are_secret"
decrypt_file(KEY, "file", IV)

1 - original.py

import os, random, struct
from Crypto.Cipher import AES
import secrets 

def encrypt_file(key, in_filename, iv, out_filename=None, chunksize=16):
    if not out_filename:
        out_filename = in_filename + '.enc'

    encryptor = AES.new(key, AES.MODE_CBC, iv)
    filesize = os.path.getsize(in_filename)

    with open(in_filename, 'rb') as infile:
        with open(out_filename, 'wb') as outfile:
            while True:
                chunk = infile.read(chunksize)
                if len(chunk) == 0:
                    break
                elif len(chunk) % 16 != 0:
                    chunk += ' ' * (16 - len(chunk) % 16)

                outfile.write(encryptor.encrypt(chunk))

def decrypt_file(key, in_filename, iv, out_filename="cashcat_dec.png", chunksize=16):
    if not out_filename:
        out_filename = os.path.splitext(in_filename)[0]

    with open(in_filename, 'rb') as infile:
        decryptor = AES.new(key, AES.MODE_CBC, iv)

        with open(out_filename, 'wb') as outfile:
            while True:
                chunk = infile.read(chunksize)
                if len(chunk) != 16:
                    break
                outfile.write(decryptor.decrypt(chunk))


KEY = secrets.ptxt
if len(KEY) == 24:
    print 'all is good'

master_key = ""
m = map(ord, ptxt)
for i in m:
	master_key += str(m)

n = 20313365319875646582924758840260496108941009525871463319046021451803402705157052789599990588403L
e = 1404119484958500351776

# hey guys i did this in sage to double check, and the ctxt does equal 4104314974842034312729644734009867622818315323910143873563666990448837112322264379294617825939
# so math works!
ctxt = power_mod(master_key, e, n);

file = "sales_img"
seed = open(file, 'r+').read(6).encode('hex') + '00' + '00'
if len(seed) == 16:
    print 'all is good'

# if we encrypt the key using RSA we can make a super secure IV
IV0 == int(ctxt[78:94]) 
IV == IV0 ^^ seed 

print 'Encrypting sales img for 10k slabs of platinum'
encrypt_file(KEY, file, IV)
print '[+] encryption complete'

2 - Original files

https://drive.google.com/file/d/0B7qase6SYJfjenVIY1BpQTk2cTg/view?usp=sharing