BKU-CTF

hill_ciper.py

#! usr/bin/env python3
import string
import sys
import numpy as np
import math
from numpy import matrix
from numpy import linalg
# from flag import FLAG 

# assert len(FLAG) == 28 


def matmultMod(A,v, p): # multiply a marix A by a vector v
    n = len(v)
    Av = []
    for i in range(len(A)):
        s = 0
        for j in range(n):
            s += A[i][j] * v[j]
        Av.append(s % 72)    
    return Av

def modMatInv(A,p):
	n = len(A)
	A = matrix(A)
	adj = np.zeros(shape=(n,n))
	for i in range(0,n):
		for j in range(0,n):
			adj[i][j] = ((-1) ** (i + j) * int(round(linalg.det(minor(A,j,i))))) % p
	return (modInv(int(round(linalg.det(A))),p) * adj) % p

# Compute the inverse of a modulo p (if it exists)
def modInv(a, p):
	# find a ^ -1 mod p (if it exists)
	# use the Extended Euclidean Algorithm
		if a > p:
			r_i = a
			r_i_1 = p
		else:
			r_i = p
			r_i_1 = a
		r_i_2 = r_i % r_i_1

		# initialize neccessary values
		q = (r_i - r_i_2) / r_i_1
		x_i = 1
		x_i_1 = 0
		y_i = 0
		y_i_1 = 1

		while r_i_2 != 0:
			# compute new x_i_2 and y_i_2
			# this is a recursive formulae
			x_i_2 = x_i - x_i_1 * q
			y_i_2 = y_i - y_i_1 * q
			
			# update values for r_i, r_i_1 and r_i_2
			r_i = r_i_1
			r_i_1 = r_i_2
			r_i_2 = r_i % r_i_1
			
			# update value for q
			q = (r_i - r_i_2) / r_i_1
			
			# update value for x_i, x_i_1
			x_i = x_i_1
			x_i_1 = x_i_2

			# update values for y_i, y_i_1
			y_i = y_i_1
			y_i_1 = y_i_2

		if a > p:
			if x_i_2 < 0:
				return p + x_i_2
			else:
				return x_i_2
		else:
			if y_i_2 < 0:
				return p + y_i_2
			else:
				return y_i_2

# Compute the minor's - during the process of computing A's determinant
def minor(A,i,j):
	A = np.array(A)
	minor = np.zeros(shape = (len(A)-1,len(A)-1))
	p = 0
	for s in range(0,len(minor)):
		if p == i:
			p = p + 1
		q = 0
		for t in range(0,len(minor)):
			if q == j:
				q = q + 1
			minor[s][t] = A[p][q]
			q = q + 1
		p = p + 1
	return minor

def decrypt_cipher(eblock):
	# Flatten and get the total length of the cipher
	n = len(np.concatenate(eblock).ravel().tolist())
	k = n % 2

	# Compute the inverse matrix of A(modulo the size of the alph)
	A_inv = modMatInv(A,72)
	if k > 0:
		n = n + 2 - k
	output = ''
	counter = 0
	for bnum in range(int(n/2)):
		decrypt_val = A_inv * np.matrix(eblock[bnum]).T
		decrypt_val = decrypt_val.T.tolist()[0]

		decrypt_val = ''.join ([alph[int(x) % 72] for x in decrypt_val])
		counter = counter + 1
		output = output + decrypt_val
		counter = 0

	return output
#######################################################
# the symbol list

alph = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_,.;: ?!()"

#######################################################

# the encryption matrix

#A = [[3,1,7,1,2,4,4,19],[2,0,11,19,-3,2,8,39],[14,45,8,6,-21,21,5,3],[1,2,3,4,5,6,7,-8],[10,20,11,21,30,40,31,41],[8,7,6,5,4,3,2,1],[35,16,46,0,8,25,1,4],[2,3,3,0,3,0,1,1]]
A = [[3, 2],[4, 5]]
#######################################################

# # This was the part of the original code
# ptext = """The Opera ghost really existed. He was not, as was long believed,
# a creature of the imagination of the artists, the superstition of
# the managers, or a product of the absurd and impressionable brains
# of the young ladies of the ballet, their mothers, the box-keepers,
# the cloak-room attendants or the concierge. Yes, he existed
# in flesh and blood, although he assumed the complete appearance
# of a real phantom; that is to say, of a spectral shade....
# So do we, Efiens, then and now. Here is the flag:""" 
# ptext += FLAG 
# n = len(ptext)
# k = n % 2#prepare for padding for blocks size 2. Encryption matrix is 2x2
# if k > 0:
# 	ptext = ptext +  ' '*(2 - k)
# 	n = n + 2 - k   
#     # padding done   

# cip = []
# for bnum in range(int(n/2)):#proces block by block, bnum is block number
# 	block = ptext[bnum*2:(bnum+1)*2]#.upper()
# 	block_vec = []
# 	# Encrypt ptext by block-of-2
# 	for x in block:
# 		if x in alph:
# 			block_vec.append(alph.index(x))
# 		else:    
# 			block_vec.append(alph.index('_')) # alph[36] == 'Z'
# 	eblock = matmultMod(A, block_vec, 72) # 47 is the size of the alphabet
# 	cip.append(eblock)

# print("alph:" + alph)
# print("A: {}".format(A))
# print("cip: {}".format(cip))
# output = decrypt_cipher(cip)
# print("The flag is: " + output)
# #

C = [[51, 25], [8, 23], [52, 45], [32, 47], [68, 7], [18, 5], [64, 20], [53, 11], [45, 34], [8, 1], [67, 38], [45, 58], [71, 6], [6, 41], [4, 49], [38, 15], [9, 34], [9, 4], [22, 36], [63, 31], [66, 25], [35, 11], [22, 36], [9, 4], [22, 36], [59, 21], [54, 67], [14, 31], [69, 42], [35, 30], [40, 67], [4, 49], [25, 58], [68, 7], [26, 39], [70, 34], [11, 50], [45, 34], [65, 36], [11, 27], [57, 57], [8, 23], [34, 38], [70, 48], [36, 43], [24, 41], [38, 48], [35, 59], [38, 27], [3, 61], [15, 66], [37, 38], [3, 37], [46, 68], [7, 40], [35, 11], [57, 57], [8, 23], [8, 46], [39, 26], [1, 32], [59, 62], [59, 62], [54, 67], [65, 36], [1, 2], [57, 57], [8, 23], [22, 66], [25, 70], [12, 62], [1, 32], [35, 11], [62, 15], [37, 38], [67, 41], [65, 12], [35, 58], [30, 49], [65, 36], [11, 27], [57, 57], [8, 23], [60, 23], [8, 46], [43, 29], [37, 38], [31, 13], [53, 6], [52, 69], [45, 34], [4, 36], [38, 48], [25, 70], [11, 5], [8, 23], [23, 35], [2, 58], [61, 16], [50, 16], [11, 27], [57, 57], [8, 23], [14, 40], [0, 19], [14, 31], [19, 62], [11, 70], [34, 52], [65, 36], [11, 27], [57, 57], [8, 23], [61, 22], [41, 45], [36, 57], [35, 11], [57, 57], [14, 2], [47, 3], [50, 64], [57, 57], [32, 47], [42, 59], [3, 61], [15, 66], [39, 43], [2, 45], [42, 68], [6, 54], [39, 26], [1, 32], [25, 58], [57, 57], [8, 23], [14, 9], [28, 2], [16, 22], [65, 12], [52, 62], [37, 38], [9, 45], [24, 27], [67, 30], [63, 21], [50, 7], [62, 15], [3, 61], [15, 66], [41, 48], [54, 67], [8, 66], [32, 47], [12, 62], [38, 15], [60, 30], [42, 59], [51, 1], [8, 23], [44, 5], [46, 68], [51, 42], [67, 66], [36, 43], [47, 63], [27, 10], [54, 53], [37, 38], [31, 13], [39, 43], [47, 60], [34, 17], [35, 11], [8, 1], [57, 57], [68, 30], [18, 5], [51, 1], [8, 23], [22, 36], [8, 46], [30, 14], [5, 19], [57, 57], [8, 23], [20, 24], [52, 69], [27, 10], [51, 42], [37, 38], [61, 9], [70, 34], [37, 14], [29, 8], [70, 70], [38, 27], [37, 38], [71, 51], [70, 34], [29, 51], [45, 41], [12, 11], [71, 20], [28, 45], [3, 61], [7, 46], [53, 11], [46, 68], [3, 61], [38, 63], [40, 18], [60, 11], [65, 36], [11, 27], [68, 7], [70, 21], [2, 44], [5, 35], [8, 1], [1, 56], [7, 46], [3, 50], [32, 0], [32, 0], [6, 50], [38, 63], [23, 28], [9, 4], [0, 3], [65, 0], [17, 6], [24, 27], [42, 59], [3, 61], [15, 66], [35, 59], [12, 11], [5, 19], [53, 68], [56, 8], [71, 15], [32, 47], [8, 23], [46, 68], [3, 61], [15, 66], [47, 63], [19, 62], [12, 26], [38, 9], [31, 60], [38, 9], [34, 22], [71, 39], [64, 38], [32, 59], [6, 2], [37, 26], [34, 6], [44, 68], [34, 22], [59, 16], [22, 55]]
print decrypt_cipher(C)
# ENFIENS_THE_GHOST_COMES_REAL