
Wayland has been around for years, and as a person who re-reads _Unix Haters Handbook_ every few occasion I've never been a fan of X11. That being said, due to the afraid of breaking my current setup I'm still stuck with X until this holiday.

What happened this holiday? I've finally dropped X and moved to the wayland. This post is a collection of things I think worth noting in the process.

## Original Setup

Before moving on, let's review the setup I had with X, and why I was reluctant to move to wayland.

On my main workstation I have three 1080p monitors: one in the center, placed horizontally, for **writing** codes and place terminals to see the result. The other two are placed left and right, both vertically, for **modifying** codes, and looking at documents.

With this setup, I need a window manager that deals with multi-head nicely, and don't require me to move my hands off the keyboard a lot to arrange windows. I've been hoping around all kinds of wms in the past years, and lastly settled on [i3](https://i3wm.org).

i3 is wonderful.

It manages multiple monitors well: I can bind a workspace to a specific monitor, and switch to that monitor by pressing a key combination. Also it's a tilling wm, which means I can do most of window positioning simply by moving window up/down/let/right with keyboard, and don't require intervention with a mouse. In fact, on my desk-side FreeBSD server I'm running another i3 setup. This server doesn't have a mouse connected at all, and I've never felt any inconvience. It's also perfectly configurable, and based on a IPC model just like wmii (it's wmii-i, hence named i3), which suits me well as I was that kind of kid who will tear down every toy I got.

Another thing is that I have been an emacs user since the day I first coded Hello world in C++. What further complexes the problem is that I'm the kind of heretic who uses [evil](https://github.com/emacs-evil/evil). What? I like the vim style mode switching and edit commands. This setup means I need to access both CTRL and ESC very, very frequently. My answer to this is two commands: `setxkbmap -option 'ctrl:swapcaps'` and `xcape -e 'Control_L=Escape` (hell, I can even recite those two commands when writing this blog). This enable me to use CAPSLOCK as **both** CTRL and ESC, which reduced a significant amount of hand movement while coding.

Unfortunately, this wonderful setup that has been working for me for years is now also blocking me from moving to wayland. I would hate having to configure my wm all from scratch. wayland does not use xinput (since it's not an X11 server), so `setxkbmap` and `xcape` is useless.

## Sway: A drop-in replacement for i3

As stated in the last paragraph, one of the things that blocking me from moving to wayland is I don't want to reconfigure my wm all from scratch.

Luckily, I found out that I don't have to. Introducing [Sway](https://swaywm.org), a drop-in replacement for i3 on wayland.

To be honest, when I first attempted it I expected to ran into all sorts of compatibility issues. After all, it's a transition to a whole new different graphical stack, you can't really expect it to run with an config file for i3, right?

WRONG.

I was astonished when I switch to a tty and typed `sway`, and **it was literally running on my `~/.config/i3/config` with no visible issue**. This drastically improved my confidence on the plan.

Of course, there's a few more things needs addressing before announcing the transition complete. When using Xorg the monitor and input device is managed by X server, so you use `xrandr` to layout displays and `xinput` to tweak input settings. However, wayland is not a **display server**, rather it's a **protocol**. So all those things are now being handled by the **compositor**, or sway in our case. Obviously, that means we need to tell sway how to layout displays and setup inputs.

Luckily, this was easy enough: just a few more lines in sway config file. For my setup it looks like this:

```
output DP-1 {
	pos 1080 315
	bg $HOME/Images/backgrounds/central.jpg fill
}

output DP-4 {
	pos 3000 0
	transform 90
	bg $HOME/Images/backgrounds/right.jpg fill
}

output DP-5 {
	pos 0 0
	transform 270
	bg $HOME/Images/backgrounds/left.jpg fill
}
```

This is just a literal translation from my original xrandr commands.

## Interception tools: works even better than setxkbmap & xcape

Now that we've got a perfect replacement for i3, let's deal with another issue: the CAPSLOCK on my keyboard. Like I said earlier, on wayland it uses a different input model than X, so `setxkbmap` and `xcape` no longer works for us.

This actually is the main reason that blocked the switch for me, since under the model of wayland this feature has to be implmented by the compositor, and hardly any upstream will be willing to implement such a weird feature. So this means we'll have to patch the compositor.

Or is it really?

There's actually another way to solve the issue: deal with it on a lower level of abstruction, before X server or wayland compositor comes to play. More specifically, deal with it on the level of `libevdev`.

There is a tool designed exactly for this job: [Interception Tools](https://gitlab.com/interception/linux/tools). Check it out, it's even in the community repo of archlinux.

It works by intercepting libevdev events, modify it, and then feed the modified event to X server or wayland compositor. And it comes with an official plugin called `caps2esc`, which you can tell from the name, does exactly what we want.

To achieve our intention, we need to write a `udevmon` configuration, which will monitor events for us, and dispatch them to interception tools for alteration when desired. My config is as follows:

```
- JOB: "intercept -g $DEVNODE | caps2esc -m 3 | uinput -d $DEVNODE"
  DEVICE:
    EVENTS:
      EV_KEY: [KEY_CAPSLOCK, KEY_ESC]
```

If you are familiar with the syntax of piping in sh (you uses linux so I assume you do), you can probably tell what this does: it intercepts events from keyboard, send it to `caps2esc`, then send the result back to upper applications. Pretty easy to understand, right?

Except you've copied this config and found out it doesn't really work.

That's because the offical version of caps2esc doesn't have a `-m 3`. It's a customized mode patched into it by myself: CAPSLOCK works as both ESC and CTRL, and **Right CTRL** as CAPSLOCK.

The reason for this patch is that I need both Left CTRL and ESC untouched for gaming (yes, there exists a [game](https://www.finalfantasyxiv.com) in which you need to spam ESC), and I need CAPSLOCK when entering my passwords. I'm not going into detail on how I've done the patch since it's pretty straightforward (check the [commit](https://github.com/MosakujiHokuto/caps2esc/commit/6a9aa6aca7e46a73e295a0c252e83b2ed84efdf4), you'll get it if you have almost any experience in C), and it's just a customization for my own setup.

Switching to interception tools have another benefic: The key swap now works even with the display manager, unlike previously it only works after I've logined into desktop, so it's actually more of an improvement than replacement.

## Finishing the switch

For me there's only one small imperfection left: lightdm somehow doesn't work with sway, or wayland sessions in general. Instead of doing some crazy patching to make lightdm work, I choosed to replace it with SDDM instead.

I've never been a fan of KDE or QT ecosystem. I've been using Archlinux and Gentoo as my daily drive for almost ten years, so obviously I don't like things that are considered bloated, and by my standard KDE is pretty bloated.

Lucky for me, SDDM actually don't have that much dependency on KDE Plasma, so I can accept that. There's plenty of documentation on how to setup SDDM, so I won't go to detail here, other than announcing **it works**.

And now I finally got rid of X11 completely (well not really, if you take xwayland into account), and embraced the future of Linux Desktop!

Embracing the future: Wayland trasition note


身为一个时不时就把《Unix 痛恨者手册》翻出来读一遍的人，我自然不是什么 X 的过激厨。不过尽管如此，Wayland 出来了这么多年，我也一直没勇气尝试迁移过去。毕竟现有配置用得好好的，何必冒风险去折腾呢？

所以我也不知道为什么这个假期我突发奇想，决定把这项一直以来搁置的任务重新搞起来。这边文章便是我折腾过程中的一点拾遗。

## 起点：X 下的配置

在进行迁移之前，我们自然要先回顾一下原本的配置，毕竟这样我们才知道我们要做什么，以及我为什么拖了这么久才来做这件事。

我的主力工作站用的是三屏幕配置：中间的显示器横放，用来**写**代码以及进行编译查看运行结果。省下两个显示器一左一右竖放，用来**改**代码以及看文档。所以我自然需求一个能完美处理多显示器的 WM。同时考虑到这个配置的显示面积，我还需要这个 WM 能少让我用鼠标调整窗口位置，不然我会需要反复把手从键盘上挪开。

以往我尝试过不少窗口管理器，比如说中规中矩的 openbox，还有前几年流行过一阵的 awesome。不过近期我还是选择了 i3 —— 毕竟 i3 真的很好用。

i3 可以完美地解决多显示器问题：你可以把某个工作区绑到特定的显示器上，这样只要切换工作区同时也便切换了显示器；而且身为平铺式的 WM，绝大部分窗口布局操作都只需要用键盘把窗口上下左右移动，完全不需要鼠标介入。实际上我桌子底下就摆着一台 FreeBSD 服务器，上面跑着的就是 i3。这个服务器只接了键盘而没有接鼠标，也并没有什么不便。身为 wmii 的精神后继 (wmii-i，所以有 3 个 i)，这套基于 IPC 的配置也很对我的口味。

我的另一个需求则同我的编辑器选择相关。自从十数年前我用 C++ 写下第一行 Hello world 以来，我便是一个忠诚的 emacs 用户。当然或许在 emacs 原教旨主义者看来，我其实算是异端，毕竟我还用了 [evil](https://github.com/emacs-evil/evil) 来模拟 vim 的多模式编辑（没办法，hjkl 移动光标实在太方便了）。这自然意味着双重的折磨——我需要反复按下 CTRL **和** ESC 键。考虑到我并不打算添置一个脚踏板，我对这个问题采取了一个比较怪异的解决方式：用 `setxkbmap -option 'ctrl:swapcaps'` 和 `xcape -e 'Control_L=Escape'` (我甚至能把这两个命令背下来)把两个按键都绑定到 CAPSLOCK 上。

不幸地，这套配置虽然极大地方便了我在 X 下的开发工作，引入的依赖却也让迁移到 Wayland 麻烦了很多。我实在懒得重头学习和配置一个新的 WM，而且 Wayland 下 `setxkbmap` 和 `xcape` 也并没什么卵用。

## Sway: i3 的 drop-in 替代

上一段提到了，我不愿意切到 Wayland 的一个主要原因是实在懒得重新配置 WM 了。不过如果其实不需要完全从头配置呢？

还是看看远处的 [Sway](https://swaywm.org) 吧家人们。

老实说虽然官网将 Sway 吹成了 i3 的 drop-in 替代，不过我其实没指望这玩意真的能拿来就用。Wayland 和 X11 毕竟是差别极大的两套模型，这种情况下大概率还是会“请以实物为准”吧？

这就是为什么当我第一次启动 Sway，然后发现它开开心心地把 `~/.config/i3/config` 拿来用时感到无比震惊。它居然真的拿着 **i3** 的配置毫无鸭梨的跑了起来！

当然 Wayland 和 X 之间的模型差别决定了我们还是需要做一小点收尾工作。在 X 下，显示器和输入设备是由 X server 管理的，所以我们通常使用 `xrandr` 和 `xinput` 来配置这些东西。然而 Wayland 的模型和 X 不同：Wayland 是一个**协议**而非**显示服务器**，在 Wayland 模型下这些设备是由 **Compositor**，也就是 Sway 来管理的。所以我们需要告诉 Sway 如何管理这些设备。

不过这并不是什么麻烦事。我现在用的配置如下：

```
output DP-1 {
	pos 1080 315
	bg $HOME/Images/backgrounds/central.jpg fill
}

output DP-4 {
	pos 3000 0
	transform 90
	bg $HOME/Images/backgrounds/right.jpg fill
}

output DP-5 {
	pos 0 0
	transform 270
	bg $HOME/Images/backgrounds/left.jpg fill
}
```

这基本上就只是把 xrandr 的配置一直一句翻译过来。

## Interception tools: 比原先的配置更好用

既然 i3 的替代品找到了，现在我们可以去处理另一个问题了：大写锁定键。如前所述，因为 Wayland 和 X 的模型区别，`setxkbmap` 和 `xcape` 在 Wayland 下是用不了的。

其实这才是一直以来阻止我切到 Wayland 的主要原因。毕竟在 Wayland 下，这些设备都由 compositor 管理，所以要实现同样的效果，我们需要在 compositor 里实现这个 feature。这样的小众需求少有 compositor 愿意维护，指望上游提供自然是痴人说梦。难不成我们只能自己去 patch？

其实也未必。

我们可以调转一下思路：这个问题或许可以在 X 和 Wayland 以下更底层的地方解决。更准确地说，在 libevdev 的层面上解决。实际上有一个工具专为此而生：[Interception Tools](https://gitlab.com/interception/linux/tools)。这玩意甚至进了 archlinux 的 community 源。

这个工具可以在 libevdev 的层面上拦截输入事件，将其变换以后再喂给上层的应用。而且它甚至还有个官方插件叫做 `caps2esc`，从名字就能看出这个插件正是我们想要的。

要让这个工具跑起来，我们需要先配置一下 `udevmon`。`udevmon` 会监听 libevdev 的事件，将其传给插件做修改。我的配置如下：

```
- JOB: "intercept -g $DEVNODE | caps2esc -m 3 | uinput -d $DEVNODE"
  DEVICE:
    EVENTS:
      EV_KEY: [KEY_CAPSLOCK, KEY_ESC]
```

如果你熟悉 shell 的 pipe 语法的话（你都用 Linux 了，总该知道这个吧？），你应该能一眼看出这个配置的源里：拦截 libevdev 事件，丢给 `caps2esc` 处理，然后再喂给上层应用。浅显易懂吧？

然后你把配置抄了过去，发现并不能用。这是因为我的 `caps2esc` 其实是一个改过的版本。原版并没有 `-m 3` 这个选项，这个模式是我的自定义配置：CAPSLOCK 同时当作 ESC 和 CTRL用，而**右边 CTRL** 当作大写锁定。

之所以要费这一道事，是因为我需要保持左边 CTRL 和 ESC 不动，防止在游戏时按错键（离谱的是，真的有[游戏](https://adsrff.web.sdo.com/web1/)要你狂敲 ESC）。而且我在敲密码的时候也会用到大写锁定。我不打算展开讲解这个 patch ，毕竟这也不是个多复杂的修改（你只要有一点 C 的基础就能轻易地看懂这个 [commit](https://github.com/MosakujiHokuto/caps2esc/commit/6a9aa6aca7e46a73e295a0c252e83b2ed84efdf4)），而且反正这只是我的个人设置。

切到 Interception Tools 还有另一个好处：现在我的登录界面也可以用上这套按键配置了，而不用等到登录进了桌面才生效。

## 收尾工作

对我来说还有一小点额外的工作要处理：不知为何 lightdm 并不能很好地启动 Sway，还有其他基于 Wayland 的桌面。调研以后发现这个问题似乎并非特例，所以我也懒得花功夫去研究解决方案了，而是直接切到了 SDDM。

老实说我从来都不怎么喜欢 Qt 和 KDE 的生态。身为 Archlinux 和 Gentoo 的十年老粉，显然我不会太喜欢臃肿的软件栈；而在我眼里 KDE 足以称为臃肿。不过好在 SDDM 现在似乎对 KDE Plasma 并没有多少依赖，所以这个解决方案对我来说可以接受。SDDM 的配置教程在网上已经满天飞了，所以我并不打算再详细展开：总之，能用。

于是我终于完成了搁置已久的 Wayland 迁移，搭上了通往未来的新干线。不知道这个未来将去向何方？

Wayland 迁移笔记


It's been a long time since the last time I've written anything on this blog. Of course there can be a lot of excluses, like I had a pretty shitty year in 2022 (actually ever year since COVID has been shitty), but that doesn't change the fact that this blog needs some attention.

Well, let's give it some.

So I took my time in this holiday and gave it a complete overhaul. The blog system is now completely rewritten with [Next.js](https://nextjs.org), which allows me to code in Typescript & React. This enabled me to implement many new fancy features I can't or won't borther to implement with Hugo, like the ability to blog in multiple languages, as you can see with this post. It's probably the time to practice some more English so this can be Handly. Also I'm planning on implementing the ability to switch themes.

Also you can see this time I attempted a pretty different style on the site. It's mean to be an Retro Sci-Fi style theme inspired by TNO and VA-11, tho at the time of writing this theme obviously needs a lot more polishing. Also I'm planning on creating an amber colored version. I'm not an expert on art and UI design so the outcome might not be so good as to use a ready-made template, but it's my own blog anyway so what's the point to not attempt and fail?

The blog is hosted with Cloudflare Pages, and I'll probably write a note about it later. And in case you are curious, [code](https://github.com/MosakujiHokuto/blog-next) is hosted on github. Feel free to fork and use it for your own site (but there's plenty of good implementations so why this one?)

Blog Update Note: 2023/05/03


上次更新 Blog 似乎已经是很久很久以前的事情了。当然关于这件事情我可以找各种各样的借口：比如说去年对我来说算是相当糟糕的一个本命年（虽说自从新冠来临以后每一年都没好到哪去）。不过没更新就是没更新，无论借口多寡。

所以这个五一假期，我决定多花点时间把博客整个重写一下。这次我试着用了 [Next.js](https://nextjs.org)，于是我终于可以用 Typescript 和 React 来构建整个网站了。以往使用的 Hugo 实际上拖慢了我实现很多想法的步伐，比如说在这篇文章里你就可以见到的多语言功能（毕竟我也该花点时间练习一下英语了）。另外计划中还有一个切换主题的功能，敬请期待。

显而易见的是这次我在网站设计上采取了和以往完全不同的风格。我试着模仿了一下 TNO 和 VA-11 的 Retro Sci-Fi 风格。当然眼下这个主题还需要更多打磨，而且考虑到我并非专业的美工和设计师，成品的质量大概率远不如现成模板。不过既然都自己打博客了，用现成模板也未免太无趣了些，所以《管他呢》 。

这次我切换到了 Cloudflare Pages 来托管博客（就此我之后大概会写一篇更详细的贴子）。另外如果你好奇的话，[源码](https://github.com/MosakujiHokuto/blog-next)循惯例托管在 Github 上。项目里面我自己的代码都是 MIT 协议的，请随意使用。（不过有那么多好用的实现可选，你为什么要用这个？）

Blog 更新笔记：2023/05/03

思路整理：对于 illumos 上 SO_REUSEPORT 补丁的笔记


## 其之二 推古及今：古典密码与现代密码

与其他很多学科不同的是，始于70年代的现代密码学，并非是在古典密码学上平缓发展而来的学科，而是一次开天辟地式的飞跃。之所以说是“开天辟地式”，是因为我们直到那时候才开始真正体系化地运用数学手段对密码学建模。密码学的这个飞跃大概可以说是到来得惊人地晚。

而若以现代密码学的眼光回首望去，在这之前的古典密码学时代（哪怕是不到一百年前的20世纪初期），相比之下可谓是茹毛饮血——那时候的攻防手段基本还是基于语言文本的分析，而非如现代密码学一般基于信息论、离散概率以及其他数学手段。因为没有衡量安全性的手段，古典密码学里自然也无从对加密算法进行数学层面上的安全分析，加解密攻防不可避免地变成了猫鼠游戏式的勾心斗角。

但即便如此，认真回顾这个持续了数千年的古典时代也是极有价值的。以史为鉴，将能让我们更为清晰地认知到加密算法所面对的威胁，以及现代密码学所提供的数学手段的宝贵。

因此，虽说有老生常谈之嫌，本文仍将迅速地带领读者过一遍几种典型的古典密码。

## 其之二甲 以史为鉴：古典密码（上篇）

### 一点背景知识：术语科普

名不正则言不顺。在正式进行古典密码的科普之前，我们需要先储备点基础的密码学术语。

- 密码（Cipher）：进行加密或解密的算法。注意此语境下的密码为 Cipher 的翻译，而非通常汉语口语中由用户输入的 Password。
- 密钥（Key）：一串保密信息，用于指导密码（Cipher）对原文及密文进行变换。
- 明文（Plaintext）：未经加密的原始消息。
- 密文（Ciphertext）：明文经加密算法变换后的产物。
- COA，惟密文攻击（Ciphertext only Attack）：最严格的攻击模型。假定攻击者只能获得加密后的密文。此时攻击者的目标通常是获得明文，以及密钥；但在特定情况下，即使攻击者无法获得完整的明文，只要能得到关于明文的更多信息，也可算作成功。
- KPA，已知明文攻击（Known Plaintext Attack）：假定攻击者能够获得明文和与之对应的密文的攻击模型。此时攻击者的目标通常是获得密钥。
- CPA，选中明文攻击（Chosen Plaintext Attack）：假定攻击者能够自选任意明文，并获得对应密文的攻击模型。此时攻击者的目标通常是获得密钥。
- CCA，选中密文攻击（Chosen Ciphertext Attack）：假定攻击者能够自选任意明文，并获得对应解密后的明文的攻击模型。此时攻击者的目标通常是获得密钥。

注意以上名词并非局限于古典密码学——不如说这些名词在现代密码学里会被更广泛地应用。

在明确词义之后，我们终于可以开始讨论古典密码了。而最适合打头阵的，当然是替换密码。

### 替换密码

谈到“密码”二字，绝大部分人的第一反应恐怕都是替换密码。这东西原理很简单：设定一张替换表，其中每一个字母都会被一一映射到另一个字母上；加密时将明文中每一个字符按照映射替换成对应的字母，解密则只是简单地逆向映射。

顺嘴一提，我们可以将这个映射表看作密钥，只要能得到它，攻击便宣告成功。

这东西安全度如何呢？按照我们上面提到的四种攻击模型分别讨论一下：

CPA 以及 CCA：显然，无论我们手里的神谕机（Oracle）是加密神谕还是解密神谕，我们都只需要把所有字母灌进去，立刻就可以得到完整的映射表，不费吹灰之力。

KPA：取决于能够获得的明文长度，以及明文中不同字母的种类，我们至少能获得映射表的一部分。对于那些字母表不大的语言来说，恐怕不需要多长的明文就足够我们推出整张映射表。

COA：这里需要我们稍微动点脑筋。假设明文的语言已知的话，我们可以采用一点统计手段：大部分自然语言的字母出现概率并不随机。以英语为例，e 出现的概率会是最高的，所以只需要统计出密文中出现概率最高的字母，我们便可以大概率确定它与 e 互相对应。其他字母也可以根据明文的语言特征分析出来。具体的例子因为过于经典已经在各种密码学教程中烂大街了，在这里我不再赘述。

显然，替换密码的安全度并不高。

### 凯撒密码及其变体

严格来说，凯撒密码其实是更弱一些的替换密码，所以对于替换密码的攻击只会对凯撒密码更有效。不过鉴于凯撒密码实际上我们之后将要介绍的不少其他密码的基础构造之一，这里我还是把它单独拎出来讲一下。

凯撒密码的构造更为简单：将明文的每个字符按字母表顺序后移三位，即可得到密文。但仅仅如此的话，凯撒密码本身并不足以成为我们所讨论的密码（Cipher）：它没有密钥。这也是为什么本节的标题强调了“及其变体”：我们可以将这个构造略微扩展，令原本的后移三位变为后移 k 位，此时这里的 k 便可被视作密钥。

显然，要破解凯撒密码，我们只需要推出 k；而要推出 k，只需要推断出明文中任意一个字母于密文中所对应的字母，二者的距离即为 k。鉴于其本质仍是替换密码，运用针对替换密码的攻击手段推出密钥轻而易举。

能否对这个构造略微修改，使得它变得更加安全呢？

### 维吉尼亚密码

一点花边：维吉尼亚密码的名称来源于 Blaise de Vigenère(1523-1596)，但现今已知的对该密码的最早论述实际由 Giovan Battista Bellaso 于1553给出。

以英语为例，我先简单介绍一下维吉尼亚密码：

维吉尼亚密码的密钥是一个单词（或者说，一串固定长度的文本）。这里我们先选用一个充满酸味的密钥，"LEMON"。

给出一段任意长度的文本，我们先将明文字母和密钥对齐地写在上下两行。若密钥长度不足，则循环密钥补齐。例如，若我们需要加密 "ATTACKATDAWN":

<pre>
明文 ATTACKATDAWN
密钥 LEMONLEMONLE
密文
</pre>

然后，我们将明文中的每一个字母循环后移“密钥中对应字母的序数”位，（换言之，若密钥中对应字母是A，则后移0位；若密钥中对应字母是 B，则后移1位，依此类推）：

<pre>
明文 ATTACKATDAWN
密钥 LEMONLEMONLE
密文 LXFOPVEFRNHR
</pre>

以 C 语言实现的话：

```c
/* Assume ASCII */

char
encrypt_char(char c_plaintext, char c_key)
{
    return (c_plaintext - 'A' + (c_key - 'A')) % 26 + 'A';
}

/* Assume `out` has enough capacity to hold ciphertext */
void
encrypt(char *out, const char *plaintext, const char *key)
{
    size_t key_size = strlen(key), plaintext_size = strlen(plaintext);

    for (size_t i = 0; i < plaintext_size; ++i) {
        out[i] = encrypt_char(plaintext[i], key[i % key_size]);
    }

    out[plaintext_size] = '\0';
}
```

花点时间理解下这东西。好了吗？你能想出破解方法吗？

想不出来也没关系，毕竟这东西发明出来以后花了三百年才被破解。不过如果你还不想太早放弃的话，我可以给点提示：我们可以先假定密钥长度已知。

下有答案，不想被糊一脸的话别急着下滑。

---
### 维吉尼亚密码的破解

假定密钥长度已知（例如，在刚才的例子里密钥长度是5），我们可以先把密文按照密钥长度分组。比如上例中，我们可以每五个字符分一组：

<pre>
LXFOP
VEFRN
HR
</pre>

然后我们将密文竖着看。注意到什么了吗？

没错，每个竖行都是用同一个字母加密的，故而位移相同。也就是说，每一个竖行都是一串经过凯撒加密的密文。此时破解方法已经呼之欲出了：我们可以对每个竖行分别应用一次针对凯撒加密的攻击，然后即可反推出密钥。

如果密钥长度未知呢？那也不难，我们只需要先假定密钥长度为1，进行攻击尝试；若无法得到有意义的明文，则再假定密钥长度为2，进行攻击尝试，依次穷举下去，直到我们得到有意义的密文。在仅有纸笔的时代密钥长度通常并不长，所以这个过程其实没有想象得那么耗时。

惊人地简单，是不是？

---

到这里我们可以先休息一下，因为接下来我们要介绍的东西值得单独分出一篇博文：转子加密机。这一类加密机中最著名的恐怕便是二战时纳粹德国使用的 Enigma 密码机了。尽管与之相关的神话数不胜数，但我将要演示的，其实是 Enigma 以如今的眼光来看，安全性到底低到什么程度。

下一话，Enigma 之死！

密码学，从入门到劝退：古典密码（上篇）


密码学——当下被广泛应用，却又被广泛忽视的学科。在这个 HTTPS / SSH / WPA / 某种工具（咳咳，你懂） 满天飞的时代，说你每分钟都在应用密码学大概不是什么夸张。但另一方面，有很大一部分人，包括那些在生产环境中应用密码学组建构建系统的人，可以说连密码学的常识都没有。

惭愧地说，我其实也是其中一员。在 ProtonMail 勾起我对密码学的兴趣之前，我甚至干出过拿$$ SHA256(Password \| Salt) $$当密码 Hash 存在数据库里的蠢事（别动歪心思，这东西现在已经不在线上运行了）；而且我毫不怀疑部分读者可能还没看出来这有什么问题。

不要紧。这个系列的目标正是普及密码学常识——至少是在我力所能及范围内的常识。

### 动机，以及本系列的目标

我记得之前看到过一个花边新闻（不幸，现在我找不到来源了）：

一位密码学家好奇 WebAssembly 在密码学意义上的安全性，于是在推上向 WA 的某个核心开发者询问 WebAssembly 的时间恒定性相关考量。他得到的回应是一个振聋发聩的问句：“旁道是什么？”

我无意指责这位不知道旁道的开发者。但这确实折射出一个严重的问题：我们的从业者对密码学常识的缺乏实际相当严重。这正是启发我创作本系列的原因。

读者要注意的是，作为“密码学劝退”科普而非“密码学”科普，我并不打算在本系列里深入讲解密码学的知识，特别是密码学的数学内容。入门密码学并非本系列的目标；恰恰相反，本系列的目标是培养读者对于密码学的敬畏之心，同时让读者无需成为密码学家也能较安全地应用现有的密码学组件。

更明确地说，在读完本系列以后，读者应当具备如下知识：

- 知道古典密码学和现代密码学的差异，以及现代密码学的安全保证。
- 对常见的密码学算法及实现有所了解，明确它们的能力和限制。
- 明白为什么密码学领域尤其不鼓励自造轮子。

选择这样的角度，一方面是因为本人的密码学水平远未达到可以进行教学的程度，另一方面则是因为密码学界并不缺乏专业的教材。故而任何有志于密码学研究的读者，应当做好接下来需要自行寻找其他教材提升的准备。

### 关于“劝退”二字

> Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break. It's not even hard. What is hard is creating an algorithm that no one else can break, even after years of analysis. 
> -- <cite>Bruce Schneier, 1998</cite>

如上所言，本系列的目标之一是令读者知晓“为何密码学领域尤其不鼓励自造轮子”。实际上这是本系列的重中之重。

无论直接还是间接，我自己见过的试图自造轮子的人简直黄河沙数。而其中大部分人不是已经悲剧，就是正在通往悲剧的路上。常见的表现有以下几种（顺序无关）：

- 搞了一套自造算法，试了一下发现自己破解不了，于是便认为安全。
- 搞了一套自造算法，觉得只要不把算法细节公布出来，自己就是安全的。
- 拿一些老旧的算法(RC4/DES/SHA1 等等)互相套娃，然后觉得自己的设计比这些组件更安全。
- 用 C/Java/JS/其他什么高级语言写了一套密码学算法实现，写了几个单元测试，发现输入输出没什么问题，然后就认定实现正确。

上表远非穷尽，而我也不知道列出来的这几个常见错误已经让多少人中枪；不过如果你未经密码学训练，而又曾经自信满满地实现过一套安全系统，那么你该当心了：本系列正是用来击碎你的自信的。当你知道现实中的攻击未必只是盯着一段密文反推原文，当你知道数学上绝对安全的算法一旦变成实现就多出了成千上万个漏洞以后，懵懂时期的安全感还能保持住几分呢？至少当我回头看我之前用上密码学的程序的话，我觉得那些全是我的黑历史。

引论到此为止。这篇文章中提到的内容，我都会在之后尽可能地展开讲述。所以若以上内容能够激起你的兴趣的话，Stay tuned。

---

[下一话，古典密码，堂堂连载！](/blog/cryptography/cryptography-introduction/classic-cryptography-1/)

密码学，从入门到劝退：引论


> **译注** 原文见《[Telegram, Aka "Stand back, we have Math PhDs!"](https://web.archive.org/web/20180420061726/http://unhandledexpression.com/2013/12/17/telegram-stand-back-we-know-maths/)》。该文发表于2013年，不少内容或许已经过期，故仅供参考。

---

> **免责声明** 本文如今已十分古老，未必能反应 Telegram 协议于时下的情况。这期间已经有了不少其他研究进展，故而此文不应当被用作你选择加密聊天软件的依据。虽说如此，就我个人而言，我依然认为 Telegram 的加密系统很古怪，并且他们对此的洗地言论站不住脚。如果你想要我推荐一个加密聊天软件：找一套基于 Axolotl/Signal 协议的体系。这套协议设计良好，且已经过大量审查。 Signal 和 WhatsApp，以及一些其他的程序都使用了这套协议。

本文是本系列中第二篇介绍奇怪加密 App 的，对象是最近甚嚣尘上的 [Telegram](https://telegram.org)。

据他们网站所言，Telegram “基于云计算而且大量运用加密”。它有多安全？

> 非常安全。我们的技术基于一套新协议，名为MTProto，由我们自己的专家研发，并运用了经过时间考验的加密算法。目前而言，你在 Telegram 上的消息泄漏的最大风险是你妈从你背后看你屏幕。其他的风险我们都能搞定。

(引自他们的 [FAQ](https://web.archive.org/web/20131210133113/http://telegram.org/faq#security))

嗯，非常安全，他们自己这么说的。

行，那我们就来看看到底多安全。

## 目前可以公开的安全情报

他们的网站上发布了协议的细节。他们其实可以多画些示意图，而不是写一堆纯文字，不过现在这样也算能读。还有个[拿 Java 写的开源协议实现](https://web.archive.org/web/20180420061726/https://github.com/ex3ndr/telegram-mt/)。这算个优点。

关于他们的团队（嗯，我还记得我说过不搞诉诸人身，但毕竟他们一直在吹这点）：

> Telegram 背后的团队，由 Nikolai Durov 牵头，共计六个 ACM 冠军组成，其中半数都是数学PhD。他们花了两年时间来设计当前的 MTProto。虽说学历未必代表能力，但至少能说明这套协议是海量专家精确计算的结果（原文：result of thougtful and prolonged work of professionals）

（来自 [Hacker News](https://web.archive.org/web/20180420061726/https://news.ycombinator.com/item?id=6916860)）

他们不是密码学家，但他们有数学学术背景。好耶！

那么，整个体系架构长什么样？**基本上就是世界各地放几台服务器，在客户端之间转发信息。** 身份验证只做在客户端和服务端之间，而不是客户端之间点对点验证。客户端和服务端之间有加密，但用的不是TLS（而是一些自制的协议）。加密可以端对端进行，但因为没有身份验证，所以服务器可以进行中间人攻击。

本质而言，他们的威胁模型就只是“信任服务器”。在公网上传输的内容可能被安全加密了，但我们毕竟无从了解他们的服务器间通信细节，也无法得知他们的数据存储方案。以今天的眼光看来，这套东西既没意思，又昭示着不安全和粗心。类似的系统可以参考 Lavabit 或者 iMessage。**这套系统并不能阻止执法部门的监听或者服务器渗透。更糟糕的：你都没法检测到和你聊天对象之间的中间人攻击。**

我可以就此收手，但这样就没意思了。真正的乐子其实常在他们的加密设计里。这些设计粗看起来似乎合理，但对加密算法的选择既奇怪又不安全，而且每一个设计都无谓地选择了最复杂的那种。

## 网络协议

网络协议有两个阶段：密钥交换和通信。

密钥交换过程会向服务器注册一个设备。为此他们自己搞了一套协议，理由是 TLS 太慢而且太复杂。有一说一，确实：TLS 需要在客户端和服务器间跑**两**个来回 (round trip) 才能完成密钥交换。而且还需求一个 x509 证书，以及一套 RSA 或者 DSA 这种公钥加密算法，最终还需要走一趟 Diffle-Hellman 密钥交换算法。

[Telegram 大幅简化了这个过程（迫真）](https://web.archive.org/web/20180420061726/http://core.telegram.org/mtproto/auth_key)，只需要**三**个 RT，用上 RSA、 AES-IGE（某个没其他人用的奇怪加密模式），以及 DH 密钥交换，同时还有一套工作量证明（客户端得因数分解个数字，估计是个 DoS 防护措施）。另外，他们还用了一套土制算法来从服务器和客户端生成的 nonce 导出 AES 密钥和 IV（ `server_nonce` 在通信过程中是明文传输的）：

```
key = SHA1(new_nonce + server_nonce) + substr(SHA1(server_nonce + new_nonce), 0, 12);
iv = substr(SHA1(server_nonce + new_nonce), 12, 8)+ SHA1(new_nonce + new_nonce) + substr (new_nonce, 0, 4);
```

注意 AES-IGE 是不带认证的。所以他们自行实现了完整性验证，方法是简单地对原文取个 SHA1 （没错，甚至都没用个正经的 MAC），然后把 Hash 结果和原文一起加密（没错，这就是个迫真 MAC-then-Encrypt）。

最终的 DH 交换会创建一个储存在服务端和客户端（搞不好还是明文存储）的认证密钥。

我实在难以理解他们为什么要搞一套这么复杂的协议。他们本来可以这么搞：客户端生成一对密钥，用服务端的公钥加密客户端的公钥，和 nonce 一起发给服务端，然后服务端把用客户端公钥加密过的 nonce 发回来。简单有效。而且这样还可以向客户端提供公钥，实现端对端加密。

至于通信阶段：他们用了一套服务端加盐、消息 ID 和消息计数器的组合来阻止重放攻击。有趣的是，他们的消息密钥是用 SHA1 值的低128位组成的。这个消息密钥**用明文传输**，所以如果你监听到了消息头，那么此处应有巨大多信息泄漏。

用来加密消息的 AES 密钥（还是 IGE 模式下的 AES）是这么生成的：

如下是从 `auth_key` 和 `msg_key` 计算 `aes_key` 和 `aes_iv` 的算法：

```
sha1_a = SHA1(msg_key + substr(auth_key, x, 32));
sha1_b = SHA1(substr(auth_key, 32+x, 16) + msg_key + substr(auth_key, 48+x, 16));
sha1_с = SHA1(substr(auth_key, 64+x, 32) + msg_key);
sha1_d = SHA1(msg_key + substr(auth_key, 96+x, 32));
aes_key = substr(sha1_a, 0, 8) + substr(sha1_b, 8, 12) + substr(sha1_c, 4, 12);
aes_iv = substr(sha1_a, 8, 12) + substr(sha1_b, 0, 8) + substr(sha1_c, 16, 4) + substr (sha1_d, 0, 8);
```

其中，在客户端给服务端的消息中 \$x = 0\$，而服务端给客户端的消息中\$x = 8\$。

<s>因为 `auth_key` 是永久的，而消息密钥只依赖于服务端提供的盐（24小时一换）、会话 ID（估计是永久的，不过可能会被服务端忘掉）以及消息的开始部分，可能很多消息都会生成同样的消息密钥。<strong>没错，很多消息会共享同样的 AES 密钥和 IV。</strong></s>

**编辑：据 Telegram 的评论所言，每条消息的 AES 密钥和 IV 都是不同的。但还是那句话，根据消息内容来生成密钥和 IV 是个及其糟糕的设计。这二者必须从 CSPRNG 生成，和加密内容保持无关。**

**编辑2：[新的协议示意图](https://core.telegram.org/img/mtproto_encryption.png)澄清了密钥是由一个很弱的密钥导出算法推出来的，而且部分内容直接明文传输。这里大概有不少可以拿统计分析搞事情的地方。**

<s><strong>编辑3：行吧，如果你把同一条消息发两遍（在一天当中，因为服务端生成的盐能活24小时），密钥和 IV 会是一样的，而且密文也会是一样的。这是个正儿八经的安全漏洞。通常的解决方式是常换 IV （即使是 WEP 这样的破烂协议都知道这么干）而且常换密钥（也即 TLS 或者 OTR 里的前向安全性）。</strong></s>消息原文里包含一个（时间相关）的消息 ID 以及自增的消息序列号，所以客户端不会接受重放的消息，或者太旧的消息。

**编辑4：有人在[端对端聊天](https://web.archive.org/web/20180420061726/http://web.archive.org/web/20131220000537/https://core.telegram.org/api/end-to-end)中找到了一个[漏洞](https://web.archive.org/web/20180420061726/http://habrahabr.ru/post/206900/)。从 DH 算法生成出来的密钥会和服务端提供的 nonce 结合：`key = (pow(g_a, b) mod dh_prime) xor nonce`。这样，服务端就可以通过在两个客户端间生成同样的密钥，以此进行中间人攻击，让密钥验证失效。Telegram 已经更新了协议描述，打算修复这个漏洞。（这个 nonce 的引入是为了修复某些移动设备上的 RNG 问题）。**

> **译注** 我觉得这个洗地站不住脚。RNG 缺陷可以有多种方式解决：比如 EdDSA 演示实现中将128个随机字节 Hash 到 32个，以此避免暴露 RNG 原始输出防止逆推 RNG 状态。TG 这个解决方法在我看来非蠢即坏——在加密相关问题上我倾向于假定后者。

正经说，我从来没见过有人用 MAC 来生成加密用密钥的。就算你想埋后门，也不用埋得这么明显啊……

结论：**快跑**。里面没有什么全新发明，而且他们还通过自行组合 RSA、AES-IGE、纯 SHA1 完整性验证、MAC后加密、和自制 KDF 引入了一堆自制安全漏洞。比起 Telegram，你更应该用个有名的而且被审计过的协议，比如说 OTR （可用于 IRC 及 Jabber ），或者 TextSecure 的 Axolotl key ratcheting。