在計算機(jī)技術(shù)突飛猛進(jìn)的今天，加密程序的開發(fā)變得越來越受到開發(fā)者的青睞。本文使用多元哈夫曼編碼技術(shù)，開發(fā)了一個對任意文件進(jìn)行加密和解密的適用程序，程序的功能實現(xiàn)了對文件的安全保密。

一、設(shè)計思路

目前大多數(shù)用戶常用的對文件進(jìn)行加密的方法就是密碼保護(hù)，而這種加密方法簡單適用，但它同時也留下了巨大的安全隱患。對于一些破譯高手而言，往往很容易攻磁這種密碼保護(hù)。要想讓非法用戶很難破譯甚至是幾乎不可能破譯，他才會望而卻步，而這樣做的惟一方法就是使密碼盡可能復(fù)雜同時對用戶而言又滿足某種規(guī)律。

由于計算機(jī)文件中的字符具有統(tǒng)計特性，能夠統(tǒng)計出每種字符在文件中出現(xiàn)的概率。當(dāng)文件中所有字符的概率統(tǒng)計出來后，就可以用多元哈夫曼編碼的方法給文件生成對應(yīng)的哈夫曼編碼表，然后用這個哈夫曼編碼表對文件進(jìn)行加密。由于這個哈夫曼編碼表足夠復(fù)雜同時又滿足編碼的規(guī)律，非法用戶想要破解密文幾乎是不可能的。

二、基本原理

1、統(tǒng)計不同字符在文件中出現(xiàn)的概率

統(tǒng)計出每種字符在文件中的概率是進(jìn)行多元哈夫曼編碼的基礎(chǔ)。為了快速統(tǒng)計出待加密文件中不同字符出現(xiàn)的概率，此處采用二叉排序樹p1算法能夠快速而方便地統(tǒng)計出字符的概率。不妨將二叉樹中的節(jié)點(diǎn)定義為：

typedef struct node *tree;

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

int count:／*統(tǒng)計同一字符在文件中出現(xiàn)的次數(shù)*／

tree lcMd，rchildl

}；

則每個節(jié)點(diǎn)如圖1所示。

tree insert(tree r，unsigned char ch)/*動態(tài)二叉排序樹的建立*／

{tree p}

if(r==NULL)/*在二義排序樹中插入一個新的節(jié)點(diǎn)*／

{ 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++；／*同一字符再次出現(xiàn)時，計數(shù)器自動加1*／

return(r);

}

由以上程序代碼即可統(tǒng)計出不同字符在文件中出現(xiàn)的次數(shù)，用字符出現(xiàn)的次數(shù)除以文件中的字符總數(shù)，就可以得到該字符的概率。

2、生成哈夫曼編碼表

獲得一個文件的哈夫曼編碼表是該文件能夠被加密的關(guān)鍵。設(shè)某個文件中含有q種字符S1，S2，…，Sq，并且統(tǒng)計出每種字符在文件中出現(xiàn)的概率分別為p(s1)，p(S2)，…，p(Sq)，則進(jìn)行r元哈夫曼編碼的具體方法如下：

(1)信源符號的個數(shù)必須滿足q=（r-1）θ+r，θ表示信源縮減次數(shù)。如果q不滿足該式，則可以在最后增補(bǔ)一些概率為O的信源符號，因此該式又可寫成q+i=(r-1)θ+r，i為增加的信源符號數(shù)，并且是滿足該式的最小正整數(shù)或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)依次繼續(xù)下去，直至信源最后只剩下r個信源符號為止，將這最后r個信源符號分別用字符“0"、“l(fā)"、…、“0”+r-l表示;

(6)然后從最后一級縮減信源開始，進(jìn)行回推，就得到每種字符所對應(yīng)的由字符“O”、“1“，”．、“0”+r-l組成的字符串序列，不妨將其稱為碼字。

3、文件的加密過程

每從文件中讀出一個字符ch，用查哈夫曼編碼表的方式得到對應(yīng)的碼字，然后用這個碼字替換相應(yīng)的字符。當(dāng)文件中的所有字符都經(jīng)過了碼字替換，則得到一個比原文件要大的加密文件。

4、文件的解密過程

文件的解密過程是文件的加密過程的逆過程，即將一個密文還原成它的本來面目。因為一個密文是不能夠直接使用的，只有被解密后才能使用。一個被加密的義件如果不能被解密，則這種加密是毫無意義的。

由于哈夫曼編碼是即時碼，因此只要得到一個碼字c，則通過查哈夫曼編碼表得到相應(yīng)的字符，用這個字符替換相應(yīng)的碼字就是還原的過程。因此，每叢密文中讀出一個碼字，就從哈夫曼編碼表查得相應(yīng)的字符替換，當(dāng)文件中所有的碼字被替換掉，這個解密過程也就完成了。

三、程序運(yùn)行結(jié)果比較

在r元哈夫曼編碼中，隨著r的取值的不同，得到的哈夫曼編碼表是不同的。表1給出了同一大小為88. 5KB的word文檔經(jīng)過不同的哈夫曼編碼所得到的密文和哈夫曼編碼表的大小。

結(jié)果表明，r越大，則得到的密文和哈夫曼編碼表越小。其實這不難理解，r越大，哈夫曼編碼能夠利用的短碼越多，從而密文中總的碼長變短。

四、加密的逆過程

通過前面的介紹，我們知道哈夫曼編碼表是文件加密的密匙。同樣，在我們需要對密文進(jìn)行解密時，也需要這個密匙。這意味著，如果哈夫曼編碼表文件弄丟了，那么我們無法對文件進(jìn)行解密。因此，保存好哈夫曼編碼表文件是一件非常重要的工作。

加密程序的源代碼如下：

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

收藏 海報分享