一种Xml数据文件压缩加密算法

在数据交换过程中，实现交换数据文件的压缩、文件加密是提高传输效率、加强信息传输安全的重要手段，我们在研究构建企业信息交换体系基础上，针对xml数据文件，提出了一种混合压缩加密算法，有效提高了数据交换的效率。

一、压缩加密方法的分析

本文采用如下3个方法的组合加密，LZW数据压缩方法；换位法；序列加密法。

1、LZW数据压缩方法

LZW数据压缩方法对原文进行编码，产生的压缩文本保留的是码本的序号。由于这些序号没有自然语言的上下文关系，离开LZW算法破译者不可能直接从保存的码本序号中凑出原文。LZW方法的一个巧妙之处是并不保留码本本身，解压缩时码本和原文从压缩文本中递推出来。一旦压缩文本中有哪怕一个字节的错误，都无法还原原文。利用LZW数据压缩方法的加密是通过密钥修改码本编码规则。没有密钥，即使通过LZW算法也不能恢复原文。另外，我们根据本应用的特点，对LZW算法做了改进。如果破译者不知道修改后LZW算法的细节，也无法用密文还原出原文。

2、换位法

这是一个经典的加密方法。根据应用特点，考虑到信道的数据传输效率，压缩加密后的数据是数字串。我们用换位法，把密文中的多个数字对对换。置换表通过密钥生成。换位法不依赖
于上下文关系，也与数据内容无关。复合换位法的目的是进一步把LZW生成的码本序号搞乱，增加破译者凑出原文的难度。

3、序列加密法

序列加密法的基本思想是依据原文和密钥生成一个和原文长度相同的随机序列，然后随机序列和原文通过某些运行产生密文。随机序列的产生方法有：线性反馈移位寄存器、线性同余产生器、非线性随机数产生器、裁剪随机数产生器、利用数学方法的随机数产生器。我们采用线性反馈移位寄存器(LinearFee(11，ack ShiIL Regisler，L14SR)方法，其考虑是计算量小。

复合如上三种加密方法的核心是隐藏LZW压缩方法产生的码本序号。整个加密过程的关键点是：根据应用特点对LZW的修改方法、根据密钥对LZW编码的修改方法、由密钥生成置换表的方法、数据分段长度n的大小、生成山、SR输入的方法、确定山、SR初值的方法、伪随机序列与原文的运算方法。只要破译者不知道这些细节，无法恢复原文对应的码本序号，破译几乎
是不可能的。

二、压缩加密方法的实现

1、总体设计

常用压缩算法有LZW、和llutfrnan方法。lluffrnan方法需要事先统计文本中字符串的频率，根据字符串的频率再编码、压缩。找出文本中多次重复的字符串本身是一个非常复杂的问题，
所以，lluffmarri方法中，编码的字符串较短，而且压缩后的数据一般是二进制的。LZW方法的巧妙之处在于在压缩过程中找出多次重复的串，而且码表并不需要保存到压缩后的数据中。一般来说，LZW方法比lluffrnan方法更灵活，压缩比也更小。我们的应用中对压缩的一个特别要求是压缩后是阿拉伯数字串。如果用阿拉伯数字串表示lluffman方法中的编码，则码串会比原串更长，压缩后的数据比原数据更大。

权衡各种利弊，我们认为选择LZW方法更合适。LZW方法有一个难以克服的缺点，要对一个特定的字符串编码，需要这个字符串出现的最小次数和串的长度成正比。例如，要对“军需物资油料部”实现编码，则至少应出现12次，在数据中前1 1次出现的这个字符串编码效率都不高。这个词在出现12次后，由于有了这个词的编码，以后的出现仅用一个码表示，和原串相比小了很多。所以说，LZW方法对大的文件压缩效果特别明显。我们需要压缩的数据是xrnl文件，而且一般较小，一些重复出现的字符串其重复次数也不是很多。因此直接用LZW方法效果并不理想。

为此，我们首先根据xml文件的特点，对xrnl文件进行预处理，然后对预处理生成的文件再用LZW方法压缩。根据xml文件的格式，可以大大简化重复串的查找。找出这些重复串后剔除位置冗余已经明显减小了文件的长度，再结合LZW方法，其压缩效果非常明显。由于压缩后的数据必须是阿拉伯数字串，对某些非常小的xrnl文件压缩效果一般。

2、xml文件的预处理算法

在xml文件中，域的标示、域的内容有些重复。由于在系统的应用中，xml文件都较小，重复次数也不是很多，仅依靠LZW算法对这些重复词编码效率低。xml预处理过程如下：

第一步：提取域的标示、域的内容，形成一个标示列表和一个内容列表，列表中项的序号用ASCU码表示，而非数字。例如“<aaa>xxx</aaa>”中，很容易找出标示“aaa”和内容“xxx”；

第二步：以在标示、内容列表中的序号替换文件中的域标示和域内容，同时只保留一个尖括号。例如：标示“<aaa>”变为“<12”，而与其配对的标示“也aa>”变为“>12”。其中“12”是标示在列表中的序号；

第三步：生成处理后的文件。文件的前面是标示列表、和内容列表，后面是替换后的xml文件体。

类C.XmLProcess用于完成xml的预处理，有两个输出函数：

BOOLSimplifyXmlStr(char*cXmlStr)

BOOLCXmlProcess::RecoverXmlStr(char*cXmlStr)

分别用于预处理、还原xml文件。

3、压缩算法的实现

为了便于传输，要求压缩后的数据是0~9的数字。LZW算法生成的压缩数据其实是压缩过程中数据对应的码本序号。把这些码本的序号用0~9数字表示，即可使输出的数据全是数字。这样做的不利是增加数据的冗余度，使输出数据的长度至少增加一倍。为了进一步减小输出数据的长度，对使用频率高的码本用短的序号表示。例如，经LZW压缩后生成2000个码本，则每个码本序号需要用4位数字表示。但是从2001~9999间的序号是没有用的，而全用三位数字表示码本序号又不够用。一个折衷办法是，在0~2000个码本之间找一个区间(简称半码区间)，这个区间内的码本序号用两位数字(简称半码)表示。自然找那些出现频率高的码本区间。这个区间的起始位置和长度必须保存在输出数据中。如果选择的区间多，保存的区间起始位置、长度数据也多。这对于较小的数据文件来说并不划算。所以只设定一个区间，其长度由其码本数决定。过程如下：

第一步：用标准LZW算法生成数据的码序列。设码本数为n；

第二步：计算半码区间的最大长度l(其值的大小依赖于n)；

第三步：计算半码区间的最佳起始位置s，使区间内码本出现频率之和最大；

第四步：在输出文件中保存码本序号位数、n、l、s，以及输入内容的码序列；

第五步：计算C.RC校验码并保存到输出数据中。

4、部分算法代码实现

类CDgtLzw用于完成处理后的xml数据的压缩，有两个输出函数：

BOOLCompress(unsignedchar*cStr)

BOOLDeCompress(unsignedchar*cStr)

分别用于压缩和解压缩。

有几个非输出函数，其中函数Compress(unsignedchar*cStr)用于完成标准的LZW压缩算法，其过程如下：

BOOLCDgtLzw::Compress(unsignedchar*cStr)

{

inti,iCodeIdx;

//初始化,码本数置零

m_iOutputCodeNum=0;

m_iOutputStrLen=0;

m_iCodeTableLen=c_sCodeRootLen;

//初始化,生成符号表,也作为初始的码本

for(i=0;i<c_sCodeRootLen;i++)

{

m_CodeTable[i].iOutputTimes=0;

m_CodeTable[i].sCodeLen=1;

m_CodeTable[i].iCodePos=i;

}

intiStrLen=strlen((char*)cStr);

CODETABLECurCode;

CurCode.iCodeL=c_UselessUInt;

CurCode.ucCodeR=cStr[0];

i=1;

while(1)

{

iCodeIdx=GetCodeIndex(&CurCode);

if(iCodeIdx>=0)

{

//新加入的数据和前面的数据构成一个已经存在的码本

if(i>=iStrLen)

{

//当前字节是输入数据的最后一个,LZW结束

//outputthelastindexReSizeOutputCodeIndexBuf(m_iOutputCode－Num+1);

m_iOutputCodeIndexBuf[m_iOutputCode－Num++]=iCodeIdx;

//m_CodeTable[iCodeIdx].iOutputTimes+=1;

break;

}

i++;

}

else

{

//出现一个新的码本

//addtocodetableReSizeCodeTable(m_iCodeTableLen+1);

m_CodeTable[m_iCodeTableLen]=CurCode;

//更新当前码本

m_CodeTable[m_iCodeTableLen].iOutputTimes=0;

m_iCodeTableLen++;

//outputtheindexReSizeOutputCodeIndexBuf(m_iOutputCodeNum+1);

//保存当前码本序号

m_iOutputCodeIndexBuf[m_iOutputCodeNum++]=CurCode.iCodeL;

m_CodeTable[CurCode.iCodeL].iOutputTimes+=1;

//[.c.]=kCurCode.iCodeL=c_UselessUInt;

//CurCode.ucCodeR=CurCode.ucCodeR;

}

}

//m_iMaxAppearedCode=m_iCodeTableLen-1;

while(m_CodeTable[m_iMaxAppearedCode].iOutputTimes<=0)

{

m_iMaxAppearedCode--;

//后面的码没有出现在输出数据中

if(m_iMaxAppearedCode<=0)break;

}

m_iMinAppearedCode=0;

while(m_CodeTable[m_iMinAppearedCode].iOutputTimes<=0)

{

m_iMinAppearedCode++;

//前面的码没有出现在输出数据中

if(m_iMinAppearedCode>=m_iMaxAppearedCode)break;

}

//计算用数字0~9表示的码本序号的长度

m_iOutputStrLen=0;

ReSizeOutputStrBuf(m_sCodeIndexStrLen*m_iOutputCode－Num+50);

//输出码转换成数字文本ConvertCodeFromBinToDigit();

//ConvertCodeFromBinToDigitDirect();

//加密变换

CipherTransform(NULL);

returnTRUE;

}