各位同学 大家好
今天我们来一起讨论古典密码
古典密码应该说有着悠久的发展历史
虽然这些密码大都比较简单
现在已经非常少的使用
但是研究这些密码的原理
对于理解、构造和分析现代密码都是十分有用的
古典密码主要分两大类
一类是置换密码
第二类是代换密码
所谓置换密码
是指在加密的过程中
明文字母保持不变 但是字母的顺序被打乱
第二类代换密码
它在加密的时候是明文字母被替换
但是顺序保持不变
所以它两个各自有各自的特点
代换密码又可分成三类
第一类叫做单表代换
单表代换是指
一个明文字母对应的密文字母是确定的
比方说A用D来代
F用H来代
都是确定的
那么多表代换
是指一个明文字母可以表示为多个密文字母
这时候就不是一一对应的了
A可能用F或者是P来替代
所以它是多表代换
第三类是多字母代换
这个多字母代换就更复杂一些
那么我们这节课主要是来讲一下
单表代换的杰出代表--恺撒密码
多表代换的代表--维吉尼亚密码
还有多字母代换--普莱费尔密码
以及费纳姆的一次一密
最后讲一下置换密码
再讲几个实例
代换密码
公元前1世纪恺撒大帝就用它来做过加密
后来密码学家们又发明了各种形式的代换密码
像单表代换、多表代换、多字母代换
虽然这些密码在今天看来比较简单
但是它充分显示了人的智慧和创造力
我们看一下恺撒密码
那么恺撒密码应该是古罗马大帝--恺撒
他发明的一种单表代换密码
它是最早的有记载的密码体制之一
历史学家 苏埃托尼乌斯
在他的著作《罗马十二帝王传》
记载了恺撒曾用此方法对重要的军事信息进行加密
下面是这个书中的一段话
如果需要保密
信中便使用暗号
也即改变字母顺序
使局外人无法组成一个单词
如果想要读懂它和理解它们的意思
得用第4个字母代替第1个字母
也就是以D来代替A
以此类推
其实看看后面这张图
看看后面这张图
我们就非常清楚了
你看前面是正常的排序
ABCDEF一直排下去
那么下面这个排序
对应关系就变了
A就对应了D 对吧
B就对成了E
C就对成了F
所以把这个字母表的位置依次向后推了三位
对吧
所以就得出了下面这个对应的表
A、B、C、D、E、F、G、一直到Z
那么把它替换以后
替换成什么呢
在密文里的表现
A就是D、B就是E、C就是F
就这样一个一一对应的关系
到了后边X是与A相对应
又循环回来了
Y是与B对应 Z是与C对应
所以我们根据代换的字母表
可以将明文“students”替换为后面一串字母
我们看这一串字母我们就读不懂了
如果是你不知道密钥的话
你很难理解这是什么东西
那么这是简单的代换
还有一种是广义的恺撒密码
刚才是往后移三位
这个是移五位
K可以是任意的位数
那么移成5为就变成什么了呢
我们看 上面的是A、B、C、D一直到Z
把它编码从0到25 对吧
当移位是5的话
A就对应于F
B就对应于G
C是对应于H 对吧
一直往后 以此类推
因此我们就说这时候对应关系就发生了改变
所以恺撒密码它的优点是什么呢
加密公式比较简单而且容易理解
缺点呢 它所用的语言是已知的
因为我们看一看就是26个英文字母
所以容易识别出这个所用的语言
第二 想想这样一个移位
我们只要测试25次
一定会把密钥给找出来、把密文破掉
所以这种密码是非常简单的
容易被穷举法破译
我们再看看多表代换
维吉尼亚密码是多表代换的一个非常优秀的代表
其实这种方法早有记录
有一本叫《吉奥万·巴蒂斯塔·贝拉索先生的密码》的书
有所记载
在19世纪时 人们误传维吉尼亚创造了这种方法
因此称为"维吉尼亚密码"
其实维吉尼亚发明了自动密钥密码
而不是维吉尼亚密码
维吉尼亚密码是为了增加密码破译的难度
在单表代换的基础上扩展出多表代换密码
维吉尼亚密码设计的基本思想
是先形成一个密钥表
然后再根据密钥
来决定使用哪一行的替换表来进行代换
那么在加密的时候
我们采用一个词组 一个英文单词作为一个密钥
密钥词组中的每一个字母都作为一个索引
来确定某个代换
确定某个代换
加密时需要循环使用代换表
来完成明文字母到密文字母的转换
最后所得到的密文字母
这个序列就是密文
其实 我们可以用更简单的一种办法
进行维吉尼亚加密
刚才说是查表
其实我们可以利用一个模26的加法运算
来做这个加密的运算
比方说我们把A到Z进行编码
编码成0到25
有一组明文——Data Security
我们用best这个单词作为密钥
那么怎么加密呢
我们首先把data security这一个字符串进行编码
d就是3、a是0、t是19
以此类推
我们再把密钥放在下面
大家看看第三行的best、best、best 放了三遍
best用数字表示出来就是
b用1表示、e是用4、s是18、t是19
我们看第一列
d和b这两个代码所代表的数字相加是4
4对应的密文就是e
那么a是0
明文的a是0 密钥e是4
0加4还得4
所以我们看到它的密文字母也是e
t是19 s是18
这个加起来是多少呢
这个加起来是37
37模26刚好是多少
多少？ 11
11把它对应到字母就应该是l
所以后面以此类推
因此 经过这样一个代换以后
明文data security
就变成了后边这一串看不懂的文字
就是一个密文了
这个方法 看上去非常简单
所以这种加密方法在现在看来不堪一击
用计算机来搜索的话 很容易会搜索出来
所以它的优点是相对复杂的密钥
第二 相同的字母被加密为不同的密文字母
有可能两个A加密出来不像前面
它是对应不同的英文字母
那么缺点呢
如果是密文足够长
这期间会有大量重复的密文序列出现
通过计算重复密文序列间的公因子
分析者可以精确的猜出密钥的长度
像这个best 4位长度
他就可以估算出来 这是非常容易破解的
那后来呢 为了增加攻击者破译的难度
普莱费尔就设计出了这个多字母代换的密码
这个看起来就稍微复杂一些
这是一种在1854年发明的密码
当时是由莱昂.普莱费尔
把它用在了英国军队和政府部门中
其实这个密码应该是查尔斯.惠斯通发明的
他是一个在电学、光学和音乐等方面
有非常大的建树的一个人 也是个多面手
他还发明了电报机
他发明这个密码以后
普莱费尔就把它进行了推广
因为普莱费尔是在政府部门工作
所以他有这种推动力
这种密码就广泛的用在政府中对信息的加密
我们看看它的这个思想是什么
它是将明文中的双字母组合作为一个单元
这个明文 把它分为两个字母、两个字母的一组
一个组就分两个字母
将这些单元转换为密文的双字母组合
加密步骤分别为编制密码表
然后再整理明文 最后再编写密文
它的算法是基于一个5×5的字母矩阵
该矩阵是用一个密钥来构造
从左至右、从上至下 填入该密钥的字母
注意这里要去掉重复字母
比如两个e这种组合 一定要把重复去掉
然后再以字母表顺序
将余下的字母填入矩阵剩余空间
我们看看字母I和J被算作同一个字母
因为这是5×5的矩阵
五五二十五 只能填25个字母
还多一个 英文字母有26个
这时候就把I和J看作一个字母
当密钥是下面这个harpsichord
harpsichord英文单词是一个叫大键琴的英文
大键琴是在16到18世纪 西方用的一个乐器
我们看看怎么放入这个密钥表
H第一个 A第二个 R第三个
P第四个 S第五个
I回过来放在第二行的第一个
C是放在第二行的第二个
后面就有意思了 又出来一个H
大家看密钥其中有一个H
由于前面第一个字母就是H
所以不再放了 接着放O
O后面是R
我们看看前面第一行第三列也有个R
所以也不能放
所以这时候就放O 因为不能重复
最后是D
前面有背景的那就是密钥字母
接下来我们还要进一步填充
把这个5×5的矩阵填满
A有了 所以就剩下的是B 按顺序
B完了是E
E完了是F、G、K、L、M、N
O前面已经有了 所以不再放 就变成Q
R和S前面都有了 所以也不写了
后面就是T、U、V、W、X、Y、Z
所以这25个字母就放到这个字母表里去了
大家看看这个字母表有什么特征呢
首先I和J同视为I
然后这个字母是没有重复的
先写密钥 先把密钥字母写进去
然后再用其他剩余的字母来补齐
就是这样一个表
那么我们看看具体的代换规则
由于矩阵中没有字母J
那么明文中如果是有J的话 要用I来代替
比方说JOY这个英文单词
我们这个时候就把J替换为I
第二个规则
对明文进行分组 每两个字母为一组
如果明文的字母为奇数
则在最后加上一个无效的字母来补位
随意加一个
前面经过替换之完了以后
那就是JOY就变成IOY
我再把它两两分组 那不够分的
三个字母分两组不够分的
所以前面一组是IO
后面就没有了
我们就随意补一个
你可以用X 也可以用P
用什么都可以 把它补齐
那么第三个规则
如果某一组中有两个相同的字母 比方说ee
这时候我们在中间插入一个任意填充的字母
然后再重新分组
像ee这样一个连着两个字母的
我就把后边的e变成v
然后把它分成三组 一组是两个字母
对吧 听明白了吧
我们看看具体代换的时候怎么来代换
如果是这两个明文字母是处于同一行
同一行就是上面那个代换
比方说我们p、s 怎么替换呢
显然根据前面的代换规则——同行代换
p后面是s 所以p就被s来替换
s只能是再回过头来被前面的h所替换
所以经过加密以后 ps就变成了sh
我们再看看同列代换
如果是有两个字母hv
hv在这个5×5的矩阵的同一列
V显然要用H来替换 而H是用I来替换
所以H、V这个明文呢加密以后就变成了I、H
那么如果是这两个字母
处于不同的行、不同的列怎么办
我们这时候还有一个规则，
明文的第一个字母将由与第一个字母同行
与第二个字母同列的字母替换
比方说N N被谁替换呢
被与它同行的、而与第二个字母同列的
那就是U了 对不对
底下是同行，在最右侧
是与第二个字母同列的 一个字母U来替换
第二字母呢 将由与第二个字母同行
第二个字母同行的是第一行，对吧？
与第一个字母同列的字母替换
那就是第一个字母呢，第一列就是A啦，对吧
所以呢 我们经过替换以后 按照规则
A、S就替换为密文U、N
明白吧？很清楚
那我们再看下加密一句话
刚才是加密两个字母
比方说我们有一句英文
叫 meet at the schoolhouse
就是"我们在学校里面见面"
我们首先把它分组
"Meet"先把它分成"me"和"et"两组
"at"是单独一组
"th"是一组 "es"一组
"ch"一组 "ox"一组
"ol"一组，等等，这样分下来
那分下来呢，我们就按照刚才讲的规则
最左边就是我们刚才讲的5×5的矩阵 替换表
我们来看怎么替换 就看一两个就可以了
"m"、"e"是同一列，所以我们用前面的规则
是同列代换规则
怎么代换呢？
往下代换 对吧？
"m"显然是替换成"v"
"e"呢替换成什么？ "m"对不对？
所以呢 "me"就变成了"vm"
那么"et"呢？ 我们再看"e"和"t"
"e"和"t"是处于不同行不同列
所以"e"在替换的时候
要用与它同行 与第二个字母同列的
是什么呢？ 是"k" 对不对？
而"t"呢是用与它同行
而与第一个字母同列的字母来替换 那就是"m"
所以"et"被"km"所取代 以此类推
所以我们可以理解的英文
就变成了右上角这个密文的字符串
你是理解不了的
但解密的时候 刚好是把它倒过来就完了
你只要是知道了这个字母表就可以
但是你很难猜到这个密钥的英文单词是什么
像HARPSICHOD
那我们要知道这个单词是密钥的话
那很容易解密
但是你如果不知道的话
要去猜 那也不是容易猜的 对不对
所以普莱费尔密码是一种更复杂的加密方法
普莱费尔密码使用方便
可以抵抗频度分析法攻击
那么特别是在1854年到1855年的克里米亚战争
克里米亚我们以前都不知道
这次乌克兰事件出来以后
我们才知道这个克里米亚
原来是一个兵家必争之地啊
战略位置非常重要
而且在1899年的布尔战争中也被广泛应用
直到1915的一战时期才被破解
在电影《国家宝藏》第二部中
英国女王曾向美国内战中的南方同盟
写过两封关于黄金城的密信
以期南方同盟能够获得巨大的财富
从而战胜北方政府
其中第二封信就是用普莱费尔密码来加密的
普莱费尔密码 它也有优点 同时也有缺点
通过双字母组合可以使得密文空间大大增加
相同的字母将被加密为不同的密文字母
字符出现频率在一定程度上被均匀化
因为相同的两个字母
我们刚才看了 一定要用其它字母来替换
有同学可能要讲 解密出来了以后 这个单词可能就错了
错了怎么办呢 自动纠错啊
像"sleep"，对吧？
"sleep"的那个"e"就变成了"ev"，对不对？
但是其实你还可以自动纠错 对不对？
那么缺点呢 可以用双频率法进行破译
我们刚才讲了，对单频度的分析它能够抵抗
但是对于双频率法进行破译呢 它就有困难了
下面我们讲一次一密密码
一次一密密码是因为代换密码的固有缺点
所以才使人们想起设计这样一个一次一密密码
我们知道代换密码经常是使用固定的密钥
所以这类密码对于破译者来讲越来越容易
如果我们老是采用一个固定不变的密钥来
对信息加密
势必造成攻击者有机可乘
他可以根据某些统计规律来破解你的密钥
如何使我们的加密方案更加安全
这也成为我们后人探索热点
因此呢人们就发明了一次一密密码体制
最早提出一次一密加密的是费纳姆
费纳姆是在1917年为电报通信
设计的费纳姆密码
之后经过约瑟夫 马宾的改进 称作一次一密
那么我们看 这个加密其实非常简单
它的基本原理是将明文与密钥进行摩尔相加
比方说第一列是11010
第二列是密钥 是11101
那么经过摩尔运算以后 就变成了00111
这就是密文 其实就是一个摩尔加
不同的是什么呢？
它是密钥每次都要进行改变 每次都要换
所以在加密的时候呢
一次一密密码呢
需要使用一个大的真随机数的字母集作为密钥
而且把字母集写在纸上
并把它装订成一个乱码本
加密的时候呢
需要将明文字符和乱码本的密钥字符
进行模26的加法运算 跟刚才的多表代换一样
大家看到右上角就是一个一次乱码本
写的很小的一个本子
右下角是把这个乱码本呢放在一个核桃里
传过去
所以一次一密的优点呢就是密钥本身是随机的
而且密钥只使用一次
那么即使获得了上次通信的密文和密钥
攻击者仍然无法确定下次通信的真正的密钥
就是给你密钥呢 下次又变了
所以即使给你密文 给你密钥
你最多只能破译上次通信的密文
下一次你就破译不了了 因为密钥又改变了
缺点呢 它需要建立一个庞大的随机字母集
一个集合
这个工作量是巨大的
而且存在密钥分发的问题
比如刚才我们说把它装在核桃里
你伪装 要送给接收者
在密钥的传递过程中有可能被敌手截获
所以风险也是很大的
有人把一次一密也称为不可破解的密码体制
因为密钥密钥总是再换 永不重复
所以你永远也破不了
它是从理论上来讲
它是永远破不掉的一种密码体制
我们在后面讲到现代密码学的时候
我们知道所有现代密码学的密码算法
都是实际上是安全的
所以一种叫做theoritical security
就是理论上是安全的
那就是一次一密
在后面我们讲现代密码学 讲了很多的算法
都是实际安全的
叫pratical security
也就是给我足够的资源 给我足够的时间
我一定能够把它破掉
只不过是在当前的计算机的计算能力下
你要破解这样的一个密码体制
需要什么呢 需要一个天文数字年
所以叫做实际安全的
但是如果说我们有一个
比方说一个速度足够快的量子计算机
那么现代的很多密码体制就很难抵抗了
都能被很快的破掉
在后面我们再讲
今天我们借着一次一密在这先做一个引子
我们最后再看一类密码 叫置换密码
置换密码是古典密码的重要一员
人类仅仅通过对明文字母进行重新排序
就可以实现对明文的加密
刚才是代换 把A变成D
这个是把你的字母顺序打乱
虽然置换密码的设计思想比较简单
但是它们对现代密码的贡献不可磨灭
后面我们会非常清楚
置换密码又称为换位密码
是通过重新排列明文中元素的位置
而不改变元素本身来实现加密的体制
就是字母的顺序给你倒一倒
字母本身不变
这个在1990年 美国艺术家吉姆·桑伯恩
创造了一个刻满密码的雕塑作品 叫Kryptos
大家看看右上角 是在美国中情局的门口
立了这样一个雕塑
整个密码分为四个部分
其中第一、二部分是多表代换密码
第三部分是置换密码
至于第四部分
2010年11月桑伯恩本人给出一点提示
但是目前仍然没有人破解这个密码
等你们如果到了美国中央情报局门口
看这个雕塑的时候
希望你们能把它破解掉
那么我们看一下置换密码的基本思想
其实就是简单的换位
每次置换都可以用一个置换矩阵来表示
且都有一个与之对应的逆置换矩阵
第一个表 密钥是hand
然后hand 可以按照字母的顺序把它写成
h就是3 a是1 n是4 d是2
是吧1234
按照这个先后顺序把它写出来
然后把Meet at the schoolhouse
这句英文按照一行一行的写下来
然后按照密钥的字母顺序来进行置换
大家看看 a就跑到最前面来了
d这一列跑到第二列
h跑到第三列 n跑到第四列
英文这句话就打乱了
密文 你把它按列读出来的话
那就变成了最右下角的这一部分
前面第一个就是 etsou
再到第二列读 thhhe
第三列读 maeoo
最后呢 etcls
所以这个密文你是读不懂的
你很难理解
但是这个密钥就是hand这个单词
很有意思
所以置换密码的优点就是加密的过程比较简单
计算量小 速度快
缺点呢 它完全保留了字符的统计特性
而且加密结果比较简单 容易被破译
因为字母只是变了一下顺序
原来是什么字母加密以后还是什么字母
只不过是次序给你捣乱了
最后我们看第一个图
就是惠斯通密码的一个实际的装置
是一个密码设备 它像我们现在的一个手表
对不对
它顺时针旋转
这个指针每次都指向下一个明文字母
圆盘随着混合的密文字母旋转
Kryha这个密码机是由Alexander发明的
这是一种多表加密设备
密钥长度是442
它的周期是固定
超过442这个又开始重复
所以一个有数量不等的齿轮引导密文轮
不规则的运动
我也没看到 大家看看就行了
但是这个还是体现了当时的人设计的这种智慧
我们做一下小结
古典密码 可以把它分成三大类
代换密码和费纳姆的一次一密
再就是置换密码
代换密码又可以把它分成三个小的类别
一个是单表代换 一个是多表代换
再就是多字母代换
我们说 代换密码和置换密码
在实际中通常是结合起来使用
先用代换来加密 再用置换做第二次加密
代换和置换这两种操作
实际上形成了现代密码的雏形
它们充分的体现了Shannon密码学的思想
Shannon在他的一篇涉及到密码学的文章表述中
他提到任何一个密码的算法应该含有两部分
一部分就是扩散 一部分就是混淆
Shannon的密码设计思想其实就是体现在
古典密码的代换和置换这两种操作中
在第四讲我们会讲现代密码学
到时候大家就会对代换和置换
这两种操作就会有更加深入的认识
我们看看在现代密码算法中
扩散和混淆这两个基本的功能
是怎么通过代换和置换这两种实际操作完成的
好了 今天我们的课就讲到这儿
下节课我们将讲机械密码
谢谢大家