Olympic：一种基于多明文的数据对称加密算法

Olympic： A Data Symmetric Encryption Algorithm Based on Multiple Plaintexts

摘要

当传统的对称加密算法遭受暴力攻击时，由于被加密的明文信息符合语义特征，攻击者可以从多个候选密钥中识别出正确的密钥以破解密码。为此，本文提出一种基于多明文的数据对称加密算法。该算法可以在一次加密过程中对n（n≥2）对明文和密钥执行加密操作，产生一个密文，并在解密过程中使用指定密钥对密文进行解密，以获得对应的明文。该算法将一对真正的明文和密钥与另外n-1对虚假的明文和密钥混合在一起进行加密，保证了即使所有明文和密钥都被破解，攻击者也无法确定真正的明文和密钥。另外，该加密算法通过引入密码盐增大破解密钥的难度，以进一步确保密钥的安全性。与传统对称加密算法相比，本文算法在抵御暴力攻击和防篡改方面具有更高的安全性。

Abstract

When traditional symmetric encryption algorithms are under brute-force attacks, the attacker can identify the correct key from several candidate keys as the encrypted plaintexts fit semantic characteristics. Therefore, we propose a data symmetric encryption algorithm based on multiple plaintexts. The encryption algorithm can generate a ciphertext by encrypting on n(n≥2) pairs of plaintexts and key in an encryption process and obtain the corresponding plaintexts in the decryption by decrypting the ciphertexts using a designated key. The encryption algorithm mixes a pair of true plaintexts and key and the other n-1 pairs of bogus plaintexts and key and encrypts them, which can ensure that the attacker cannot determine the true key and plaintexts even when all the keys are cracked. Additionally, the encryption algorithm increases the difficulty of cracking the key by introducing a password salt to further ensure the security of the key. Compared with the traditional symmetric encryption algorithm, the proposed algorithm has higher security in resisting brute force attacks and tamper-proofing.

Graphical abstract

关键词

多明文加密 / 安全密钥 / 暴力攻击 / 密码盐

Key words

multiple plaintexts / security keys / brute-force attack / password salt

0　 引 言

传统的数据对称加密算法，包括DES^［1］、3DES^［2］、AES^［3］、IDEA^［4］、Blowfish^［5］等，其主要特点是通信双方进行加解密的密钥相同。这些算法容易受到各种暴力穷举技术的攻击，且加密系统的安全性主要取决于用于加密消息的密钥的长度。长度为128位的密钥可以为当今的加密算法提供较高的安全性，但是将来，随着计算机处理速度的不断提高，只有增加密钥长度才能有效保护数据。同样，当用于穷举攻击的系统数量增加时，系统之间共享的密钥空间将再次削弱加密算法的安全级别。总而言之，加密算法的安全级别由攻击系统搜索密钥空间所花费的时间决定。

针对上述问题，本课题组曾经提出一种双明文加密机制^［6］。该机制的核心数学原理是，在二维平面直角坐标系中两点可以确定一条直线，这条直线有确定的斜率和截距，对于这条直线，给定一个横坐标就能计算出对应的纵坐标。因此，将该数学原理应用于双明文加密算法^［6］中，加密时，将两对密钥和明文作为平面上两个点的横纵坐标，由这两点确定的直线的斜率和截距作为密文；解密时，结合密钥和密文即可计算出相应的明文。双明文加密机制使得明文和密钥的穷举空间数量从传统对称加密算法的一个增加到了两个，在一定程度上增加了穷举的时间和难度。Lakshmi等^［7］曾经提出了类似的基于双密钥的加密算法以抵御穷举攻击，不同的是，这两个密钥一个为常规密钥，另一个是该常规密钥的输入时间，并同时使用常规加密方式加密数据，在解密过程中需要检查密钥的时效性而花费固定的时间，以此来增大暴力攻击的时间消耗。

然而，计算机处理速度与日俱增，在未来，搜索密钥空间的时间可能不再是限制攻击者穷举攻击的因素。Juels等^［8］通过Honey加密算法创建密文，当使用不正确的密钥解密时，会产生看上去有效但虚假的消息，没有明确指示攻击者输入的密钥是对还是错，使得即使是强大的攻击者（具有无限计算能力的攻击者）也无法确定解密消息，以此来抵御暴力攻击。受Honey加密思想的启发，本文在双明文加密机制^［6］的基础上，引入多明文机制，通过对n（n≥2）对明文和密钥进行加密运算，设计了一种基于多明文的数据对称加密算法，即Olympic加密算法。相较于双明文加密算法^［6］，本算法将进行加密的密钥和明文的数量从两对增大到n对，n为大于等于2的任意值，增大攻击者穷举的时间和难度；更重要的是，通信双方可以将协商好的真正用于真实信息加解密的密钥混合在这n个密钥中，让其他精心设计的n-1对看上去有效但虚假的密钥和明文产生混淆的作用。由此，攻击者即使能够依靠强大的计算能力花费大量的时间穷举得到用于加密的所有密钥和明文，也仍然无法确定真实的明文信息及对应的正确密钥，因而该算法可以从根本上有效抵御密钥穷举攻击。另外相较于双明文机制，该多明文机制还进行了密码加盐处理，进一步增大了攻击者破解密码的难度。

1　 Olympic加密算法

本文提出一种原理简单、易于实现的基于多明文的Olympic加密算法。在沿用双明文加密机制^［6］中明文、密钥预处理操作的基础上，设计了一种多明文加解密方法，使得Olympic算法能够同时对n（n≥2）对明文和密钥进行加解密，以达到有效抵御暴力穷举攻击的目的。

本节首先介绍Olympic算法的数学原理，并分析其有效性和正确性；然后对算法的通信模型进行描述；接着对明文、密钥的预处理方法进行简要说明，并对加密过程和解密过程进行详细介绍；最后对算法的特性进行阐述。

1.1　数学原理

Olympic算法依据的数学原理是拉格朗日插值算法^［9］。如图1所示，拉格朗日插值算法可以根据一个二维平面直角坐标系中已知的互不相同的n（n≥2）个点，确定一条穿过这n个点的曲线，对应于这条曲线有且只有一个确定的多项式。对于这条已知多项式系数的曲线，任意给出横坐标，即可求出对应的纵坐标。因此，拉格朗日插值算法可以应用于本文加密算法设计中。

1）　加密过程

给定的n（n≥2）对密钥和明文（密钥k₁，明文m₁）、（密钥k₂，明文m₂）、…、（密钥k_n，明文m_n ），相当于二维平面直角坐标系中的n个点。根据拉格朗日插值公式，计算出唯一的次数不超过n的多项式p（k），满足p\left(k_i\right)=m_i\left(i=\mathrm{1,2},\dots ,n\right)，如（1）式所示。

\begin{array}{l}p\left(k\right)=\frac{\left(k-k_{\mathrm{2}}\right)\dots \left(k-k_n\right)}{\left(k_{\mathrm{1}}-k_{\mathrm{2}}\right)\dots \left(k_{\mathrm{1}}-k_n\right)}\times m_{\mathrm{1}}+\\ \frac{\left(k-k_{\mathrm{1}}\right)\dots \left(k-k_n\right)}{\left(k_{\mathrm{2}}-k_{\mathrm{1}}\right)\dots \left(k_{\mathrm{2}}-k_n\right)}\times m_{\mathrm{2}}+\dots +\\ \frac{\left(k-k_{\mathrm{1}}\right)\dots \left(k-k_{n-\mathrm{1}}\right)}{\left(k_n-k_{\mathrm{1}}\right)\dots \left(k_n-k_{n-\mathrm{1}}\right)}\times m_n=\\ R_{\mathrm{1}}{k}^{n-\mathrm{1}}+R_{\mathrm{2}}{k}^{n-\mathrm{2}}+\dots +R_n\end{array}(1)

其中，R_{\mathrm{1}},R_{\mathrm{2}},\dots ,R_n为对所有(k_i,m_i)利用拉格朗日插值公式计算得到的多项式系数。R_{\mathrm{1}},R_{\mathrm{2}},\dots ,R_n将按照某种组合方式排列并作为密文的一部分，如R_{\mathrm{1}}||R_{\mathrm{2}}||\dots ||R_n。

2）　解密过程

接收到密文后，根据从中分离出的多项式系数即可确定一个曲线函数，分别将密钥k_{\mathrm{1}},k_{\mathrm{2}},\dots ,k_n代入计算即可得到相应的明文m_{\mathrm{1}},m_{\mathrm{2}},\dots ,m_n。

根据Olympic算法的数学原理，已知n个不同的点坐标可以确定唯一一条穿过它们的曲线，并计算得到该曲线的多项式系数；反之，根据一条曲线的多项式系数可以得到一个多项式函数并计算出任意横坐标上对应的纵坐标的值。由此可知，利用合法的横坐标必定可以计算得到符合语义的纵坐标，即Olympic算法可以使用相应密钥解密得到正确的明文信息。

1.2　通信模型

如图2所示的通信模型对Olympic算法如何抵御穷举攻击进行了解释，具体流程如下：

1） 消息发送方Alice在终端A对n（n≥2）个互不相同的密钥k_{\mathrm{1}},k_{\mathrm{2}},\dots ,k_n和n个明文m_{\mathrm{1}},m_{\mathrm{2}},\dots ,m_n进行加密运算，计算得到密文c。注意，在本次通信之前，消息发送方Alice与消息接收方Bob需要协商一个真正的密钥k_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}，用于加解密他们实际需要传输的真实明文信息，其他的n-1个密钥由Alice自行确定，而无需与Bob进行协商，密钥k_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}和这n-1个密钥共同组成加密的n个密钥；另外，密钥k_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}的协商算法与传统对称加密算法相似，通过非对称加密算法（例如RSA加密算法^［10］）或者专用的密钥协商算法（例如Diffie-Hellman密钥协商算法^［11］）交换密钥，因此密钥协商过程具有较高安全性；

2） 密文c在公开信道上从终端A传送到终端B；

3） 当通信接收方Bob在终端B接收到密文c，就可以使用他和Alice协商好的密钥k_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}解密得到需要传送的明文信息m_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}。尽管其他的n-1个虚假密钥（k_{\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}}）也能对密文进行解密得到相应的信息，但都不是真实信息，主要用于迷惑攻击者以抵御穷举攻击。换句话说，即使攻击者成功穷举得到所有密钥及相应明文，由于各明文都具有语义且相互混淆，导致其无法确定哪个才是真实的信息；

4） 另外，当输入这n个密钥之外的其他错误密钥（k_{\mathrm{e}\mathrm{r}\mathrm{r}\mathrm{o}\mathrm{r}}）时，算法会提示解密失败。

1.3　加解密过程

Olympic算法的结构如图3所示，虚线的左右两侧分别为算法加密和解密过程。

1.3.1　Olympic算法的预处理

Olympic算法在加密过程中对明文和口令的预处理操作与双明文加密机制^［6］中的处理大体一致，主要存在以下3点改进：

1） 对明文预处理时，明文的数量由两个增加到n（n≥2）个。利用文献［6］中填充算法对n个明文m_{\mathrm{1}},m_{\mathrm{2}},\dots ,m_n进行填充生成n个新的等长消息\mathrm{m}\_{\mathrm{p}}_{\mathrm{1}},\mathrm{m}\_{\mathrm{p}}_{\mathrm{2}},\dots ,\mathrm{m}\_{\mathrm{p}}_n，对n个明文使用Hash算法^［12］计算得到\mathrm{m}\_{\mathrm{h}}_{\mathrm{1}},\mathrm{m}\_{\mathrm{h}}_{\mathrm{2}},\dots ,\mathrm{m}\_{\mathrm{h}}_n；然后将\mathrm{m}\_{\mathrm{h}}_{\mathrm{1}},\mathrm{m}\_{\mathrm{h}}_{\mathrm{2}},\dots ,\mathrm{m}\_{\mathrm{h}}_n分别与\mathrm{m}\_{\mathrm{p}}_{\mathrm{1}},\mathrm{m}\_{\mathrm{p}}_{\mathrm{2}},\dots ,\mathrm{m}\_{\mathrm{p}}_n通过扩散明文函数\mathrm{D}\mathrm{i}\mathrm{f}\mathrm{f}\mathrm{u}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}()进行扩散操作，生成新的消息\mathrm{m}\_\mathrm{h}{\mathrm{p}}_{\mathrm{1}},\mathrm{m}\_\mathrm{h}{\mathrm{p}}_{\mathrm{2}},\dots ,\mathrm{m}\_\mathrm{h}{\mathrm{p}}_n，即\mathrm{m}\_\mathrm{h}{\mathrm{p}}_i=\mathrm{m}\_{\mathrm{p}}_i\oplus\mathrm{m}\_{\mathrm{h}}_i；最后将\mathrm{m}\_{\mathrm{h}}_{\mathrm{1}},\mathrm{m}\_{\mathrm{h}}_{\mathrm{2}},\dots ,\mathrm{m}\_{\mathrm{h}}_n分别拼接于\mathrm{m}\_\mathrm{h}{\mathrm{p}}_{\mathrm{1}},\mathrm{m}\_\mathrm{h}{\mathrm{p}}_{\mathrm{2}},\dots ,\mathrm{m}\_\mathrm{h}{\mathrm{p}}_n之前，生成新的待加密消息\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{1}},\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{2}},\dots ,\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_n，即\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_i=\mathrm{m}\_{\mathrm{h}}_i||\mathrm{m}\_\mathrm{h}{\mathrm{p}}_i。

2） 对口令预处理时，口令的数量由两个增加到n（n≥2）个，并进行了加盐处理。将随机产生的Salt拼接于每个口令MasterKey的后面，将拼接后的数据利用Hash算法^［12］生成密钥k_{\mathrm{1}},k_{\mathrm{2}},\dots ,k_n；注意，每个口令对应的Salt可以不同，目的是使加入Salt后经过Hash计算得到的所有密钥互不相同，增加密钥破解的难度。

3） 将预处理后的明文和密钥进行分组分割后，通过加密函数分组加密生成字段c'，并将口令预处理中的Salt与c'拼接在一起，组成最终的密文c。

在解密过程中，接收方收到密文后，输入用于解密的口令MasterKey，并从密文c中提取出用于加盐处理的Salt值，将两者拼接后用Hash算法生成用于解密的密钥k；由密钥k和从密文c中提取的字段c'通过解密函数计算得到明文m_{\mathrm{0}}^{\mathrm{\text{'}}}，并提取出代表Hash值的数据{\mathrm{m}}_{\mathrm{0}}^{\mathrm{\text{'}}}\_\mathrm{h}和{\mathrm{m}}_{\mathrm{0}}^{\mathrm{\text{'}}}\_\mathrm{h}\mathrm{p}；对两者使用逆扩散明文函数进行运算后得到明文，并通过验证算法检验解密是否成功。

和双明文加密机制^［6］一样，上述加解密过程的对象均为明文和密文经过分割算法处理后得到的一个分组，之后在对整个明文和密文进行加解密运算时，需要借助电码本(\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{r}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{c}\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{b}\mathrm{o}\mathrm{o}\mathrm{k}, ECB）将加解密的对象由一个分组拓展成为任意长度数据。

Olympic算法使用了双明文加密机制^［6］中的填充算法、分割算法、扩散算法、逆扩散算法、密钥分配算法以及验证算法等辅助性算法。填充算法是将初始密钥和明文填充为分组长度的整数倍；分割算法将填充后的密钥和明文分割成长度为分组长度的分组；扩散算法通过异或运算将明文的影响以比特为单位扩散到密文中去，逆扩散算法则是扩散算法的逆运算；密钥分配算法解决明文分组多于密钥分组的问题，给每个明文分组分配在加密过程中对应的密钥分组；验证算法给加密数据提供完整性保障，这些算法的具体过程详见文献［6］。

Olympic算法相较于双明文加密机制^［6］的核心变化在于算法中处理对象的数量由双明文加密中的两个增长到了n（n≥2）个。下面对Olympic算法的加密和解密函数进行详细介绍。

1.3.2　加密函数

使用分割算法将密钥k_{\mathrm{1}},k_{\mathrm{2}},\dots ,k_n和经过预处理得到的明文\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{1}},\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{2}},\dots ,\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{n}}分割成如下形式

k_i=k_{i,\mathrm{1}}||k_{i,\mathrm{2}}||\dots ||k_{i,K/L}(2)

\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_i=\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{i,\mathrm{1}}||\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{i,\mathrm{2}}||\dots ||\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{i,M/L}(3)

其中，K为密钥k_i的长度，M为预处理后明文m_hpd _i 的长度，L为分组的长度，本文将L的大小设置为128位。与双明文加密机制一样，进行加密的n对密钥和明文均可完全分割。

在每个分组中：

\begin{array}{l}{c}_j=\mathrm{E}\mathrm{n}\mathrm{c}\left(k_{\mathrm{1},j},k_{\mathrm{2},j},\dots ,k_{n,j},\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{1},j},\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{2},j},\dots ,\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{n,j},\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}{\mathrm{t}}_j\right)=\\ R_{\mathrm{1},j}||R_{\mathrm{2},j}||\dots ||R_{n,j}||\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}{\mathrm{t}}_j\end{array}(4)

其中，R_{\mathrm{1},j},R_{\mathrm{2},j},\dots ,R_{n,j}\left(j=\mathrm{1,2},\dots ,M/L\right)分别为对第j组密钥和明文分组\left(k_j,\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_j\right)利用拉格朗日插值公式所生成的多项式系数，j为分组序号，n为明文的个数。根据拉格朗日插值公式，将n个点坐标\left(k_{\mathrm{1},j},\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{1},j}\right),\left(k_{\mathrm{2},j},\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{2},j}\right),\dots ,\left(k_{n,j},\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{n,j}\right)代入计算，得到关于k的多项式如下

\begin{array}{l}p\left(k\right)=\frac{\left(k-k_{\mathrm{2},j}\right)\dots \left(k-k_{n,j}\right)}{\left(k_{\mathrm{1},j}-k_{\mathrm{2},j}\right)\dots \left(k_{\mathrm{1},j}-k_{n,j}\right)}\times \\ \left(\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{1},j}\oplus \mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}{\mathrm{t}}_j\right)+\\ \frac{\left(k-k_{\mathrm{1},j}\right)\dots \left(k-k_{n,j}\right)}{\left(k_{\mathrm{2},j}-k_{\mathrm{1},j}\right)\dots \left(k_{\mathrm{2},j}-k_{n,j}\right)}\times \\ \left(\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{2},j}\oplus \mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}{\mathrm{t}}_j\right)+\dots \\ \frac{\left(k-k_{\mathrm{1},j}\right)\dots \left(k-k_{n-\mathrm{1},j}\right)}{\left(k_{n,j}-k_{\mathrm{1},j}\right)\dots \left(k_{n,j}-k_{n-\mathrm{1},j}\right)}\times \\ \left(\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{n,j}\oplus \mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}{\mathrm{t}}_j\right)=\\ R_{\mathrm{1},j}{k}^{n-\mathrm{1}}+R_{\mathrm{2},j}{k}^{n-\mathrm{2}}+\dots +R_{n,j}\end{array}(5)

其中，+、-、×和÷运算均为模p运算，p为小于{\mathrm{2}}^L的最大素数；运算\oplus为模q运算，q的大小为{\mathrm{2}}^L，offset取随机值（由SHA256算法产生的长度为256 bit的Hash值），且使得。

在对密钥分组和明文分组进行加密的基础上，对整个n对密钥和明文进行加密，加密函数如下

\begin{array}{l}c=\mathrm{S}\mathrm{a}\mathrm{l}\mathrm{t}||\mathrm{E}\mathrm{n}\mathrm{c}\left(k_{\mathrm{1}},k_{\mathrm{2}},\dots ,k_n,\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{1}},\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{2}},\dots ,\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_n,\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}\mathrm{t}\right)=\\ \mathrm{S}\mathrm{a}\mathrm{l}\mathrm{t}||c_{\mathrm{1}}||c_{\mathrm{2}}||\dots ||c_{M/L}\end{array}(6)

其中，offset为随机产生的偏移值，Salt为随机产生的盐值，offset和Salt均是由SHA256算法产生的长度为256 bit的Hash值，n为输入的明文个数，c_j 为每个密文分组。

整个加密过程如算法1所示。

1.3.3　解密函数

对收到的密文c进行解密，首先分离出Salt和密文分组c{}_j，然后对密文进行解密，解密函数如下

m_{\mathrm{0}}^{\mathrm{\text{'}}}=\mathrm{D}\mathrm{e}\mathrm{c}\left(k,c^{\text{'}}\right)(7)

针对密文分组c{}_j，通过解密函数解密得到的明文分组为

\begin{array}{l}{m}_{\mathrm{0},j}=\mathrm{D}\mathrm{e}\mathrm{c}\left(k_j,c_j\right)=\\ \mathrm{D}\mathrm{e}\mathrm{c}\left(k_j,R_{\mathrm{1},j}||R_{\mathrm{2},j}||\dots ||R_{n,j}||\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}{\mathrm{t}}_j\right)=\\ \left(R_{\mathrm{1},j}\times k_j^{n-\mathrm{1}}+R_{\mathrm{2},j}\times k_j^{n-\mathrm{2}}+\dots R_{n,j}\right)\oplus \left(-\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}{\mathrm{t}}_j\right)\end{array}(8)

其中，+、-和×运算均为模p运算，运算\oplus为模q运算。这里的明文分组m_{\mathrm{0},j}并非具有语义信息的实际明文分组，而是经过预处理的消息\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{0},j}，各明文分组m_{\mathrm{0},j}拼接形成明文m_{\mathrm{0}}^{\mathrm{\text{'}}}。

经过解密得到明文m_{\mathrm{0}}^{\mathrm{\text{'}}}（即\mathrm{m}\_\mathrm{h}\mathrm{p}{\mathrm{d}}_{\mathrm{0}}），提取其中的{\mathrm{m}}_{\mathrm{0}}^{\mathrm{\text{'}}}\_\mathrm{h}和{\mathrm{m}}_{\mathrm{0}}^{\mathrm{\text{'}}}\_\mathrm{h}\mathrm{p}并进行明文扩散的逆操作，即{\mathrm{m}}_{\mathrm{0}}^{\mathrm{\text{'}}}\_\mathrm{p}={\mathrm{m}}_{\mathrm{0}}^{\mathrm{\text{'}}}\_\mathrm{h}\mathrm{p}\oplus {\mathrm{m}}_{\mathrm{0}}^{\mathrm{\text{'}}}\_\mathrm{h}，得到{\mathrm{m}}_{\mathrm{0}}^{\mathrm{\text{'}}}\_\mathrm{p}，接着对{\mathrm{m}}_{\mathrm{0}}^{\mathrm{\text{'}}}\_\mathrm{p}进行去填充操作，最终得到明文m_{\mathrm{0}}。将明文m_{\mathrm{0}}的散列值{\mathrm{m}}_{\mathrm{0}}\_\mathrm{h}与{\mathrm{m}}_{\mathrm{0}}^{\mathrm{\text{'}}}\_\mathrm{h}进行比较，若两者相等，则解密成功；否则，解密失败。

整个解密过程如算法2所示。

1.4　算法特性

Olympic算法具有的特性包括：公开性、易用性和机密性。

1） 公开性。和传统对称加密算法一样，Olympic算法的加解密算法完全公开，其加解密过程的正确性及安全性可以被证明。

2） 易用性。Olympic算法采用拉格朗日插值定理，巧妙地将n（n≥2）对密钥和明文视作二维平面直角坐标系中n个点的横纵坐标，并将计算得到的多项式系数作为加密生成的密文，该算法在工程中易于理解和实现。

3） 机密性。Olympic算法和所有加密算法一样，保证明文信息不会泄露给未经授权的人员，并且只有特定的密钥才能解密得到相应明文。

2　 安全性分析

本节对Olympic算法抵御攻击的能力进行分析，并通过举例进一步阐明该算法的安全性。

常见的密码攻击方式主要有字典攻击^［13］、暴力破解^［13］、彩虹表^［14］等，这些都属于穷举攻击的范畴。字典攻击需要提前生成与密码相关的字典进行存储查询，占用空间大；暴力攻击需要穷举密码进行比对，耗时长；彩虹表是字典攻击和暴力破解的折中方案，在时间和空间中形成一个平衡。

Bošnjak等^［13］做过一项研究，对某大学在线评分系统所使用的密码进行了广泛且具针对性的攻击，其中结合了多种成熟的破解技术，例如暴力攻击、字典攻击和混合攻击，研究结果显示，即使是使用单个中低端的现代GPU，如AMD Radeon R9 280X，也可以在短短几天内破解95%以上的密码。由此可以看到，暴力破解等技术在具备足够强的计算能力的条件下可能达到破解密码的目的。

为了更清楚地体现Olympic算法的安全性，在这里举例说明该算法抵御穷举攻击的具体过程。假设Alice和Bob是同班同学，他们约定下周去公园郊游，但还没有确定是哪一天。Alice想利用Olympic算法加密她计划的时间并通知Bob。在发送密文消息之前，Alice和Bob通过非对称加密的方式（例如RSA加密算法^［10］）将用于生成加密正确时间信息“星期五”的密钥Key的口令MasterKey进行交换。同时，Alice设计了其他6个虚假信息，分别为“星期一”“星期二”“星期三”“星期四”“星期六”“星期日”，以及各自对应的口令，并对这7个口令进行预处理生成相应的密钥。Alice利用Olympic算法对这7对明文和密钥进行加密生成密文C，通过公开信道发送给Bob，Bob收到密文C后，通过口令MasterKey预处理得到的密钥Key解密得到明文信息“星期五”。

在密文C的传输过程中可能会遭受两种攻击：

1） 密文C被攻击者Eve截获，并尝试利用各种穷举攻击技术进行破解，她最多可以得到7对明文和密钥，但由于每个明文信息看起来都像有效信息，她仍然无法确定真正的明文；

2） Eve截获密文C并进行篡改后继续发送给Bob，Bob会在密文解密过程中通过计算Hash值是否一致来判断密文是否被篡改。

在这个例子中，Alice在加密前的口令预处理中，对口令进行加盐处理后利用Hash算法产生密钥，由于当同一个口令加入不同的盐后进行Hash运算得到的Hash值互不相同，导致攻击者对于同一口令在加了不同盐后都得重新计算而使攻击变得更加低效。注意，Olympic算法加密过程中进行加盐处理除了上述作用外，还有一个重要的目的是使所有口令经过预处理后生成的密钥互不相同，以满足拉格朗日插值算法中各点横坐标互不相同的条件。

总而言之，Olympic算法的安全性主要由3道措施保证：

① 在密钥的产生中进行加盐处理，尽可能地增大暴力攻击的时间消耗；

② 设置除了真实明文信息和密钥之外的其他看起来有效但虚假的明文和密钥，使得攻击者即使穷举得到所有明文和密钥也无法确定真正有效的那对明文信息和密钥；

③ 在密文中设置消息完整性验证，作为解密过程中判断密文是否被篡改的指标。

3　 Olympic算法的优劣分析

本节将Olympic算法与传统对称加密算法和双明文加密算法^［6］进行比较，并对其优劣进行总结分析。

3.1　算法比较

Olympic算法与传统对称加密算法^［15］和双明文加密算法^［6］的主要区别在于输入明文数量、密钥数量、算法原理、密钥是否加盐、密钥长度这几个方面，具体参数如表1所示。

从表1中可以看到，Olympic算法与传统对称加密算法在输入的明文和密钥的数量上存在显著区别，相较于传统对称加密算法采用的一对明文和密钥以及双明文加密算法采用的两对明文和密钥，Olympic算法将明文和密钥的数量提高到了n（n≥2）对，这样做主要具有以下两点作用：

1） 增大攻击者的穷举难度；

2） 设计虚假明文进行混淆，有效抵御穷举攻击。

在加密算法原理和密钥长度方面，传统对称加密算法大体上都是经过一系列的置换操作及多轮迭代进行加密的，主要区别在于各自的密钥长度不同。DES加密算法^［1］实际用于加密的有效密钥长度为56位，导致其安全性较低；3DES加密算法^［2］则是DES算法^［1］的一种变形，由于密钥长度的增大，其安全性得到了一定程度的提高，但加密速度较慢；IDEA加密算法^［4］也是在DES算法^［1］基础上发展而来，128位的密钥长度使其具备较高的安全性，同时可以有效抵御差分分析；同样，对于AES加密算法^［3］，较长的密钥长度使其具有较高的安全性，且具备较快的加密速度；Blowfish加密算法^［5］由于其可变的密钥长度以及自身特点，安全性和加密速度都比较高。双明文加密算法^［6］和Olympic算法则分别基于各自的数学原理，实现两对或多对明文和密钥同时加密，输出一个密文。双明文加密算法^［6］和Olympic算法的密钥长度虽然可变，但需要大于分组长度以进行密钥分配，因此密钥长度引起的安全性可以由用户自行控制；另外，由于加密过程没有经历多轮的迭代加密而是根据数学公式直接计算密文，双明文加密算法^［6］和Olympic算法的加密速度都比较快。

关于密钥加盐方面，相较于传统对称加密算法和双明文加密都未对密钥进行加盐操作，Olympic算法在加密过程中，对口令预处理时进行加盐操作使穷举攻击变得低效。

为了更深入地了解Olympic算法的运算性能，对其加解密的速度进行测试，操作系统为Windows10 64位，编译环境为Microsoft Visual Studio 2017。在实验过程中，测试所用的加密数据为4对明文和密钥，共160 Bytes；进行解密的数据大小为986 Bytes。表2记录了Olympic算法进行10次测试的实验结果，每次测试的结果为Olympic算法循环执行5 000次加密和解密所用的时间。

由表2数据可以计算得到，Olympic算法加密5 000次平均耗时约为2.338 s，解密5 000次平均耗时约为1.608 s，加密速率为2.74 Mbit/s，解密速率为24.53 Mbit/s，与双明文加密算法^［6］27.35 kbit/s的加密速率和1.62 Mbit/s的解密速率相比，Olympic算法的执行速率显然更快。

3.2　Olympic算法存在的不足

Olympic算法虽然可以有效抵御穷举攻击，但是由于其自身原因仍存在一些不足，主要有以下几点：

1） Olympic算法基于拉格朗日插值算法，根据二维平面直角坐标系上的多个点确定一条曲线，计算得到曲线的多项式系数作为加密的密文，当经过的点越多时，多项式的系数的数量也越多，导致生成的密文的长度越大，计算时间越长。因此，Olympic算法需要为引入虚假的n-1对明文和密钥而付出更多的存储空间和计算时间，换言之，相较于自身而言，Olympic算法的安全性越高，则付出的时间和空间的代价越大。

2） Olympic算法本质上仍属于分组对称加密的范畴，因此其安全性仍在一定程度上依赖于密钥的长度。

3） Olympic算法要求消息发送方能够精心设计除真实明文信息之外的n-1个看起来有效但实际虚假的明文，以达到攻击者无法从穷举的n个明文中选择真实明文信息的目的，这n-1个明文设计的好坏在很大程度上影响混淆真实明文信息的效果。

4　 结 语

随着近些年计算机计算能力的快速提升，传统对称加密算法面临来自暴力攻击的威胁日益严重。因此，本文提出一种基于多明文的数据对称加密算法Olympic以应对该威胁。相较于双明文加密机制，该算法将加密的明文和密钥的数量由两个扩展到n（n≥2）个，增大了攻击者穷举的时间和难度。更重要的是，Olympic算法巧妙地将通信双方真正用于真实信息加密的明文和密钥与其他n-1对虚假的明文和密钥混合在一起加密，即使攻击者在暴力穷举破解得到这n对明文和密钥的情况下，最终也无法确定真正有效的明文和密钥，故而该算法在理论上可以消除暴力穷举带来的危害。同时，该算法在加密过程中引入密钥加盐处理，也进一步增大了攻击者破解密钥的难度。

参考文献

[1] SHARMA M， GARG R B. DES： The oldest symmetric block key encryption algorithm［C］//2016 International Conference System Modeling & Advancement in Research Trends （SMART）. New York： IEEE Press， 2016： 53-58. 10.1109/sysmart.2016.7894489

[2] KARN P， METAGER P， SIMPSON W.RFC 1851［EB/OL］. ［2020-07-08］.

[3] MEWADA S， SHARMA P， GAUTAM S S. Exploration of efficient symmetric AES algorithm［C］//2016 Symposium on Colossal Data Analysis and Networking （CDAN）. New York： IEEE Press， 2016： 1-5. 10.1109/cdan.2016.7570921

[4] LAI X. International data encryption algorithm［J］. Hepatology， 2016，60（6）：2125-2126. DOI： 10.1002/hep.27154 .

[5] NIE T Y， ZHANG T. A study of DES and Blowfish encryption algorithm ［C］//2009 IEEE Region 10 Conference. New York： IEEE Press， 2009： 1-4. 10.1109/tencon.2009.5396115

[6] 向永谦， 宋智琪， 王天宇. 一种基于双明文的数据对称加密算法［J］. 信息网络安全， 2018（7）： 69-78. DOI： CNKI： SUN： XXAQ.0.2018-07-010 .

[7] XIANG Y Q， SONG Z Q， WANG T Y. A data symmetric encryption algorithm based on double plaintext［J］. Netinfo Security， 2018（7）： 69-78. DOI： CNKI： SUN： XXAQ.0.2018-07-010（Ch ）.

[8] LAKSHMI B， PRABAKAR T N， KIRUBAKARAN E. Real time cryptography with dual key encryption［C］//2008 International Conference on Computing， Communication and Networking. New York： IEEE Press， 2008： 1-4. 10.1109/icccnet.2008.4787696

[9] JUELS A， RISTENPART T. Honey encryption： Encryption beyond the brute-force barrier［J］. IEEE Security & Privacy， 2014， 12（4）： 59-62. DOI：10.1109/MSP.2014.67 .

[10] 吴燕仙， 何妮. 拉格朗日插值公式的完全展开［J］. 通化师范学院学报， 2007， 28（2）： 10-12. DOI： 10.3969/j.issn.1008-7974.2007.02.003 .

[11] WU Y X， HE N. Complete expansion of Lagrange interpolation formula［J］. Journal of Tonghua Teachers College， 2007， 28（2）： 10-12. DOI： 10.3969/j.issn.1008-7974.2007.02.003（Ch ）.

[12] RIVEST R L， SHAMIR A， ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems［J］. Communications of the ACM， 1978， 21（2）： 120-126. DOI：10.1145/359340.359342 .

[13] DIFFIE W， HELLMAN M. New directions in cryptography［J］. IEEE Transactions on Information Theory， 1976， 22（6）： 644-654. DOI：10.1109/TIT.1976.1055638 .

[14] 王张宜， 李波， 张焕国. Hash函数的安全性研究［J］. 计算机工程与应用， 2005， 41（12）： 18-19. 10.3321/j.issn:1002-8331.2005.12.006

[15] WANG Z Y， LI B， ZHANG H G. Research on security of Hash functions［J］. Computer Engineering and Applications， 2005， 41（12）： 18-19 （Ch）. 10.3321/j.issn:1002-8331.2005.12.006

[16] BOŠNJAK L， SREŠ J， BRUMEN B. Brute-force and dictionary attack on hashed real-world passwords［C］//2018 41st International Convention on Information and Communication Technology， Electronics and Microelectronics （MIPRO）. New York： IEEE Press， 2018： 1161-1166. 10.23919/mipro.2018.8400211

[17] KUMAR H， KUMAR S， JOSEPH R， et al. Rainbow table to crack password using MD5 hashing algorithm［C］//2013 IEEE Conference on Information & Communication Technologies. New York： IEEE Press， 2013： 433-439. 10.1109/cict.2013.6558135

[18] PANDA M. Performance analysis of encryption algorithms for security ［C］//2016 International Conference on Signal Processing， Communication， Power and Embedded System （SCOPES）. New York： IEEE Press， 2016： 278-284. 10.1109/scopes.2016.7955835

基金资助

国家“十三五”重点研发计划(2016YFB0501800)