信息论与编码密码学

1、近代密码学的发展史保密学的理论基础序列（流）密码分组（块）密码-DES-RSA密码学的发展前沿密码学Cryptography-目录1近代密码学发展史准确的现代术语为“密码编制学”简称为“编密学” 与之相对的研究的专门研究如何破解密码的学问称为“密码分析学”(Cryptanalysis). Cryptography=希腊文的Kruptos + grapheinhiddento write2 密码学密码编制学密码分析学近代密码学发展史-23近代密码学发展史-3 20世纪60年代一部与众不同的著作-David Kahn 的破译者出现了虽然此书没有任何新的技术思想，但它的意义在于它涉及到的相当广泛的领

2、域，而且在于它使成千上万原本不知道密码学的人了解密码学。从而使新的密码学文章慢慢地开始源源不断地被编写出来了。4近代密码学发展史-4 第一次世界大战结束时，公开的密码学文献几乎殆尽。只有一个突出 的例外，仙农(Claude Shannon）的文章保密系统的通信理论出现在1949 年贝尔系统技术杂志上，是战时工作的产物。这 篇文章在第二次世界大战结束后即被解密。5近代密码学发展史-5 Alan Turing 数理逻辑天才、现代计算机设计思想的创始人，第二次世界大战在年仅26岁Turing领导下完成了一部针对德国“谜”型机的密码破译机，每秒钟可处理2000个字符，人们给它起了个绰号叫“炸弹（Bom

3、b)”。6近代密码学发展史-6一个传统的密码体制S定义为： S (M, C, K, E, D)； message space 代表的是明文空间 key space 代表的是密钥空间 cipher space 代表的是密文空间MKC加密映射族： E = fk: M C | k K 脱密映射族： E = gk: C M | k K 7安全性的含义：1）接收端防止窃听；2）发送端防止伪造。数学模型保密学的理论基础 明文源MA加密T1m加密T2信道C解密T2解密T1明文宿MB密钥源K1密钥源K伪造者窃听者密钥源K-1密钥源K28基本定理保密学的理论基础-29惟一解距离和明文冗余度惟一解距离ud：当窃听

4、者获取的密文长度大于之，则密码成为可破译的；反之，小于它时，密码理论上是不可破译的，因为它具有多个解的可能性。实现理想保密，则ud趋向无穷大，有两种可能：1）完全保密体制：密钥熵H(K)无穷大2）理想保密体制：密钥熵有限，但信源的冗余度D=0，即完全随机。这样，就得到两个启示：1）实现保密的过程实质上是使密文随机化的过程，可通过增大密钥，2)或减少明文的冗余度。保密学的理论基础-3 10实际保密系统一、减少冗余度：1）直接法，采用信源编码的方法；2）间接法，采用扩散和混淆的方法将信源的冗余度在更大的范围上扩散开或加以扰乱混淆，间接实现减少信源冗余度的目的。序列加密（扩散法）、DES（混淆与扩散

5、）二、增大密钥量保密学的理论基础-4 11优点适合实时加密，如实时的数字话音等理论成熟，其设计、分析较易较分组密码易于实现基本概念序列流密码 12经典算法介绍DESDES算法的历史回顾DES算法如何实现？DES算法的基本思想DES算法如何被破解？13DES-21973年美国国家标准局NBS (National Bureau of Standard)正式向社会公开征集加密算法。1974年IBM正式向NBS提交了应征方案。NBS会同美国国家保密局（NSA National Security Agency)研究发现这是唯一满足各项要求的方案。在此方案基础上形成的数据加密标准DES (data enc

6、ryption standard)于1977年1月15日颁布，同年7月正式生效成为美国联邦标准FIPS (Federal Information Processing Standard )。其后大约每5年对DES的安全性进行一次审查评估，最后一次是1993年进行的，批准DES的使用终结日期是1998年的12月。14DES-3 DES (Data Encryption Standard)算法是美国政府机关为了保护信息处理中的计算机数据而使用的一种加密方式，是一种常规密码体制的密码算法，目前已广泛用于电子商务系统中。 ：加解密双方在加解密过程中要使用完全相同的一个密钥，密钥就经过安全的密钥信道由发

7、方传给收方。什么是DES？ 基本思想15DES-416DES-5 该算法输入的是64比特的明文，在64比特密钥的控制下产生64比特的密文；反之64比特的密文在解密的过程下产生64位的明文。64比特的密钥中含有8个比特的奇偶校验位，所以实际有效密钥长度为56比特。具体算法实现17DES-618DES-7 穷举法破译DES 密码的问题。设已知一段密码文C及与它对应的明码文M，用一切可能的密钥K加密M，直到得到E（M）=C，这时所用的密钥K即为要破译的密码的密钥。穷举法的时间复杂性是T=O（n）DES 算法破解19DES-8 对于DES密码n=25671016，即使使用每秒种可以计算一百万个密钥的大

8、型计算机，也需要算106天才能求得所使用的密钥，因此看来是很安全的。但是到了1997美国有一程序员采用Sever-Client方式在众多网上志愿者的帮助下利用Internet 96天成功破密获取密钥。20DES-91999年1月，EFF（Electronic Frontier Foundation)用DES Crack (内含1856块芯片)和网络分布式计算，在22小时15分钟内破解了RSA数据安全公司提出的“DES 挑战者III”21经典算法RSARSA算法的历史回顾RSA算法的基本思想RSA算法如何实现？22经典算法RSA1976年，W.diffie和M.hellman首次提出了公开密钥密

9、码体制的概念，其中最关键的思想是寻找一个“单向函数”23经典算法RSA什么叫“单向函数”呢？ X YY=F(x) Y XX=F-1(y)不能实现241977年R.Rivest A.Shamir L.Adleman 提出了第一个比较完善的公开密钥密码体制，即著名的RSA体制。25经典算法RSA 选择两个大质数 和 ,每个都大于 ；计算 和 ； 选择一个与 有关的质数,令其为 ；找到一个 满足 保密 ; 算法步骤：qp10100 n=p*qz=(p-1)*(q-1) zdede*d=1(mod z)26经典算法RSA 将明码（当作位串看待）划分成块，使得每个明码报文 落在 之间，这可以通过将明码分

10、成每块有 位的组来实现，并且使得 是使 成立的最大整数。P0Pnkzknk27C=Pe( mod n) P=Cd ( mod n)28经典算法RSA RSA的安全性在于加密变换： C=F(P)=Pe（mod n）的单向性 ：敌方从e和n中无法求出脱密的密钥d，产生这种单向性的原因是基于大整数分解在计算上的困难。RSA的安全性29经典算法RSA 如果能有效的分解出n=p*q,则能很容易的求出z=(p-1)*(q-1)最后使用穷尽的方法来找出与z有关的所有质数d使其能与公钥e之间有如下的关系： d*e=1(mod n)RSA的安全性30公共密钥算法RSA 现在我们就来看这个简单的例子。 我们选择了

11、p=3，q=11，则n=33，z=20。d的一个适合的值是d=7，因为7和20没有公共因子，e可以通过求解式7e1（模20）得出，即e=3。明码报文P的一个密码C，则由C=P3（模33）将密文解密。给出明码“SUZANNE”的加密作为例子。因质数选择得很小，所以P必须小于33，因此，每个明码块只能包含一个字符。结果形成了一个单一字母表代换密码。这个例子安全吗？3132密码学的发展前沿PKI算法如何实现？PKI算法的基本思想33密码学的发展前沿PKI（Public Key infrastructure，公钥基础设施）从字面上理解，PKI就是利用公钥理论和技术建立的提供安全服务的基础设施。PKI技

12、术是信息安全技术的核心，也是电子商务的关键和基础技术。由于通过网络进行的电子商务、电子政务、电子事务等活动缺少物理的接触，因而使得用电子方式验证信任关系变得至关重要。什么是PKI技术? 34密码学的发展前沿 PKI技术恰好是一种适合电子商务、电子政务、电子事务的密码技术，它能够有效地解决电子商务应用中的机密性、真实性、完整性、不可否认性和存取控制等安全问题。 一个实用的PKI体系应该是安全的、易用的、灵活的和经济的。它必须充分考虑互操作性和可扩展性。它包含: 35密码学的发展前沿CARA KCASA认证机构 （Certification Authority）注册机构 （Registration

13、 Authority）策略管理 （strategy administration）密钥、证书管理 （key & certification administration）36密码学的发展前沿 CA（Certificate Authority） 电子签证机关，CA拥有一个证书（内含公钥）当然，它也有自己的私钥，所以它有签字的能力。网上的公众用户通过验证CA的签字从而信任CA，任何人都应该可以得到CA的证书（含公钥），用以验证它所签发的证书。 如果用户想得到一份属于自己的证书，他应先向CA提出申请。在CA判明申请者的身份后，便为他分配一个公钥，并且CA将该公钥与申请者的身份信息绑在一起，并为之签字

14、后，便形成证书发给那个用户（申请者）。37密码学的发展前沿 RA（Registration Authority） 是用户和CA的接口，它所获得的用户标识的准确性是CA颁发证书的基础。RA不仅要支持面对面的登记，也必须支持远程登记，如通过电子邮件、浏览器等方式登记。38密码学的发展前沿 数字签名是防止网上交易时进行伪造和欺骗的一种有效手段。发送者在自己要公布或发送的电子文档上“签名”，接收者通过验证签名的真实性确认文档是否被篡改过。在公布一份电子文档时，发送者首先对要公布的文档进行哈希（Hash）运算，然后发送者就可以用自己的签名私钥对Hash运算得出的简洁数据进行加密签名；PKI算法思想： 39密码学的发展前沿40密码学的发展前