第2讲 密码学的基本概念和理论基础

第2阶段：常规现代密码学,从1949年到1975年。
标志：1949年Shannon发表的《保密系统的信

息理论》一文。信息论为对称密码系统建立了理 论基础，从此密码学成为一门科学。
以及《破译者》的出版和美国数据加密标准DES
的实施，标志着密码学的理论与技术的划时代的 革命性变革，宣布了近代密码学的开始。
21
代替密码和置换密码


代替密码（Substitution Cipher)是明文中的每一 个字符被替换成密文中的另一个字符。接收者对密 文做反向替换就可以恢复出明文。 置换密码(Permutation Cipher)又称换位密码 （Transposition Cipher)，加密过程中明文的字母 保持相同，但顺序被打乱了。
第2讲 密码学的基本概 念和理论基础
1
2.1 基本概念
2.1.1 什么是密码学 密码学是研究密码系统或通信安全的一门学科，分 为密码编码学和密码分析学。 密码编码学是使得消息保密的学科 密码分析学是要研究加密消息破译的学科
2
2.1前,密码技术的主要特 点是数据的安全基于算法的保密 。
明文X 加密机 密文Y
原来的明文X
解密机
单钥密码的加密、解密过程
8

双密钥系统又称为非对称密码系统或公开密钥系统。双密钥 系统有两个密钥，一个是公开的，用K1表示，谁都可以使 用；另一个是私人密钥，用K2表示。
K1 明文X 加密算法 密文Y K2 解密算法
原来的明文X
双钥密码的加密、解密过程
双密钥系统的主要特点是将加密和解密密钥分开。即用公 开的密钥K1加密消息，发送给持有相应私人密钥K2的人， 只有持私人密钥K2的人才能解密；而用私人密钥K2加密的 消息，任何人都可以用公开的密钥K1解密，此时说明消息 来自持有私人密钥的人。前者可以实现公共网络的保密通 信，后者则可以实现对消息进行数字签名。
6
2.1.4 密码体制的分类

几种不同的分类标准 1. 按操作方式进行分类 操作方式：是明文变换成密文的方法。 替换密码、换位密码。 替换密码又称代替密码是明文中的每一个字符被替换成 密文中的另一个字符。接收者对密文做反向替换就可以恢复 出明文。 换位密码又称置换密码，加密过程中明文的字母保持相 同，但顺序被打乱了。 2. 按照对明文的处理方法进行分类 流密码（将明文按字符逐位加密）。 分组密码（对明文进行分组后逐组加密）。
22
一、代替密码
在经典密码学中，有4种类型的代替密码： 1．简单代替密码又称单字母密码（Simple Substitution Cipher） 明文的一个字符用相应的一个密文字符代替。恺撒密码就是一 种简单的代替密码，它的每一个明文字母都由其右边第三个 字母代替。ROT13是建立在UNIX系统上的简单的加密程序， 它也是简单代替密码。在这种密码中A被N代替，B被O代替， 等等，每个字母是环移13所对应的字母。用ROT13加密文件 两遍便恢复出原始的文件： P=ROT13（ROT13（P））
24
举例：



为了创建多码代换密码，要使每个明文字符，既依赖于信息 的相关明文字符也依赖于明文字符的位置。这就表明密钥应 该是一个子密钥流，其中的每一个子密钥都取决于用子密钥 加密的明文字符的位置。也就是说，要用一个密钥流 k = (k1, k2, k3,...)，在这一密钥流中，ki 用来加密第i个明文 字符，以便在密文中创建第i个字符。 例如：自动密钥密码(autokey cipher)。在该密码中，密钥是 一个子密钥流，其中每一个子密钥都可以用来对明文中相关 的字符进行加解密。第一个子密钥是一个在A和B之间秘密 协议过的预先规定的值，第二个子密钥是第一个明文字符的 值(在0~25之间)，第三个子密钥是第二个明文字符的值，如 此等等。 密码的名称“自动密钥”是指，在加密过程中，子密钥是从 明文密码字符中自动创建的。 设初始密钥值k1 = 12，“Attack is today”密文应该是什么？ 25
7
密码体制的分类



几种不同的分类标准 3.按照使用密钥的数量进行分类 对称密钥（单密钥）、公开密钥（双密钥） 从密钥使用数量上看，密码系统分为单密钥系统和双密钥系 统 单密钥系统又称为对称密码系统或秘密密钥系统，其加密密 钥和解密密钥或者相同或者实质上等同，即从一个密钥得出 另一个。 K K
19
（2）曾有这样一件事，有一天，距斯巴达城很远的兵营 中来了一个专程从斯巴达城赶来送信的奴隶，兵营中 有位名叫莱桑德的将军读了信以后，感到很失望，因 为信中毫无重要消息，就随手把它扔到一边去了。可 是，刹那间，将军锐利的目光好像发现了什么，他立 即命令侍卫人员暂时回避，然后对这个奴隶说：“把 腰带给我。” 这是一条普通的腰带，只是在腰带周围雕刻着一串字 母，看上去毫无意义，大概只是做装饰之用。但当将 军把腰带螺旋式地绕在一根棍棒上时，奇迹出现了。 显现在棍棒上的字母不再是无意义的了。它告诉将军 一个极端重要的消息：斯巴达当时的同盟者波斯人正 在搞阴谋，企图谋反夺权；于是将军立即带着他的队 伍急速返回斯巴达城，粉碎了这起叛乱。
18
例子：Scytale密码和恺撒密码
（1）最先有意识的使用一些技术的方法来加密信息的可能是 公元前500年的古希腊人。他们使用的是一根叫scytale的棍 子。送信人先绕棍子卷一张纸条，然后把要写的信息打纵写 在上面，接着打开纸送给收信人。如果不知道棍子的粗细是 不可能解密里面的内容的，如下图所示。
20
（3）公元前50年，著名的恺撒大帝发明了一种密码叫做恺 撒密码。在恺撒密码中，每个字母都与其后第三位的字母 对应，然后进行替换。如果到了字母表的末尾，就回到开 始，如此形成一个循环。当时罗马的军队就用恺撒密码进 行通信。 恺撒密码明文字母表：A B C D E F G … X Y Z 恺撒密码密文字母表：D E F G H I J …A BC 26个字符代表字母表的26个字母，从一般意义上说，也可 以使用其它字符表，一一对应的数字也不一定要是3，可 以选其它数字。
Shannon保密系统模型
术语：明文、密文、密钥（加密密钥与解密密钥）、 加密、解密、加密算法、解密算法、加密系统
5
组成部分





X,明文（plain-text）： 作为加密输入的原始信息。 Y,密文（cipher-text）：对明文变换的结果。 E,加密（encrypt）：对需要保密的消息进行编码的过程， 是一组含有参数的变换。 D,解密（decrypt）：将密文恢复出明文的过程，是加密的 逆变换。 Z（K）,密钥（key）：是参与加密解密变换的参数。 加密算法：对明文进行加密时采取的一组规则或变化 解密算法：对密文进行解密时采用的一组规则或变化 加密算法和解密算法通常在一对密钥控制下进行，分别称为 加密密钥和解密密钥。 一个密码系统（或称密码体制或密码）由加解密算法以及所 有可能的明文、密文和密钥（分别称为明文空间、密文空间 和密钥空间）组成。
10
2. 密码分析的方法

密码分析 ：从密文推导出明文或密钥 。 密码分析：常用的方法有以下4类： 惟密文攻击（cybertextonly attack）； 已知明文攻击（knownplaintext attack）； 选择明文攻击（chosenplaintext attack）； 选择密文攻击（chosenciphertext attack）。
13
（3）选择明文攻击



密码分析者不仅知道一些消息的密文以及与之对应的明文， 而且可以选择被加密的明文（这种选择可能导致产生更多关 于密钥的信息）和对应的密文 ，并试图推导出加密密钥或 算法。 攻击者可以事先任意选择一定数量的明文，让被攻击的加密 算法加密，并得到相应的密文。目标是通过这一过程获得关 于加密算法的一些信息，以利于攻击者在将来更有效的破解 由同样加密算法（以及相关密钥）加密的信息。在最坏情况 下，攻击者可以直接获得解密用的密钥。 在公钥密码学中，这就是一个很现实的模式。因为公钥密码 方案中，加密用的密钥是公开的，这样攻击者就可以直接用 它来加密任意的信息。
3
密码学的发展历史

第3阶段：公钥密码学，1976年至今。
标志：1976年Diffie和Hellman发表了《密码学
新方向》一文，提出了适应网络上保密通信的公 钥密码思想 。
1978年RSA公钥密码体制的出现，成为公钥密
码的杰出代表，并成为事实标准，在密码学史上 是一个里程碑。
4
2.1.3 相关术语
16
2.1.6 加密的功能


保密性：基本功能，使非授权者无法知道消息的内容。 鉴别：消息的接收者应该能够确认消息的来源。 完整性：消息的接收者应该能够验证消息在传输过程中没有 被改变。 不可否认性：发送方不能否认已发送的消息。
17
2.2 传统密码

从古代密码出现一直到现代计算机诞生，密码学是 由基于字符的密码算法构成的。不同的密码算法是 字符之间互相代替或者是互相之间换位，好的密码 算法是结合这两种方法，进行多次计算。
9
2.1.5 密码分析
对通信双方而言，通信的一方将信息加密后发送给另一 方，是为了使攻击者即使得到密文也无法读懂。对于攻 击者来说，在不知道密钥的情况下，要想读懂密文，就 要根据他的知识以及掌握的情报来进行密码分析。
1. Kerckhoffs柯克霍夫斯假设


假定：密码分析者知道对方所使用的密码系统 包括明文的统计特性、加密体制（操作方式、处理方 法和加/解密算法 ）、密钥空间及其统计特性。 不知道密钥。 在设计一个密码系统时，目标是在Kerckhoffs 假设的前 提下实现安全 。

简单代替密码很容易破解，因为它没有将明文的不同字母的 出现频率掩盖起来。（例如E在正常的英语散文中出现频率最 高13%，其次是T、R、I、N、O、B等）。