## Fatima
### Challenge> I think we should all learn elliptic curves and fatima is a good start, enjoy!
```python#!/usr/bin/env python3# -*- coding: utf-8 -*-
from fastecdsa.curve import Curvefrom fastecdsa.point import Pointimport math, randomfrom flag import flagimport time
def multiply(A, B):	ac, ar, bc, br = len(A[0]), len(A), len(B[0]), len(B)	if ac != br:		return None	result = []	for i in range(ar):		r = []		for j in range(bc):			r.append(0)		result.append(r)	for i in range(ar):		for j in range(bc):			for k in range(br):				result[i][j] += A[i][k] * B[k][j] 		return result
def pow_matrix(A, n):	R = circulant([1] + [0 for i in range(len(A)-1)])	for _ in range(n):		R = multiply(R, A)	return R
def circulant(v):	C, n = [], len(v)	for i in range(n):		C.append(v)		tmp = []		tmp.append (v[-1])		tmp.extend(v[:-1])		v = tmp	return C
def spiral(A):	row = len(A)	col = len(A[0])	top = 0	left = 0	tmp = []
	while (top < row and left < col) :       		for i in range(left,col) :			tmp.append(A[top][i])              		top += 1		for i in range(top,row) :			tmp.append(A[i][col - 1])     		col -= 1		if ( top < row) :			for i in range(col - 1,(left - 1),-1) :				tmp.append(A[row - 1][i])  			row -= 1
		if (left < col) :			for i in range(row - 1,top - 1,-1) :				tmp.append(A[i][left])   			left += 1	result = []	for i in range(len(A)):		r = []		for j in range(len(A[0])):			r.append(tmp[i*len(A[0]) + j])		result.append(r)	return result
def revspiral(A):	tmp = sum(spiral(A),[])	tmp = tmp[::-1]	result = []	for i in range(len(A)):		r = []		for j in range(len(A[0])):			r.append(tmp[i*len(A[0]) + j])		result.append(r)	return result
def sinwaveform(A):	row = len(A)	col = len(A[0])	tmp = []	for j in range(col):		if j%2 == 0:			for i in range(row):				tmp.append(A[i][j])		else:			for i in range(row-1,-1,-1 ):				tmp.append(A[i][j])	result = []	for i in range(len(A)):		r = []		for j in range(len(A[0])):			r.append(tmp[i*len(A[0]) + j])		result.append(r)	return result
def helical(A):	row = len(A)	col = len(A[0])	tmp = []	dir = 0	for k in range(0,row):		if dir == 0:			i = k			for j in range(0,k+1):				tmp.append(A[i][j])				i -= 1			dir = 1		else:			j = k			for i in range(0,k+1):				tmp.append(A[i][j])				j -= 1			dir = 0	for k in range(1, row):		if dir == 0:			i = row - 1			for j in range(k, row):				tmp.append(A[i][j])				i -= 1			dir = 1		else:			j = row - 1			for i in range(k, row):				tmp.append(A[i][j])				j -= 1			dir = 0	result = []	for i in range(len(A)):		r = []		for j in range(len(A[0])):			r.append(tmp[i*len(A[0]) + j])		result.append(r)	return result
def revhelical(A):	tmp = sum(helical(A),[])	tmp = tmp[::-1]	result = []	for i in range(len(A)):		r = []		for j in range(len(A[0])):			r.append(tmp[i*len(A[0]) + j])		result.append(r)	return result
dict_traversal = {	1: spiral,	2: revspiral,	3: sinwaveform,	4: helical,	5: revhelical}
def c2p(c, G):	C = ord(c) * G	return bin(C.x)[2:].zfill(8) + bin(C.y)[2:].zfill(8)
def aux(msg, G):	enc = ''	for c in msg:		enc += c2p(c, G)	return enc
def enmat(c, l):	s = int(math.sqrt(len(c) // l))	return [[int(c[i*l:i*l+l], 2) for i in range(s * j, s * (j + 1))] for j in range(s) ]
def encrypt(msg):	name = 'curve'.encode('utf-8')	p, a, b, q, gx, gy, aux = 241, 173, 41, 256, 53, 192, ''	curve = Curve(name, p, a, b, q, gx, gy)	G = Point(gx, gy, curve = curve)
	for c in msg:		aux += c2p(c, G)	B = enmat(aux, 3)	S = list(range(1,6))	random.shuffle(S)	for i in range(5):		B = dict_traversal[S[i]](B)	C = circulant([0 for i in range(len(B)-1)] + [1])	a, l = [random.randint(2, len(B)) for _ in '01']	CL = pow_matrix(C, l)	CAL = pow_matrix(CL, a)	enc = (CL[0], multiply(B, CAL))	return encprint("enc = ", encrypt(flag))```
### Solution
Note that `pow_matrix(C, i) == circulant([0]*(100 - i) + [1] + [0]*(i - 1))` with `C = circulant([0 for i in range(len(B)-1)] + [1])`, with knowing that we can recover the plaintext step-by-step.
```enc[1] = B*C^(a*l)enc[1]*C^k = B*C^(a*l + k)```
Therefore if we can find `k` such that `a*l + k == 0 (mod 100)`, which mean `C^(a*l + k)` is the identity matrix, we can recover `B`. Note that `C^k` has the form `circulant([0]*(100 - i) + [1] + [0]*(i - 1))` so we can just bruteforce `i` and check for each case which produces the right plaintext. The traversal operators and EC part can be reversed using look-up tables.
### Implementation```pythonfrom Crypto.Util.number import *import itertoolsimport tqdmfrom fastecdsa.curve import Curvefrom fastecdsa.point import Pointimport math, random
############ Reuse code of the challenge ############def multiply(A, B):	ac, ar, bc, br = len(A[0]), len(A), len(B[0]), len(B)	if ac != br:		return None	result = []	for i in range(ar):		r = []		for j in range(bc):			r.append(0)		result.append(r)	for i in range(ar):		for j in range(bc):			for k in range(br):				result[i][j] += A[i][k] * B[k][j] 		return result
def pow_matrix(A, n):	R = circulant([1] + [0 for i in range(len(A)-1)])	for _ in range(n):		R = multiply(R, A)	return R
def circulant(v):	C, n = [], len(v)	for i in range(n):		C.append(v)		tmp = []		tmp.append (v[-1])		tmp.extend(v[:-1])		v = tmp	return C
def spiral(A):	row = len(A)	col = len(A[0])	top = 0	left = 0	tmp = []
	while (top < row and left < col) :       		for i in range(left,col) :			tmp.append(A[top][i])              		top += 1		for i in range(top,row) :			tmp.append(A[i][col - 1])     		col -= 1		if ( top < row) :			for i in range(col - 1,(left - 1),-1) :				tmp.append(A[row - 1][i])  			row -= 1
		if (left < col) :			for i in range(row - 1,top - 1,-1) :				tmp.append(A[i][left])   			left += 1	result = []	for i in range(len(A)):		r = []		for j in range(len(A[0])):			r.append(tmp[i*len(A[0]) + j])		result.append(r)	return result
def revspiral(A):	tmp = sum(spiral(A),[])	tmp = tmp[::-1]	result = []	for i in range(len(A)):		r = []		for j in range(len(A[0])):			r.append(tmp[i*len(A[0]) + j])		result.append(r)	return result
def sinwaveform(A):	row = len(A)	col = len(A[0])	tmp = []	for j in range(col):		if j%2 == 0:			for i in range(row):				tmp.append(A[i][j])		else:			for i in range(row-1,-1,-1 ):				tmp.append(A[i][j])	result = []	for i in range(len(A)):		r = []		for j in range(len(A[0])):			r.append(tmp[i*len(A[0]) + j])		result.append(r)	return result
def helical(A):	row = len(A)	col = len(A[0])	tmp = []	dir = 0	for k in range(0,row):		if dir == 0:			i = k			for j in range(0,k+1):				tmp.append(A[i][j])				i -= 1			dir = 1		else:			j = k			for i in range(0,k+1):				tmp.append(A[i][j])				j -= 1			dir = 0	for k in range(1, row):		if dir == 0:			i = row - 1			for j in range(k, row):				tmp.append(A[i][j])				i -= 1			dir = 1		else:			j = row - 1			for i in range(k, row):				tmp.append(A[i][j])				j -= 1			dir = 0	result = []	for i in range(len(A)):		r = []		for j in range(len(A[0])):			r.append(tmp[i*len(A[0]) + j])		result.append(r)	return result
def revhelical(A):	tmp = sum(helical(A),[])	tmp = tmp[::-1]	result = []	for i in range(len(A)):		r = []		for j in range(len(A[0])):			r.append(tmp[i*len(A[0]) + j])		result.append(r)	return result
dict_traversal = {	1: spiral,	2: revspiral,	3: sinwaveform,	4: helical,	5: revhelical}#####################################################
enc =  # REDACTED
# Create lookup tables for all permutationsdef qn(n=100):    lookup = list(range(n**2))    res = []    for it in tqdm.tqdm(itertools.permutations(range(1, 6))):        B = [lookup[i:i+n] for i in range(0, n**2, n)]        for i in it:            B = dict_traversal[i](B)        B = sum(B, [])        B = [B.index(i) for i in range(n**2)]        res.append([B[i:i+n] for i in range(0, n**2, n)])    return res
def apply_lookup(A, lk):    n = len(A)    A = sum(A, [])    lk = sum(lk, [])    return [[A[j] for j in lk[i:i+n]] for i in range(0, n**2, n)]
kk = qn()  #  Around 6 mins, can be cached
# Look-up table for ec partrev = [[None for i in range(256)] for j in range(256)]for i in range(256):    t = i*G    rev[t.x][t.y] = chr(i)
for i in tqdm.trange(99, -1, -1):    CC = circulant([0]*i + [1] + [0]*(100 - i - 1))    B = multiply(enc[1], CC)    for lk in kk:        BB = [x[::] for x in B]        BB = apply_lookup(BB, lk)        BB = sum(BB, [])        s = ''        for x in BB:            s += bin(x)[2:].zfill(3)        m = ''        for j in range(0, len(s), 16):            px, py = int(s[j:j+8], 2), int(s[j+8:j+16], 2)            if rev[px][py] is not None:                m += rev[px][py]                continue        if 'CCTF' in m:            print(m)            break```
And this is the output, a paragraph from [`Our Lady of Fátima`](https://en.wikipedia.org/wiki/Our_Lady_of_F%C3%A1tima#Marian_apparitions).
> Beginning in the spring of 1917, the children reported apparitions of an Angel, and starting in May 1917, apparitions of the Virgin Mary, whom the children described as the Lady more brilliant than the Sun. The children reported a prophecy that prayer would lead to an end to the Great War, and that on 13 October that year the Lady would reveal her identity and perform a CCTF{Elliptic_Curv3_1s_fun_&_simpLE_Circulaitng_it_make_it_funnier!!} so that all may believe. Newspapers reported the prophecies, and many pilgrims began visiting the area. The children's accounts were deeply controversial, drawing intense criticism from both local secular and religious authorities. A provincial administrator briefly took the children into custody, believing the prophecies were politically motivated in opposition to the officially secular First Portuguese Republic established in 1910.[6] The events of 13 October became known as the Miracle of the Sun...
### Flag
`CCTF{Elliptic_Curv3_1s_fun_&_simpLE_Circulaitng_it_make_it_funnier!!}`