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

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

本章大纲2.1基本概念

2.2传统密码及其破译

2.3Shannon的保密系统信息理论

2.4Simmons认证系统的信息理论

2.5概率论基础2.1基本概念2.1.2密码学的发展历史第1阶段：1949年以前,凭直觉和信念，一种艺术。第2阶段：从1949年到1975年。标志：1949年Shannon发表的《保密系统的信息理论》一文。第3阶段：1976年至今。标志：1976年Diffie和Hellman发表了《密码学新方向》一文，密码学上的一场革命。首次证明了在发送端和接收端不需要传输密钥的保密通信的可能性，开创了公钥密码新纪元。第4个阶段:1982年姚期智提出姚氏百万富翁-安全多方计算2000年图灵奖,唯一一位华人及亚洲人

谢尔比乌斯发明的加密电子机械名ENIGMA，在以后的年代里，它将被证明是有史以来最为可靠的加密系统之一亚瑟·谢尔比乌斯ENIGMA

史海钩沉马里安·雷杰夫斯基破译ENIGMA机的功臣

汉斯—提罗·施密特(Hans-Thilo波兰人，1888年出生在柏林的一个中产阶级家庭里）

史海钩沉2.1.1密码学的概念

密码学是研究密码系统或通信安全的一门学科,分为密码编码学和密码分析学。密码编码学是使得消息保密的学科，从事此行的称为密码编码者。密码分析学是研究加密消息的破译的学科，从事此行的称为密码分析者，精于此道的人被称为密码学家，现代的密码学家通常是理论数学家。2.1.33个术语Shannon模型组成部分X,明文（plain-text）：作为加密输入的原始信息。Y,密文（cipher-text）：对明文变换的结果。E,加密（encrypt）：是一组含有参数的变换。D,解密（decrypt）：加密的逆变换。Z,密钥（key）：是参与加密解密变换的参数。2.1.4密码体制的分类

密码学分类密码学(Cryptology):是研究如何实现秘密通信的科学。包括密码编码学和密码分析学。密码编码学(Cryptography):

主要研究对信息进行编码,实现信息保密性的科学。密码分析学(Cryptanalytics):主要研究、分析、破译密码的科学。密码编码学的分类

几种不同的分类标准

按操作方式进行分类操作方式：是明文变换成密文的方法。替代操作、置换操作、复合操作。按照使用密钥的数量进行分类对称密钥（单密钥）。公开密钥（双密钥）。按照对明文的处理方法进行分类流密码。分组密码。古典密码算法现代密码算法代换算法换位算法恺撒密码滚轮密码维吉尼亚密码希尔密码纵行换位对称算法公钥算法DESAES…RSA椭圆曲线…密码算法分类2.1.5密码分析

Kerckhoffs假设

假定：密码分析者知道对方所使用的密码系统包括明文的统计特性、加密体制（操作方式、处理方法和加/解密算法）、密钥空间及其统计特性。不知道密钥。在设计一个密码系统时，目标是在Kerckhoffs假设的前提下实现安全。密码分析分类密码分析：从密文推导出明文或密钥。密码分析：常用的方法有以下4类：惟密文攻击（cybertextonlyattack）；已知明文攻击（knownplaintextattack）；选择明文攻击（chosenplaintextattack）；选择密文攻击（chosenciphertextattack）。目前，最常见的是已知明文和选择明文攻击惟密文攻击

密码分析者知道一些消息的密文（加密算法相同），并且试图恢复尽可能多的消息明文，并进一步试图推算出加密消息的密钥（以便通过密钥得出更多的消息明文。

已知：C1=EK（M1），C2=EK（M2），……，Ci=EK（Mi）推导出：M1，M2，，Mi；K或者找出一个算法从Ci+1=EK（Mi+1）推出Mi+1。比如，pstscript格式加密文件总是以相同的格式开头；电子金融消息往往有标准化的文件头或标志。已知明文攻击

密码分析者不仅知道一些消息的密文，也知道与这些密文对应的明文，并试图推导出加密密钥或算法（该算法可对采用同一密钥加密的所有新消息进行解密。

已知：M1，C1=EK（M1）；M2，C2=EK（M2）；……，Mi，Ci=EK（Mi）；推导出：K或者找出一个算法从Ci+1=EK（Mi+1）推出Mi+1的算法。选择明文攻击

选择明文攻击的破译者除了知道加密算法外，他还可以选定明文消息，并可以知道对应的加密得到的密文，即知道选择的明文和对应的密文。例如，公钥密码体制中，攻击者可以利用公钥加密他任意选定的明文，这种攻击就是选择明文攻击。已知：M1，C1=EK（M1）；M2，C2（M2）；……，Mi，Ci=EK（Mi）；其中M1，M2，……,Mi是由密码分析者选择的。推导：K或者找出一个算法从Ci+1=EK（Mi+1）推出Mi+1的算法。与选择明文攻击相对应，破译者除了知道加密算法外，还包括他自己选定的密文和对应的、已解密的原文，即知道选择的密文和对应的明文。

需要掌握的内容：加密算法截获的部分密文自己选择的密文消息相应的被解密的明文选择密文攻击基于加密信息的攻击类型密码系统一个好的密码系统应满足：系统理论上安全，或计算上安全；系统的保密性是依赖于密钥的，而不是依赖于对加密体制或算法的保密；加密和解密算法适用于密钥空间中的所有元素；系统既易于实现又便于使用。2.1.6鉴别、完整性和不可否认性

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

古典加密技术代替密码（substitutioncipher）明文中的每个字符被替换成密文中的另一个字符。简单代替，即单字母密码，如Caesar密码；多码代替密码；多字母代替密码；多表代替密码，如Vigenère密码。置换密码（permutationcipher）：又称换位密码（transpositioncipher），并没有改变明文字母，只改变了这些字母的出现顺序。代替密码代替密码的特点单字母代换密码：明文中字母的出现频度、重复字母的模式和字母相互之间的结合模式等统计特性不变，安全性差。多码代替密码：没有隐藏明文中不同字母的统计特性，安全性有所提高。多字母代替密码：字符块被成组加密，有利于抗击统计分析。多表代替密码：有多个映射表，可隐藏单字母出现的频率分布。凯撒密码ABCDEFGHIJKLMNOPQRSTUVWXY0123456789101112131415161718192021222324Z25如：data对应数据序列30190,当k=5时，得密文序列85245,则对应的密文为ifyf。可把26个字母A~Z看作是数字0~25，密钥k看作是循环右移若干位(0~25之间)，则恺撒密码的加密可表示为c=(m+k)mod26，c为密文序列；则解密可表示为P=(c-k)mod26，P为原文序列代换密码举例恺撒密码的效果是使字母以统一偏移量循环移位试能破译下面这段话。密文：VjkukuEcguctEqfgABCDEFGHIJKLMLOPQRSTUVWXYZYZABCDEFGHIJKLMLOPQRSTUVWX

设偏移量k为24(-2)，解密是逆变换，k也是24明文：ThisisCaesarCode评价：结构过于简单，极易分析破解；移位密码很容易受到唯密文攻击。凯撒密码分析单表代换密码Caesar密码中仅有25种可能的密钥，是很不安全的。通过允许任意代换，密钥空间将会急剧增大。这是因为每条消息用于一个字母表(给出从明文字母到密文字母的映射)加密。如果密文行是26个字母的任意置换，那么就有26！或大于4*1026种可能密钥。特点：穷举攻击很难，但是由于保留了密码语言的规律，所以可以用密码语言的规律进行破解，如密码语言中的字符使用频率、双字符组合使用频率等。英文字母的相对使用频率多表代换密码特征：1、采用相关的单表代换规则集；2、由密钥决定给定变换的具体规则。此类算法中最著名、最简单的是Vigenère。Vigenère密码构成明文：每个字符惟一对应一个0~25间的数字。密钥：一个字符串，其中每个字符同明文一样对应一个数字，代表位移值，如a表示位移0，b表示位移1，c表示位移2，......）。加密过程：将明文数字串依据密钥长度分段，并逐一与密钥数字串相加（模26），得到密文数字串；最后，将密文数字串转换为字母串。解密：采用模26减运算）构造Vigenère密码矩阵。26个密码水平放置，最左边是其密钥字母，顶部排列的是明文的标准字母表。Vigenère密码举例1加密过程：给定密钥字母X和明文字母Y，密文字母是位于X行和Y列的那个字母。加密一条消息需要与消息一样长的密钥。通常，密钥是一个密钥词的重复，比如密钥词是deceptive,消息是：wearediscoveredsaveyourselfVigenère密码加密过程Vigenère密码的特点Vigenère密码的强度在于每个明文字母对应着多个密文字母，且每个使用唯一的字母作为密钥词，因此，字母出现的频率信息被隐蔽了。Vigenère密码攻击分析(1)区分Vigenère密码和单表代换密码

单表代换密码中密文统计特性应与明文统计特性相同；(2)密钥词长度的确认如果两个相同的明文序列之间的距离是密钥词长度的整数倍，那么产生的密文序列也是相同的；反之，密文中出现两个相同的字母组，则对应的明文字母组不一定相同。(3)密钥词长度整数倍位置是单表代换如果密钥词长度是N，那么密码实际上包含了N个单表代换。一次一密使用与消息一样长且无重复的随机密钥来加密消息，它是不可攻破的。它产生随机数出与明文没有任何统计关系。假设使用27个字符(第27个字符是空格)的Vigenère密码,但是这里使用的一次密钥和消息一样长。密文:ankyodkyurepfjbyojdsplreyiunofdoiuerfpluyts密钥:pxlmvmsydoftyrvzwctnlebnecvgdupahfzzlmnyih明文:mrmustardwiththecandlestickinthehall密文:ankyodkyurepfjbyojdsplreyiunofdoiuerfpluyts密钥:mfugpmiydgaxgoufhklllmhsqdqogtewbqfgyovuhwt明文:missscarletwiththeknifeinthelibrary一次一密的分析如果给出任何长度与密文一样的铭文，都存在着一个密钥产生这个明文。一次一密的安全性完全取决于密钥的随机性。实际中使用一次一密的基本难点：(1)产生大规模随机密钥的实际困难。(2)更令人担忧的是密钥的分配和保护。代替密码的特点单字母代换密码：明文中字母的出现频度、重复字母的模式和字母相互之间的结合模式等统计特性不变，安全性差。多码代替密码：没有隐藏明文中不同字母的统计特性，安全性有所提高。(明文攻击,抗唯密文攻击)多字母代替密码：字符块被成组加密，有利于抗击统计分析。(已知明文攻击)多表代替密码：有多个映射表，可隐藏单字母出现的频率分布。置换密码谜底信，方成安息息息深式为全安化技刻，世的全发术地推界研保展的改动性究障的发变着问和能当展了社题发力务与人会。展也之广们文加，是急泛的明速加我。应生，信强国用活已息信信活已息信信信，方成安息息息深式为全安化技刻，世的全发术地推界研保展的改动性究障的发变着问和能当展了社题发力务与人会。展也之广们文加，是急泛的明速加我。应生，信强国用活已息信信原文"猜猜看？滚筒密码置换技术——栅栏技术栅栏技术:按照对角线的顺序写入明文,而按行的顺序读出作为密文。例如:深度为2的栅栏技术加密”meetmeafterthetogaparty”密文：mematrhtgpryetefeteoaat置换技术——矩形块置换把消息一行一行地写成矩形块,然后按列的次序读出，但是列的次序被打乱。列的次序就是算法密钥。明文：attackpostphoneduntiltwoamxyz密钥：4312567密文：ttnaaptmtsuoaodwcoixknlypetz与原始明文相同的字母频率特性置换技术——多步置换可以通过对前面的消息在用相同的算法再加密一次。明文：attackpostphoneduntiltwoamxyz密钥：4312567密文：nscyauopttwltmdnaoiepaxttokz隐写术隐写术可以隐藏信息的存在，而密码学则是通过对文本信息的不同转换而实现的对外不可读。一种简单却很耗时的隐写术可由一段无伤大雅文本的字词重新排列而成。侦探Morse的疑惑YourpackagereadyFriday21stroomthreepleasedestroythisimmediately2.3Shannon的保密系统信息理论

1949年，Shannon发表了一篇题为《保密系统的信息理论》的论文。用信息论的观点对信息保密问题进行了全面的阐述。宣告了科学的密码学时代的到来。香农用统计的观点研究信息的传输和保密问题。Shannon的保密系统信息理论目的：在信道有干扰的情况下，使接收的信息无错误或差错尽可能小。通信系统模型目的：使窃听者即使在完全准确地收到了接收信号的情况下也无法恢复出原始消息。保密系统模型一个保密系统（P，C，K，E，D）称为完善的无条件的保密系统，如果H(P)=H(P|C),其中，P为明文集合，C为密文集合，K为密钥集合，E为加密算法,D为解密算法,则完善保密系统存在的必要条件是H(P)≤H(K)。(唯密文攻击条件下)要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。存在完善保密系统如：一次一密（one-timepad）方案；不实用。信息熵完善保密性下节课内容实际上安全计算上是安全：算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。可证明安全：从理论上证明破译它的计算量不低于解已知难题的计算量。密码体制的安全性（2）伪密钥和惟一解距离

当分析者截获到密文c时，他首先利用所有的密钥对其进行解密，并得到明文m′＝Dk(c)，k∈K。接下来，对于所有有意义的消息m′，他记录下与之对应的密钥。这些密钥构成的集合通常含有多个元素，并且至少含有一个元素，即正确的密钥。人们把那些可能在这个集合中出现但并不正确的密钥称为伪密钥（spuriouskey）。一个保密系统的惟一解距离定义为使得伪密钥的期望数等于零的n的值，记为n0，即在给定的足够的计算时间下分析者能惟一地计算出密钥所需要的密文的平均量。用于衡量在惟密文攻击下破译一个密码系统时，密码分析者必须处理的密文量的理论下界。2.4Simmons认证系统的信息理论

Simmons认证系统的信息理论1984年，Simmons首次提出了认证系统的理论。内容：将信息论用于研究认证系统的理论安全性和实际安全性问题，指出认证系统的性能极限以及设计认证码所必须遵循的原则。地位:保密系统中shannon理论。认证理论的主要研究目标：(1)推导欺骗者欺骗成功的概率的下界；(2)构造欺骗者欺骗成功的概率尽可能小认证码。认证码基本要素有3个：信源集合；消息集合；编码规则集合，其中每一个编码规则由一个秘密密钥来控制。发送者的任何一个编码规则都是从信源集合到消息集合的一个映射，这个映射的每一个原像可能有一个像，也可能有几个像。如果发送者的每个编码规则的每一个原像只有一个像，则称这种认证码为无分裂的认证码。如果发送者的每个编码规则的每一个原像不只一个，则称这种认证码为有分裂的认证码。

认证系统模型一种是无仲裁者的认证系统模型。在这种模型中，只有3种参加者，即消息的发送者、接收者和入侵者。消息的发送者和接收者之间相互信任，他们拥有同样的秘密信息。另一种是有仲裁者的认证系统模型。在这种模型中，有4种参加者，即消息的发送者、接收者、入侵者和仲裁者，信息的发送者和接收者之间相互不信任，但他们都信任仲裁者，仲裁者拥有所有的秘密信息并且不进行欺骗。本节主要研究无分裂的、没有保密功能的、无仲裁者认证系统模型。无仲裁者的认证系统模型无仲裁者的认证系统特点发送者和接收者之间相互信任，共同对付入侵。最终目的：能使发送者通过一个公开的无干扰信道将消息发送给接受者，接收者不仅能收到消息本身，而且还能验证消息是否来自于发送者以及消息是否被入侵者窜改过