Created
January 16, 2018 21:00
-
-
Save minhtt159/f19d414fcc5d261e2faf2bd2bff5e520 to your computer and use it in GitHub Desktop.
BKU-CTF
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#! 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment