pdf第2章 密码学的基本概念和信息理论基础

第2章密码学的基本概念和信息理论基础

1主要内容2.1基本概念2.2经典密码及其破译2.3Shannon的保密系统信息理论2.4Simmons认证系统的信息理论22.1基本概念2.1.1什么是密码学2.1.2密码学的发展历史2.1.3五个术语2.1.4密码体制的分类2.1.5密码分析2.1.6加密的功能32.1.1什么是密码学密码学是研究密码系统或通信系统的一门学科，分为密码编码学和密码分析学。密码编码者密码分析者42.1.2密码学的发展历史第1阶段：1949年以前。

第2阶段：从1949年到1975年。标志：1949年Shannon发表的《保密系统的信息理论》一文。第3阶段：1976年至今。标志：1976年Diffie和Hellman发表了《密码学新方向》一文。5古典加密早妆未罢暗凝眉，迎户愁看紫燕飞，无力回天春已老，双栖画栋不如归。6Shannon模型72.1.3五个术语X,明文（plain-text）：作为加密输入的原始信息。Y,密文（cipher-text）：对明文变换的结果。E,加密（encrypt）：是一组含有参数的变换。D,解密（decrypt）：加密的逆变换。Z,密钥（key）：是参与加密解密变换的参数。82.1.4密码体制的分类几种不同的分类标准按操作方式进行分类操作方式：是明文变换成密文的方法替代操作、置换操作、复合操作按照使用密钥的数量进行分类对称密钥（单密钥）公开密钥（双密钥）按照对明文的处理方法进行分类流密码分组密码9Kerckhoffs假设假定：密码分析者知道对方所使用的密码系统包括明文的统计特性、加密体制（操作方式、处理方法和加/解密算法）、密钥空间及其统计特性。不知道密钥。在设计一个密码系统时，目标是在Kerckhoffs假设的前提下实现安全。102.1.5密码分析密码分析：从密文推导出明文或密钥。密码分析常用的方法有以下4类：惟密文攻击（cybertextonlyattack）；已知明文攻击（knownplaintextattack）；选择明文攻击（chosenplaintextattack）；选择密文攻击（chosenciphertextattack）。11密码分析惟密文攻击:密码分析者知道一些消息的密文（加密算法相同），并且试图恢复尽可能多的消息明文，并进一步试图推算出加密消息的密钥（以便通过密钥得出更多的消息明文。已知明文攻击:密码分析者不仅知道一些消息的密文，也知道与这些密文对应的明文，并试图推导出加密密钥或算法（该算法可对采用同一密钥加密的所有新消息进行解密)。

12密码分析选择明文攻击:密码分析者不仅知道一些消息的密文以及与之对应的明文，而且可以选择被加密的明文（这种选择可能导致产生更多关于密钥的信息），并试图推导出加密密钥或算法（该算法可对采用同一密钥加密的所有新消息进行解密）选择密文攻击:密码分析者能够选择不同的密文并能得到对应的明文，密码分析的目的是推导出密钥。13密码系统一个好的密码系统应满足：系统理论上安全，或计算上安全；系统的保密性是依赖于密钥的，而不是依赖于对加密体制或算法的保密；加密和解密算法适用于密钥空间中的所有元素；系统既易于实现又便于使用。142.1.6加密的功能保密性：基本功能，使非授权者无法知道消息的内容。鉴别：消息的接收者应该能够确认消息的来源。完整性：消息的接收者应该能够验证消息在传输过程中没有被改变。不可否认性：发送方不能否认已发送的消息。152.2经典密码及其破译2.2.1代替密码2.2.2置换密码16【例2．1】简单的加密形式，基于块加密和异或运算。消息：0011010101000101001101010010101110010101消息块：0011010101000101001101010010101110010101密钥：0101010101010101010101010101010101010101密文：0110000000010000011000000111111011000000

17代替密码（1）代替密码（substitutioncipher）：明文中的每个字符被替换成密文中的另一个字符。简单代替，即单字母密码;明文中字母的出现频度、重复字母的模式和字母相互之间的结合模式等统计特性不变，安全性差。如Caesar密码；

多码代替密码；没有隐藏明文中不同字母的统计特性，安全性有所提高。

18代替密码（2）多字母代替密码：字符块被成组加密，有利于抗击统计分析,如Playfair密码。多表代替密码：有多个映射表，可隐藏单字母出现的频率分布,如Vigenère密码。19【例2．2】著名的Caesar密码：加密时26个英文字母循环后移3位，解密时则循环前移3位。该方法最早在公元前50年，被罗马大帝JuliusCaesar使用。ABCDEFGHIJKLMNOPQRSTUVWXYZ则密文为：PRP2.设明文为：CHINA则密文为:FKLQD1.设明文为：MOM20【例2．3】代替密码体制的一般定义，设P=C=K=Z26,

这里P,C,K,Z26分别表示明文空间，密文空间，密钥空间和26个整数（对应26个英文字母）组成的空间。很明显，明文，密文和密钥的取值范围是一样的，它们的空间也是相同的。对于任意的定义：加密：即明文为x，密钥为k（实际上就是每个英文字母向后循环移k位），密文为y。

解密：使用该方法时，要求26个字母与模26的剩余类集合建立一一对应关系，如A对应0，B对应1，…，Z对应25，不区分大小写。21ABCDEFGHI012345678JKLMNOPQR91011121314151617STUVWXYZ181920212223242522当k=3时，即为著名的Caesar密码设明文为：China，对应的数字为：278130加密：C:e3(2)=2+3(mod26)=5,对应着字母Fh：e3(7)=7+3(mod26)=10,对应着字母KI:e3(8)=8+3(mod26)=11,对应着字母LN:e3(13)=13+3(mod26)=16,对应着字母Q A:e3(0)=0+3(mod26)=3,对应着字母D所以明文“China”基于Caesar密码被加密为“FKLQD”

23解密就是加密过程的逆过程 解密：F:d3(5)=5-3(mod26)=2,对应着CK:d3(10)=10-3(mod26)=7,对应着H L:d3(11)=11-3(mod26)=8,对应着I Q:d3(16)=16-3(mod26)=13,对应着N D:d3(3)=3-3(mod26)=0,对应着A

即“FKLQD“经Caesar密码解密恢复为”China”（不区分大小写）Caesar密码的特点：明文语言集已知，并且易于识别，结构过于简单，所以很容易被攻击。

24【例2．4】（简单代替）移位密码，即向后移k位，k是任意的，故认为k是密钥，共有26个密钥，看看使用密钥的代替加密。选用一个英文短语或单词作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后将字母表中的其他字母依此写于此字母串之后。设密钥为：key明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ对应的密文：keyabcdfghijlmnopqrstuvwxz因此，明文“China”,对应的密文为：“yfgmk”25【例2．5】（多字母代替）Playfair密码，将明文中的一个字母组合作为一个单元对待，并将这些单元转换为密文双字母组合。Playfair密码是基于一个5×5字母矩阵，该矩阵使用一个密钥来构造，构造方法是：从左到右，从上到下依此填入密钥的字母（去除重复的字母），然后再以字母表顺序依此填入其他字母。字母I和J被算做一个字母。对每对明文字母P1,P2的加密方法如下：261）若P1,P2在同一行上，则对应的密文C1,C2分别是紧靠在P1,P2右端的字母。其中第一列被看做是最后一列的右方（解密时反向）2)

若P1,P2在同一列上，则对应的密文C1,C2分别是紧靠在P1,P2下方的字母，其中第一行被看做是最后一行的下方（解密时反向）3)若P1,P2不在同一行上，也不在同一列上，则C1,C2是由P1,P2确定的矩阵的其他两角的字母。并且C1和P1，C2和P2同行。（解密时反向）4)

若P1=P2，则插入一个字母（比如Q，需要事先约定）于重复字母之间，并用前述方法处理5）若明文字母数是奇数，则在明文的末端添加某个事先约定的字母作为填充。27密钥是:PLAYFAIRISADIGRAMCIPHER,则构造的字母矩阵如图所示。PLAYFI/JRSDGMCHEBKNOQTUVWXZ28如果明文是：P=playfaircipher先将明文分成两个一组：playfaircipher基于表对应的密文为：LAYFPYRSMRAMCDPLAYFI/JRSDGMCHEBKNOQTUVWXZ29Vigenère密码构成明文：每个字符惟一对应一个0~25间的数字。密钥：一个字符串，其中每个字符同明文一样对应一个数字，代表位移值，如a表示位移0，b表示位移1，c表示位移2，......）。加密过程：将明文数字串依据密钥长度分段，并逐一与密钥数字串相加（模26），得到密文数字串；最后，将密文数字串转换为字母串。30ABCDEFGHI012345678JKLMNOPQR91011121314151617STUVWXYZ181920212223242531【例2．5】明文串：theywillarrivetomorrow，采用密钥k=Monday对其加密的过程如首先，依据上表，将密钥与明文转化为数字串：k=(12,14,13,3,0,24)m=(19,7,4,24,22,8,11,11,0,17,17,8,21,4,19,12,14,17,17,14,22)

其次，将明文数字串依据密钥匙长度分段，并逐一与密钥数字串相加（模26），得到密文数字串

3219

742422811110171781214133024121413302452117122623251320176

214191412141717142212141330241214133718617121235125

33C=(5,21,17,1,22,6,23,25,13,20,17,6,7,18,6,17,12,12,3,5,1,25)最后，依据上表将密文数字串转换为字母串c=FVRBWGXZNURGHSGRMMDFBZ

34明文密钥35Vigenère密码的密码分析（1）主要方法有：Kasiski测试法；字典攻击。36Kasiski测试法基本原理：对于密钥长度为d的Vigenère密码，如果利用给定的密钥表周期性地对明文字母进行加密，则当明文中有两个相同的字母组在明文序列中间隔的字母数为d的倍数时，这两个明文字母组对应的密文字母组一定相同；反之，如果密文中出现两个相同的字母组，则其对应的明文字母组不一定相同。找出密文中的相同字母组，并研究其相间隔的字母数，确定这些字母数的最大公因子，便有可能得到有关密钥长度的信息37字典攻击发送方和接收方会选择容易记忆的词或短语做密钥。那么对于发送方和接收方熟悉的攻击者就可能会尝试这种密钥,只需要生成一个短的多的最有可能的密钥列表即可。如果明文和密钥都不是没有意义的文字时，字典攻击就有可能成功。38置换密码