Python密码学入门:凯撒密码

异步社区官方博客

1 什么是密码学

自古以来,间谍、士兵、黑客、海盗、商人等人,大多依靠密码学来确保他们的秘密不会人尽皆知。密码学是一门使用秘密编码的学科。想要明白密码长什么样,看一看下面两段文本。

nyr N.vNwz5uNz5Ns6620Nz0N3z2v

N yvNwz9vNz5N6!9Nyvr9

y0QNnvNwv tyNz

Nw964N6!9N5vzxys690,N.vN2z5u-

3vNz Nr Ny64v,N.vNt644!5ztr vNz

N 6N6 yv90,Nr5uNz Nsvt64v0N

yvN7967v9 BN6wNr33Q N-m63 rz9v

!NN2 Nuwv,N9,vNN!vNrBN3zyN4vN

N6 Qvv0z6nvN.7N0yv4N 4 zzvNN

vyN,NN99z0zz6wz0y3vv26 9

w296vyNNrrNyQst.560N94Nu5y

rN5nz5vv5t6v63zNr5.

N75sz6966NNvw6 zu0 wtNxs6t

49NrN3Ny9Nvzy!

以上左侧的文本是一个经过加密(转换为秘密编码)的消息。对于那些不知道如何将密码解密(将其转换回原始的英文消息)的人来说,它完全不可读。而以上右侧的文本是随机的“胡言乱语”,没有任何隐藏的含义。加密使不懂得如何解密的人即便拿到了密码,也无法参透其中的含义,因为加密后的消息和随机的“胡言乱语”毫无区别。

密码学家使用和研究密码。当然,这些秘密消息并不总是保密的。密码分析学家,又称为密码破解者或黑客,可以破解密码并读懂他人的加密消息。本书讲解如何使用各种技术对信息进行加密和解密。

2 编码与密码

与密码不同的是,编码的方式是可以公开获得并理解的。编码使用符号替换消息中的内容,任何人都可以查阅符号是如何进行翻译的。

19世纪初,一个著名的编码来源于电报的发展,它使各地通过电线进行即时通信成为现实。用电报发送信息比之前骑马去送一大袋信件的传统方式要快得多。然而,电报不能直接发送纸上书写的字母,它只能发送两种类型的电脉冲:称为“点”的短脉冲和称为“线”的长脉冲。

要将字母表中的字母转换成脉冲类型中的点和线,需要一个编码系统将英语翻译成电脉冲。英语转换成电报发送的点和线的过程称为编码,而收到消息时把电脉冲转换成英语的过程称为解码。电报(和后来的无线电)对消息进行编码和解码的方式称为摩尔斯电码,如表1-1所示。摩尔斯电码是由Samuel Morse和Alfred Vail开发的。

电报操作员通过在拥有一个按钮的电报机上敲击点和线,可以向世界另一边的人传达英语信息,而且仅需要很短的时间!

与编码相对,密码是一种特定类型的编码方式,目的是保证消息的机密性。可以使用密码将可理解的英文文本(称为明文)转换为隐藏秘密的乱码(称为密文)。密码是使明文和密文相互转换的一组规则。这些规则中,通常会使用一个只有通信者知道的密钥来进行加密或解密。在这本书中,读者将学习几个密码,并编写程序来使用这些密码对文本进行加密和解密。但在此之前,让我们先用简单的纸质工具手动完成文本加密。

3 凯撒密码

即将学习的第一个密码是凯撒密码,它以早期使用者Julius Caesar的名字命名。它简单易学,但也因此极易被密码分析员破解。但是,它仍然可以用来进行练习。

凯撒密码通过替换字母完成加密,每个字母由字母表中其后特定位数的字母代替。例如,Julius Caesar将字母表向后移动3个字母的位置,然后用得到的新字母表中的字母替换原消息中的每个字母。

例如,消息中的每一个A都变成D,每个B都变成E等。当Caesar需要将字母表末尾的字母(如Y)移位时,他会绕回到字母表的开头,移动3个位置到B。在本节中,将使用凯撒密码手动加密消息。

3.1 密码轮

为了更方便地使用凯撒密码将明文转换为密文,将使用一个密码轮,也称为密码盘。密码轮包含两个由字母组成的环,每个环有26个槽(为字母表的26个字母准备)。外圈表示明文中的字母,内圈表示在密文中相对应的字母。内圈同样把字母从0到25进行标号,这些数字代表加密密钥,这里的加密密钥是指将A移动到内环上对应的字母所需经过的字母位数。因为轮盘是圆形的,用大于25的密钥移位会使字母表绕一整个圈,所以移动26位与移动0位相同,移动27位与移动1位相同,以此类推。

读者可以通过原书网站在线访问虚拟的密码轮,其形式如图1-1所示。为了旋转密码轮,需要先单击它,然后移动鼠标光标,直到想要的配置到位。再次单击鼠标,密码轮停止旋转。

在本书的配套资源中也可以获得可打印的纸版密码轮。剪下两个圆圈,把它们叠放,小的圆圈放在大的圆圈中间。在两个圆圈的中心插入一个大头钉或曲头钉,这样它们就可以旋转了。

无论使用纸质密码轮还是虚拟密码轮,都可以完成手动加密。

图1-1 在线密码轮

3.2 使用密码轮进行加密

开始加密前,请先用英文在一张纸上写下待加密的消息。在这个例子中,待加密消息是“THE SECRET PASSWORD IS ROSEBUD”。接下来,旋转密码轮的内轮,直到它的槽与外轮中的槽相匹配。注意外轮上字母“A”旁边的点,点在内轮上最接近的数字就是加密密钥。

例如,在图1-1中,外轮的“A”对应内轮的8。现在使用8作为加密密钥来加密上面例子中的消息,如图1-2所示。

图1-2 用8作为密钥的凯撒密码加密消息

在外轮上找到消息中的每一个字母,并用内轮中对应的字母替换它。在这个例子中,消息的第一个字母是“T”(在“THE SECRET…”中的第一个“T”),因此在外轮上找到字母“T”,然后在内轮上找到对应的字母,也就是字母“B”。秘密信息总是用“B”替换“T”。(如果使用不同的加密密钥,则明文中的每个T将被替换为其他的字母。)消息中的下一个字母是“H”,加密时变成“P”,而字母“E”变成“M”。外轮上的每个字母总是加密为内轮上固定的对应字母。为了节省时间,在查找“THE SECRET…”中的第一个“T”并且发现它加密变成“B”之后,就可以将消息中的每个“T”都替换为“B”,因此每个字母只需查找一次。

在对整个消息进行加密之后,原始消息“THE SECRET PASSWORD IS ROSEBUD”就变成了“BPM AMKZMB XIAAEWZL QA ZWAMJCL”。注意,非字母字符(如空格)是没有改变的。

现在,可以把这个加密后的消息发送给他人(或者自己保存),除非告诉他们密钥,否则没有人能够读懂消息的含义。请确保加密密钥是保密的,因为任何知道消息是用密钥8加密的人都可以读懂密文。

3.3 使用密码轮进行解密

要对密文进行解密,需要查找从密码轮的内轮到外轮的映射。假设接收的密文为“IWT CTL EPHHLDGS XH HLDGSUXHW”,除非知道密钥(或者是一个聪明的黑客),否则将无法解密该消息。幸运的是,朋友已经提前告知,他们对消息加密时使用的密钥是15。该密钥的密码轮如图1-3所示。

图1-3 密钥设为15的密码轮

现在可以将外轮上的字母“A”(下面带点的那个字母)与内轮上的数字15(字母“P”)相对应。然后,在内轮上找到密文的第一个字母,即“I”,并查看外圈对应的字母,即“T”。密文中的第二个字母“W”解密为字母“H”。对密文中剩下的字母进行解密,还原成明文,可以得到完整的消息“THE NEW PASSWORD IS SWORDFISH”,如图1-4所示。

图1-4 用密钥为15的凯撒密码解密消息

如果使用不正确的密钥(如16),则解密的消息将是“SGD MVV OZRRVNQC HR RVNQCEHG”,依然不可读。除非使用正确的密钥,否则解密出来的消息也是不可理解的。

3.4 通过计算进行加密和解密

使用密码轮实现凯撒密码的加密和解密是十分便捷的,但是也可以通过数学计算进行加密和解密。在此过程中,从“A”到“Z”写出字母表中的字母,在每个字母下标注数字0~25。从“A”下面的0开始,“B”下面是1,以此类推,直到“Z”下面是25,如图1-5所示。

图1-5 为字母标号0~25

可以用这些数字来表示对应的字母。这是一个强有力的概念,有了它的存在,就可以在字母上进行数学运算。如果将字母“CAT”表示为数字2、0和19,分别加3获得数字5、3和22,则根据图1-5,这些新的数字表示字母“FDW”,这样就实现了为“CAT”加密。稍后,会设计一个计算机程序实现这一计算过程。

要运用算术实现凯撒密码的加密,请找到要加密的字母下方的数字,并将其加上密钥的值,得到的和就是对应密文字母下的数字。可以使用1~25的任意数字作为密钥,例如,使用密钥13加密“HELLO. HOW ARE YOU?”。首先,找到“H”下的数字7,然后加上13:7+13=20。因为数字20在字母“U”之下,所以字母“H”加密得到“U”。

类似地,加密字母“E”(4)为4 + 13=17。因为17对应的是“R”,所以“E”加密得到“R”,以此类推。

直到字母“O”之前的过程都很顺利。“O”之下的数字是14,但是14加上13是27,而序号只到25。如果字母对应的数字和密钥相加的和是26或者更多,则需要从结果中减去26。在此例中,27−26=1。1对应的字母是“B”,因此“O”用密钥13加密得到“B”。消息中的每一个字母加密完成后,密文是“URYYB. UBJ NER LBH?”

要对密文进行解密,需要减去密钥而不再是进行加法运算。密文字母“B”对应的数字是1,1减去13得到−12。类似于“减去26”的加密规则,当解密结果小于0时,需要加上26。因为−12 + 26=14,所以密文字母“B”解密为“O”。

本文摘自刚刚上架的《Python密码学编程 第2版》,[美] 阿尔·斯维加特(Al Sweigart) 著,郑新芳,赵怡翾 译。

通过阅读本书,您将学习如何通过 Python 编程制作和破解密码,以此创建和发送密文!学习 Python 编程的基础 知识之后,您将从使用反向和凯撒密码的简单程序开始,了解为公开密钥加密的方法,该加密方法用于保护在线事务的 正常运作,包括数字签名和电子邮件。另外,您还将学习如何使用经典密码(如置换密码和维吉尼亚密码)对文本进行加密。 每个程序都包含完整的代码和逐行说明。本书结尾,您将学习如何使用 Python 进行编码。

您还将学习以下内容:

简要目录

第1章 制作纸质密码学工具免费

第2章 在交互式运行环境中编程免费

第3章 字符串及编写程序

第4章 反向密码

第5章 凯撒密码

第6章 用暴力算法破解凯撒密码

第7章 通过置换密码实现加密

第8章 解密置换密码

第9章 编写测试程序

第10章 文件的加密与解密

第11章 编程检测英语文本

第12章 破解置换密码

第13章 仿射密码的模运算模块

第14章 编写仿射密码

第15章 破解仿射密码

第16章 编写简单代换密码

第17章 破解简单代换密码

第18章 编写维吉尼亚密码

第19章 频率分析

第20章 破解维吉尼亚密码

第21章 一次一密

第22章 素数的查找与生成

第23章 为公钥密码生成密钥

第24章 编写公钥密码算法

附录 调试Python代码