Brainfuck 语言实现 ChaCha20 加密算法并输出声音

ChaCha20 是一种电子密码，被认为能够抵御高级对手的攻击。它通过对一个 4x4 的 32 位整数矩阵进行运算，计算出一个伪随机比特流，即密钥流。

其核心是四分之一轮函数，它接收四个变量并按如下方式揉合：

a = a 加 b，d = d 异或 a，d = d 循环左移 16 c = c 加 d，b = b 异或 c，b = b 循环左移 12 a = a 加 b，d = d 异或 a，d = d 循环左移 8 c = c 加 d，b = b 异或 c，b = b 循环左移 7

这个四分之一轮函数被应用到矩阵的每一列，构成一轮。第二轮将同样的四分之一轮函数应用到矩阵的每一条对角线。后续的轮次在列和对角线之间交替进行。

初始时，这个矩阵包含密钥、块计数器、nonce（一次性数字）和一个密码级常量。在 ChaCha20 中，会对矩阵应用 20 个这样的轮次。由于所有这些轮次都是可逆的，最后一步将初始矩阵加到最终结果上。最终的矩阵构成密钥流。这个密钥流随后与明文进行 XOR 运算，生成密文。

Brainfuck 无需介绍。它的极简主义和不够成熟的名字让它人尽皆知。这门语言由一条用于内存的纸带、输入输出流以及八条控制它们的指令组成。

但把两者结合起来会怎样？在编写了超过 14 万条 Brainfuck 指令之后，我呈现这个 Brainfuck ChaCha 加密器。我建议你现在就启动它。源码可以在这里找到。

必须开启 JavaScript 才能运行。

已执行 0 条指令 a b c d 点击开始以启动

核心需要 85 个八位字节的内存：1 个用作双轮计数器，20 个用于临时数据，64 个用于状态矩阵。实际加密还需要更多一些用于初始矩阵。

Brainfuck 的特性足以实现图灵完备性——这个性质，粗略地说，意味着只要有足够的时间和内存，任何可计算的东西都能被找到。然而在实践中，图灵完备性带来的好处并不多。你不需要图灵完备性来编写 ChaCha20 实现、路径追踪器或键盘控制器。我们几乎总是处理这类实际有限的问题。

另一方面，图灵完备性带来了停机问题形式的缺陷：不可预测的执行、内存使用、对编译器缺乏保证等等。我们不需要会崩溃的图形加速器。

简而言之，图灵完备性并不意味着实用性。你稍后会明白我的意思。

ChaCha20 及其前身 Salsa20 属于所谓的 ARX 密码，也就是说它们只使用加法、旋转和 XOR 进行运算。这自然使 ChaCha20 对软件友好，不像 AES 需要硬件加速才能在速度上有竞争力。然而 Brainfuck 只有字节级别的递增和递减，这使得它对两者都不友好。我还是选择了 ChaCha20，因为它的普及性，也因为一个只有加法的密码安全性极低。如你将看到的，ChaCha20 的一整轮已经让它对人眼来说显得随机，但我们只从 8 轮起才对其安全性有信心。

尽管 Brainfuck 有递增指令，加法却是最慢的部分。这得怪我，因为算法是我自己写的。它先加最高八位字节，然后加次高八位字节并处理一层溢出，再加第三八位字节并处理两层溢出，依此类推。每次递增都需要一次溢出测试，以便进位到下一个八位字节，而我选择的特定测试每次都需要复制该八位字节两次（这就是你有时会听到的“pew.. pew pew pew”声）。我相信可以做得更好，但我尽量减少了外部影响。

此外，对于可变的输入，Brainfuck 的执行时间变化极大。考虑代码 [-]。如果纸带头指向非零值，我们会执行 - 并递减该值。之后我们执行 ]，如果值仍然非零，就跳回 [。这个循环一直持续到值为零，但从 255 到 0 比从 1 到 0 花费的时间更长。出于同样的原因，复制较大的值也更慢，尽管所有这些值占用相同的内存量。Brainfuck 实现可能会识别某些模式并优化它们，但终究还是有个问题。

精通信息安全或密码学的人会明白我的意思。让我确认你的直觉：基本上没有什么是常数时间的。这在理论上使该实现充满了基于时序的信息泄漏。我敢说泄漏多到绝对没人会费心去分析？我在开玩笑，但这是个有趣的想法。我不是密码学家。总之，这样的缺陷通常会导致不鼓励在线使用，比如用于保护 Brainfuck 静态 HTTP 服务器。别为此怪我。

在 ChaCha 中，一半的轮次作用于矩阵的列，一半作用于对角线。这里只展示了一整轮，因为否则会花太长时间。Beef 在我的电脑上以全速跑完一轮需要整整 0.3 秒。各个操作是以自包含的方式编写的，所以有相当多的冗余复制。

密码核心随后被用于一个实用程序 sest.bf，它最初接收一个密钥作为输入，然后持续接收明文并输出密文。另一个问题是，由于单元只能存储 0..255，, 指令（从输入流读取）没有一种愉快的方式来表示 EoF。有些实现给出零，这对可读文本有效但对二进制数据不行。有些给出 -1，这有其他的优缺点。有些根本不更新单元。最终我让这个实用程序持续接收输入，直到被显式终止。ChaCha20 不需要某种“终止信号”，所以我认为那是最好的方案。

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）