信息论与编码-密码学.ppt

l近代密码学的发展史 l保密学的理论基础 l序列（流）密码 l分组（块）密码 l经典算法-DES l经典算法-RSA l密码学的发展前沿 密码学Cryptography-目录 近代密码学发展史 准确的现代术语为“密码编制学”简称为“编密 学” 与之相对的研究的专门研究如何破解密码的 学问称为“密码分析学”(Cryptanalysis). Cryptography = 希腊文的 Kruptos + graphein hiddento write 密码学 密码编制学密码分析学 近代密码学发展史-2 近代密码学发展史-3 20世纪60年代一部与 众不同的著作-David Kahn 的破译者出 现了虽然此书没有任何 新的技术思想，但它的 意义在于它涉及到的相 当广泛的领域，而且在 于它使成千上万原本不 知道密码学的人了解密 码学。从而使新的密码 学文章慢慢地开始源源 不断地被编写出来了。 近代密码学发展史-4 第一次世界大战结束 时，公开的密码学文献 几乎殆尽。只有一个突 出 的例外，仙农 (Claude Shannon）的 文章保密系统的通信 理论出现在1949 年 贝尔系统技术杂志上 ，是战时工作的产物。 这 篇文章在第二次世 界大战结束后即被解密 。 近代密码学发展史-5 Alan Turing 数理逻 辑天才、现代计算 机设计思想的创始 人，第二次世界大 战在年仅26岁 Turing领导下完成 了一部针对德国“谜” 型机的密码破译机 ，每秒钟可处理 2000个字符，人们 给它起了个绰号叫“ 炸弹（Bomb)”。 近代密码学发展史-6 一个传统的密码体制S定义为： S (M, C, K, E, D)； message space 代表的是明文空间 key space 代表的是密钥空间 cipher space 代表的是密文空间 M K C 加密映射族： E = fk: M C | k K 脱密映射族： E = gk: C M | k K 安全性的含义：1）接收端防止窃听；2） 发送端防止伪造。 l数学模型 保密学的理论基础 明文 源MA 加密 T1 m 加密 T2 信道 C 解密 T2 解密 T1 明文 宿MB 密钥 源K1 密钥 源K 伪造者窃听者 密钥 源K-1 密钥 源K2 l基本定理 保密学的理论基础-2 l惟一解距离和明文冗余度 惟一解距离ud：当窃听者获取的密文长度大于之， 则密码成为可破译的；反之，小于它时，密码理 论上是不可破译的，因为它具有多个解的可能性 。 实现理想保密，则ud趋向无穷大，有两种可能： 1）完全保密体制：密钥熵H(K)无穷大 2）理想保密体制：密钥熵有限，但信源的冗余度D=0，即 完全随机。 这样，就得到两个启示： 1）实现保密的过程实质上是使密文随机化的过程，可通过 增大密钥，2)或减少明文的冗余度。 保密学的理论基础-3 l实际保密系统 一、减少冗余度： 1）直接法，采用信源编码的方法； 2）间接法，采用扩散和混淆的方法将信 源的冗余度在更大的范围上扩散开或加 以扰乱混淆，间接实现减少信源冗余度 的目的。序列加密（扩散法）、DES（ 混淆与扩散） 二、增大密钥量 保密学的理论基础-4 l优点 l适合实时加密，如实时的数字话音等 l理论成熟，其设计、分析较易 l较分组密码易于实现 l基本概念 序列流密码 经典算法介绍DES DES-2 l1973年美国国家标准局NBS (National Bureau of Standard)正式向社会公开征集加密算法。 l1974年IBM正式向NBS提交了应征方案。 lNBS会同美国国家保密局（NSA National Security Agency)研究发现这是唯一满足各项要求的方案。 l在此方案基础上形成的数据加密标准DES (data encryption standard)于1977年1月15日颁布，同年7 月正式生效成为美国联邦标准FIPS (Federal Information Processing Standard )。 l其后大约每5年对DES的安全性进行一次审查评估， 最后一次是1993年进行的，批准DES的使用终结日期 是1998年的12月。 DES-3 DES (Data Encryption Standard)算 法是美国政府机关为了保护信息处理中 的计算机数据而使用的一种加密方式， 是一种常规密码体制的密码算法，目前 已广泛用于电子商务系统中。 ：加解密双方在加解密过程中 要使用完全相同的一个密钥，密钥就经 过安全的密钥信道由发方传给收方。 基本思想 DES-4 DES-5 该算法输入的是64比特的明文，在64 比特密钥的控制下产生64比特的密文； 反之64比特的密文在解密的过程下产生 64位的明文。64比特的密钥中含有8个 比特的奇偶校验位，所以实际有效密钥 长度为56比特。 具体算法实现 DES-6 DES-7 穷举法破译DES 密码的问题。设已知 一段密码文C及与它对应的明码文M， 用一切可能的密钥K加密M，直到得到E （M）=C，这时所用的密钥K即为要破 译的密码的密钥。穷举法的时间复杂性 是T=O（n） DES 算法破解 DES-8 对于DES密码n=25671016，即使 使用每秒种可以计算一百万个密钥的大 型计算机，也需要算106天才能求得所 使用的密钥，因此看来是很安全的。但 是到了1997美国有一程序员采用Sever- Client方式在众多网上志愿者的帮助下 利用Internet 96天成功破密获取密钥。 DES-9 l1999年1月，EFF（ Electronic Frontier Foundation)用DES Crack (内含1856块 芯片)和网络分布式 计算，在22小时15 分钟内破解了RSA数 据安全公司提出的 “DES 挑战者III” 经典算法RSA 经典算法RSA 1976年，W.diffie和M.hellman首次提出了公开 密钥密码体制的概念，其中最关键的思想是寻 找一个“单向函数” 经典算法RSA 什么叫“单向函数”呢？ X Y Y=F(x) Y X X=F-1(y) 不能实现 l1977年R.Rivest A.Shamir L.Adleman 提 出了第一个比较完善的公开密钥密码体制 ，即著名的RSA体制。 经典算法RSA 选择两个大质数 和 ,每个都大于 ； 计算 和 ； 选择一个与 有关的质数,令其为 ； 找到一个 满足 保密 ; qp10100 n=p*q z=(p-1)*(q-1) zd e d e*d=1(mod z) 经典算法RSA 将明码（当作位串看待）划分成 块，使得每个明码报文 落在 之间，这可以通过将明码分成每块 有 位的组来实现，并且使得 是 使 成立的最大整数。 P0Pn kzkn k C=Pe( mod n) P=Cd ( mod n) 经典算法RSA RSA的安全性在于加密变换： C=F(P)=Pe（mod n） 的单向性 ：敌方从e和n中无法求出脱密的 密钥d，产生这种单向性的原因是基于大 整数分解在计算上的困难。 经典算法RSA 如果能有效的分解出n=p*q,则能很容 易的求出z=(p-1)*(q-1)最后使用穷尽的 方法来找出与z有关的所有质数d使其能 与公钥e之间有如下的关系： d*e=1(mod n) 公共密钥算法RSA 现在我们就来看这个简单的例子。 我们选择了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，因此 ，每个明码块只能包含一个字符。结果形成了 一个单一字母表代换密码。 这个例子安全 吗？ 明文密文 解密 字母 序号 P3P3（ MOD 33） C7C7 （ MOD 33 ） 字 母 S 196859 2813492928512 28 S U 219261 211801088541 21 U Z 2617576 20128000000 20 Z A 01 1 1 1 1 A N 142744 5 78125 5 N N 142744 5 78125 5 N E 05 125 268031810176 26 E 密码学的发展前沿 密码学的发展前沿 lPKI（Public Key infrastructure，公钥基 础设施）从字面上理解，PKI就是利用 公钥理论和技术建立的提供安全服务的 基础设施。PKI技术是信息安全技术的 核心，也是电子商务的关键和基础技术 。由于通过网络进行的电子商务、电子 政务、电子事务等活动缺少物理的接触 ，因而使得用电子方式验证信任关系变 得至关重要。 密码学的发展前沿 PKI技术恰好是一种适合电子商务、 电子政务、电子事务的密码技术，它能 够有效地解决电子商务应用中的机密性 、真实性、完整性、不可否认性和存取 控制等安全问题。 一个实用的PKI体系应该是安全的、 易用的、灵活的和经济的。它必须充分 考虑互操作性和可扩展性。它包含: 密码学的发展前沿 CA RA KCA SA 认证机构 （Certification Authority） 注册机构 （Registration Authority） 策略管理 （strategy administration） 密钥、证书管理 （key & certification administration） 密码学的发展前沿 CA（Certificate Authority） 电子签证机关，CA拥有一个证书（内含公 钥）当然，它也有自己的私钥，所以它有签字 的能力。网上的公众用户通过验证CA的签字 从而信任CA，任何人都应该可以得到CA的证 书（含公钥），用以验证它所签发的证书。 如果用户想得到一份属于自己的证书，他 应先向CA提出申请。在CA判明申请者的身份 后，便为他分配一个公钥，并且CA将该公钥 与申请者的身份信息绑在一起，并为之签字后 ，便形成证书发给那个用户（申请者）。 密码学的发展前沿 RA（Registration Authority） 是用户和CA的接口，它所获得的用户 标识的准确性是CA颁发证书的基础。 RA不仅要支持面对面的登记，也必须支 持远程登记，如通过电子邮件、浏览器 等方式登记。 密码学的发展前沿 数字签名是防止网上交易时进行伪造和 欺骗的一种有效手段。发送者在自己要公布或 发送的电子文档上“签名”，接收者通过验证签 名的真实性确认文档是否被篡改过。在公布一 份电子文档时，发送者首先对要公布的文档进 行哈希（Hash）运算，然后发送者就可以用 自己的签名私钥对Hash运算得出的简洁数据 进行加密签名； 密码学的发展前沿 密码学