Tags: ecc reversing
Rating:
## 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 Curve
from fastecdsa.point import Point
import math, random
from flag import flag
import 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 enc
print("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
```python
from Crypto.Util.number import *
import itertools
import tqdm
from fastecdsa.curve import Curve
from fastecdsa.point import Point
import 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 permutations
def 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 part
rev = [[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!!}`
