密码学还为信息安全中除保密性外的其他一些问题提供了解决方案。 ①完整性服务解决方案

数据完整性检验通常通过密码学中的单向散列函数(hash函数)来实现。单向散列函数能够将任意长度的输入转化为一个固定大小的消息摘要，记为：h:{0,1}*→{0,1}n, m|→h(m)

上式表明，单向散列函数h将任意长度的比特串{0,1}*映射成长度为n的比特串{0,1}n。单向散列函数具有错误检测的能力，即改变输入数据的任何一位或者多位，都会导致消息摘要的改变。根据消息m和消息摘要h(m)的对应关系，接收者可以判断消息在传输过程中是否被篡改过。

单向散列函数的目的就是要产生消息的“指纹”，用于认证和数字签名。因此，单向散列函数必须具备单向性并且能够避免冲突。这就意味着：

? 对于任何给定的消息摘要y，找到满足h(m) = y的消息m在计算上是不可行的。 ? 对于任何给定的消息m1，找到满足h(m1) = h(m2)且m1≠m2的消息m2在计算上是不可行的。 ? 找到任何满足h(m1)=h(m2)且m1≠m2的消息对(m1,m2)在计算上是不可行的。 美国国家标准技术研究所NIST和一些国际组织不断地制定和颁布单向散列函数标准。1991年美国麻省理工计算机科学实验室和RSA数据安全公司的Ronald L. Rivest教授开发出MD5 (Message Digest Algorithm 5)算法。MD5经由MD2, MD3和MD4发展而来，对输入按512比特进行分组，并以分组为单位进行处理，输出为128位的数据摘要。1993年美国NIST公布了FIPS PUB 180，通常称之为SHA-0 (Secure Hash Algorithm)。1995年美国NIST对SHA-0进行了改进，公布了FIPS PUB 180-1，称之为SHA-1。SHA-1对输入按512比特进行分组，并以分组为单位进行处理，输出为160比特的数据摘要。为了增加单向散列函数的安全性并与加密标准AES配套，2002年美国NIST公布了SHA的修订版FIPS PUB 180-2，称之为SHA-2。SHA-2包含若干单向散列函数，其输出的数据摘要长度分别为256、384和512比特，分别称之为SHA-256, SHA-384和SHA-512。

例3-4 单向散列函数示例。

hash(?abc?，?MD5?)=900150983cd24fb0d6963f7d28e17f72

hash(?abc?，?SHA-1?)=a9993e364706816aba3e25717850c26c9cd0d89d hash(?abc?，?SHA-256?)=

ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad

hash('abc','SHA-384')=cb00753f45a35e8bb5a03d699ac65007272c32ab0eded1631a8b605a43ff5bed8086072bale7cc2358baeca134c825a7

hash ('abc', 'SHA-512') =

ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a2192992a274fc1a836ba3c23a3feebbd454d4423643ce80e2a9ac94fa54ca49f?

②认证性服务解决方案

为了认证消息的完整性，需要对消息生成某种形式的鉴别符，通过分析鉴别符，可以得知原始消息是否完整。在密码学中，消息加密、单向散列函数和消息认证码(Message Authentication Code, MAC)都是消息认证的重要手段。消息加密是将需要认证的消息加密，以加密的结果作为鉴别符。单向散列函数是将需要认证的消息通过一个公共函数映射为定长的消息摘要，以消息摘要作为鉴别符。消息认证码是将需要认证的消息通过一个公共函数产生一个结果，以产生的结果和密钥作为鉴别符。

利用消息认证码对消息进行认证的过程是这样的：发送者Alice利用MAC函数f和密钥k把需要认证的消息m变换成n比特的消息认证码f(k, m)，将消息认证码f(k, m)作为鉴别符附加在消息m之后，

发送消息序列{m||f(k,m)}给接收者Bob(如图3-4所示)。接收者Bob收到Alice发送的消息序列{m||f(k,m)}后，按照与发送者Alice相同的方法对接收的数据m进行计算，得到n比特的消息认证码f'(k, m)，然后比较f'(k,m)}和f(k,m)是否一致。如果一致，则消息认证成功；否则，消息认证失败。在该认证过程中，即使攻击者Eve篡改了消息m，在不知道密钥k的情况下，Eve也不可能计算出正确的消息认证码f(k,m)。接收者Bob通过比较f'(k,m)和f(k,m)是否一致，可以判断消息m在传输过程中是否被篡改。

实现消息认证码可以有多种方法。基于单向散列函数的消息认证码算法HMAC (Hash-based Message Authentication Code)和基于分组密码的消息认证码算法CMAC(Cipher-based Message Authentication Code)是目前广泛使用的两种消息认证码算法。HMAC算法像单向散列函数算法一样输出一个固定大小的消息标记，但是，与单向散列函数算法不同的是，HMAC算法需要使用密钥来阻止任何对消息标记的伪造，记为：h:{0,1}*→{0,1}n, m|→h(k,m)

CMAC算法以分组加密为基础，将完整性校验消息m进行分组得到m={m1||m2||…||mn}，利用完整性校验密钥k和初始向量IV对消息m进行递进分组加密，最后输出消息认证码MAC(如图3-5所示)。

公钥算法是实现认证的另一种方法，在第5章会详细介绍。与HMAC算法和CMAC算法不同的是，基于公钥的认证算法不需要通信双方在通信之前共享私有信息。采用什么样的认证算法取决于认证系统的构造。在传输信道安全的情况下，使用HMAC算法和CMAC算法可以提高通信的效率，节省通信的资源。基于公钥的认证算法通常用于通信双方的初始认证。

③不可否认性服务解决方案

不可否认性通常是通过公钥密码学中的数字签名算法实现的。一方面，数字签名依赖于签名人的私钥。另一方面，任何人都可以利用签名人的公钥和依赖于签名人公钥的公开验证算法Verify验证签名的有效性(如图3-6所示)。

在图3-6的描述中，Alice用自己的私钥kd和签名算法Sign对消息m签名，得到签名：s:=Sign(kd, m)。并把消息m和签名s传送给Bob。Bob接收到消息m和签名s后，用Alice的公钥ke和验证算法Verify检验：Verify(ke,s,m)=ok，是否成立来验证签名是否有效。通常，签名不是针对消息m本身，而是先用单向散列函数求出消息m的摘要，然后对消息摘要进行签名。攻击者Eve可以截获签名消息{m||s}，但是，Eve没有签名者Alice的私钥，不能伪造有效的签名。 3.1.4 密码体制安全性

攻击密码体制就是为了从密文中恢复明文或者恢复密钥。衡量密码体制安全性的方法有三种。 第一种方法是计算安全性(computational security)，又称实际保密性(practical secrecy) 。如果一种密码系统最有效的攻击算法至少是指数时间的，则称这个密码体制是计算安全的。在实际中，人们经常通过穷尽密钥搜索攻击来研究计算上的安全性。然而还没有一个已知的实际密码系统能被证明是计算上安全的。在实际中，人们说一个密码系统是计算上安全的，意思是利用已有的最好的方法破译该系统所需要的努力超过了攻击者的破译能力(如时间、空间和资金等资源)。

第二种方法是可证明安全性(provable security)。如果密码体制的安全性可以归结为某个NP (Nondeterministic Polynomial time)完全问题，则称其是可证明安全的。例如，RSA密码可以归结为大整数分解问题，ECC密码可以归结为椭圆曲线离散对数求解问题。计算机可以在多项式时间复杂度内解决的问题称为P类问题，在多项式时间复杂度内不可以解决的问题称为NP类问题，NP类问题中最困难的问题称为NP完全问题，简称NPC (NP-Complete)问题。Shannon曾指出，设计一个安全的密码本质上是要寻找一个难解的问题。

第三种方法是无条件安全性(unconditional security)或者完善保密性(perfect secrecy)。假设存在一个具有无限计算能力的攻击者，如果密码体制无法被这样的攻击者攻破，则称其为无条件安全的。Shannon证明了一次一密系统具有无条件安全性，即从密文中得不到关于明文或者密钥的任何信息。 3.1.5 密码分析

密码分析是一门研究在不知道密钥的情况下，通过密文获得明文信息或密钥信息的学问。密码分析也称为对密码体制的攻击。攻击者Eve主要使用三种手段对密码体制进行攻击。

(1)穷举攻击

穷举攻击又称为蛮力攻击，是指攻击者一次尝试所有可能的密钥对所截获的密文进行解密，直至得到正确的明文。1997年6月18日，美国科罗拉多州Rocket Verser工作小组宣布，通过网络利用数万台计算机历时4个多月以穷举攻击方式攻破了DES。

(2)统计分析攻击

统计分析攻击是指攻击者通过分析密文和明文的统计规律来攻击密码系统。统计分析攻击在历史上为破译密码做出过极大的贡献。许多古典密码都可以通过分析密文字母和字母组的频率及其他统计参数而破译。例如，在英语里，字母E是英文文本中最常用的字母，字母组合TH是英文文本中最常用的字母组合。在简单的替换密码中，每个字母只是简单地被替换成另一个字母，那么在密文中出现频率最高的字母就最有可能是E，出现频率最高的字母组合就最有可能是TH。抵抗统计分析攻击的方式是在密文中消除明文的统计特性。

(3)数学分析攻击

数学分析攻击是指攻击者针对加密算法的数学特征和密码学特性，通过数学求解的方法来破译密码。按照从密文推导明文的方式，数学分析攻击包括：唯密文攻击、已知明文攻击、选择明文攻击、自适应选择明文攻击、选择密文攻击和自适应选择密文攻击(如表3-3所示)。

3.2 加密方法及技术

加密方法就是使用算法和密钥加密信息的方法。加密体制就是通过采用适当的加密方法使得通信双方能在不安全的信道上进行信息的秘密交换。一种加密体制由使用适当的密钥把明文转变成密文的方法和它的反过程组成。密钥是完成转换的基本因素。 3.2.1 基于共享密钥的加密方法及技术

基于共享密钥的加密方法又称为对称密钥加密方法。对称密码学的基本思想就是共享密钥。用户Alice和Bob相互通信，采用双方共享的密钥和对称密钥加密方法保护消息，攻击者Eve即使截获密文，也会因为没有适当的密钥而不能得到任何关于通信内容的有效信息。通常使用流密码(stream cipher)和分组密码(block cipher)实现对称密钥加密。

(1)流密码

设K为密钥的集合，M为明文的集合。一个流密码：E*:M*×K*→C*, E*(k, m):=c:= c1c2c3...

利用密钥流k:= k1 k2 k3...K*(ki∈K}把明文序列m:= m1 m2 m3...M*(字符mi∈M)加密为密文序列c= c1c2c3...C*(密文ci∈C)。因此，存在加密映射：Ek:M→C。使得对任意的密钥k，有ci:=Eki(mi):= E(ki, mi), i=1, 2,...。

流密码又称序列密码，是对称密码学中的重要体制之一，它的起源可以追溯到20世纪20年代的Vernam密码。Vernam密码简单且易于实现，其关键是生成随机的密钥序列。设M:=K:=C:={0,1}，并且E:{0,1}×{0,1}→{0,1}, (m, k) |→m⊕k是消息比特和密钥比特的简单异或运算。为了加密消息m:= m1 m2 m3..., mi∈{0,1}需要一个密钥流k:= k1 k2 k3...，ki∈{0,1}。

加密函数定义如下：E*(k,m):= c:= c1c2c3...，其中ci:=mi⊕ki 解密函数定义如下：D*(k, c):= m:= m1 m2 m3...，其中mi:=ci⊕ki 例3-5 流密码应用示例。

流密码是一种方便快捷的加密方法，在现实中得到了广泛的应用。RC4密码是目前普遍使用的流密码之一，是美国麻省理工学院的Ron Rivest于1987年设计的密钥长度可变的流密码算法。RC4密码不仅已经应用于Microsoft Windows和Lotus Notes等应用程序中，而且应用于安全套接字层SSL(Secure Sockets Layer)保护因特网的信息流，还应用在无线局域网通信协议WEP( Wired Equivalent Privacy)以及蜂窝数字数据包规范中。在数字蜂窝GSM (Global System for Mobile Communications)移动通信系统中，AS密码被用于加密从电话到基站的信息。

(2)分组密码

分组密码满足M=C={0, l}n，n称为密码的分组长度。这是一个二元分组密码的概念，一般地，码元不限于二元，且M和C的长度不一定相等。对于密钥k，加密函数E是{0,1}n上的一个置换，消息空间由分组长度为n的2n个明文消息构成。分组密码的加密原理是：将明文按照某一规定的n比特长度分组，最后一组长度不够时要用规定的值填充，使其成为完整的一组，然后使用相同的密钥对每一分组分别进行加密。典型的分组加密方法有DES、三重DES, AES和IDEA等。

①数据加密标准DES

1973年美国国家标准局(National Bureau of Standards, NBS)公开征集用于保护商用信息的密码算法，并于1975年公布了数据加密标准(Data Encryption Standard, DES)。随后人们陆续设计了许多成熟的分组密码算法，如IDEA、AFER、Skipjack、RCS、Blowfish、Rijndael等。分组密码的核心问题就是设计足够复杂的算法，以实现Shannon提出的混乱和扩散准则。DES是最著名的、使用最广泛的对称密钥分组加密算法。1977年1月15日美国联邦信息处理标准版46(FIPS PUB 46)中给出了DES的完整描述。DES算法首开先例成为第一代公开的、完全说明实现细节的商业级密码算法，并被世界公认。

DES处理n=64比特的明文分组并产生64比特的密文分组(如图3-7所示)。密钥的有效尺寸为56比特，更准确地说，输入密钥64比特，其中8个比特(8,16,...,64)可用做校验位。