多元哈夫曼编码在加密技术中的应用

在计算机技术突飞猛进的今天，加密程序的开发变得越来越受到开发者的青睐。本文使用多元哈夫曼编码技术，开发了一个对任意文件进行加密和解密的适用程序，程序的功能实现了对文件的安全保密。

一、设计思路

目前大多数用户常用的对文件进行加密的方法就是密码保护，而这种加密方法简单适用，但它同时也留下了巨大的安全隐患。对于一些破译高手而言，往往很容易攻磁这种密码保护。要想让非法用户很难破译甚至是几乎不可能破译，他才会望而却步，而这样做的惟一方法就是使密码尽可能复杂同时对用户而言又满足某种规律。

由于计算机文件中的字符具有统计特性，能够统计出每种字符在文件中出现的概率。当文件中所有字符的概率统计出来后，就可以用多元哈夫曼编码的方法给文件生成对应的哈夫曼编码表，然后用这个哈夫曼编码表对文件进行加密。由于这个哈夫曼编码表足够复杂同时又满足编码的规律，非法用户想要破解密文几乎是不可能的。

二、基本原理

1、统计不同字符在文件中出现的概率

统计出每种字符在文件中的概率是进行多元哈夫曼编码的基础。为了快速统计出待加密文件中不同字符出现的概率，此处采用二叉排序树p1算法能够快速而方便地统计出字符的概率。不妨将二叉树中的节点定义为：

typedef struct node *tree;

Struct node{ unsigned char data;/*存放不同的字符*／

int count:／*统计同一字符在文件中出现的次数*／

tree lcMd，rchildl

}；

则每个节点如图1所示。

tree insert(tree r，unsigned char ch)/*动态二叉排序树的建立*／

{tree p}

if(r==NULL)/*在二义排序树中插入一个新的节点*／

{ p=(tree)malloc(sizeof(*十p));

p->data=ch;

p->count=l;

p->lchild=NULL;

p->rchild=NULL;

return(p);

}

else if(root—>data>ch)root->lch.ild=insert(root->lchild，ch);／*在左子树中查找字符*／

else jf(root->data<ch)root->rchild=insert(root->rchild，ch);／*在右子树中查找字符*／

p->count++；／*同一字符再次出现时，计数器自动加1*／

return(r);

}

由以上程序代码即可统计出不同字符在文件中出现的次数，用字符出现的次数除以文件中的字符总数，就可以得到该字符的概率。

2、生成哈夫曼编码表

获得一个文件的哈夫曼编码表是该文件能够被加密的关键。设某个文件中含有q种字符S1，S2，…，Sq，并且统计出每种字符在文件中出现的概率分别为p(s1)，p(S2)，…，p(Sq)，则进行r元哈夫曼编码的具体方法如下：

(1)信源符号的个数必须满足q=（r-1）θ+r，θ表示信源缩减次数。如果q不满足该式，则可以在最后增补一些概率为O的信源符号，因此该式又可写成q+i=(r-1)θ+r，i为增加的信源符号数，并且是满足该式的最小正整数或0；

(2)将q+i个信源符号按概率大小递减排列p(Sl)≥p(S2)≥...≥p(sq)…≥P(Sq+i);

(3)用字符“0”、“1”，…、“0”+r-l分别代表概率最小的r个信源符号，并将这r个概率最小的倍源符号合并成一个信源符号，从而得到只包含q-r+l个符号的新信源，称为缩减信源S1；

(4)把缩减信源S，的符号仍按概率大小递减次序排列，再将其最后r个概率最小的信源符号分别用字符“On、“1"，…，．“0”+r -1表示，并且合并戍一个符号，这样又形成了q-2r+2个信源符号的缩减信源S2;

(5)依次继续下去，直至信源最后只剩下r个信源符号为止，将这最后r个信源符号分别用字符“0"、“l"、…、“0”+r-l表示;

(6)然后从最后一级缩减信源开始，进行回推，就得到每种字符所对应的由字符“O”、“1“，”．、“0”+r-l组成的字符串序列，不妨将其称为码字。

3、文件的加密过程

每从文件中读出一个字符ch，用查哈夫曼编码表的方式得到对应的码字，然后用这个码字替换相应的字符。当文件中的所有字符都经过了码字替换，则得到一个比原文件要大的加密文件。

4、文件的解密过程

文件的解密过程是文件的加密过程的逆过程，即将一个密文还原成它的本来面目。因为一个密文是不能够直接使用的，只有被解密后才能使用。一个被加密的义件如果不能被解密，则这种加密是毫无意义的。

由于哈夫曼编码是即时码，因此只要得到一个码字c，则通过查哈夫曼编码表得到相应的字符，用这个字符替换相应的码字就是还原的过程。因此，每丛密文中读出一个码字，就从哈夫曼编码表查得相应的字符替换，当文件中所有的码字被替换掉，这个解密过程也就完成了。

三、程序运行结果比较

在r元哈夫曼编码中，随着r的取值的不同，得到的哈夫曼编码表是不同的。表1给出了同一大小为88. 5KB的word文档经过不同的哈夫曼编码所得到的密文和哈夫曼编码表的大小。

结果表明，r越大，则得到的密文和哈夫曼编码表越小。其实这不难理解，r越大，哈夫曼编码能够利用的短码越多，从而密文中总的码长变短。

四、加密的逆过程

通过前面的介绍，我们知道哈夫曼编码表是文件加密的密匙。同样，在我们需要对密文进行解密时，也需要这个密匙。这意味着，如果哈夫曼编码表文件弄丢了，那么我们无法对文件进行解密。因此，保存好哈夫曼编码表文件是一件非常重要的工作。

加密程序的源代码如下：

void encode()

{ struct node *s}

int i,n,li

unsigned char xi

char str[100], fdename[20], file2[20],w[100], ch,

FILE *fpl,*fp2,*fp3*

printf（”请输入文件名：？”）

gets(filename)；

fpl=fopen(fdename, urb");

if (fpl==NULL),

{printf(对不起！该文件不存在。");

exit(0);

}

strcpy(file2, filename);

l=strlen(file2)；

for(i=0 l i

if(file2[il=='.’)breaki

strcpy(file2+i,“.dic");

fp2=fopen(file2, nr")}

if(fp2==NULL)；

{printf（”哈夫曼编码表文件不存在’）

exit(O);

}

fscanf (fp2, "%d", &n) ;

s= (struct node *) calloc(n, sizeof (struct node))

fscanf (fp2, "%d%s", &x, str) ;

i=0 ;

while(!feof (fp2))

{l=strlen(str) ;

s [i] . c= (char *) calloc (1+1, sizeof (char)) ;

s [i] . data=x;

strcpy (s [i] . c, str) ;

fscanf (fp2, "%d%s", &x, str) ;

i++ ;

}

fclose(fp2) ;

fp3=fopen ("temp. dat", "wb") ;

str [0] =O;w[l]=0

ch=fgetc (fpl) ;

while (!feof (fpl))

strcat (str, w) ;

if (strcmp (str, s [i]. c)==0)

break;

if (il=n)

{fputc (S [ij . data, fp3) ;

str[0]=0;

ch=fgetc (fpl) ;

fclose(fpl) ;

fclose(fp3) ;

remove (filename) ;

remove (file2) ;

rename ("temp. dat", filename)

}

admin普通用户

海报分享