---
title: 可汗学院 2014 密码挑战
tags: algo, crypto
---
# 可汗学院 2014 密码挑战
2014 年可汗学院举办了一场名为 [2014 Crypto challenge](https://www.khanacademy.org/computing/computer-science/cryptography/cryptochallenge/a/cryptochallenge-introduction) 的密码学挑战，他被设计成一个密码破译的故事，由一系列破译任务组成，每一个任务完成后得到的内容，都为下一个任务提供了关键线索，且随着破译进度的推进，密码的破解难度越来越高。
这个挑战的目标人群是那些密码学新手，目的是通过示例展示这些加密算法的原理，并尝试用代码实现，虽然都是一些很传统的加密算法，有的甚至很古老是古罗马皇帝使用的。不过在它举办之后的差不多十年，我才偶然发现了它，仍然有点相见恨晚的感觉，在完成挑战过程中，学习了这些古老密码算法的实现思路，作为初次接触加密算法的新手，虽然很困难，不过能够耐着心完成挑战，获得这些关于密码的知识，感觉还是很不错的，所以记录下这几天的解密过程。
故事开始于我们的主角偶然发现一对窃贼遗失的背包，里面包括某系统硬件的原理图，一张报纸的片段，以及一张写有加密信息的便条，挑战的最终目标是破译其中的内容：
虽然我们这是我们要破译的目标，但是我们必须通过获取这对窃贼之前的通信，才能弄清楚如何破译。
## 线索一
可汗学院给我们的提示是这是一个叫做[凯撒密码](https://en.khanacademy.org/math/applied-math/cryptography/crypt/v/caesar-cipher)的[移位加密算法](https://en.khanacademy.org/computing/computer-science/cryptography/ciphers/a/shift-cipher)，原文的每一个字母都被移动了 n 位得到密文，例如假设原文是“cat”，分别对应字母表中的第 3 、第 1 和第 20 号字母，每个字母都 +3 ，就得到一个内容为 “fdw” 的密文。虽然看起来很容易破解，但是对于了解其原理的人来说，完全无法下手。
不过，正因为其加密过程是对所有内容都按照相同的规则移位得到的，而且这种加密方式理论上只有 25 种可能性，所以，对 [1:25] 区间内每个 n 都测试下，就可以暴力破解。这个算法很容易实现， python 代码如下：
```python
import string
def char_dict() -> dict[str:int]:
d: dict = {}
key: int = 0
for c in string.ascii_lowercase:
d[c] = key
key += 1
return d
def caeser_cipher_decrypt(encrypted: str, shift: int):
"""Caeser Cipher 解密
参数：
encrypted (str): 密文
shift (str): 移位值，也就是密钥
返回：
str: 解密后的明文
"""
cdict = char_dict()
decrypted = ''
for char in encrypted:
if char.isalpha():
place = (cdict[char] - shift) % 26
for c, code in cdict.items():
if code == place:
decrypted += c
else:
# 非字母字符直接添加到明文中
decrypted += char
return decrypted
encrypted1 = "vwduw l judeehg hyhubwklqj l frxog ilqg sohdvh uhwxuq dqb eoxhsulqwv iru ydxow dqg dodup ghvljq edvhg " \
"rq zklfk edqn brx ghflgh rq l dp vhwwlqj xs vdih krxvh fr"
encrypted2 = "gl uhtl ishjrvba dvyyplk aoha vby jpwoly pz avv dlhr vu ulea tlzzhnl zdpajo av cpnlulyl jpwoly rlf dvyk " \
"pz aol opkklu zftivs vm klhao pu tf mhcvypal ovsilpu luk"
for i in range(1,26):
print(caeser_cipher_decrypt(encrypted1, i))
print(caeser_cipher_decrypt(encrypted2, i))
```
## 线索二
根据线索一破解得到的信息中的提示，这份密码应用了一种叫做的 [Polylphabetic Cipher](https://en.khanacademy.org/math/applied-math/cryptography/crypt/v/polyalphabetic-cipher) 加密算法。这种加密方法使用一组密钥对原文进行加密，以下是 [Vigenère Cipher](https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher) 维基百科中提供的示例：
```
原文：ATTACKATDAWN
密钥：LEMONLEMONLE
密码：LXFOPVEFRNHR
```
A（字母表中的第 0 个字母）加上 L（第 11 个字母）加在一起会产生 11，即 L；T
（第 19 个）加上 E（第 4 个）等于 23，对应于 X；以此类推...
本质上这还是移位密码，要破解此密码，首先需要获取密钥序列，然后计算出加密字符对应的密钥，最后用和凯撒密码相同的算法对加密字符进行解密。
根据线索一破解内容中的提示，密钥的灵感来源于在 [Holbein the Younger, the Ambassadors](https://en.khanacademy.org/humanities/renaissance-reformation/northern/holbein/v/hans-holbein-the-younger-the-ambassadors-1533)这幅画作。另外，根据可汗学院的提示，密钥中每个字母可能被重复使用两次。
另外，在线索一中，窃贼之前的通信以 start 开始，以 end 结束，有可能后续所有通信都具有这个特征。利用这个特征，将加密信息与“start”相减，确认密钥的格式为“xxyyz...”。结合 [Holbein the Younger, the Ambassadors](https://en.khanacademy.org/humanities/renaissance-reformation/northern/holbein/v/hans-holbein-the-younger-the-ambassadors-1533) 这幅画作，猜测密钥的内容为 “sskkuullll”，然后将之代入以下 python 代码中，成功破解了密码：
```python
from cryptography.caeser_cipher import char_dict
from cryptography.caeser_cipher import caeser_cipher_decrypt
def vigenere_decrypt(encrypted: str, shiftword: str) -> str:
"""
Vigenère Cipher 解密
参数：
encrypted (str): 密文
shiftword (str): 密钥序列
返回：
str: 解密后的明文
"""
decrypted = ''
shiftword_length = len(shiftword)
shiftword_index = 0
cdict = char_dict()
for char in encrypted:
if char.isalpha():
# 获取 shiftword 中对应位置的字符作为密钥
s = shiftword[shiftword_index % shiftword_length]
shift = cdict[s]
# 使用凯撒密码解密算法解密
decrypted_char = caeser_cipher_decrypt(char, shift)
# 添加解密字符
decrypted += decrypted_char
shiftword_index += 1
else:
# 非字母字符直接添加到明文中
decrypted += char
return decrypted
encrypted3 = "klkbnqlcytfysryucocphgbdizzfcmjwkuchzyeswfogmmetwwossdchrzyldsbwnydednzwnefydthtddbojicemlucdygicczhoad " \
"rzcylwadsxpilpiecskomoltejtkmqqymehpmmjxyolwpeewjckznpccpsvsxauyodhalmriocwpelwbcniyfxmwjcemcyrazdqlsom " \
"dbfljwnbijxpddsyoehxpceswtoxwbleecsaxcnuetzywfn"
print(vigenere_decrypt(encrypted3, "sskkuullll"))
```
## 线索三
根据线索二破解得到内容，结合可汗学院的提示，确定线索三是使用以 [Polybius Square](https://en.wikipedia.org/wiki/Polybius_square) 作为密钥的 [Visual Telegraph](https://www.khanacademy.org/computing/computer-science/informationtheory/info-theory/v/history-of-optical-telegraphs-language-of-coins-5-9)加密算法。
根据 [Polybius Square](https://en.wikipedia.org/wiki/Polybius_square) 维基百科中的描述，这种加密法将原文中的字母加密为 $Polybius Square$ 表中的对应位置的序号，假设字母 A 在给定 $Polybius Square$ 表中位于第一行第一列，则将 A 加密为 11 。
这个线索的最大难点在于确定使用什么样的 $Polybius Square$ ，我不得不参考提示，列出可能的 $Polybius Square$ ，然后测试哪个 $Polybius Square$ 能够将 “start” 加密为 “4454113454”，从而确定了以下 $Polybius Square$ ：
```
[
['a', 'f', 'k', 'p', 'u'],
['b', 'g', 'l', 'q', 'v'],
['c', 'h', 'm', 'r', 'w'],
['d', 'i', 'n', 's', 'x'],
['e', 'j', 'o', 't', 'y']
]
```
最终用这个 Polybius Square 破解了密码，python 代码如下：
```python
# polybius square
_polybius_square = [
['a', 'f', 'k', 'p', 'u'],
['b', 'g', 'l', 'q', 'v'],
['c', 'h', 'm', 'r', 'w'],
['d', 'i', 'n', 's', 'x'],
['e', 'j', 'o', 't', 'y']
]
def polybius_decrypt(ciphertext: str, keys=_polybius_square) -> str:
"""Polybius 方阵数字解码函数
参数：
ciphertext (str): 密文，由数字组成
keys （list[list[str]]）: Polybius Square
返回：
str: 解码后的明文
"""
# 初始化解密内容
plaintext = ''
i = 0
while i < len(ciphertext):
if ciphertext[i] == '.':
# 忽略掉代表丢失信息的 "."
i += 1
elif i < len(ciphertext) - 1 and ciphertext[i + 1] == '.':
# 忽略掉 "." 后面的字符，因为后续可能存在 "." 的情况
i += 1
else:
# 将输入字符串转换为坐标
row = int(ciphertext[i])
col = int(ciphertext[i + 1])
if row <= len(keys) and col <= len(keys[0]):
# 从 Polybius 方阵中找到对应坐标的字符并添加到明文中
plaintext += keys[row - 1][col - 1]
else:
# 非法的坐标，视为无效字符
plaintext += '?'
i += 2
return plaintext
encrypted4 = "44541134541123335344541242434244325141212311311353155442544244424344325141534354324234411125513553341342432253431144543453432251343142143251341253341215541534513351444411225144425442444415345123551543213451111311212351425431533321424351445315341434512542531544335154325341443......43513544"
print(polybius_decrypt(ciphertext=encrypted4))
```
## 最后的线索
再展示下我们要破解的目标：
根据前面的线索，我们的主角找到了一个安全屋，在里面找到了一些破译最终目标的关键线索：
下面三张图解释了密文中的符号的意义，每个符号对应两位十进制数：
- 垂直/水平线代表高位值：北=0，东=1，南=2，西=3
- 对角线代表低位值：东南=0，西南=1，西北=2，东北=3
下面两张图解释了报纸的作用：在加密的某个阶段，将二进制序列与根据报纸生成的二进制密钥序列进行按位 XOR 运算，然后将结果每三个分为一组。
还记得一开始获得了一张剪报吗？是从这里获得二进制密钥序列的。
根据上两张图所示的规则，从报纸所示的内容的元音字母获得 1 ，从辅音字母获得 0。
最后一张图展示了加密流程
1. 首先使用 “visual telegraph” 将明文中的每个字母加密为 2 个十进制数；
2. 将 2 个十进制数转换为 6 bit 二进制数，获得二进制序列；
3. 将上一步得到的二进制序列与从报纸获得的二进制密钥序列进行按位 XOR 运算，获得加密序列；
4. 将上一步加密得到的二进制序列，每三个 bit 分为一组，然后每两个组编制为一个加密符号。
好吧，我承认最后一部上述内容是我参考提示信息得到的。本来觉得智商不够，都想放弃了，在提示信息中看到有人提到在[NSA是如何解密氪星雕塑的](http://www.wired.com/threatlevel/2013/07/nsa-cracked-kryptos-before-cia/)这篇文章中介绍：即使是顶尖专家，也遇到类似的困难。这给我续了最后一口气。
本来根据提示整理了大概思路，可是第一版代码无论如何也无法解密信息。那就 google 看看有没有人把思路 post 出来。然后就找到了[这篇文章](https://www.coastalvectors.com/blog/2016/10/2014-crypto-challenge/)。好吧，我又得承认了，整个挑战过程的解密思路，我都参考这篇文章做了修正，以至于行文也做了模仿。
阅读文中的代码后，发现我的代码没有大的逻辑问题，错误在于步骤一用的还是解码线索三时使用的 $5 \times 5 Polybius Square$ ，既然 2 个十进制数被转换为 6 bit 二进制数，那么每个十进制数最大值应该为 6 ，所以应该用一个 $6 \times 6 Polybius Square$ 执行 $Visual Telegraph$ 加密。
再看最后一张图，发现里面代表 $Polybius Square$ 的符号是个顺时针从外向内卷的螺旋符号。
到这里，也就理解了为什么参考代码中选择了这个 $Polybius Square$:
```
[
["f", "g", "h", "i", "j", "k"],
["e", "x", "y", "z", "0", "l"],
["d", "w", "7", "8", "1", "m"],
["c", "v", "6", "9", "2", "n"],
["b", "u", "5", "4", "3", "o"],
["a", "t", "s", "r", "q", "p"]
]
```
另外值得一提的是，上面步骤三涉及的加密算法叫做 [One-Time Pad](https://en.khanacademy.org/computing/computer-science/cryptography/crypt/v/one-time-pad)，这是对 Polylphabetic Cipher 算法的扩展，其中作为密钥的二进制序列叫做 $pad$，理论上 $pad$ 越长，密文越难被破解。可是，无论是 Polylphabetic Cipher 算法、 Visual Telegraph ， 还是 One-Time Pad 算法，破解传统密码的关键从来不是密码本身，而是密钥，任何以明文或以某种实体存在的固定密钥，只要被泄露了，或被推测出来了，密码也就被破解了，因此对于传统加密算法的改进，密钥的随机化是关键，这一需求也促进了20世纪[恩尼格玛密码机](https://en.khanacademy.org/computing/computer-science/cryptography/crypt/v/case-study-ww2-encryption-machines)以及第一代伪随机数算法[冯诺依曼平方取中法](https://en.khanacademy.org/computing/computer-science/cryptography/crypt/v/random-vs-pseudorandom-number-generators)的出现。
要成功解码，需要反转上述流程：
1. 将 pad 根据是否为元音字母转换为二进制序列；
2. 将密文符号转写为两个十进制数，然后将每个十进制数转换为 3 bit 二进制数；
3. 二进制密文用二进制 $pad$ 按位做 $XOR$ 运算获得解密坐标编码
4. 将解密坐标编码每 3 bit 编为一组，然后将每个二进制序列组转换为一个十进制数，得到一个十进制序列。
5. 使用 $6 \times 6 Polybius Square$ 对十进制序列进行 $Visual Telegraph$ 解密
解密过程实现如下：
```python
def onetime_pad_decrypt(cipher_code: str, pad_bin: list[int]):
decrypted = ""
i = 0
while i < len(pad_bin) and i < len(cipher_code):
if cipher_code[i].isdecimal():
decrypted += str(pad_bin[i] ^ int(cipher_code[i]))
i += 1
return decrypted
def polybius_decrypt2(ciphertext: str, keys=_polybius_square) -> str:
# 将加密字符串按照两个字符一组解码
plaintext = ''
i = 0
while i < len(ciphertext):
if ciphertext[i] == '.':
# 忽略掉代表丢失信息的 "."
i += 1
elif i < len(ciphertext) - 1 and ciphertext[i + 1] == '.':
# 忽略掉 "." 后面的字符，因为可能存在 "." 的情况
i += 1
else:
# 将数字映射到 Polybius 矩阵的行号和列号
row = int(ciphertext[i])
col = int(ciphertext[i + 1])
if row <= len(keys) and col <= len(keys[0]):
# 将对应位置的字母添加到明文字符串中
plaintext += keys[row][col]
else:
# 非法的坐标，视为无效字符
plaintext += '?'
i += 2
return plaintext
secret_code = "20 33 22 21 00 33 30 01 02 20 22 02 32 20 11 33 03 30 03 32 03 00 22 01 33 23 23 10 03 22 13 13 20 01 " \
"11 03 22 20 20 20 22 33 20 13 23 13 33 22 30 33 01 20 21 10 12 11 00 32 23 13 22 02 00 10 31 02 33 20 " \
"31 03 12 01 11 33 32 23 02 01 00 32 10 10 30 01 10 23 31 10 02 00 30 23 31 10 03 03 01 02 33 02 23 21 " \
"30 12 03 12 22 00 03 13 31 00 10 11 21 03 23 02 20 13 02 32 30 31 23 33 20 02 12 33 30 00 30 12 30 13 " \
"03 01 03 03 23 22 02 30 20 03 22 23 32 23 02 02 31 20 23 13 30 02"
pad_text = "the whole grain goodness of blue chip dividend stocks has its limits utility stocks consumer staples pipelines " \
"telecoms and real estate investment trusts have all lost ground over the past month even while the broader " \
"market has been flat with the bond market signalling an expectation of rising interest rates the five year " \
"rally for steady blue chip dividend payers has stalled should you be scared if you own a lot of these stocks " \
"either directly or through mutual funds or exchange traded funds david baskin president of baskin financial " \
"services has a two pronged answer keep your top quality dividend stocks but be prepared to follow his firms " \
"example in trimming holdings in stocks such as transcanada corp keyera corp and pembina pipeline corp lets " \
"have mr baskin run us through his thinking on dividend stocks which are the big part of the portfolios his " \
"firm puts together for clients a mini manifesto for the managers"
def text_to_binary_arr(plain_text: str) -> list[int]:
vowels = "aeiouy" # 元音字符
binary: list[int] = []
for c in plain_text:
# 判断字符是否为字母
if ord(c) < ord('A') or ord(c) > ord('z'):
continue
if c.lower() in vowels:
binary.append(1)
else:
binary.append(0)
return binary
def decimal_to_binary(ciphertext: str) -> str:
decrypted = ''
for c in ciphertext:
if c.isdecimal():
# 将 10 进制字符转换为二进制字符串，去掉 "0b" 前缀
binary = bin(int(c))[2:]
# 在前面填充零，使其总长度为 3
binary = binary.zfill(2)
decrypted += binary
return decrypted
def secret_code_to_charcoords_code(secretcode: str) -> str:
charcoords_code = ''
for i in range(0, len(secretcode), 3):
group = secretcode[i:i + 3]
if len(group) == 3:
charcoords_code += str(int(group, 2))
return charcoords_code
keys = [
["f", "g", "h", "i", "j", "k"],
["e", "x", "y", "z", "0", "l"],
["d", "w", "7", "8", "1", "m"],
["c", "v", "6", "9", "2", "n"],
["b", "u", "5", "4", "3", "o"],
["a", "t", "s", "r", "q", "p"]
]
def decrypt(encrypted, pad, keys):
pad_bin: list[int] = text_to_binary_arr(pad)
binary_secret_code: str = decimal_to_binary(encrypted)
decrypted = onetime_pad_decrypt(binary_secret_code, pad_bin)
charcoords_code = secret_code_to_charcoords_code(decrypted)
decrypted_secret_code = polybius_decrypt2(ciphertext=charcoords_code,
keys=keys)
print("\tdecrypted secret code, length: %d %s\n" %
(len(decrypted_secret_code), decrypted_secret_code))
return
decrypt(secret_code, pad_text, keys)
```
Sign in with Wallet
Connect another wallet