Skip to content

Latest commit

 

History

History
254 lines (196 loc) · 6.66 KB

README.md

File metadata and controls

254 lines (196 loc) · 6.66 KB
Raw

加密算法和解密算法

小赵听到自己还要给自己出的题目写 write up 感到十分震惊——明明那么简单的题目，write up 还要出题人来写。不过，小赵还是硬着头皮把 write up 写完了。

寻找规律

这道题涉及的 BrainFuck 代码看似复杂，实际上如果仔细分析，可以发现大部分代码都是有规律可循的。

我们首先得知 BrainFuck 虚拟机元素的初始值都是零：

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

我们打开encrypt.bf，将整段代码按循环（一对匹配的[]对及其中间的部分）分段：

,
[->>+++++++>>+++++>>+++>>++>>++++>++++++<<+++<<+++++++++<<++++++++<<++++++<<++++++++<]
>
[->>+++++>>+++++++++>>+++++++++>>++>>++++<+++++++++<<++++<<++++<<++<<++<]
<,
[->>+++++>>++++++++>>++++++>>+++++++>>+++++++>++++++<<++++++<<++++++++<<+++<<+++<<++++++++<]
>
[->>++++++++>>+++>>+++++++>>++++>>+++++++++<++++++<<+++++++++<<++<<+++++++++<<++++++++<]
<,

etc

然后我们从第一段开始：

,

这段只有一个字符的代码读入一个值，我们不妨设它为a1。现在 BrainFuck 虚拟机情况如下：

a1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

然后我们进入循环：

[
    -
    >>
    +++++++
    >>
    +++++
    >>
    +++
    >>
    ++
    >>
    ++++
    >
    ++++++
    <<
    +++
    <<
    +++++++++
    <<
    ++++++++
    <<
    ++++++
    <<
    ++++++++
    <
]

经过一次循环后的虚拟机情况如下：

a1-1 8 7 6 5 8 3 9 2 3 4 6 ...

指针回到a1-1处，我们可以得出这个循环还要进行a1-1次，共a1次，最后虚拟机情况如下：

0 8*a1 7*a1 6*a1 5*a1 8*a1 3*a1 9*a1 2*a1 3*a1 4*a1 6*a1 0 0 0 ...

然后下一段：

>

指针向右一格，停在8*a1处。然后进入下一个循环：

[
    -
    >>
    +++++
    >>
    +++++++++
    >>
    +++++++++
    >>
    ++
    >>
    ++++
    <
    +++++++++
    <<
    ++++
    <<
    ++++
    <<
    ++
    <<
    ++
    <
]

我们可以得知这个循环将会进行8*a1次，和上面的循环一样，我们将增量代入，最后结果如下：

0 0 23*a1 46*a1 21*a1 80*a1 35*a1 81*a1 34*a1 19*a1 76*a1 38*a1 0 0 0 ...

接下来的指令是：

<,

首先将指针向左一格到最左点，然后读入一个字符，不妨设为a2：

a2 0 23*a1 46*a1 21*a1 80*a1 35*a1 81*a1 34*a1 19*a1 76*a1 38*a1 0 0 0 ...

然后接着进行上面的两组循环。这样的操作一共进行十轮，共二十次循环。

最后的代码段将每个元素加上一个固定的值输出：

>++.
>++++++.
>++++++++.
>++++++++.
>+++.
>+++++.
>+++++.
>+++++++.
>++++.
>+++++++++.

通过分析我们实际上可以发现，这就是对a1...a10十个数组成的一次线性变换，当然如果算上最后加上一个固定的值输出的话就是仿射变换。

如果我们设输出为b1...b10的话，我们的目标是找到一个十一维的矩阵A_(11x11)满足：

[b1, b2, ..., b10, 1] = A_(11x11) * [a1, a2, ..., a10, 1]

实际上每一轮操作除了+的数量不同，代码形式是一模一样的，我们只需要将代码中连续的+序列分离并分组，然后依次处理就可以了。

提取数据

我们编写一段 Python 脚本提取出整个矩阵（为方便后续运算，运算结果为A_(11x11)的转置）：

import re

def to_matrix(code):
    i = re.compile("[+]+").finditer(code.replace("\n", ""))
    m = [[0 for k in range(11)] for j in range(11)]
    for j in range(10):
        for k in [0, 2, 4, 6, 8, 9, 7, 5, 3, 1]:
            m[j][k] += len(next(i).group(0))
        factor = len(next(i).group(0))
        for k in [1, 3, 5, 7, 9, 8, 6, 4, 2, 0]:
            m[j][k] += factor * len(next(i).group(0))
    for k in range(10):
        m[10][k] += len(next(i).group(0))
    m[10][10] = 1
    return m

以下是输出：

[[23, 46, 21, 80, 35, 81, 34, 19, 76, 38, 0],
 [69, 67, 80, 27, 22, 64, 79, 38, 55, 78, 0],
 [40, 40, 63, 69, 66, 51, 74, 52, 41, 43, 0],
 [61, 54, 33, 53, 43, 46, 52, 72, 68, 59, 0],
 [47, 31, 60, 37, 68, 37, 27, 49, 39, 55, 0],
 [21, 23, 26, 81, 36, 44, 19, 71, 62, 74, 0],
 [62, 54, 39, 24, 67, 75, 38, 36, 48, 50, 0],
 [73, 75, 32, 61, 22, 77, 79, 40, 65, 18, 0],
 [18, 64, 48, 23, 58, 71, 30, 60, 21, 36, 0],
 [81, 69, 39, 50, 37, 18, 68, 45, 66, 77, 0],
 [ 2,  6,  8,  8,  3,  5,  5,  7,  4,  9, 1]]

整理算法

有经验的参赛成员应该能够发现这正是希尔密码（Hill Cipher）的一个变种。当然了，如果没有经验，此时也应能想到下一步是求这个矩阵的逆。不过，在题目中也有说明，矩阵的运算结果需要对 64 取余。因此这个矩阵不是定义在实数域（R）上的，而是定义在整数模 64 环（可记为Z_64）上的。

求矩阵的逆的直接方法无非求解伴随矩阵，再除以矩阵的行列式共两步。当然一些库是可以直接对某个整数模 n 环（可记为Z_n）求逆的（比方说 SymPy 的inv_mod）。

以下是待求矩阵的逆（同样经过转置）：

[[ 2, 17, 34, 57, 17, 45, 15, 61, 45, 24, 0],
 [ 0, 20, 38, 43, 56, 29, 34, 41, 29, 61, 0],
 [29,  3, 25, 25, 32, 57, 22,  4, 32, 52, 0],
 [41, 63, 22, 19, 49, 32,  4, 22, 40, 18, 0],
 [27, 24, 11, 11,  2, 15, 57,  9, 36,  4, 0],
 [26, 55, 52, 10, 10, 54, 32, 37, 52, 28, 0],
 [14, 31, 12, 60, 47, 44, 53, 41, 19, 13, 0],
 [ 3, 53, 16, 51, 53, 11, 48, 35, 49, 28, 0],
 [25, 26,  8, 57, 51, 30, 62, 17, 53,  0, 0],
 [25, 37, 46, 19, 52, 53, 24, 18, 31, 12, 0],
 [25, 56, 17, 57, 16, 55, 18,  4, 39, 41, 1]]

求解答案

最后 transform 一下输入输出就大功告成了。以下是本人编写的 Python 代码：

import sympy

def decrypt(matrix):
    base64_mapping = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"

    def to_output(output):
        transformed_output = output[:4, :10]
        return "".join([base64_mapping[o % 64] for o in transformed_output])

    def from_input(input):
        transformed_input = [base64_mapping.index(i) for i in input]
        return sympy.Matrix(4, 10, transformed_input).row_join(sympy.ones(4, 1))

    inv_matrix = sympy.Matrix(matrix).inv_mod(64)
    return lambda input: to_output(from_input(input).multiply(inv_matrix))

整个 Python 代码位于encryption_and_decryption_solution.py中。

彩蛋

其实这道题的加解密函数存在一个刻意加入 （但却毫无意义） 的不动点，请参阅附带的 Python 代码（^_^）