1.2 密码学基础知识

密码学是一门既古老又年轻的学科，它用于保护军事和外交机密通信可追溯到几千年前。在当今的信息时代，大量的敏感信息如病历、法庭记录、资金转移等常通过公共通信设施或计算机网络进行交换，而这些信息的秘密性和真实性是人们迫切需要的。因此，现代密码学的应用已不局限于军事、政治和外交等方面，它已经渗透到人们生产生活的各个领域。

1.2.1 密码学基本概念

密码学是研究密码系统或通信安全的一门科学。它主要分为两个分支，即密码编码学和密码分析学。密码编码学的主要目的是寻求保障消息保密性或认证性的方法；密码分析学的主要目的是研究加密消息的破译或消息的伪造。

被隐蔽前的消息称为明文，隐蔽后的消息称为密文或密报。将明文转换成密文的过程称为加密，把密文重新转换为明文的过程称为解密。对明文进行加密时所采用一组规则称为加密算法；对密文进行解密所采用的一组法则称为解密算法。加密和解密算法的操作通常都是在一组密钥控制下进行的，分别称为加密密钥和解密密钥。

根据密钥的特点，Simmons[12]将密码体制分为对称和非对称密码体制两种。对称密码体制又被称为单钥或私钥密码体制，是指密码系统的加密密钥与解密密钥相同或者可以由其中一个推算出另一个。非对称密码体制又被称为双钥或公钥密码体制，加密密钥和解密密钥不同，从一个难以推出另一个。

按加密方式又可将对称密码体制分为流密码和分组密码两种。在流密码中，将明文消息按字符逐位进行加密。在分组密码中，将明文消息分组（每组含有多个字符），逐组进行加密。现有的大多数公钥密码属于分组密码，只有概率加密体制属于流密码[11]。

1.2.2 流密码系统简介

流密码将明文分成连续的符号或比特x = x1, x2, …,用密钥流k = k1, k2, …的第i个元素ki对xi加密，即…。图1.1为流密码的保密通信模型[13]。如果密钥流经过若干个符号之后重复，则称此流密码是周期的，否则称为非周期的。流密码与分组密码之间主要区别在于记忆性，如图1.2所示[13]。

在流密码中，密钥流元素kj的产生由第j时刻流密码的内部状态σj和被称为种子密钥或实际密钥的k所决定，一般可写为kj = f (k,σj)。加（解）密变换是时变的，其时变性由加（解）密器中的记忆元件来保证。在流密码中，加密器中存储器的状态随时间变化而变化，这一变化过程可用一个函数来描述，即状态转移函数fs。根据fs是否依赖于输入的明文符号，可将流密码分为两类，即同步流密码和自同步流密码。

在同步流密码中，状态转移函数 fs 与输入的明文符号无关。此时，密钥流与明文符号无关，而j时刻输出的密文cj也不依赖于j时刻之前的明文符号。因而，同步流密码的加密器可划分为密钥流生成器（伪随机序列生成器）和加密变换器两个部分。在同步流密码中，只要收发双方有相同的密钥k和内部状态就能产生相同的密钥流。同步流密码有两种基本的工作模式，即输出-分组反馈模式（OFM）和计算模式。

在自同步流密码中，状态转移函数fs与输入的明文符号有关。此时，密钥流kj =f (k,σj)与明文符号相关，而j时刻输出的密文cj不仅仅依赖于明文符号xj。密码反馈模式是自同步流密码的一种最常用的工作模式。

1.2.3 分组密码系统简介

分组密码就是将明文x1, x2, …,分成长度为m的组x = (x1, x2, …, xm)，各组分别在密钥k的控制下变换成等长的密文分组y=(y 1,y 2,…,ym)。分组密码的模型如图1.3所示[11]。

分组密码的优点是容易被标准化，且容易实现同步，一个分组的传输错误不会影响其他分组。它主要的缺陷有两个方面：一是分组加密不能隐蔽数据模式，即相同的密文组蕴含着相同的明文组；二是分组加密不能抵抗组的重放、嵌入和删除等攻击。

流密码和分组密码都属于对称密钥密码系统，具有加密速度快和安全强度高的优点，在军事、外交、金融以及商业应用等领域中被广泛使用。但是它存在一个最薄弱、也是风险最大的环节，就是密钥的管理与分配。由于加/解密双方要使用相同的密钥，因此在发送、接收数据之前，必须完成密钥的分配，如何可靠、安全地进行大范围、随机变化环境下的密钥分配是确保对称密钥体制安全的关键问题。

1.2.4 公开密钥密码系统简介[11]

公开密钥密码体制是在试图解决对称密钥密码体制碰到的难题的过程中发展起来的。公钥密码系统的观点是由Diffie和Hellman在1976年首次提出的，它使密码学发生了一场变革。

公开密码体制的最大特点是采用两个不同但相关的密钥分别进行加密和解密，其中一个密钥是公开的，称为公开密钥；另一个密钥是保密的，称为秘密密钥。公开密码算法有以下的重要特性：已知密码算法和加密密钥，要想确定解密密钥，在计算上是不可能的。公开密钥系统的模型如图1.4所示[14]，它要求：

① 接收方B容易通过计算产生出一对密钥（公开密钥PKB和秘密密钥SKB）；

② 发送方A用接受方的公开密钥PKB对消息X加密产生密文Y，即Y=EPKB(X)在计算上是容易的；

③ 接收方B用自己的秘密密钥对Y解密，即B在计算上是容易的；

④ 密码破译者由B的公开密钥PKB求秘密密钥SKB在计算上是不可行的；

⑤ 密码破译者由密文Y和B的公开密钥PKB恢复出明文X在计算上是不可行的；

⑥ 加密、解密次序可交换，即。

其中，最后一条非常有用，但不是对所有的算法都有此要求。

公开密钥密码体制安全性的基础一般都依赖于数学中的某个困难性问题。在加解密过程中，往往涉及大量的复杂运算，因此比起对称密钥密码来说速度要慢得多。它的主要用途是用于密钥交换、数字签名，而不直接用它来加密数据。

1.2.5 密码分析与算法安全

密码分析学是研究如何破译密码的科学，其目的就是要找到消息X或/和密钥K。通常情况下，假设密码分析者知道所使用的密码系统，这个假设称为Kerckhoff假设。在设计加密系统时，必须满足在Kerckhoff假设下达到安全性。根据密码分析者破译时已具备的前提条件，通常将攻击类型分为4种[15]，其攻击强度是依次递增的。

① 唯密文攻击：密码分析者有一个或多个用同一密钥加密的密文，通过对这些密文进行分析得出明文或密钥。

② 已知明文攻击：除待解密的密文外，密码分析者有一些明文和用同一个密钥加密这些明文后所产生的密文。

③ 选择明文攻击：密码分析者可获得对加密机的访问权限，因此可得到所需要的任何明文所对应的密文。这些密文与待解密的密文是用同一个密钥加密得到的。

④ 选择密文攻击：密码分析者可获得对解密机的访问权限，因此可得到所需要的任意密文所对应的明文。解密这些密文所使用的密钥与解密待解密的密文的密钥是相同的。

关于密码体制的安全性有不同的准则，常见的有无条件安全性，计算安全性和可证明的安全性等。密码学中更关心的是计算安全性和可证明的安全性[16]。

计算安全性是指密码攻击者使用了可以利用的所有计算资源（包括时间、空间、设备等），仍然无法攻破密码体制，那么可以说该密码体制具有计算安全性。对于对称密码体制，一般可以用密码系统的熵来衡量系统的理论安全性，它由密钥空间的大小计算出来：H(K)=log2 K，密码系统的熵越大，破译它就越困难。好的密码系统应设计成能抵御未来许多年计算能力发展后的攻击。

可证明安全性将密码体制的安全性归结为某个经过深入研究的数学难题，这种密码体制是可证明安全的。这和证明一个问题是NP完全的有些类似。例如，RSA公开密码体制的安全性是基于分解大整数的难度，ElGamal公开密码体制的安全性是基于计算有限域上离散对数的难度，等等。

1.2.6 消息认证与Hash函数简介

在网络通信环境中，可能受到下述内容的攻击：

① 泄密：消息被透露给没有合法秘密密钥的任何人或程序。

② 传输分析：分析通信双方的通信模式。在面向连接的应用中，确定连接的频率和持续时间；在无连接的环境中，确定双方的消息数量和长度。

③ 伪装：欺诈源向网络中插入一条消息。如攻击者产生一条消息并声称这条消息是来自某合法实体，或者非消息接收方发送关于收到或未收到消息的欺诈应答。

④ 内容修改：对消息内容的修改，包括插入、删除、转换和修改消息。

⑤ 顺序修改：对通信双方消息顺序的修改，包括插入、删除和重新排序。

⑥ 计时修改：对消息的延时和重放。在面向连接的应用中，整个消息序列可能是前面某合法消息序列的重放，也可能是消息序列中的一条消息被延时或重放；在面向无连接的应用中，可能是一条消息(如数据报)被延时或重放。

⑦ 发送方否认：发送方否认发送过来的某消息。

⑧ 接收方否认：接收方否认接收到的某消息。

对①，②两种攻击方法的防护属于消息保密的范畴，即通过信息加密来进行保护；对③至⑥种攻击方法的防护属于消息认证的范畴；对⑦和⑧两种攻击的防护主要可通过数字签名技术来进行防护。数字签名技术同样也属于消息认证的研究范畴。

所谓消息认证是指验证所收到的消息确实是来自真正的发送方且未被修改的消息，也可以验证消息的顺序和及时性。消息认证在功能上可以划分为两个层次。底层中有某种产生认证符的函数，而认证符是一个用于认证消息的值；上层主要是一些协议，将产生认证符的函数作为原语，从而使接收方可以验证消息的真实性。

产生认证符的函数可以分为三类：

① 消息加密：将整个消息的密文作为认证符；

② 消息认证码（MAC）：它是消息和密钥的公开函数，它产生定长的值，并以此值作为认证符；

③ Hash函数：它是一个公开的函数，将任意长的消息映射为定长值（Hash值），并以Hash值作为认证符。

单向Hash函数是消息认证码的一种变形。与消息认证码一样，Hash函数的输入是可变大小的消息M，输出是固定大小的Hash值H(M)。与MAC不同的是，Hash值不使用密钥，它仅仅只是输入消息的函数。Hash值有时也被称为消息摘要，或Hash码。Hash值是所有消息位的函数，具有错误检测能力，即变化消息的一位或多位，都会导致Hash值发生较大的变化。

目前被广泛使用的Hash函数，比如MD5、SHA等，大都采用了一种典型的如图1.5所示的迭代型结构[14]。

输入的明文消息M被分成L个分组Y0,Y1,…,YL-1，每个分组的长度为b比特，若最后一个分组的长度不够的话，需要对其进行填充。最后一个分组还包括该Hash函数输入的总长度值，这样可以增加攻击者进行攻击的难度，攻击者必须保证假冒消息的散列值与原消息的散列值相同，且假冒消息的长度也要与原消息的长度相等。算法中重复使用一个压缩函数 f。压缩函数 f 有两个输入，一个是前一轮的n比特输出CVi-1，称为链接变量，另一个是本轮的b比特输入分组Yi-1；压缩函数f 的输出为n比特的CVi，它又作为下一轮的输入。算法开始时还需为链接变量指定一个初值IV。最后一轮输出的链接变量是最终的散列值。整个算法可表述如下：

CV0=IV=n比特长的初始值

CVi = f(CVi-1,Yi-1),1≤i≤L

H (M)=CVL

算法的核心是设计无碰撞的压缩函数 f，一般采用异或等逻辑运算的复杂方法实现。

Hash函数通常具有以下性质[14]∶

① 压缩性：输入可以为任意的长度消息，而输出为固定长度的二进值串，比如128比特或256比特；

② 不可逆性：已知输入x，计算其Hash值h(x)容易，但已知Hash值h，要找到对应的x在计算上不可行；

③ 抗弱碰撞性：对任意的输入x，找到满足y≠x，且h(x)=h(y)的y在计算上不可行。

④ 抗碰撞性：找到任意满足h(x)=h(y)的偶对(x, y)在计算上是不可行的。