# fibinary

[top](https://hackmd.io/tX_tkXceT0WY2Oq_F78qUw)

205pt

Problem
---
Warmup your crypto skills with the superior number system?

# enc.py

fib = [1, 1]
for i in range(2, 11):
	fib.append(fib[i - 1] + fib[i - 2])

def c2f(c):
	n = ord(c)
	b = ''
	for i in range(10, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			b += '1'
		else:
			b += '0'
	return b

flag = open('flag.txt', 'r').read()
enc = ''
for c in flag:
	enc += c2f(c) + ' '
with open('flag.enc', 'w') as f:
	f.write(enc.strip())

Output
---

# flag.enc
10000100100 10010000010 10010001010 10000100100 10010010010 10001000000 10100000000 10000100010 00101010000 10010010000 00101001010 10000101000 10000010010 00101010000 10010000000 10000101000 10000010010 10001000000 00101000100 10000100010 10010000100 00010101010 00101000100 00101000100 00101001010 10000101000 10100000100 00000100100

Solver
---

flagの文字を10進で表した時の値をnとして、fibonacchi数列の10~0と比べて大きければ1,小さければ0とする長さ１１の01の列としてflagの文字ごとに計算して暗号化？している
因みにfib(11)までのfibonacci数列は$\{1,1,2,3,5,8,13,21,34,55,89\}$である。
ex) 文字`c`の時
`c`をAsciiの10進表現に変換すると、`99`であるから`n=99`
b=''
89: n>=89 #n-=89 -> n=10 b+='1'
55: b+='0'
34: b+='0'
$\vdots$
8 : n>=8 #n-=8 -> n=2 b+='1'
$\vdots$
2 : n>=2 #n-=2 -> n=0 b+='1'
1 : b+='0'
1 : b+='0'
=> b='10000100100'

となっている。
これは線型変換なので、逆変換を行う
処理を見ると、01の列の`1`の時にfib(i)をnから引いている
つまり、上の例では$n-89-8-2=0$という処理をしているから、$n=89+8+2=>99$のように逆の処理をすれば良い

# solver.py

fib = [1,1]
for i in range(2,11):
    fib.append(fib[i-1]+fib[i-2])

def dec(c):
    m=0
    for i in range(0,11):
        if c[i]=='1':
            m+=fib[10-i]
    return m
        
cipher = open('flag.enc','r').read()
m = ''
for c in cipher.split(' '):
    m+=chr(dec(c))

print(m)

Flag
---
:tada:　corctf{b4s3d_4nd_f1bp!113d}
###### tags: `CTF` `corCTF` `crypto`