早年间写过一个utf8-ctc，用来将文字转换成中文电码表示，当时还写了一篇文章来介绍它的基本原理。但当时有几个东西让我耿耿于怀：压缩、加密和校验。终于在机缘巧合之下，本文将记述如何改进这些问题。
前言
简单来说，utf8-ctc这个程序已经能够做到将任意输入文本转换成一系列中文电码，以便使用者可以将其方便地（相比于base58）抄写在依赖光学进行阅读的物理媒介上（例如明信片或信纸）。在遇到中文电码表之外的字符时，这个程序可以自动以utf8编码将其转换成字节数据，然后利用base9992表示。在这个过程中，程序还会尝试使用deflate压缩算法进行压缩，如果压缩后的结果更短，则使用压缩后的结果，进一步减少用户需要抄写的电码数目。同时在输出前，还加入了对称和非对称的密钥生成机制，以密钥作为CSPRNG的种子将结果分块进行置换加密（Transposition Cipher）。
但目前有三个问题：
- Deflate压缩算法在长文本的情况下效率不佳，而对于中文中夹杂的外文短语，几乎大部分场景下未压缩的数据量都更小一些。
- 加密算法实质上是置换加密，虽然程序中有估计拖延时间的设计，但本质上多次置换和一次置换没有本质区别。
- 无法校验用户的输入，因此用户输入错误一位或几位数字，程序无法判断。最好情况是对应的字变成乱码，最坏情况是utb8字符解码失败，导致整块外文引用无法解析。
更换压缩算法
最开始由于Java标准库内置Deflate算法（zip同款），所以我当时毫不犹豫地就使用了这个算法。但随着后续测试发现，对于中文夹杂的外文短语或emoji，由于其数据量非常小，通常不到50字节，在这种情况下几乎任何常规的压缩算法都难以发挥作用。因此大部分时候我们需要用base9992表示原始数据。而当文本中出现成片的外文引用，例如引用了一整段外文，此时的数据量使使劲能达到大约1KB的量级，此时压缩算法能够略施拳脚。而考虑最坏情况，比如一个外国人输入了一段从头到尾都没有中文的文字，那这种情况对于压缩算法来说是最好不过的了。
我选取了三组数据进行测试，第一组是一段英文文字，第二组是一段日文文字，第三组是电影利兹与青鸟的台词。
| Deflate | LZMA2 | |
|---|---|---|
| 174B | 115 | 122 |
| 393B | 221 | 228 |
| 29KB | 10218 | 9517 |
可以发现在文本量比较少的时候，选用LZMA2算法会导致我们比使用Deflate时多产生7个左右的字节，这对应大约4到5个电码。而对于长文本时，我们能够节省超过500个字节，大约对应300个电码。由于能够使用的符号有限，程序中只能选取一种压缩算法。经过一番思索，我认为能够在长文本上取得较好压缩效果更为重要，这样能够在处理长输入时尽可能减少用户需要抄写或处理的电码数量。
其实在选择LZMA2算法之前，我更中意的是zstd算法，可惜zstd并没有纯Java实现，因此它的依赖会对便携性产生影响。
由于符号有限，9992和9993分别表示未压缩的UTF8数据的开始和结束，而9994和9995表示压缩的UTF8数据的开始和结束，此外我便找不出其他可以挪用的成对的电码了。因此我不得不将Deflat替换成LZMA2，这也意味着如果有人用新程序解码了旧程序压缩的数据，由于压缩算法的变化，新的程序会直接报错，导致所有非中文段落无法解析。
更换加密算法
原本的置换加密就是图一乐。置换加密有点像是y=kx+b：你可以做很多次置换迭代，相当于多次洗牌，对应地，你可以在一元一次方程上迭代多次y=k( k( k ( kx + b) + b) + b )+b，但如果你化简这个式子，你会发现最终可以用一套新的参数替换这一系列迭代y=k' x + b'。这对于置换加密也是类似的：你可以多次洗牌，但本质上迭代N次和迭代1次并没有对攻击者造成实质性的困扰。由于明文本身没有变，只是打乱了顺序，因此攻击者可以根据统计学数据来做类似小学时候看词造句这样的攻击。虽然这种方法无法解析出抽象的句子，但你总不能从头到尾句句抽象吧。因此我们需要一种更安全的加密手段。
但由于我们的输入输出是电码，并不是传统意义上的二进制数据。如果我们将输入转换成utf8编码进行加密，那样又会破坏使用电码的本意。因此我将目光转到了ChaCha20，TLS1.3的核心标准之一。
ChaCha20本身是一个加密算法，它将明文与密钥流进行XOR运算来加密，其设计方案具有诸多特点，这里就不多赘述了。我们的问题是如何将电码这种非二进制数据利用ChaCha20进行压缩。
如果从数学的角度入手，二进制的XOR或许可以被加法和取模替代。假如我们有个密钥流，它的元素是0000到9999的数字，那么我们就可以这样加密：
enc = (input + key) % 10000而解密时：
plain = (enc - key + 10000) % 1000虽然没有xor那么简洁对称，但我认为也足够好了。同时由于ChaCha20使用XOR加密数据，那我们只要不停地加密字节0，0 XOR key = key，这样我们的输出就是二进制的密钥流了。通过拒绝采样，我们可以拒绝所有大于等于60000的值，剩下的值对10000取模，就可以根据ChaCha20得到我们需要的密钥流了。
采取拒绝采样的原因是我们需要保证0000到9999中每个元素的出现概率不会因为我们的操作而产生偏差。例如我们不使用拒绝采样，而是简单地将两个临近的字节解析为short数值，然后对10000取模，那么受制于short的0到65535的取值范围，我们可能会得到5536、15536、。。。、55536，但我们得不到65536；而对于1234来说，我们有1234、11234、。。。、61234。这样你会发现，对于1234来说，我们有六个可能的来源，而对于5536来说，我们只有五个可能的来源。这便是人为引入的偏差。
对于ChaCha20本身的参数而言，我们需要一个256bit的密钥，和一个96bit的nonce。受制于ChaCha20的原理，这个nonce必须不能重复，否则就会出现使用同一个密钥流加密文本的情况：
enc1 = (plain1 + key) % 10000
enc2 = (plain2 + key) % 10000
enc1 - enc2 = (plain1 - plain2) % 10000可以看到当我们使用同一个密钥流两次加密不同信息的时候，对密文应用取模减法就可以抵消密钥流带来随机性（同样地，原版ChaCha20使用的XOR也有类似的缺陷）。虽然攻击者无法获得明文，但两次明文的差值也足够提供丰富的信息以便后续攻击。
这里我们也可以认为ChaCha20不是加密，而是提供了一个密码学安全的随机流。我们的数据安全就建立在攻击者无法猜到下一个密钥流是什么随机数值的事实上。合法的用户通过提供正确的密钥和参数可以重复可靠地产生这个确定但不可预测的流，而一旦攻击者能够通过某种手段消除我们引入的随机性，那么整个ChaCha20加密的安全性也就此被打破
因此我们需要保证nonce永远不会重复。然而时间是最大的敌人，只要时间足够长，总会有重复的可能。怎么办呢？把时间变成我们的朋友就好了：
- 前64bit（8字节）使用当前时刻的毫秒精度的时间戳
- 后32bit（4字节）使用SecureRandom生成的随机数
只要我们保证在同一毫秒内生成的随机数不会产生碰撞即可。但随机数碰撞（或不碰撞）是一个概率问题，最简单粗暴的方式就是保证每毫秒只进行一次加密。但考虑到系统的时间可能会漂移（例如人为调整时间，或者NTP同步），因此同一个毫秒可能会重复出现。
根据生日问题的原理，2的32次方大约有42亿种不同的可能（记作k），假如我们采样N次，那么N次不发生碰撞的可能性是：
$$ \frac{k!}{(k - N)! \times k^N} $$
感觉42亿的阶乘好像不太好算，那我们用其近似形式来计算一下碰撞的概率：
$$ P = 1 - e^\frac{-N^2}{2k} $$
这样我们就可以计算出不同的采样次数下，发生碰撞的可能性：
| P | N |
|---|---|
| 0.000010% | 29 |
| 0.100000% | 2931 |
| 1.000000% | 9291 |
| 10.000000% | 30083 |
| 25.000000% | 49710 |
| 50.000000% | 77162 |
| 75.000000% | 109124 |
| 99.000000% | 198892 |
假设我们每毫秒采样2931次，那么发生碰撞的概率就是0.1%，根据数学期望，当发生时钟漂移导致同一时间戳重复出现长达1秒时，或1000次（每次一毫秒），即总共取样293万次时，可能会发生一次碰撞。不过我实在想象不到得是发生什么事才能导致这种状况。就算万一真的出现了这种状况，我想那应当不在我的程序的使用范围内。
引入每行校验
解决了加密的问题，下面就要考虑如何验证并提示用户有没有输入错误。常见的校验码，如CRC32，大多会生成4字节的数据用来校验，但四字节用hex表示就是8个字符，对于书面抄写而言，这是极大的负担。如果秉承着正文只要抄写数字的目标，那么ISO 7064 mod 97-10会是个不错的选择。因为它的主要用途是验算IBAN（国际银行账号）号码。
这下我也可以说我的程序会进行“金融级校验”了 XD
简单来说，它的计算公式如下：
mod(98 - mod(data * 100, 97), 97)而计算结果只需要简单地拼接在输入的数字串末尾，然后一并进行如下校验：
mod(data_check,97) == 1如果输入的数字串（包含2位末尾校验位）对97取模余1，就说明数据是正确的，否则数据就是错误的。因此当即将输出电码（加密或未加密）时，我们对电码进行分组，例如每行包含N个电码以便用户抄写，将这一行的电码视为一个数字，然后计算校验，在每行最后会产生两位校验位，用户将他们一并抄写在同一行。在读取时，我们在每行结束时将一行的输入进行校验，如果成功则剥去最后两位校验数字，余下当作电码按四位一组解析；如果失败则告诉用户打错了。这样就能有效避免输入错误导致的解码错误。
关于先加密后校验还是先校验后加密：我的程序采取了先加密后校验，这样对于解密时就是先校验数据，确保数据没有损坏或篡改，再输入解密算法。如果不做校验，或先解密后校验，那么你无法确保输入进解密算法的数据不包含恶意数据，例如针对你的解密算法而特制的攻击数据。这样早晚会出现安全问题。
对输出整体进行签名
虽然我们有每行校验，可以在一行结束时判断用户是否输入正确，但这无法确保用户不会抄串行，因为每行都是正确的，但行的顺序变了。考虑到我们的ChaCha20加密算法并不包含对数据完整性的校验，所以在加密时对数据进行签名显得尤为重要。
在众多HMAC算法中，SipHash能够给出较短的密码学安全摘要，长度为64bit，用hex表示则只需要抄写16个字符。但SipHash需要128bit的密钥，而程序里用的都是256位的。我们当然可以直接截断，将前128bit作为SpiHash密钥，但这样好像不够优雅，因此我使用了HKFD（Hash Key derivation function，这里使用SHA256）来生成一个专门给SipHash使用的密钥。
至于输入嘛，考虑到我们的输入是0000到9999的数字，我们可以将其作为short数值，按照大端序转换成字节，依次喂进SipHash。因此加密时的输出流程是：
电码 -> 加密 -> SipHash摘要 -> 按行校验而解密时则是反过来的：
按行校验 -> SipHash验证 -> 解密 -> 电码还原成文字效果展示
以如下明文为例：
天匠染青红，花腰呈袅娜。使用对称加密（密钥为test-key）：
# ./ctc encode -t "天匠染青红，花腰呈袅娜。" -w 4 -k test-key
Nonce = 0000 019B D1DD 117C ADE4 95E3
MAC = 7026 79EA E6BB 074B
4442 4214 2130 3200 35
1120 3419 2668 8328 70
6938 6776 9452 0880 03其中-w 4表示每行打印4个电码，可以看到程序输出了nonce和mac，分别用于解密和验证消息完整性。而实际的电码输出有三行，每行后面都会有一个两位校验码。
解密时假如不提供密钥（使用-i选项忽略错误强行打印文字）：
# ./ctc decode -i
>> 4442 4214 2130 3200 35
>> 1120 3419 2668 8328 70
>> 6938 6776 9452 0880 03
>> EOF
秩瞀抹涞外泽□岬锅鄱□嘶你会发现加密后的数据是完全无从下手的。而正确的解密则是这样：
# ./ctc decode -k test-key -n "0000 019B D1DD 117C ADE4 95E3" -m "7026 79EA E6BB 074B"
>> 4442 4214 2130 3200 35
>> 1120 3419 2668 8328 70
>> 6938 6776 9452 0880 03
>> EOF
天匠染青红，花腰呈袅娜。当某一行的数据输入错误时，即便没有提供密钥也能检测出来：
# ./ctc decode
>> 4442 4214 2131 3212 35
>> 1120 3419 2668 8328 70
>> 6938 6776 9452 0880 03
>> EOF
Detect error line: 4442 4214 2131 3212 35如果每行都对了，但是摘要不对的话，也是能检测出来的：
# `-m` 最后一位从B换成了C
# ./ctc decode -n "0000 019B D1DD 117C ADE4 95E3" -m "7026 79EA E6BB 074C" -k test-key
>> 4442 4214 2130 3200 35
>> 1120 3419 2668 8328 70
>> 6938 6776 9452 0880 03
>> EOF
Exception in thread "main" java.lang.IllegalArgumentException: MAC mismatch
at info.skyblond.ctc.commands.DecodeCommand.run(DecodeCommand.kt:49)
at com.github.ajalt.clikt.core.CoreCliktCommandKt.parse(CoreCliktCommand.kt:107)
at com.github.ajalt.clikt.core.CoreCliktCommandKt.main(CoreCliktCommand.kt:78)
at com.github.ajalt.clikt.core.CoreCliktCommandKt.main(CoreCliktCommand.kt:90)
at info.skyblond.ctc.MainKt.main(Main.kt:6)虽然报错的方式不太体面，但好歹是报了。
后记
本文修正了utf8-ctc中尚未解决的一些问题，至此我认为这个项目可以算作是完成了。这样一来我也可以光明正大地邀请大家前往 https://github.com/hurui200320/utf8-ctc 下载并体验。当然了，一如既往地，这是我一时性起编写的项目，因此不存在任何保证，也不会许诺大伙任何新增的功能。如果有什么想法可以尝试着开个issue，但我不会保证会有回应。
那么以上就是全文了，祝大家新春快乐。
-全文完-
【代码札记】改进电码转换程序 由 天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://skyblond.info/about.html 处获得。