[工学]第2章密码学的基本概念和信息.ppt

第2章 密码学的基本概念和信息理论基础,密码学的起源和发展, 1949年之前 密码学是一门艺术 19491975年 密码学成为科学 1976年以后 密码学的新方向公钥密码学,谢尔比乌斯发明的加密电子机械名ENIGMA，在以后的年代里，它将被证明是有史以来最为可靠的加密系统之一,亚瑟谢尔比乌斯,ENIGMA,史海钩沉,马里安雷杰夫斯基,破译ENIGMA机的功臣 汉斯提罗施密特(Hans-Thilo 波兰人，1888年出生在柏林的一个中产阶级家庭里）,史海钩沉,密码学分类,密码学(Cryptology): 是研究如何实现秘密通信的科学。包括密码编码学和密码分析学。 密码编码学(Cryptography): 主要研究对信息进行编码,实现信息保密性的科学。 密码分析学(Cryptanalytics):主要研究、分析、破译密码的科学。,密码编码学的分类,几种不同的分类标准 按操作方式进行分类 操作方式：是明文变换成密文的方法。 替代操作、置换操作、复合操作。 按照使用密钥的数量进行分类 对称密钥（单密钥）。 公开密钥（双密钥）。 按照对明文的处理方法进行分类 流密码。 分组密码。,密码算法分类,古典密码算法,现代密码算法,代换算法,换位算法,恺撒密码 滚轮密码 维吉尼亚密码 希尔密码,纵行换位,对称算法,公钥算法,DES AES ,RSA 椭圆曲线 ,Kerckhoffs假设,假定：密码分析者知道对方所使用的密码系统 包括明文的统计特性、加密体制（操作方式、处理方法和加/解密算法 ）、密钥空间及其统计特性。 不知道密钥。 在设计一个密码系统时，目标是在Kerckhoffs 假设的前提下实现安全 。,密码分析分类,密码分析 ：从密文推导出明文或密钥 。 密码分析：常用的方法有以下4类： 惟密文攻击（cybertextonly attack）； 已知明文攻击（knownplaintext attack）； 选择明文攻击（chosenplaintext attack）； 选择密文攻击（chosenciphertext attack）。 目前，最常见的是已知明文和选择明文攻击,惟密文攻击,密码分析者知道一些消息的密文（加密算法相同），并且试图恢复尽可能多的消息明文，并进一步试图推算出加密消息的密钥（以便通过密钥得出更多的消息明文。 已知：C1=EK（M1），C2=EK（M2），Ci=EK（Mi） 推导出：M1，M2，Mi；K或者找出一个算法从 Ci+1= EK（Mi+1）推出Mi+1。,已知明文攻击,密码分析者不仅知道一些消息的密文，也知道与这些密文对应的明文，并试图推导出加密密钥或算法（该算法可对采用同一密钥加密的所有新消息进行解密。 已知： 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的算法。,与选择明文攻击相对应，破译者除了知道加密算法外，还包括他自己选定的密文和对应的、已解密的原文，即知道选择的密文和对应的明文。 需要掌握的内容： 加密算法 截获的部分密文 自己选择的密文消息 相应的被解密的明文,选择密文攻击,密码系统,一个好的密码系统应满足： 系统理论上安全，或计算上安全； 系统的保密性是依赖于密钥的，而不是依赖于对加密体制或算法的保密； 加密和解密算法适用于密钥空间中的所有元素； 系统既易于实现又便于使用。,加密的要求,保密性：基本功能，使非授权者无法知道消息的内容。 鉴别：消息的接收者应该能够确认消息的来源。 完整性：消息的接收者应该能够验证消息在传输过程中没有被改变。 不可否认性：发送方不能否认已发送的消息。,古典加密技术,代替密码 （substitution cipher） 明文中的每个字符被替换成密文中的另一个字符。 简单代替，即单字母密码，如Caesar密码； 多码代替密码； 多字母代替密码； 多表代替密码，如Vigenre密码。 置换密码（permutation cipher）： 又称换位密码（transposition cipher） ，并没有改变明文字母，只改变了这些字母的出现顺序。,代替密码的特点,单字母代换密码 ：明文中字母的出现频度、重复字母的模式和字母相互之间的结合模式等统计特性不变，安全性差。 多码代替密码 ：没有隐藏明文中不同字母的统计特性 ，安全性有所提高。 多字母代替密码 ：字符块被成组加密 ，有利于抗击统计分析。 多表代替密码 ：有多个映射表，可隐藏单字母出现的频率分布。,代换密码举例,凯撒密码,如：data 对应数据序列 3 0 19 0 , 当k=5时，得密文序列8 5 24 5, 则对应的密文为ifyf。 可把26个字母AZ看作是数字025，密钥k看作是循环右移若干位(025之间)，则恺撒密码的加密可表示为 c =(m+k) mod 26 ，c为密文序列； 则解密可表示为P=(c-k) mod 26， P为原文序列,恺撒密码的效果是使字母以统一偏移量循环移位 试能破译下面这段话。 密文：V j k u k u E c g u c t E q f g A B C D E F G H I J K L M L O P Q R S T U V W X Y Z Y Z A B C D E F G H I J K L M L O P Q R S T U V W X 设偏移量k为24(-2)，解密是逆变换，k 也是24 明文：T h i s i s C a e s a r C o d e 评价：结构过于简单，极易分析破解；移位密码很容易受到唯密文攻击。,凯撒密码分析,置换密码分析,给定加密的消息: PHHW PH DIWHU WKH WRJD SDUWB 由于（）加解密算法已知 （）可能尝试的密钥只有6个 通过强力攻击得到明文： meet me after the toga party. 移位密码很容易受到唯密文攻击。K=3,谜底,信，方成安息息 息深式为全安化 技刻，世的全发 术地推界研保展 的改动性究障的 发变着问和能当 展了社题发力务 与人会。展也之 广们文加，是急 泛的明速加我。 应生，信强国 用活已息信信活已息信信,信，方成安息息息深式为全安化 技刻，世的全发术地推界研保展 的改动性究障的发变着问和能当 展了社题发力务与人会。展也之 广们文加，是急泛的明速加我。 应生，信强国用活已息信信,原文,滚筒密码,“猜猜看？,Vigenre密码,构成 明文：每个字符惟一对应一个025间的数字。 密钥：一个字符串，其中每个字符同明文一样对应一个数字，代表位移值，如a 表示位移 0，b 表示位移 1，c 表示位移 2， ）。 加密过程： 将明文数字串依据密钥长度分段，并逐一与密钥数字串相加（模26），得到密文数字串； 最后，将密文数字串转换为字母串。,利用Vigenre密码，使用密钥word加密信息computer。 明文：comp uter 密钥：word word 密文：ycds qhvu,Vigenre加密举例,Vigenre cipher-分析破译,分析： Vigenre保留了字符频率某些统计信息 重码分析法：间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个相同的子串对应的密文相同的可能性很大。,Shannon的保密系统信息理论,1949年， Shannon发表了一篇题为保密系统的信息理论的论文。 用信息论的观点对信息保密问题进行了全面的阐述。 宣告了科学的密码学时代的到来。,通信系统模型,目的：在信道有干扰的情况下，使接收的信息无错误或差错尽可能小。,保密系统模型,目的：使窃听者即使在完全准确地收到了接收信号的情况下也无法恢复出原始消息。,密码体制的安全性（1）,无条件安全或完善保密性（unconditionally secure）： 不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文； 具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。,完善保密性,一个保密系统（P，C，K，E，D）称为完善的无条件的保密系统，如果H(P)=H(P|C),其中，P为明文集合，C为密文集合，K为密钥集合，E为加密算法,D为解密算法,则完善保密系统存在的必要条件是H(P)H(K)。可见，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。 从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。 存在完善保密系统 如：一次一密（one-time pad）方案；不实用。,密码体制的安全性（2）,实际上安全 计算上是安全：算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。 可证明安全：从理论上证明破译它的计算量不低于解已知难题的计算量。,伪密钥和惟一解距离,当分析者截获到密文c时，他首先利用所有的密钥对其进行解密，并得到明文mDk(c)，kK。接下来，对于所有有意义的消息m，他记录下与之对应的密钥。这些密钥构成的集合通常含有多个元素，并且至少含有一个元素，即正确的密钥。人们把那些可能在这个集合中出现但并不正确的密钥称为伪密钥（spurious key）。 一个保密系统的惟一解距离定义为使得伪密钥的期望数等于零的n的值，记为n0，即在给定的足够的计算时间下分析者能惟一地计算出密钥所需要的密文的平均量。 用于衡量在惟密文攻击下破译一个密码系统时，密码分析者必须处理的密文量的理论下界。,认证系统的信息理论,内容：将信息论用于研究认证系统的理论安全性和实际安全性问题，指出认证系统的性能极限以及设计认证码所必须遵循的原则。 目的：一个是推导欺骗者欺骗成功的概率的下界；另一个是构造欺骗者欺骗成功的概率尽可能小的认证码。,认证码,基本要素有3个： 信源集合； 消息集合； 编码规则集合，其中每一个编码规则由一个秘密密钥来控制。,认证系统模型,一种是无仲裁者的认证系统模型。在这种模型中，只有3种参加者，即消息的发送者、接收者和入侵者。消息的发送者和接收者之间相互信任，他们拥有同样的秘密信息。 另一种是有仲裁者的认证系统模型。在这种模型中，有4种参加者，即消息的发送者、接收者、入侵者和仲裁者，信息的发送者和接收者之间相互不信任，但他们都信任仲裁者，仲裁者拥有所有的秘密信息并且不进行欺骗。,无仲裁者的认证系统模型,无仲裁者的认证系统数学描述,一个无分裂的、没有保密功能的、无仲裁者的认证系统，可由满足下列条件的四重组（S，A，