[Crypto] 3dlight - CirQ

xp0int Posted on May 2 2018

准确来说更像一道ppc而不是crypto，需要根据所给的一个8x8x8的网格恢复64字节的字符串，研究题目就花了好半天，最后很幸运地拿到了一血，也算是有所收获了。

根据题意，将一个64字节的字符串写成8x8的方格，每个字节按8位表示，最终被编码成8x8x8的三维01矩阵，这个空间中写作1的点代表一种光源，会向其自身以及上下左右前后六个方向发射光线，光照强度随距离线性递减，光源的强度被写死为2，就是说，光源自身的brightness是2，离它曼哈顿距离为1的点brightness是1，再往后就没了。brightness是可以叠加的，也就是说，一个点的brightness是有自身以及周围6个点的光照强度的和。512个点的brightness加起来重新编码就是最终发送的字符串。

power是2的话对于解题算是比较简单的，可以直接把所有原来的for循环都展开，便于分析。这次在写代码的过程中也发现了，python真的可以写的十分直观，把一些重复用到的代码封装成函数，那么代码可以写的很像自然语言（其实其他编程语言应该也可以）。

为了便于理解，先把所有的三维空间的点分成三组：一定是非光源（记为dark），一定是光源（记为light），未知（记为unknown），最终的目标就是**把所有的unknown的点都标记为dark或light**，一开始则是所有的点都是unknown的。先从找trivial cases开始。一开始，有一些点肯定是dark或light的，可以总结出这四条规则：

1. 对于brightness=8的点，他自身肯定是light，并且他周围6个点肯定是light，这样亮度加起来才能成为8；
2. 对于brightness=0的点，他自身肯定是dark，并且他周围都是dark，理由同上；
3. 对于brightness=7的点，他自身肯定是light，周围肯定有一个dark，但不能确定是哪一个点；
4. 对于brightness=1的点，他自身肯定是dark，但无法确定周围哪一个是light。

其实根据这个发现，一开始就能找出几十个已知点了，然后就可以迭代查找剩下的点，直到所有点都known为止，这里又是另外的四条规则：

1. 如果自身是dark，且周围的light和unknown加起来刚好等于brightness，那么就可以确定这些unknown全是light；
2. 自身dark，且周围的light数已经等于brightness了，那么其余的unknown全是dark；
3. 自身light，且周围的light数加自身刚好是brightness，那么周围的unknown都是dark；
4. 自身light，且周围的light和unknown加自身等于brightness，那么周围的unknown都是light。

靠着四条规则就能够一直跑到全部找出来为止，实际上跑的过程中大概每次都要经理四至五轮的遍历，时间上来说挺快的，毕竟也才512个点～

```python
# -*- coding: utf8
from pwn import *

context.log_level = 'error'

def str2arr(str):
    ret = [[[0 for _ in xrange(8)] for _ in xrange(8)] for _ in xrange(8)]
    for i in xrange(8):
        for j in xrange(8):
            for k in xrange(8):
                ret[i][j][k] = ord(str[64*i+8*j+k])
    return ret
def str2arr_(str):
    return [[[(ord(str[i * 8 + j]) >> k & 1) for k in xrange(8)] for j in xrange(8)] for i in xrange(8)]

def arr2str(arr):
    s = ''
    for i in range(8):
        for j in range(8):
            s += chr(int(''.join(map(str, arr[i][j][::-1])), 2))
    return s
def arr2str_(arr):
    ret = ''
    for i in xrange(8):
        for j in xrange(8):
            for k in xrange(8):
                ret += chr(arr[i][j][k])
    return ret

def pprint(arr, lmap=None):
    for i in range(8):
        for j in range(8):
            for k in range(8):
                if lmap:
                    print '%d %d  ' % (arr[i][j][k], lmap[i][j][k]),
                else:
                    print arr[i][j][k],
            print ''
        print ''
    print ''

six_directions = [(-1,0,0), (1,0,0), (0,-1,0), (0,1,0), (0,0,-1), (0,0,1)]

def recover_by_dark(arr):
    light_hash = { c:set() for c in range(9) }
    for i in range(8):
        for j in range(8):
            for k in range(8):
                light_hash[ arr[i][j][k] ].add( (i, j, k) )

# 0 for dark, 1 for light, 2 for unknown
    light_map = [[[2 for _ in range(8)] for _ in range(8)] for _ in range(8)]
    
    def label(x, y, z, t):
        if 0<=x<8 and 0<=y<8 and 0<=z<8:
            if t == 'dark':
                light_map[x][y][z] = 0
            elif t == 'light':
                light_map[x][y][z] = 1
            else:
                raise ValueError('label must be dark or light not "{}"'.format(t))

def neighbor(x, y, z, t):
        all_flag = t == 'all'
        if t == 'dark':
            i = 0
        elif t == 'light':
            i = 1
        elif t != 'all':
            raise ValueError('label must be all, dark or light not "{}"'.format(t))
        ret = set()
        for a, b, c in six_directions:
            if 0<=x+a<8 and 0<=y+b<8 and 0<=z+c<8:
                if all_flag or light_map[x+a][y+b][z+c] == i:
                    ret.add( (x+a, y+b, z+c) )
        return ret

def check(x, y, z, t=None):
        if 0<=x<8 and 0<=y<8 and 0<=z<8:
            if t is None:
                str_map = ['dark', 'light', 'unknown']
                return str_map[light_map[x][y][z]]
            if t == 'dark':
                return light_map[x][y][z] == 0
            elif t == 'light':
                return light_map[x][y][z] == 1
            else:
                raise ValueError('label must be dark or light not "{}"'.format(t))
        return False

def all_known():
        for x in range(8):
            for y in range(8):
                for z in range(8):
                    if light_map[x][y][z] == 2:
                        return False
        return True

for x, y, z in light_hash[8]:   # 亮度为8时，自己肯定是灯，且周围也都是灯
        label(x, y, z, 'light')
        for a, b, c in six_directions:
            label(x+a, y+b, z+c, 'light')
    for x, y, z in light_hash[7]:   # 亮度为7时，自己一定是灯，但周围有一个没灯
        label(x, y, z, 'light')

for x, y, z in light_hash[0]:   # 亮度为0时，自己肯定没灯，且周围也都没灯
        label(x, y, z, 'dark')
        for a, b, c in six_directions:
            label(x+a, y+b, z+c, 'dark')
    for x, y, z in light_hash[1]:   # 亮度为1时，自己肯定没灯，且周围有一个灯
        label(x, y, z, 'dark')

while True:
        for lightening in light_hash:
            for x, y, z in light_hash[lightening]:
                dark_n = neighbor(x, y, z, 'dark')
                light_n = neighbor(x, y, z, 'light')
                un_n = neighbor(x, y, z, 'all').difference(dark_n).difference(light_n)
                print x, y, z, ' ', arr[x][y][z], check(x, y, z)
                print 'dark neighbor', dark_n
                print 'light neighbor', light_n
                print 'unknown neighbor', un_n, '\n'

# 规则1，自身没灯，且周围有灯和未知的数量刚好等于亮度，则所有未知都是有灯
                if check(x, y, z, 'dark') and len(light_n.union(un_n))==arr[x][y][z]:
                    for x1, y1,z1 in un_n:
                        label(x1, y1, z1, 'light')

# 规则2，自身没灯，且周围有灯的数量刚好等于亮度，则所有未知都是没灯
                if check(x, y, z, 'dark') and len(light_n)==arr[x][y][z]:
                    for x1, y1,z1 in un_n:
                        label(x1, y1, z1, 'dark')

# 规则3，自身有灯，且周围有灯的数量加自身刚好等于亮度，则所有未知都是没灯
                if check(x, y, z, 'light') and len(light_n)+2==arr[x][y][z]:
                    for x1, y1,z1 in un_n:
                        label(x1, y1, z1, 'dark')

# 规则4，自身有灯，且周围有灯和未知的数量加自身刚好等于亮度，则所有未知都是有灯
                if check(x, y, z, 'light') and len(light_n.union(un_n))+2==arr[x][y][z]:
                    for x1, y1,z1 in un_n:
                        label(x1, y1, z1, 'light')

if all_known():
            print 'ura!!!'
            return light_map
        else:
            print 'not yet'

#pprint(arr, light_map)

def main():
    p = remote('123.59.138.211', 20000)

p.recvuntil('ciphertext is : ')
    ef = p.recvline(keepends=False).decode('hex')
    arr = str2arr(ef)
    assert arr2str_(arr) == ef

#pprint(arr)

lmap = recover_by_dark(arr)
    s = arr2str(lmap)
    f = ''.join( s[i]+s[len(s)-i-1] for i in range(0, len(s), 2) )
    print f

main()
```

大概可以说这次的代码是个人写的最满意的一次吧，最后flag是：
![enter image description here](https://leanote.com/api/file/getImage?fileId=5ae85fe9ab64414542000dd5)

把大括号后面的填充字符都去掉就是了。

打赏还是打残，这是个问题