基于字形編碼的中文字符密碼算法研究

趙 杰

(福建江夏學(xué)院 電子信息科學(xué)學(xué)院，福建 福州 350108)

0 引言

隨著網(wǎng)絡(luò)的飛速發(fā)展，加之中國國力的不斷提升，中文字符在網(wǎng)絡(luò)上的使用程度也越來越廣．然而目前大部分的密碼算法都是廣泛應(yīng)用于西文字符的加解密上，專門針對中文字符的加解密研究甚少．縱然有也不多，從已知文獻(xiàn)[1-3]可以查閱得出，現(xiàn)有研究的加解密多是基于中文的GB碼(國標(biāo)碼)或Unicode碼(統(tǒng)一碼)進(jìn)行的，并沒有針對中文本身的特點(diǎn)進(jìn)行密碼研究分析，所以其加密后的密文多為亂碼的形式．然而本文將針對性的根據(jù)中文字符的象形特點(diǎn)，從基于字形編碼的角度，對其進(jìn)行密碼算法研究，其密文結(jié)果將依然是一般的中文字符，增強(qiáng)了密文的可信度和迷惑性，進(jìn)一步提高了其安全性．

1 中文字符的特點(diǎn)分析

研究中文字符密碼算法，首先應(yīng)該對中文本身的字符特點(diǎn)進(jìn)行分析．中文字符亦稱漢字，其屬于象形文字，主要的表意象征突出明顯．一般把漢字分解為偏旁部首、字根等基本結(jié)構(gòu)，字根等再分解為筆畫、筆順等元結(jié)構(gòu)．

1.1 筆畫

從書寫形態(tài)來看，中文字符都是由筆畫構(gòu)成的．所謂筆畫就是不間斷地一次連續(xù)寫成的一個(gè)線條，但筆畫的形態(tài)變化很多，如果按其長短、曲直和筆勢走向來分，可以分成幾十種．為了方便，在此基礎(chǔ)上，依據(jù)五筆字型的方法，對其歸結(jié)為5種基本筆畫：橫(挑、提)、豎(左鉤)、撇、捺(點(diǎn))、折．

1.2 筆順

一般書寫中文字符時(shí)，均遵循如下規(guī)則：先左后右，先上后下，先橫后豎，先撇后捺，先內(nèi)后外，先中間后兩邊，先進(jìn)門后關(guān)門等．

1.3 字根

由若干筆劃交叉連接而形成的相對不變的結(jié)構(gòu)稱之為字根．本文綜合各文獻(xiàn)[4-7]對于漢字部件的研究結(jié)果，最后選用了常見的130個(gè)基本漢字部件作為字根基礎(chǔ)，即組字能力強(qiáng)，出現(xiàn)頻率高的偏旁部首．

1.4 結(jié)構(gòu)和字形

結(jié)構(gòu)可分為：單(單一字根組字)、散(多字根不相交組字)、連(單字根連單筆畫組字)、交(多字根相交組字)．

字形可分為：左右型(左右結(jié)構(gòu))、上下型(上下結(jié)構(gòu))、雜合型(單字、內(nèi)外結(jié)構(gòu)、混合結(jié)構(gòu)等)．

1.5 字符拆分原則

按書寫順序、能散不連、能連不交、取大優(yōu)先、兼顧直觀[8-10]．其詳細(xì)規(guī)則：含4個(gè)或以上字根的漢字，用4個(gè)字根碼組成編碼，不足4個(gè)的，除字根碼外，還要補(bǔ)加一個(gè)末筆字型交叉識別碼，如仍不足4碼，用0代替．

舉例：字符“明”由兩個(gè)基本字根構(gòu)成，一個(gè)是“日”，編碼9；一個(gè)是“月”，編碼86．“明”的最后一筆是橫，整個(gè)漢字呈左右結(jié)構(gòu)，所以它的末筆字型交叉識別碼是11．因此，“明”的四字根碼為(9，86，11，0)．

1.6 中文字符與西文字符的對比分析

1.6.1 從字符頻率的角度分析

中文與西文不同，前者出現(xiàn)的頻率表現(xiàn)了其特殊性，據(jù)文獻(xiàn)[11]統(tǒng)計(jì)，后者出現(xiàn)的最常見的1 000個(gè)英文單詞在普通文章中約占70%，如果是2 000個(gè)英文單詞，也只增長到78%，如果要掌握90%的英文文章內(nèi)容，就要學(xué)會7 000個(gè)英文單詞，而相比中文則只要識字740個(gè)，就可以看懂9成的中文文章了，兩者相差了近10倍，以上足以體現(xiàn)中文的優(yōu)越性．

此外，和英文截然不同的是，英文單詞的新詞數(shù)量在不斷的增加，而中文字符(漢字)卻沒有不斷造出新字出現(xiàn)，在解決新觀念、新事物時(shí)，都是通過組合漢字造新詞來闡述問題的，鮮有創(chuàng)新字，反而是一些生冷僻字的使用率在不斷下降，有被逐步淘汰的趨勢．

1.6.2 從信息量的角度分析

文字的作用是傳遞信息，文字的信息量是-Pwlog2Pw(單位為bit)，Pw是出現(xiàn)的或然率．n個(gè)字的信息量(負(fù)熵)，就是n個(gè)字信息量的總和：Hn=-∑Pwlog2Pw．據(jù)文獻(xiàn)[12]統(tǒng)計(jì)，當(dāng)中文容量n擴(kuò)大時(shí)，熵值H也相應(yīng)迅速增大，如表1所示，但增大到12370時(shí)，趨勢逐漸放緩趨于穩(wěn)定，如圖1所示.

表1 不同中文容量下的熵值

圖1 熵值變化圖

在同樣信息量Hn=7時(shí)，英文需要數(shù)量為2 700個(gè)，而中文只需470個(gè)；當(dāng)Hn=8，英文要5200個(gè)，而中文只需720個(gè)．因此，在傳遞同樣比較復(fù)雜的信息時(shí)，中文所需的字?jǐn)?shù)量僅約為英文的13.8%～17.4%．

綜上所述，中文在某些方面有著英文所無法替代的優(yōu)越性，然而專門針對中文字符的密碼算法至今少有出現(xiàn)．現(xiàn)在廣泛使用的密碼算法都是對其GB碼或Unicode碼進(jìn)行加密，并不是針對中文字符本身的特點(diǎn)來加解密的．這不能不說是密碼學(xué)研究領(lǐng)域的一種遺憾，也是中國漢語文明研究的一種遺憾．本文的研究初衷正是要對有符合中文自身特點(diǎn)的密碼算法進(jìn)行深入地分析和探討．

2 常用密碼算法的應(yīng)用分析

2.1 預(yù)備知識

文中用p表示明文、c表示密文、密鑰空間為K、密鑰為k、加密算法E、解密算法D．

2.2 替代密碼

2.2.1 單一字母替代密碼——Caesar密碼(凱撒密碼)

2.2.1.1 算法介紹

Caesar密碼是由Julins Caesar發(fā)明的，其原理簡單易懂，就是對英文字母表中的每個(gè)字母用其后第3位的字母來替換成密文，即密鑰k=3．如果密鑰空間K={0,1,2,……,24,25}，k∈Z26，那就成了移位密碼，所以它是移位算法的特例，其通用表示為：

加密算法：

Ek(p)≡p+k(mod 26)

(1)

解密算法：

Dk(c)≡c-k(mod 26)

(2)

2.2.1.2 實(shí)際應(yīng)用

加密過程

對中文“明”進(jìn)行加密，取密鑰k=3，基于字形的密鑰空間K={0,1,2,……,128,129}，則“明”對應(yīng)的數(shù)字分別為(9，86，11，0)，如將9帶入公式(1)變形，易得E3(9)≡9+3(mod 130)≡12，相應(yīng)的，對于每位數(shù)字帶入公式后得到的數(shù)字分別為(12，89，14，3)，即轉(zhuǎn)換為中文“勃”．

解密過程

將密文數(shù)字c分別帶入公式(2)變形，D3(c)≡c-3 (mod 130)，即可．

2.2.1.3 密碼分析

由于替代密碼算法加解密過程公開，明文p所用的語言有意義容易識別，且只有130種不同的密鑰位移長度，攻擊者很容易使用蠻力窮舉攻擊方法來破解，所以在現(xiàn)有安全體系下，使用其作為密碼算法是不安全的．

2.2.2 多字母替代密碼——Vigenere密碼(維吉尼亞密碼)

2.2.2.1 算法介紹

該密碼算法有一個(gè)參數(shù)n，在加解密過程中，把字母映射到0～25的數(shù)字再進(jìn)行運(yùn)算，并按照n個(gè)字母為一組整體進(jìn)行變換．

設(shè)密鑰k= (k1,k2,……,kn)，明文p= (p1,p2,……,pn)，則加密算法為：

Ek(p) = (c1,c2,……,cn)

(3)

其中,

ci≡(pi+ki) (mod 26)，i=1,2,……,n．

對密文c= (c1,c2,……,cn)，其解密算法為：

Dk(c) = (p1,p2,……,pn)

(4)

其中,pi≡(ci-ki) (mod 26)，i=1,2,……,n．

此外，其還可以通過查表的方式來進(jìn)行加解密的過程，如表2所示.

表2 基于西文編碼的Vigenere密碼表

2.2.2.2 實(shí)際應(yīng)用

加密/解密算法均可帶入公式(3)(4)變形，即可得到結(jié)果，或者通過查表3可得：

表3 基于中文編碼的Vigenere密碼表

加密過程

對中文“明”(9，86，11，0)進(jìn)行加密，取密鑰中文“勃”(12，89，14，3)，將9帶入表格行，12帶入表格列，或帶入公式(3)變形，易得E3(9)≡(9+12) mod 130≡21，相應(yīng)的，對于每位數(shù)字查表或帶入公式后得到的數(shù)字分別為(21，45，25，3)，即轉(zhuǎn)換為中文“滂”．

解密過程

可將密文c帶入公式(4)變形或者反查表格從行的位置得到明文p．

2.2.2.3 密碼分析

對于Vigenere密碼的破解攻擊關(guān)鍵取決于對n的分析，如果采用的n長度是與p一樣，就能消除其周期性特點(diǎn)．算法本身建議使用自動密鑰系統(tǒng)，系統(tǒng)中k與p相連．當(dāng)然即使如此依然是脆弱的，因?yàn)閮烧咧g共享同樣的頻率分布，依賴統(tǒng)計(jì)原理就可以進(jìn)行分析，所以只能選擇與p長度一致但毫無統(tǒng)計(jì)關(guān)聯(lián)的k．此外，由于是對中文信息加密，原表是基于西文字符而構(gòu)造的(26×26)，與之相比建立130×130的表格，無形中加大了工作量難度．

2.3 仿射密碼——Hill密碼(希爾密碼)

2.3.1 算法介紹

由n個(gè)線性方程決定用連續(xù)的n個(gè)密文c替代明文p，每個(gè)字符賦予一個(gè)值，例如a=0,b=1,……,z=25．假設(shè)n=3，則可得：

c1=(k11p1+k12p2+k13p3) mod 26

c2=(k21p1+k22p2+k23p3) mod 26

c3=(k31p1+k32p2+k33p3) mod 26

即c=kp．(c、p分別為列向量，長度等于3，k是一個(gè)3×3的矩陣)．

解密使用k的逆k-1即可．

2.3.2 實(shí)際應(yīng)用

與上面例子一樣，舉“明”為例，使用密鑰：

則密文c(c1,c2,c3,c4)：

c1= (2×9+7×86+9×11+5×0) mod 130=69

c2=(7×9+6×86+3×11+8×0) mod 130=92

c3=(4×9+5×86+8×11+6×0) mod 130=34

c4=(3×9+2×86+1×11+9×0) mod 130=80

可得，(69,92,34,80)，即“拿”．

2.3.3 密碼分析

盡管Hill密碼能夠?qū)箖H有密文攻擊的強(qiáng)度較高，但它容易被已知明文攻擊所攻破，所以其也不適合當(dāng)今中文字符的加密要求．

2.4 分組密碼——DES密碼(Data Encryption Standard，數(shù)據(jù)加密標(biāo)準(zhǔn))

2.4.1 算法介紹

作為典型的Feistel密碼結(jié)構(gòu)，DES的加密過程主要如圖2所示，其明文p分組長為64 bit，由此生成同樣大小的密文c，輸入的初始密鑰k亦是相同長度，其中，第8、16、24、32、40、56、64為奇偶校驗(yàn)碼，實(shí)際長度為56bit．

整個(gè)加密階段分為三大步驟來描述，首先是初始置換IP，用于重新排列分組好的p，然后采用功能一樣的16輪迭代，每輪都有置換和代換運(yùn)算(其中第16輪變換輸出左右各一半后，交換次序)．最后再經(jīng)過初始置換的逆IP-1，從而產(chǎn)生最終64 bit的c．

解密過程中，由于其算法可逆，解密算法與加密如出一轍，所不同的是子密鑰的使用順序相反(k16,k15,……,k1)．鑒于篇幅所限，請?jiān)旈單墨I(xiàn)[13-14]．

2.4.2 實(shí)際應(yīng)用

首先將字符“明”按照規(guī)定分組，即進(jìn)行初始置換IP，打亂原先順序，然后將輸出的64 bit分為左右各自32 bit(L0R0)．然后將R0與子密鑰k1進(jìn)行f函數(shù)運(yùn)算，再將結(jié)果與L0做XOR(異或)運(yùn)算，得到新R1，參與下一輪的右分組，而左分組L1由R0賦值得到．如此循環(huán)往復(fù)16輪，得到L16與R16，最終再進(jìn)行初始逆置換IP-1，便得到結(jié)果．(IP、IP-1、k選位表、壓縮p置換、f函數(shù)S盒等均由算法規(guī)定得)．通過對逐一字符字根的替換加密后，對于字符“明”(9,86,11,0)可得“吊”(26,68,30,74)．利用這種方法可以加密所有文字．

圖2 DES密碼原理圖

2.4.3 密碼分析

對于DES的安全性分析中，主要問題集中于兩點(diǎn)：

1.密鑰長度偏短，其密鑰實(shí)質(zhì)為56 bit，密鑰量約為1017，難以抵抗窮舉搜索攻擊．因?yàn)閷?shí)踐證明，在一些政府機(jī)構(gòu)和大型組織可用專門機(jī)器在數(shù)小時(shí)內(nèi)搜索完整個(gè)密鑰空間．

2.非線性S盒的安全性遭質(zhì)疑，由于設(shè)計(jì)者IBM對于其原理未公開，致使眾多學(xué)者專家懷疑其存在陷門，不過后來NSA建議優(yōu)化，現(xiàn)已能夠抵抗差分密碼分析攻擊了．

縱然DES的安全性還有待加強(qiáng)，但其演變形式的密碼算法，例如3-DES(三重DES)、AES(Advanced Encryption Standard，高級加密標(biāo)準(zhǔn))等，具有較高的安全性，諸如經(jīng)過三重DES加密后，盡管在運(yùn)行速度上慢了近2/3，然而其較高的安全性還是可以作為中文字符密碼算法的考慮方案之一．

2.5 公鑰密碼——RSA密碼(Rivest Shamir Adle-man)

2.5.1 算法介紹

RSA作為典型的非對稱密碼算法其原理基于一個(gè)數(shù)論事實(shí)：將兩個(gè)大素?cái)?shù)相乘很容易，但想要對乘積進(jìn)行分解卻很難，因此可以將乘積公開作為加密密鑰．其過程如下[15]：

S1:兩個(gè)大素?cái)?shù)P、Q乘積為n，另e與(P-1)(Q-1)互質(zhì)，(n,e) 作為公鑰對．

S2:要求(de)mod((P-1)(Q-1))=1，(n,d) 作為私鑰對．

故而其加密為：c=pemodn，解密為：p=cdmodn．

2.5.2 實(shí)際應(yīng)用

假設(shè)加密中文“明”，根據(jù)編碼，分別對9，86，11，0進(jìn)行加密(設(shè)：P=47,Q=71,e=79)．第一分組加密為：979mod 3337=1605，再對其求模：1605 mod 130= 45，對隨后的分組進(jìn)行同樣的操作，產(chǎn)生加密后的密文：“純”(45，60，40，0)．

加密時(shí)要注意對130求模時(shí)，為了能夠還原密文就必須先計(jì)算對其求商保留值，以便在解密過程中能還原出對每組分組計(jì)算的原始值．

2.5.3 密碼分析

RSA安全性基于對大素?cái)?shù)的分解難度，其常用攻擊方法主要有針對其協(xié)議的選擇密文攻擊、公共模數(shù)攻擊、低加密/解密指數(shù)攻擊等．但對于中文字符的加解密有其不利因素，如遇到編碼為0的情況，代表末筆識別碼為空格時(shí)，容易知曉明文的字根總數(shù)為2，其安全程度便大大降低，使得選擇密文攻擊有可能會成功，而且其對130求商的結(jié)果保存也是必須要考慮的問題．因此該算法用于對中文字符的加密顯得不是十分合適．

2.6 總結(jié)

綜上所述，對于以上多種常用密碼算法對于中文字符的加解密，綜合各種因素分析后，從安全性和時(shí)效性角度得出結(jié)論，本文認(rèn)為DES(或3-DES、AES)等加密算法對于中文進(jìn)行加解密可行性較高．

3 對字符重碼的安全性分析

之所以會產(chǎn)生重碼是因?yàn)槠湓雌鹩谥形淖址瞧矫嫖淖值脑颍驗(yàn)樽址加玫氖嵌S空間的信息符號，如果用一些數(shù)值符號做線性排列來替代，那么空間維度必然從二維降為一維，也對應(yīng)的減少了信息表示．當(dāng)然重碼不僅存在于中文，在西文字符中同樣存在．

基于五筆的漢字編碼形式其單字重碼率低于0.02%，但本文提出的基于字形的中文字符編碼不同于五筆，五筆的四字根碼是基于鍵盤上25個(gè)按鍵來布局的[16]，所以重碼率雖然相比拼音編碼低，但還是依然存在一定的局限性．而本文所闡述的是基于130個(gè)字根來編碼的，與五筆輸入法是有本質(zhì)區(qū)別的，所以其重碼率將遠(yuǎn)低于0.02%，對于處理日常的幾千個(gè)常用中文字符是完全可以應(yīng)付的．

盡管如此，如果用五個(gè)字根碼來表示一個(gè)中文字符，那么重碼率肯定會更低，但必須考慮編碼的轉(zhuǎn)換時(shí)效問題．另一方面，實(shí)際鮮少使用的生冷僻字在日常使用中出現(xiàn)的概率極低，即使一旦出現(xiàn)，對于大部分人來說，也無異于是“天書”，無形中起到了加密的作用．

4 結(jié)論

本文創(chuàng)新地提出了結(jié)合基于字形編碼的中文字符密碼算法，一改以往只是基于GB碼或Unicode碼來進(jìn)行的加解密過程，彌補(bǔ)了過往各種研究中沒有針對中文字符本身字形特性進(jìn)行分析的遺憾和空缺，且對于加密后的結(jié)果依然以中文字符的形式存在，無形中提高了密文自身的安全性．

對于未來的研究方向，主要還是要著手解決重碼的問題，由于個(gè)人能力有限，本文最后共對GB2312-80規(guī)定的一、二級字庫共計(jì)6763個(gè)常用和次常用中文字符進(jìn)行加解密的字庫設(shè)計(jì)，尚未遇到不能解決的重碼單字(遇到重碼單字在最后一位改寫成序列碼)，但這依然不是治本之道，后期的研究中將擴(kuò)展字庫、字根編碼以及重新研究更加可靠的編碼方案，同時(shí)也將涉及各種異體字、罕用字、甚至繁體字的領(lǐng)域，擴(kuò)大算法的使用范圍．

最后，本文所提出的密碼算法除了可用于日常中文信息的隱寫處理，亦可用于機(jī)要部門網(wǎng)絡(luò)通信，金融行業(yè)銀行系統(tǒng)的重要信息保密，以及電子郵件、手機(jī)短信等涉及中文密碼的領(lǐng)域．

[1]吳業(yè)福.用VB6實(shí)現(xiàn)漢字的加密方法探討[J].計(jì)算機(jī)應(yīng)用研究,2001，(3):143～145.

[2]崔艷榮.字符型密碼隨機(jī)加密與解密算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2013，(3):826～830.

[3]胡善岳,李俊山,吳 婭.漢字加密的新思路——漢字混合加密技術(shù)研究與實(shí)現(xiàn)[J].計(jì)算機(jī)安全,2004，(12):21～23.

[4]王道平,黃文麗.關(guān)于兩個(gè)漢字部件規(guī)范的一點(diǎn)思考[J].中文信息學(xué)報(bào),2013，(2):74～78.

[5]韓布新.部件組合──潛在的漢字結(jié)構(gòu)層次[J].中文信息學(xué)報(bào),1995，(3):27～32.

[6]曉 東.現(xiàn)代漢字部件分析的規(guī)范化[J].語言文字應(yīng)用,1995，(3):56～59.

[7]李 麗.現(xiàn)代漢字部件研究述評[D].長春:東北師范大學(xué),2012.

[8]王永民.計(jì)算機(jī)漢字輸入五筆字形編碼方案簡介[J].冶金自動化,1984，(6):27～30.

[9]張德劭.漢字部件規(guī)范的目的和部件拆分標(biāo)準(zhǔn)——兼評《基礎(chǔ)教學(xué)用現(xiàn)代漢語常用字部件規(guī)范》[J].中國文字研究,2007，(2):229～233.

[10]王 寧.漢字構(gòu)形理據(jù)與現(xiàn)代漢字部件拆分[J].語文建設(shè),1997，(3):4～9.

[11]盧遂現(xiàn).漢字的科學(xué)研究[M].北京:光明日報(bào)出版社，1987．

[12]馮志偉.現(xiàn)代漢字和計(jì)算機(jī)[M].北京:北京大學(xué)出版社，1989．

[13]宋秀麗.現(xiàn)代密碼學(xué)原理與應(yīng)用[M].北京:機(jī)械工業(yè)出版社，2012．

[14]Wade Trappe,Lawrence C.Washington.Introduction to Cryptography with Coding Theory (Second Edition)[M].London:Prentice Hall,2008．

[15]Ranjan Bose.Information Theory,Coding and Cryptography[M].New York:McGraw-Hill,2008．

[16]陳欽梧,彭小忠.新音形編碼漢字輸入法設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用,2014，(1):36～40.