程序员如何用Python编程暴力算法破解凯撒密码

off999 2024-10-19 07:24 35 浏览 0 评论

破解凯撒密码可以用到一项密码分析技术，叫作暴力算法（brute-force），它的攻击是通过尝试每一种可能解密密文的密钥实现的。没有什么能够阻挡密码分析人员猜测密钥、用密钥解密密文、观察输出，并在没能破解出密文的情况下寻找下一把密钥。正因为这样的暴力算法对凯撒密码来说过于有效，所以在实际应用中根本不应该使用凯撒密码去加密一段秘密信息。

在理想的情况下，一段密文不会落入任何人的手中，然而Kerckhoffs原则（以19世纪密码学家Auguste Kerckhoffs命名）表明，一段密文即使在所有人都知道来源且某些人可能得到的情况下，也应该保持其安全性。20世纪时，数学家Claude Shannon在《香农格言》（Shannon's maxim）中重新提出了这个原则，即“敌人了解系统”。在密码算法中，是密钥保证了信息的机密性，而在凯撒密码中，密钥的信息非常容易被发现。

本章要点

Kerckhoffs原则和香农格言。
暴力算法技术。
range()方法。
字符串标准化（字符串插值）。

1　破解凯撒密码的源代码

选中 File

New File，打开一个新的编辑窗口，将下列代码输入编辑窗口并将其存储为caesarHacker.py。随后，如果读者的计算机中没有pyperclip.py模块，则可以下载它并将它放置在与caesarHacker.py相同的路径下（同一个文件夹中），该模块将在caesarHacker.py文件中被引入。

结束文件配置后，按 F5键执行程序，如果代码中出现了报错或其他问题，请仔细比对书上代码和文件中代码有何不同。

caesarHacker.py

 1. # 凯撒密码破解
 2. # https://www.nostarch.com/crackingcodes/ (BSD Licensed)
 3.
 4. message = 'guv6Jv6Jz!J6rp5r7Jzr66ntrM'
 5. SYMBOLS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz12345
　　　67890 !?.'
 6.
 7. # 循环遍历所有可能的关键字
 8. for key in range(len(SYMBOLS)):
 9.　　 # 将translated设置为空字符串很重要，这样可以清除上一个迭代中
10.　　 # translated的值
11.　　 translated = ''
12.
13.　　 # 程序的其余部分与凯撒程序几乎相同
14.
15.　　 # 循环遍历message中的每一个字符
16.　　 for symbol in message:
17.　　　　 if symbol in SYMBOLS:
18.　　　　　　 symbolIndex = SYMBOLS.find(symbol)
19.　　　　　　 translatedIndex = symbolIndex - key
20.
21.　　　　　　 # 执行回环
22.　　　　　　 if translatedIndex < 0:
23.　　　　　　　　 translatedIndex = translatedIndex + len(SYMBOLS)
24.
25.　　　　　　 # 添加解密的字符
26.　　　　　　 translated = translated + SYMBOLS[translatedIndex]
27.
28.　　　　 else:
29.　　　　　　 # 添加未加/解密的字符
30.　　　　　　 translated = translated + symbol
31.
32.　　 # 显示每一个可能的解密值
33.　　 print('Key #%s: %s' % (key, translated))

注意，本段代码有很大一部分和原始的凯撒密码程序相同，这是因为凯撒密码的破解程序使用了和加密一样的步骤去解密信息。

2　运行凯撒密码破解程序的样例

运行凯撒密码的破解程序，将会得到如下输出。它使用全部66种可能的密钥解密密文“guv6Jv6Jz!J6rp5r7Jzr66ntrM”，将其成功破解。

Key #0: guv6Jv6Jz!J6rp5r7Jzr66ntrM
Key #1: ftu5Iu5Iy I5qo4q6Iyq55msqL
Key #2: est4Ht4Hx0H4pn3p5Hxp44lrpK
Key #3: drs3Gs3Gw9G3om2o4Gwo33kqoJ
Key #4: cqr2Fr2Fv8F2nl1n3Fvn22jpnI
--snip--
Key #11: Vjku?ku?o1?ugetgv?oguucigB
Key #12: Uijt!jt!nz!tfdsfu!nfttbhfA
Key #13: This is my secret message.
Key #14: Sghr0hr0lx0rdbqds0ldrrZfd?
Key #15: Rfgq9gq9kw9qcapcr9kcqqYec!
--snip--
Key #61: lz1 O1 O5CO wu0w!O5w　sywR
Key #62: kyz0Nz0N4BN0vt9v N4v00rxvQ
Key #63: jxy9My9M3AM9us8u0M3u99qwuP
Key #64: iwx8Lx8L2.L8tr7t9L2t88pvtO
Key #65: hvw7Kw7K1?K7sq6s8K1s77ousN

由于第13把密钥得到的输出是标准的英文，因此可以断定原始的加密密钥就是第13把密钥。

3　设置变量

破解程序生成了变量message，用于存储需要解密的密文字符串，常量SYMBOLS则包含了所有可以被加密的字符。

 1. # 凯撒密码破解
 2. # https://www.nostarch.com/crackingcodes/ (BSD Licensed)
 3.
 4. message = 'guv6Jv6Jz!J6rp5r7Jzr66ntrM'
 5. SYMBOLS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz12345
　　　67890 !?.'

SYMBOLS的值需要和凯撒密码加密程序中使用的SYMBOLS的值完全相同，同时待破解的密文正是由该加密程序得来；否则，破解程序将失效。注意，SYMBOLS字符串中的 0 和 ! 之间有一个空格。

4　在循环中使用range()方法

第8行使用了一个for循环，然而它并没有在一个字符串值上进行迭代，而是在调用range()方法的返回值上进行迭代。

 7. # 循环遍历所有可能的关键字
 8. for key in range(len(SYMBOLS)):

range()方法接收一个整型参数，并返回range数据类型的值。这种数据类型的值可以在for循环中用于进行指定次数的循环，循环次数由传递给range()方法的整数决定。尝试下面的例子，将下列代码输入交互式运行环境中。

>>> for i in range(3):
...　 print('Hello')
...
Hello
Hello
Hello

由于将整数3传递给了range()方法，因此for循环将进行3次循环。

更确切地说，range()方法返回的range值会将for循环的变量值设置为0～输入的参数值（不包含后者），例如，将下列代码输入交互式运行环境中。

>>> for i in range(6):
...　 print(i)
...
0
1
2
3
4
5

这段代码将变量i的值设置为0～6（不包含6），与caesarHacker.py文件的第8行类似——文件的第8行将key的值设置为0～66（不包含66）。为了避免将66直接硬编码到程序中，程序使用了len（SYMBOLS）的返回值，因此即使改变SYMBOLS的值，程序的运行也不会受到影响。

程序首次执行到循环时，key被设置为0，message中的密文被密钥0解密（当然，如果0并不是真正的密钥，message会被解密为乱码）。for循环内部的第9～31行代码用于解密，并且与原始的凯撒密码加密程序类似，之后会对其进行解释。程序执行到下一次对for循环的迭代时，key被设置为1，继续进行解密。

尽管这个程序中没有用到，读者还是可以尝试向range()方法中传递两个整型参数，而不像本程序中只使用了一个。第1个参数是range的起始值，第2个参数则是range的终值（range从起始值开始取值，但并不会取到终值），两个参数用逗号隔开。

>>> for i in range(2, 6):
...　 print(i)
...
2
3
4
5

变量i的取值为2～6（含2而不含6）。

5　解密消息

for循环之下用于解密的代码，每次执行都将解密后的文本添加到translated字符串的末尾。在第11行，translated被置为空字符串。

 7. # 循环遍历所有可能的关键字
 8. for key in range(len(SYMBOLS)):
 9.　　 # 将translated设置为空字符串很重要，这样可以清除上一个迭代中
10.　　 # translated的值
11.　　 translated = ''

在for循环的开始将translated置空非常重要，如果不这么做，则本次尝试的密钥解密出的文本将被添加到上一次迭代后生成的字符串后面。

第16～30行和第5章中的凯撒密码加密程序几乎是相同的，但是要比第5章中的代码更简单一些，因为它们只被用作解密。

13.　　 # 程序的其余部分与凯撒程序几乎相同
14.
15.　　 # 循环遍历message中的每一个字符
16.　　 for symbol in message:
17.　　　　 if symbol in SYMBOLS:
18.　　　　　　 symbolIndex = SYMBOLS.find(symbol)

在第16行中，程序循环遍历了message中存储的每一个字符。每经过一次循环迭代，第17行就检查symbol是否存在于常量SYMBOLS中，如果存在，就对其进行解密。第18行的find()方法对symbol在SYMBOLS中的位置进行确定，并将这个位置的值记录在变量symbolIndex中。

随后，第19行从symbolIndex中减去key值进行解密。

19.　　　　　　 translatedIndex = symbolIndex - key
20.
21.　　　　　　 # 执行回环
22.　　　　　　 if translatedIndex < 0:
23.　　　　　　　　 translatedIndex = translatedIndex + len(SYMBOLS)

减法操作可能会导致translatedIndex的值小于0，这时就需要回到常量SYMBOLS的开头去寻找解密出的字符位置。第22行对可能的情况进行判断，如果出现了translatedIndex值小于0的情况，就为其加上66［len（SYMBOLS）的返回值］。

translatedIndex的值改变后，SYMBOLS[translatedIndex]就可以获取解密得到的字符了。第26行将这个字符添加到translated存储的字符串末尾。

25.　　　　　　 # 添加解密的字符
26.　　　　　　 translated = translated + SYMBOLS[translatedIndex]
27.
28.　　　　 else:
29.　　　　　　 # 添加未被加/解密的字符
30.　　　　　　 translated = translated + symbol

如果symbol的值没有在SYMBOLS中找到，则第30行将把它保持不变地添加到translated的结尾。

6　使用字符串标准化输出密钥及解密后的信息

虽然第33行是凯撒密码破解程序中唯一的一个print()方法，但它会得到多行执行结果，这是因为第8行的for循环每进行一次迭代，它就将被调用一次。

32.　　 # 显示可能的解密值
33.　　 print('Key #%s: %s' % (key, translated))

print()方法中的参数是一个使用了字符串标准化（string formatting，也叫作字符串插值）的字符串。字符串标准化使用%s将一个字符串放置到另一个字符串当中，在这个字符串的结尾，第1个%s被括号中的第一个值替换。

将下列代码输入交互式运行环境。

>>> 'Hello %s!' % ('world')
'Hello world!'
>>> 'Hello ' + 'world' + '!'
'Hello world!'
>>> 'The %s ate the %s that ate the %s.' % ('dog', 'cat', 'rat')
'The dog ate the cat that ate the rat.'

本例中，首先将字符串world插入字符串“Hello %s!”，替换掉%s。这个过程和连接起%s之前、待插入的字符串、%s之后这三部分文本的过程是类似的，当需要插入多个字符串的时候，%s按照这些字符串的顺序被依次替换。

字符串标准化往往比使用 + 操作符对字符串进行连接更便于输入，尤其是在面对长字符串的情况下。同时，与字符串连接不一样的是，使用字符串标准化甚至可以将非字符型的值（如整型）插入字符串中。将如下代码输入交互式运行环境。

>>> '%s had %s pies.' % ('Alice', 42)
'Alice had 42 pies.'
>>> 'Alice' + ' had ' + 42 + ' pies.'
Traceback (most recent call last):
　File "<stdin>", line 1, in <module>
TypeError: Can't convert 'int' object to str implicitly

使用字符串插值的时候，整数42可以非常顺利地插入字符串中，然而如果想要通过字符串连接将它插入字符串中，就会出现报错。

caesarHacker.py文件的第33行使用字符串标准化生成了一个包含变量key和translated的字符串。由于key中存储的是一个整数的值，因此使用字符串标准化就可以将它作为字符串的值传递到print()方法中了。