Cryptopals 是一套现代密码学相关的 Codelab，这一系列文章用于自己存档，如果你还没有做过这个Lab，也强烈建议访问 https://cryptopals.com/ 来亲自体验。

1. 热身

热身的练习相对比较简单，但为后续的练习提供了一些相对好用的代码模板。

1.3 Single-byte XOR cipher

这一个问题要求我们破译一个使用1字节异或加密的字符串。

1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736

需要注意题目中提到明文是一段英文句子，那么其理应：

• 字母的分布符合英文字符的统计规律。
• 不包含字母、数字、标点符号、空白字符之外的字符。

在实际解密中，感觉第二条更加重要一些，因为有可能解密解密出有一堆a或者e但其它全是乱码的句子。

维基百科提供了一个英文句子中字符出现的频率，我们只需要自己也统计一下解码之后的字符串各个字符出现的频率，然后做一个向量点乘，排除明显不符合的（包含非法字符的）答案之后即可。

这一题中，得分最高的句子不包含任何非法字符，但下一题就未必了。

cargo run --bin 1_3_single_byte_xor_cipher
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `target/debug/1_3_single_byte_xor_cipher`
Ok("Cooking MC's like a pound of bacon") (score 3.826559)

1.4 Detect single-character XOR

这题在第三题的基础上加强，给出了一堆字符串，其中一个是用异或加密过的。需要注意的是这一题给出的字符串过多，如果不过滤掉包含ASCII中，不是字母、数字等字符的字符串，会出现得分最高的句子是乱码的情况。

cargo run --bin 1_4_detect_single_byte_xor_cipher
   Compiling cryptopals v0.1.0 (/home/matsu/my_solutions/misc/cryptopals)
    Finished dev [unoptimized + debuginfo] target(s) in 0.19s
     Running `target/debug/1_4_detect_single_byte_xor_cipher`
#35 Ok("iu`'ern.&nZeM,MjT\u{b}:FD~i5+OyEmL") (score 2.2037334)
#149 Ok("K2\"YPe(JOG5\u{1c}]/o)_B\"FsXABnPgu&\u{1b}") (score 1.5408334)
#165 Ok("Hs>u1Y/orf:AP|m\0@?v:9\n=9yNct<o") (score 1.9225669)
#170 Ok("Now that the party is jumping\n") (score 4.449133)
#195 Ok("Ae$JA}6LgEkB6Qi{GQ|a!w-Wr2=OUH") (score 1.8434335)
#225 Ok("U3YOh,\\0sUHXcQ.?3an$$\\U4Knolp@") (score 1.6776335)
#230 Ok("mjOia}tti:\\\"x7{N(0`H[ra]p$bo_^") (score 2.2667336)
#289 Ok("Ey0DGvdt|eg:XtgmB}{_7mh\u{12}tXNTeg") (score 2.5576)
#295 Ok("^!IwIl>mvAgs$0%o!Jd@cB8;wNAi8V") (score 1.943767)

在这个基础上保留得分最高的字符串即是结果。

1.6 Break repeating-key XOR

本题要求我们解密一个用异或加密的字符串，而密钥是一个有一定长度的字符串。

题目里面提示我们：

• 枚举可能的密钥长度，取密文的前若干块，计算这些块之间的编辑距离。编辑距离最小的可能就是答案。
• 对于枚举出的密钥长度，按密文（也是明文）下标取模，依次暴力枚举密钥的每一位。

在做这一题的时候，最开始比较偷懒，只取了前两块来计算，但最后发现怎么解密都不对。这时候意识到是样本太小，统计规律不足以显示。于是修改代码比较五倍密钥长度的字符串。

为何可以通过这样的统计来得知密钥长度？

异或加密没有改变明文每一位的相对关系，由于我们知道明文是一段英文文本，那么其明文的每一位必定是在一段很小的区间內，即在明文二进制表示中有很多位都相同，而异或加密没有打破这一层统计学关系，因此可以被如此攻击。

在真实世界中，如果不带消息校验码（MAC）的话，ECB、CFB等加密模式也可以被这样攻击，因为其明文的第i位在加密后一定是在密文的第i位上，如果不校验消息则可能被探测到通信协议相关特征。

更新：上述表述并不正确，在AES加密过程中，明文有参与到扩散这一步骤当中。但需要注意的是，由于CBC加密IV的参与，对IV对应位的修改会反映到明文对应位上。

本题密钥长达29字节。

...
Key = [84, 101, 114, 109, 105, 110, 97, 116, 111, 114, 32, 88, 58, 32, 66, 114, 105, 110, 103, 32, 116, 104, 101, 32, 110, 111, 105, 115, 101]
Ok("I'm back and I'm ringin' the bell \nA rockin' on the mike while the fly girls yell 
...

1.8 Detect AES in ECB mode

这题延续上一题的思路，我们知道ECB模式只是简单地将明文异或一个字符串，同异或加密没有本质区别。

我们也是简单统计各块之间的相关性即可，需要注意也是要多统计几块，由于密文不长，我直接统计了两两之间的编辑距离。最后得出的编辑距离显著小于其它输入。

Possible ECB cipher #132: distance=239.8
d880619740a8a19b7840a8a31c810a3d
08649af70dc06f4fd5d2d69c744cd283
e2dd052f6b641dbf9d11b0348542bb57
08649af70dc06f4fd5d2d69c744cd283
9475c9dfdbc1d46597949d9c7e82bf5a
08649af70dc06f4fd5d2d69c744cd283
97a93eab8d6aecd566489154789a6b03
08649af70dc06f4fd5d2d69c744cd283
d403180c98c8f6db1f2a3f9c4040deb0
ab51b29933f2c123c58386b06fba186a

可以注意到肉眼可见的统计特征。