基于简易混合选择编码的对称密钥自变动加密

针对安全性要求不太高的加密系统，将单边范式HufFman编码与等长编码相结合，提出一种基于混合选择编码的对称密钥自变动加密方案。通过将明文的统计结果作为自身加密的密钥和编码依据，使方案易于实现，且计算存储成本低。

一、单边范式Huffman编码简介

范式Huffman编码是Huffman编码的一个子集。其中心思想是：使用某些强制的约定，仅通过很少的数据便能重构出哈夫曼编码树的结构。单边范式Huffman编码是范式Huffman编码中的一种特例。假设满足单边范式Huffman编码的信源X由n个信源符号组成，按照符号概率由大到小排列后，写成{X1，X2，…，xn}，对应的概率集合为{P(x1），P(X2)，…，P(xn))，则其编码树结构如图1所示。

与这棵树对应的编码如表1所示。

根据Huffman树构造规则，可知信源符号Xk必定满足以下条件：

观察表1和图1可以得出单边范式Huffman编码的一些特性：

(1)符号的码字长度与其排列的位置有关，即排列后除最后一个符号xn外，任一符号Xk的单边范式Huffman码字长度为后。

(2)码字长度为七的单边范式Huffman编码的前k-1位码字为1，第后位码字为0。

(3)排列后最后一个符号石。的码字长度为n-1，其单边范式Huffman编码由n-1个1组成。

从这些特性可以看出，使用单边范式Huffman编码的编解码十分简单。通过已知的符号排列序位，编码器可以直接输出对应码字长度的单边范式Huffman编码；而解码器只需通过对输入编码进行码字长度判断，便可以解码出对应的符号序位，从而完成解码。整个编解码过程中并不需要进行Huffman树的构造，也不需要进行编码的辨识，只需对输入编码进行码字长度判断。

二、简易混合选择编码方法

单边范式Huffman编码是Huffman编码的一种特例，其适用条件为满足式(1)。但当信源符号概率按照大小顺序排列后不满足条件式(1)时，单边范式Huffman编码的压缩性能将变差。由单边范式Huffman编码的特性，容易得到其编码平均码字长度L为：

又因为P(x1)≥1/n，所以可得其上限值ln：

当且仅当P(X1)=P(X2)....=P(xn）=1/n时上式取等号。

当不满足式(1)时，单边范式Huffman编码并不是最佳的，其与Huffman编码的平均码字长度的差值将变大，压缩性能也随之变差。观察三的上限值，当n>2时，l近似为n/2。对比使用等长编码时的平均码字长度[lbn]，容易看出当n>6时，[lbn]<n/2。等长编码的压缩性能较Huffman编码来说虽有所降低，但由于使用固定的码字长度编码，因此识别和编码较为简单，信源符号的编码码字可以与符号排列后的序位对应。例如，一个有n个信源符号的信源，其符号按照符号概率大小排列后，使用等长编码，那么第七个符号的等长编码码字正好是值k-1的二进制表示。

单边范式Huffman编码的编解码构造简单，但其平均编码码字长度变化范围会随着信源符号及其概率的变动而过大；等长编码同样编解码构造简单，其平均编码码字长度在一定程度上是固定的。那么可以对任意一个信源输出序列采取单边范式Huffman编码与等长编码的混合选择编码：对已知信源符号根据其概率进行大小排序后，先计算单边范式Huffman编码平均码字长度，若此平均码字长度大于采取等长编码的平均码字长度，则使用等长编码，否则，使用单边范式Huffman编码。这样信源编码的平均码字长度将取等长编码平均码字长度与单边范式Huffman编码平均码字长度中最小的一个，即信源的平均码字长度L≤[1bn]。由于该编码方法是使用等长编码与单边范式Huffman编码中的一种，因此对于任一信源其编解码结构都将十分简单，不需要构造 Huffman树或者进行符号对应的码字存储，使得其计算开销成本极大地减小，而时间成本也仅取决于码字长度的判断或二进制与十进制之间的转换；在压缩性能方面，较最佳的Huffman编码来说会有所降低，但不会差过在同等概率条件下使用等长编码时的压缩性能。

三、基于混合选择编码的对称密钥自变动加密方案

事实上对于大型文本的统计，不同的文本，即便其字符个数相同，其统计结果也是不一样的；若对文本划分多个文本块，那么每个文本块的统计结果也各不相同。这样若将文本划分成多个块，而每个块采取单边范式Huffman编码与等长编码的混合选择编码方案，则整个编解码系统结构将十分简单，计算开销较小，只是在压缩性能上有所降低，但最低只会达到整个文本全部采取等长编码时的压缩性能。考虑将一个长的信源输出序列进行多个块的划分，当前块的统计结果将作为下一个块的简易混合选择编码的依据。这样后续的块将基于前一个块的统计结果不断改变编码方式和信源符号的排列，从而实现自变动的编解码，整个编解码过程并不依赖于整个信源符号的磷切概率；为了使整个系统计算开销均衡，可以采取等长划分块，即划分块长度是一定的。若考虑将第1个块的编解码依据作为整个编解码系统的密钥，那么整个系统成为一个基于简易混合选择编码方案的对称密钥自变动加密系统。

1、加密与解密过程

由于加解密需要知道第1块段字符的编码方式、块的字符串长度、字符排列顺序后，才可以对整个密文或者明文进行编码，因此发送者Alice需要将它们生成为密钥并对明文加密后都传送给接收者Bob。这样整个加解密过程如下：

(1)Alice对外发布整个信源符号的无序排列集合(x1，X2，...，Xk)，选取块字符串长度n并对信源符号进行特定排列，记录下排列后各个符号对应的排列序位（tl，t2，…，tk)以及第1块段的编码方式Z，并根据这些生成密钥，通过安全信道传输给接收者Bob。

(2)Alice根据靠对明文m划取第1个块，根据（t1，t2，…，tk)以及编码方式Z对第一个块进行编码，并统计当前块的各个符号数量，第1个块编码结束后根据统计结果计算更新(t1，t2，…，tk)与编码方式i。

(3)Alice继续根据n划取块，根据前一个块更新的t1，t2，…，tk与编码方式f对当前块编码，并统计当前块的各个符号数量，待当前块编码结束后根据统计结果计算更新(tl，t2，…，tk)与编码方式i。

(4)Alice不断重复步骤(3)，完成对明文m的加密，生成密文c，并将c传送给接收者Bob。

解密过程正好是加密过程的逆过程，具体如下：

(1)Bob接收到Alice发送过来的密钥，生成块长度n，第1个块信源各符号排列序位(tl，t2，…，tk)与其编码方式i。

(2)Bob根据(t1，t2，…，tk)与编码方式i，开始对密文c解码，并同时统计解码出的各符号个数。

(3)当解码个数达到块的字符串长度n时，Bob根据当前统计的结果计算更新(tl，t2，…，tk)与编码方式i。

(4)Bob不断重复步骤(2)和步骤(3)，完成整个密文c的解码，从而获取Alice所发送的明文m。

2、系统安全性分析

从整个加解密过程中可以看出，每个块的编码方式和每个信源符号对应的码字取决于前一个块的统计结果，而与信源符号本身的概率集合无关。Alice发送的密钥中包含了第1个块编码所依据的信源符号集合的排列序位、编码方式和块的字符串长度靠。可以推断，攻击者如果无法准确获取到这个密钥，那么破解出密文c将是极为困难的。

现在假定攻击者获取到了块的字符串长度玎和第1个块的编码方式i，但他却没有获得第1个块编码所依据的信源符号集合的排列序位。这样攻击者可以准确获得对应密文c编码块数、信源输出序列长度以及各个块的数学上的统计结果。由于攻击者缺少信源符号集合排列序位这个信息，他不得不去猜测编码码字与各个符号上的数学对应关系，因此他将获得k！种信源符号排序可能。由于每个块的编码取决于上一个块的数学统计结果，而不是信源符号本身，从第1个块所对应的信源符号的一种排序只会获得一种可能解密所得的明文，因此在攻击者获知块的字符串长度玎和第1个块的编码方式i时，必定得到k!种明文可能。

进一步假设攻击者只获得了第1个块的编码方式i。这时攻击者不仅需要确定块的字符串长度n，还需要得到k!种信源符号集合的大小排列序位。对于处理n，攻击者可以采取穷举方法不断尝试不同数值的n。由于攻击者能全部获取密文c，因此他能够轻易统计出密文c中的比特总数M。不妨假定，编码时Alice都只获得了最差的压缩性能，即整个明文m都采取等长编码生成密文c。所以，攻击者能够计算出信源输出序列总长度：

其中，k表示信源符号个数；M表示密文e比特总数；K表示信源符号使用等长编码时的平均码字长度。这样攻击者可以根据N开始进行穷举，以获得可能的块长度。由于整个输出序列使用等长划分块，因此划分的块的总个数l为：

攻击者根据式(5)可以近似地认为对于不同的雅，若划分的块总个数l相同，则对于这些n值，其破译结果是基本一致的。攻击者考虑到对于明文m的划分不会将块的字符串长度n取值过小，因此他需要设定一个穷举n的下限值。而信源符号个数k是已知的，攻击者可以将k作为穷举n的下限值。那么不妨假设攻击者取后作为穷举n的下限值，这样攻击者将只需要穷举l取1[n/k]时所对应的一个n值。对于最终这些穷举的靠，攻击者认为根据这些H值每次密文c解码的结果将会不同。因为每一个穆值对应着k!种信源符号集合的大小排列序位可能，所以最终攻击者得到的解码明文总数为[n/k]×k!种。下面将证明若序列总长度N大于k2时，攻击者将不得不猜测后种可能的序列块划分。

引理若N>k2，则存在后个不同的整数对(n,l)满足：

 

证明：不妨假设l=1，2，…，k，先证明l取k个值中任意一个都存在一个靠使之满足式(6)与式(7)。

设：

可得：

联立式(8)与式(9)有：

由式(10)可得：

联立式(11)与式(12)可得：

因此，l取k个值中任意一个都存在一个n，使之满足式(6)与式(7)。

下面使用反证法证明这k个l各不相同。假设存在2个l值l1与l2，与其对应的n值相同为no，其中，l1>l2。

因为no对于l1与l2都满足式(6)与式(7)，所以：

联立式(14)与式(15)，可得：

又因为l1与l2为l-k的一个整数，且l1>l2，所以：

很明显，式(16)与式(17)互相矛盾，假设不成立，即l不同取值所对应的H都不会相同。引理得证。

由引理可知，若序列总长度N>k2，，那么攻击者将不得不穷举出后种可能的序列块划分情况，最终攻击者得到的解码明文总数为kxk!。由此有：

即一个超指数级别的数。因此，若保证信源输出序列总长度大于k2，同时确保信源字符数后也足够大，那么攻击者使用穷举方式获得的解码明文总数将是一个超指数级别的。显然这种情形对于攻击者来说，破译密文的难度将会很大，计算开销与时间开销也将呈超指数级别的。

最后假定攻击者只获得了密文c，根据前面的分析可知此时攻击者已经很难破译密文。明文编码后，其密文比特总数M取决于各个块的编码方式：

其中，N1表示采取单边范式Huffman编码的字符总数；N2表示采取等长编码的字符总数；K表示采取等长编码时平均码字长度；K’表示采取单边范式Huffman编码时总平均码字长度。N1和N2满足：N= Ni +N2。攻击者对第1块段采取不当的编码方式猜测，将对N1和N2值产生偏差，从而使得N值也有所偏差，最终获得更多的错误破译明文。

随意截取《指环王》英文文本中的几段作为加密明文，将其对应的二进制文件的4位二进制作为信源符号，即信源符号共16个。当第1块的编码方式为单边范式Huffman编码以及第一块所依据的信源符号排列为已知时，不同块长度靠对应的输出密文总比特数M如表2所示。

从表2中可以看出，随着块长度n的变化，输出总比特个数M也在变化，但M与信源符号总个数N之间并不具有可循的变化规律。很显然，攻击者此时若不能截获块长度n的密钥信息，将不能有效地获得Ⅳ的信息，来降低破译密文的难度。

由于每次加密的明文都不相同，因此其统计的结果也各不相同，划分块字符串长度穆也不相同。所以，对于不同的明文，其生产的密钥是截然不同的，该方案也满足“一次一密”的加密要求。

3、密钥的安全性考虑

发送者Alice需要将块字符串长度玑第1个块编码所依据的信源符号集合的大小排列序位（t1,t2,...,tk)以及第1块段的编码方式i作为密钥传送给接收者Bob，倘若直接传送给Bob，那么需要至少一个长度为k+2的数组保存这些信息。同时由于（t1,t2,...,tk)与n为纯数值数据；而编码方式i也可以被定义为：当i=0时使用等长编码方式，当i=1时使用单边范式编码方式，因此Alice传送给Bob的密钥数组为纯数值数组，攻击者如果获得这个数值数组的部分信息，将大大降低破译密文c的难度，所以，Alice需要对要传输的密钥进行一定的安全性考虑。可以考虑一种简单可行的方法——插值法，对密钥的保存也使用了插值法。由于整个数组都为数值数组，而（（t1,t2,...,tk)与其序列标号有关tk与k具有对应关系，因此Alice可以将整个数组与其序位构成序列，从而获得k+2个序列对：(1，t1)，（2，t2)，…，(k，tk)，(k+l，n)，(k+2，i))，这时Alice可以使用插值法生成一个满足这k+2个序列对的插值多项式Pk+．(X)。通过插值法，可以得到多项式Pk+1 (X)完全展开后的形式：

根据式(20)的形式，Alice实际需要向Bob传送这个多项式的k+2个系数，同样为k+2个长度的虢数值数组。当Bob接收到这k+2个系数后，重构出Pk+1 (X)，将1～k+2代入Pk+l (X)，从而获得序列对(1，t1)，（2，t2)，…，(k，tk)，(k+l，n)，(k+2，i))，最终获取密钥。而对于攻击者来说，如果他只获取了Alice所发送的这些系数中的几个，将无法完整复原Pk+1(X)，进而无法获得真正的密钥，所以，他对密文c的破译难度不会得到任何的改善。

另还有多种可行的密钥传输方法，如提出的一种基于椭圆曲线离散对数的无证书混合加密方案，利用该加密方案对密钥加密，能够有效保障密钥传输的安全性。

该方案将信源输出序列进行块划分，并把第一个块的编码所依据的信源符号排列位置、编码方式和块长度作为密钥，使整个编码系统成为一种自变动的加密系统；由于将依赖于信源符号概率的编码转变为一种排列序位的数值编码，因此在整个编解码过程中并不需要存储编码码字，大大减少了存储空间，易于实现。并证明在完全不知道密钥的情况下，攻击基于混合选择编码方法的自变动加密体制是较为困难的。