保障与安全密码

1、第三章 密码学,1、密码学的发展 密码学的历史比较悠久，在四千年前，古埃及人就开始使用密码来保密传递消息。两千多年前，罗马国王Julius Caesar（恺撒）就开始使用目前称为“恺撒密码”的密码系统。但是密码技术直到20世纪40年代以后才有重大突破和发展。特别是20世纪70年代后期，由于计算机、电子通信的广泛使用，现代密码学得到了空前的发展,密码学基础,密码学基础,2. 密码学作为数学的一个分支，其相关科学大致可以分为3个方面,密码编码学：使消息保密的技术和科学（Cryptography），从事此行的叫密码编码者（Cryptographer）。 密码分析学：破译密文的技术和科学（Crypta

2、nalysis）密码分析者是从事密码分析的专业人员 密码学（Cryptology）密码学是一门秘密书写、非授权解密以及使得非法解密更加困难的规则的科学，数学理论在目前的密码学研究中发挥着非常重要的作用，其中包含数论、群论、组合逻辑、复杂性理论、遍历理论以及信息论。 包括密码编码学和密码分析学两部分，精于此道的人称为密码学家（Cryptologist），现代的密码学家通常也是理论数学家,密码学的发展大致经过3个阶段： 第一阶段是1949年之前，密码学是一门艺术，这阶段的研究特点是： 密码学还不是科学，而是艺术； 出现一些密码算法和加密设备； 密码算法的基本手段出现，主要针对字符；简单的密码分析手

3、段出现，数据的安全基于算法的保密。 该阶段具有代表性的事件是：1883年Kerchoffs第一次明确的提出了编码的原则： 加密算法应建立在算法的公开且不影响明文和密钥的安全的基础上。这个原则得到广泛承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。 第二阶段是1949-1975年，密码学成为一门独立的科学，该阶段计算机的出现使基于复杂计算的密码成为可能。主要研究特点是：数据安全基于密钥而不是算法的保密,第三阶段是1976年以后，密码学中公钥密码学成为主要研究方向，该阶段具有代表性的事件是： 1976年，Diffie和Hellman提出了不对称密钥。 1977年，Rive

4、st，Shamir和Adleman提出了RSA公钥算法。 1977年，DES算法出现。 80年代，出现IDEA和CAST等算法。 90年代，对称密钥密码算法进一步成熟，Rijndael，RC6等出现，逐步出现椭圆曲线等其他公钥算法。 2001年，Rijndael成为DES算法的替代者。 2004年8月，山东大学信息安全所所长王小云在国际会议上首次宣布了她及她的研究小组对MD5、HAVAL-128、MD4和RIPEMD等四个著名密码算法的破译结果，引起世界轰动。这阶段的主要特点是：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能,经典密码学,经典的密码学是关于加密和解密的理论，主要用于保密

5、通信。目前，密码学已经得到了更加深入、广泛的发展，其内容已经不再是单一的加解密技术，已被有效、系统地用于保证电子数据的保密性、完整性和真实性。保密性就是对数据进行加密，使非法用户无法读懂数据信息，而合法用户可以应用密钥读取信息。完整性是对数据完整性的鉴别，以确定数据是否被非法篡改，保证合法用户得到正确、完整的信息。真实性是数据来源的真实性、数据本身真实性的鉴别，可以保证合法用户不被欺骗,现代密码技术,现代密码技术的应用已经深入到数据处理过程的各个环节，包括：数据加密、密码分析、数字签名、信息鉴别、零知识认证、秘密共享等。 密码学的数学工具也更加广泛，有概率统计、数论、代数、混沌和椭圆曲线等。常

6、用密码学专业术语包括：消息和加密、鉴别、完整性和抗抵赖性、算法和密钥、对称算法和公开密钥算法（非对称算法），等等,基本概念,3. 加密（Encrypt)和解密(Decrypt,一般模型都假定Alice和Bob在一个不安全的信道上通信，而Eve作为第三者(或密码分析者)总是企图破译Alice和Bob之间的通信内容。Alice发送给Bob的信息，通常称为明文(Plaintext),如英文单词、数字符号或数据,Alice事先用某个密钥(Key)对要发送的信息进行加密, 加密过的明文常称为密文(Cipher Text),然后Alice将密文发给Bob。Eve可以窃听到Alice发给Bob的信息，但无法

7、知道明文；而Bob收到密文后，能利用事先知道的密钥对密文进行解密而获得明文,基本概念,3. 加密（Encrypt)和解密(Decrypt,通信过程,1) 通信双方通过协商选择并共享一个密钥kK。 (2) 发送方使用加密函数Ek对明文串进行加密得到密文C。 (3) 当Bob接到密文串C时，他使用解密函数Dk对其进行解密，就可以得到原始明文串m,基本概念,3. 加密（Encrypt)和解密(Decrypt,a) 对称密码体制,基本概念,3. 加密（Encrypt)和解密(Decrypt,3. 加密（Encrypt)和解密(Decrypt,非对称密码体制,4. 密码学的作用,密码学基础,除了提供机密

8、性外，密码学需要提供三方面的功能：鉴别、完整性和抗抵赖性。这些功能是通过计算机进行社会交流至关重要的需求。 机密性:提供只允许特定用户访问和阅读信息，任何非授权用户对信息都不可理解的服务通过数据加密实现。 数据完整性:提供确保数据在存储和传输过程中不被未授权修改（窜改、删除、插入和重放等）的服务。通过数据加密、数据散列或数字签名来实现,密码学基础,鉴别:提供与数据和身份识别有关的服务。通过数据加密、数据散列或数字签名来实现 抗否认性:提供阻止用户否认先前的言论或行为的服务。通过对称加密或非对称加密，以及数字签名等，并借助可信的注册机构或证书机构的辅助，提供这种服务,信源,加密机,解密机,接收者

9、,安全信道,密钥源,窃听者,x,y,x,k1,加密通信的模型,密钥源,k2,不安全信道,密码分析,Shannon模型,信息传递的一般问题,信源、信道、信宿 攻击的种类： 中断（Interruption)（干扰） 截取（Interception) (侦听） 修改（Modification） 伪造（Fabrication) 角色：通信双方、可信第三方、不可信第三方 介质：软件、硬件、数据,数据的性质,Interruption - Interception - Modification - Fabrication,Availability,Availability,Availability,Conf

10、identiality,Availability,Integrity,Availability,Authenticity,时间性,被动攻击,窃听,获取消息内容,流量分析,主动攻击,中断,修改,伪造,破坏可用性,破坏完整性,破坏真实性,密码体制,一个满足下面条件的五元组(P,C,K,E,D)为一个密码体制: (1) P是一个非空有限集合，表示所有的明文空间。 (2) C是一个非空有限集合，表示所有的密文空间。 (3) K是一个非空有限集合，表示所有的密钥空间。 (4) 对任意的kK,都存在一个加密函数： Ek(E):PC 和相应的解密函数： Dk(D):CP 对任意的明文mP均有Dk(Ek(m)

11、=m。其中Ek和Dk都必须是单射函数,密码学基础,5. 算法与密钥,算法 是用于加密和解密的数学函数 受限制(restricted)的算法 算法的强度是基于保持算法的秘密 算法强度依赖于密钥(K)的算法密钥K的可能值的范围叫做密钥空间(keyspace,使用同一密钥的加/解密(symmetric algorithm) 加密：EK（M）= C 解密：DK（C）= M 等效于 DK（EK（M）=M,密码学基础,使用不同密钥的加/解密(public-key) 加密：EK1（M）= C 解密：DK2（C）= M 等效于 DK2（EK1（M）=M,密码学基础,基于密钥的算法有两类：对称算法与公开密钥算法

12、,密码学基础,对称算法 也叫传统密码算法（秘密密钥算法、单钥算法），就是加密密钥能从解密密钥中推算出来。反过来也成立 对称算法的数学表示,加密：EK（M）= C 解密：DK（C）= M,对称算法分类,密码学基础,序列算法（stream algorithm) 一次只对明文中的单个位（或字节）进行运算的算法。 分组算法（block algorithm) 一次对明文的一组位进行运算，典型分组长度是64位,公开密钥算法（public-key algorithm） 也叫非对称算法,公钥算法，公开密钥算法的加密密钥和解密密钥不同，而且解密密钥不能根据加密密钥计算出来，或者至少在可以计算的时间内不能计算出来

13、。 一般称加密密钥为公钥（public-key），解密密钥为私钥（private-key）。比较著名的公钥密码算法有：RSA、背包密码、McEliece密码、Diffe-Hellman、Rabin、零知识证明的算法、椭圆曲线（Elliptic Curve）、ElGamal算法等等。RSA是最有影响的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击。现今世界上广为应用的PGP邮件加密软件就是基于RSA算法的,密码学基础,公开密钥算法特点 用作加密的密钥（也称公开密钥）不同于用作解密的密钥（也称私人密钥)。 解密密钥不能根据加密密钥推算出来。 加密密钥能公开。 有时也用私人密钥加密而用公开密钥

14、解密，这主要用于数字签名,6. 密码协议,协议：一系列步骤，其目的是为完成一项任务,密码学基础,密码协议：是使用密码学的协议 对称密码通信（以Alice和Bob通信为例） Alice和Bob协商用同一密码系统 Alice和Bob协商同一密钥 Alice用加密算法和选取的密钥加密她的明文消息，得到了密文消息 Alice发送密文消息给Bob Bob用同样的算法和密钥解密密文 单向函数,密码学基础,例子 已知x，我们很容易计算f(x),但已知f(x)，却难于计算出x. 单向函数的作用,密码学基础,不能用作加密 使用单向函数进行鉴别，其鉴别过程如下： Alice将她的口令传送给计算机 计算机完成口令的

15、单向函数的计算 计算机把单向函数的运算结果和它以前存储的值进行比较,密码学基础,单向散列（Hash)函数,功能 把可变输入长度串（称预映射，pre_image)转换成固定长度的输出串（称散列值）。 特点 难于产生两个预映射的值，使它们的散列值相同 散列函数是公开的，对处理过程不保密。 平均而言，预映射的单个位的改变，将引起散列值中一半以上位的改变,已知一个散列值，要找到预映射，使它的散列值等于已知的散列值在计算上是不可行的。 一般情况下，应使用不带密钥的单向散列函数，以便任何人都能验证散列值。 说明： 消息鉴别码（Message Authentication Code, MAC),它是带有秘密

16、密钥的单向散列函数，散列值是预映射的值和密钥的函数,密码学基础,公开密码通信（以Alice和Bob通信为例） Alice从数据库中得到Bob的公开密钥 Alice用Bob的公开密钥加密消息， 然后发送给Bob Bob用自己的私人密钥解密Alice发送的消息,混合密码通信 Bob将他的公开密钥发给Alice Alice产生随机会话密钥K，用Bob的公开密钥加密，并把加密的密钥EKBP(K)送给Bob,密码学基础,Bob用他的私人密钥解密Alice的消息，恢复出会话密钥：DKBPri(EKBPub(K) = K 他们两人用同一会话密钥K对他们的通信消息进行加密,密码学基础,数字签名（以采用公开密码

17、技术为例） Alice用她的私人密钥对文件加密，从而对文件签名 Alice将签名的文件传给Bob Bob用Alice的公开密钥解密文件，从而验证签名,密钥交换 对称密码学的密钥交换 假设：Alice和Bob每人和KDC共享一个秘密密钥，分别为,密码学基础,密码学基础,Alice呼叫KDC，并请求一个与Bob通信的会话密钥 KDC产生一随机会话密钥，并对它的两个副本加密：一个用，另一个用，KDC发这两个副本给Alice Alice对她的会话密钥的副本解密 Alice将Bob会话密钥的副本转发给Bob Bob对他的会话密钥的副本解密 lice和Bob用这个会话密钥安全的通信,密码学基础,公开密码学

18、的密钥交换,密码学基础,Alice从KDC提到Bob的公开密钥 Alice产生出随机会话密钥，用Bob的公开密钥加密它，然后将它传给Bob Bob用他的私人密钥解密Alice的消息 两人用同一会话密钥对他们的通信进行加密,K= DKPri(EKPub(K,密码学基础,密码学基础,6密码分析 密码分析学是在不知道密钥的情况下，恢复出明文的科学。成功的密码分析能恢复出消息的明文或密钥。密码分析也可以发现密码体制的弱点，最终得到上述结果。密钥通过非密码分析方式的丢失叫做泄露。 常用的密码分析攻击有四类。 （1）唯密文攻击（Cipher Text-Only Attack）。密码分析者有一些消息的密文，

19、这些消息都用同一加密算法加密。密码分析者的任务是恢复尽可能多的明文，或者最好是能推算出加密消息的密钥来，以便可采用相同的密钥解出其他被加密的消息,密码学基础,2）已知明文攻击（Known-Plaintext Attack）。密码分析者不仅可得到一些消息的密文，而且也知道这些消息的明文。分析者的任务就是用加密信息推出用来加密的密钥或推导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密,密码学基础,3）选择明文攻击（Chosen-Plaintext Attack）。分析者不仅可得到一些消息的密文和相应的明文，而且他们也可选择被加密的明文。这比已知明文攻击更有效。因为密码分析者能选择特定

20、的明文块去加密，那些块可能产生更多关于密钥的信息，分析者的任务是推出用来加密消息的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。(这种攻击常常是通过跟踪Alice发给Bob的明文串来分析。,密码学基础,4）选择密文攻击（Chosen-Cipher Text Attack）。密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，例如密码分析者存取一个防窜改的自动解密盒，密码分析者的任务是推出密钥。 （5）自适应选择明文攻击（Adaptive-Chosen-Plaintext Attack）。这是选择明文攻击的特殊情况。密码分析者不仅能选择被加密的明文，而且也能基于

21、以前加密的结果修正这个选择。在选择明文攻击中，密码分析者还可以选择一大块被加密的明文，而在自适应选择密文攻击中，可选取较小的明文块，然后再基于第一块的结果选择另一明文块，依此类推,密码学基础,6）选择密钥攻击（Chosen-Key Attack）。这种攻击并不表示密码分析者能够选择密钥，它只表示密码分析者具有不同密钥之间的关系的有关知识。 （7）软磨硬泡攻击（Rubber-Hose Cryptanalysis）。这种攻击是对密码设计者威胁、勒索，或者折磨某人，直到他给出密钥为止。行贿有时称为购买密钥攻击（purchase-key attack）。这些是非常有效的攻击，并且经常是破译算法的最好途

22、径,7算法的安全性 不同的密码算法具有不同的安全等级。如果破译算法的代价大于加密数据的价值，破译算法所需的时间比加密数据保密的时间更长，用单密钥加密的数据量比破译算法需要的数据量少得多，那么这种算法可能是安全的。 Shannon理论：仅当密钥至少和明文一样长时才无条件安全。 如果不论密码分析者有多少密文，都没有足够的信息恢复出明文，那么这个算法就是无条件保密的，只有一次一密乱码本，才是无条件安全的。所有其它的密码系统在唯密文攻击中都是可破的 （蛮力攻击,密码学基础,破译算法可分为不同的类别，安全性的递减顺序为： 全部破译。密码分析者找出密钥 K，这样 DK（C）=P。 全盘推导。密码分析者找到

23、一个代替算法在不知道密钥 K的情况下，等价于DK（C）=P。 局部推导。密码分析者从截获的密文中找出明文。 信息推导。密码分析者获得一些有关密钥或明文的信息。这些信息可能是密钥的几个位、有关明文格式的信息等,条件与工具： 已知加密消息，已知加密算法，截取到明文、密文中已知或推测的数据项，数学或统计工具和技术，语言特性，计算机，技巧与运气,加密算法的好与坏破译难度 - 理论难度，如解密运算需1012年（分析技巧可以降低破译代价） - 运算能力，飞速发展,密码破译,密码破译的原则: 遵循观察与经验 方法:采用归纳与演绎 步骤:分析、假设、推测和证实 三大要素： 语言的频率特征： e 连接特征: q

24、 u, I e x, 重复特征: th, tion , tious,5. 英语字母使用频率,第四章 传统密码学,密码学更关心在计算上不可破译的密码系统。如果一个算法用（现在或将来）可得到的资源（公开数据 ）都不能破译，这个算法则被认为在计算上是安全的。 可以用不同方式衡量攻击方法的复杂性： 数据复杂性。用作攻击输入所需的数据量。 处理复杂性。完成攻击所需要的时间，这个经常叫做工作因素。 存储需求。进行攻击所需要的存储量。 作为一个法则，攻击的复杂性取这三个因素的最小化，有些攻击包括这三种复杂性的折中：存储需求越大，攻击可能越快,好”密码体制的若干特性,1 Shannon标准 2 混淆(Diffusion) 与扩散(Confusion) 3 完善保密性（Perfect Secrecy） 4 冗余度（Redundancy）与唯一解距离(Unicity Distance) 5 乘积密码（Product Cipher） 6 编码与密码体制,1 Shannon标准,1）为了确定加密和解密算法所必需的密文量应拥有相当的劳动强度，也就是说，一个简单的密码体制它足以抵挡少量的密文的丢失，被窃或者抵挡一个攻击者在很短时间内拥有相当的密文。