基于字形编码的中文字符密码算法研究

赵 杰

(福建江夏学院 电子信息科学学院，福建 福州 350108)

0 引言

随着网络的飞速发展，加之中国国力的不断提升，中文字符在网络上的使用程度也越来越广．然而目前大部分的密码算法都是广泛应用于西文字符的加解密上，专门针对中文字符的加解密研究甚少．纵然有也不多，从已知文献[1-3]可以查阅得出，现有研究的加解密多是基于中文的GB码(国标码)或Unicode码(统一码)进行的，并没有针对中文本身的特点进行密码研究分析，所以其加密后的密文多为乱码的形式．然而本文将针对性的根据中文字符的象形特点，从基于字形编码的角度，对其进行密码算法研究，其密文结果将依然是一般的中文字符，增强了密文的可信度和迷惑性，进一步提高了其安全性．

1 中文字符的特点分析

研究中文字符密码算法，首先应该对中文本身的字符特点进行分析．中文字符亦称汉字，其属于象形文字，主要的表意象征突出明显．一般把汉字分解为偏旁部首、字根等基本结构，字根等再分解为笔画、笔顺等元结构．

1.1 笔画

从书写形态来看，中文字符都是由笔画构成的．所谓笔画就是不间断地一次连续写成的一个线条，但笔画的形态变化很多，如果按其长短、曲直和笔势走向来分，可以分成几十种．为了方便，在此基础上，依据五笔字型的方法，对其归结为5种基本笔画：横(挑、提)、竖(左钩)、撇、捺(点)、折．

1.2 笔顺

一般书写中文字符时，均遵循如下规则：先左后右，先上后下，先横后竖，先撇后捺，先内后外，先中间后两边，先进门后关门等．

1.3 字根

由若干笔划交叉连接而形成的相对不变的结构称之为字根．本文综合各文献[4-7]对于汉字部件的研究结果，最后选用了常见的130个基本汉字部件作为字根基础，即组字能力强，出现频率高的偏旁部首．

1.4 结构和字形

结构可分为：单(单一字根组字)、散(多字根不相交组字)、连(单字根连单笔画组字)、交(多字根相交组字)．

字形可分为：左右型(左右结构)、上下型(上下结构)、杂合型(单字、内外结构、混合结构等)．

1.5 字符拆分原则

按书写顺序、能散不连、能连不交、取大优先、兼顾直观[8-10]．其详细规则：含4个或以上字根的汉字，用4个字根码组成编码，不足4个的，除字根码外，还要补加一个末笔字型交叉识别码，如仍不足4码，用0代替．

举例：字符“明”由两个基本字根构成，一个是“日”，编码9；一个是“月”，编码86．“明”的最后一笔是横，整个汉字呈左右结构，所以它的末笔字型交叉识别码是11．因此，“明”的四字根码为(9，86，11，0)．

1.6 中文字符与西文字符的对比分析

1.6.1 从字符频率的角度分析

中文与西文不同，前者出现的频率表现了其特殊性，据文献[11]统计，后者出现的最常见的1 000个英文单词在普通文章中约占70%，如果是2 000个英文单词，也只增长到78%，如果要掌握90%的英文文章内容，就要学会7 000个英文单词，而相比中文则只要识字740个，就可以看懂9成的中文文章了，两者相差了近10倍，以上足以体现中文的优越性．

此外，和英文截然不同的是，英文单词的新词数量在不断的增加，而中文字符(汉字)却没有不断造出新字出现，在解决新观念、新事物时，都是通过组合汉字造新词来阐述问题的，鲜有创新字，反而是一些生冷僻字的使用率在不断下降，有被逐步淘汰的趋势．

1.6.2 从信息量的角度分析

文字的作用是传递信息，文字的信息量是-Pwlog2Pw(单位为bit)，Pw是出现的或然率．n个字的信息量(负熵)，就是n个字信息量的总和：Hn=-∑Pwlog2Pw．据文献[12]统计，当中文容量n扩大时，熵值H也相应迅速增大，如表1所示，但增大到12370时，趋势逐渐放缓趋于稳定，如图1所示.

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

图1 熵值变化图

在同样信息量Hn=7时，英文需要数量为2 700个，而中文只需470个；当Hn=8，英文要5200个，而中文只需720个．因此，在传递同样比较复杂的信息时，中文所需的字数量仅约为英文的13.8%～17.4%．

综上所述，中文在某些方面有着英文所无法替代的优越性，然而专门针对中文字符的密码算法至今少有出现．现在广泛使用的密码算法都是对其GB码或Unicode码进行加密，并不是针对中文字符本身的特点来加解密的．这不能不说是密码学研究领域的一种遗憾，也是中国汉语文明研究的一种遗憾．本文的研究初衷正是要对有符合中文自身特点的密码算法进行深入地分析和探讨．

2 常用密码算法的应用分析

2.1 预备知识

文中用p表示明文、c表示密文、密钥空间为K、密钥为k、加密算法E、解密算法D．

2.2 替代密码

2.2.1 单一字母替代密码——Caesar密码(凯撒密码)

2.2.1.1 算法介绍

Caesar密码是由Julins Caesar发明的，其原理简单易懂，就是对英文字母表中的每个字母用其后第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 实际应用

加密过程

对中文“明”进行加密，取密钥k=3，基于字形的密钥空间K={0,1,2,……,128,129}，则“明”对应的数字分别为(9，86，11，0)，如将9带入公式(1)变形，易得E3(9)≡9+3(mod 130)≡12，相应的，对于每位数字带入公式后得到的数字分别为(12，89，14，3)，即转换为中文“勃”．

解密过程

将密文数字c分别带入公式(2)变形，D3(c)≡c-3 (mod 130)，即可．

2.2.1.3 密码分析

由于替代密码算法加解密过程公开，明文p所用的语言有意义容易识别，且只有130种不同的密钥位移长度，攻击者很容易使用蛮力穷举攻击方法来破解，所以在现有安全体系下，使用其作为密码算法是不安全的．

2.2.2 多字母替代密码——Vigenere密码(维吉尼亚密码)

2.2.2.1 算法介绍

该密码算法有一个参数n，在加解密过程中，把字母映射到0～25的数字再进行运算，并按照n个字母为一组整体进行变换．

设密钥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．

此外，其还可以通过查表的方式来进行加解密的过程，如表2所示.

表2 基于西文编码的Vigenere密码表

2.2.2.2 实际应用

加密/解密算法均可带入公式(3)(4)变形，即可得到结果，或者通过查表3可得：

表3 基于中文编码的Vigenere密码表

加密过程

对中文“明”(9，86，11，0)进行加密，取密钥中文“勃”(12，89，14，3)，将9带入表格行，12带入表格列，或带入公式(3)变形，易得E3(9)≡(9+12) mod 130≡21，相应的，对于每位数字查表或带入公式后得到的数字分别为(21，45，25，3)，即转换为中文“滂”．

解密过程

可将密文c带入公式(4)变形或者反查表格从行的位置得到明文p．

2.2.2.3 密码分析

对于Vigenere密码的破解攻击关键取决于对n的分析，如果采用的n长度是与p一样，就能消除其周期性特点．算法本身建议使用自动密钥系统，系统中k与p相连．当然即使如此依然是脆弱的，因为两者之间共享同样的频率分布，依赖统计原理就可以进行分析，所以只能选择与p长度一致但毫无统计关联的k．此外，由于是对中文信息加密，原表是基于西文字符而构造的(26×26)，与之相比建立130×130的表格，无形中加大了工作量难度．

2.3 仿射密码——Hill密码(希尔密码)

2.3.1 算法介绍

由n个线性方程决定用连续的n个密文c替代明文p，每个字符赋予一个值，例如a=0,b=1,……,z=25．假设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是一个3×3的矩阵)．

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

2.3.2 实际应用

与上面例子一样，举“明”为例，使用密钥：

则密文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密码能够对抗仅有密文攻击的强度较高，但它容易被已知明文攻击所攻破，所以其也不适合当今中文字符的加密要求．

2.4 分组密码——DES密码(Data Encryption Standard，数据加密标准)

2.4.1 算法介绍

作为典型的Feistel密码结构，DES的加密过程主要如图2所示，其明文p分组长为64 bit，由此生成同样大小的密文c，输入的初始密钥k亦是相同长度，其中，第8、16、24、32、40、56、64为奇偶校验码，实际长度为56bit．

整个加密阶段分为三大步骤来描述，首先是初始置换IP，用于重新排列分组好的p，然后采用功能一样的16轮迭代，每轮都有置换和代换运算(其中第16轮变换输出左右各一半后，交换次序)．最后再经过初始置换的逆IP-1，从而产生最终64 bit的c．

解密过程中，由于其算法可逆，解密算法与加密如出一辙，所不同的是子密钥的使用顺序相反(k16,k15,……,k1)．鉴于篇幅所限，请详阅文献[13-14]．

2.4.2 实际应用

首先将字符“明”按照规定分组，即进行初始置换IP，打乱原先顺序，然后将输出的64 bit分为左右各自32 bit(L0R0)．然后将R0与子密钥k1进行f函数运算，再将结果与L0做XOR(异或)运算，得到新R1，参与下一轮的右分组，而左分组L1由R0赋值得到．如此循环往复16轮，得到L16与R16，最终再进行初始逆置换IP-1，便得到结果．(IP、IP-1、k选位表、压缩p置换、f函数S盒等均由算法规定得)．通过对逐一字符字根的替换加密后，对于字符“明”(9,86,11,0)可得“吊”(26,68,30,74)．利用这种方法可以加密所有文字．

图2 DES密码原理图

2.4.3 密码分析

对于DES的安全性分析中，主要问题集中于两点：

1.密钥长度偏短，其密钥实质为56 bit，密钥量约为1017，难以抵抗穷举搜索攻击．因为实践证明，在一些政府机构和大型组织可用专门机器在数小时内搜索完整个密钥空间．

2.非线性S盒的安全性遭质疑，由于设计者IBM对于其原理未公开，致使众多学者专家怀疑其存在陷门，不过后来NSA建议优化，现已能够抵抗差分密码分析攻击了．

纵然DES的安全性还有待加强，但其演变形式的密码算法，例如3-DES(三重DES)、AES(Advanced Encryption Standard，高级加密标准)等，具有较高的安全性，诸如经过三重DES加密后，尽管在运行速度上慢了近2/3，然而其较高的安全性还是可以作为中文字符密码算法的考虑方案之一．

2.5 公钥密码——RSA密码(Rivest Shamir Adle-man)

2.5.1 算法介绍

RSA作为典型的非对称密码算法其原理基于一个数论事实：将两个大素数相乘很容易，但想要对乘积进行分解却很难，因此可以将乘积公开作为加密密钥．其过程如下[15]：

S1:两个大素数P、Q乘积为n，另e与(P-1)(Q-1)互质，(n,e) 作为公钥对．

S2:要求(de)mod((P-1)(Q-1))=1，(n,d) 作为私钥对．

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

2.5.2 实际应用

假设加密中文“明”，根据编码，分别对9，86，11，0进行加密(设：P=47,Q=71,e=79)．第一分组加密为：979mod 3337=1605，再对其求模：1605 mod 130= 45，对随后的分组进行同样的操作，产生加密后的密文：“纯”(45，60，40，0)．

加密时要注意对130求模时，为了能够还原密文就必须先计算对其求商保留值，以便在解密过程中能还原出对每组分组计算的原始值．

2.5.3 密码分析

RSA安全性基于对大素数的分解难度，其常用攻击方法主要有针对其协议的选择密文攻击、公共模数攻击、低加密/解密指数攻击等．但对于中文字符的加解密有其不利因素，如遇到编码为0的情况，代表末笔识别码为空格时，容易知晓明文的字根总数为2，其安全程度便大大降低，使得选择密文攻击有可能会成功，而且其对130求商的结果保存也是必须要考虑的问题．因此该算法用于对中文字符的加密显得不是十分合适．

2.6 总结

综上所述，对于以上多种常用密码算法对于中文字符的加解密，综合各种因素分析后，从安全性和时效性角度得出结论，本文认为DES(或3-DES、AES)等加密算法对于中文进行加解密可行性较高．

3 对字符重码的安全性分析

之所以会产生重码是因为其源起于中文字符是平面文字的原因，因为字符占用的是二维空间的信息符号，如果用一些数值符号做线性排列来替代，那么空间维度必然从二维降为一维，也对应的减少了信息表示．当然重码不仅存在于中文，在西文字符中同样存在．

基于五笔的汉字编码形式其单字重码率低于0.02%，但本文提出的基于字形的中文字符编码不同于五笔，五笔的四字根码是基于键盘上25个按键来布局的[16]，所以重码率虽然相比拼音编码低，但还是依然存在一定的局限性．而本文所阐述的是基于130个字根来编码的，与五笔输入法是有本质区别的，所以其重码率将远低于0.02%，对于处理日常的几千个常用中文字符是完全可以应付的．

尽管如此，如果用五个字根码来表示一个中文字符，那么重码率肯定会更低，但必须考虑编码的转换时效问题．另一方面，实际鲜少使用的生冷僻字在日常使用中出现的概率极低，即使一旦出现，对于大部分人来说，也无异于是“天书”，无形中起到了加密的作用．

4 结论

本文创新地提出了结合基于字形编码的中文字符密码算法，一改以往只是基于GB码或Unicode码来进行的加解密过程，弥补了过往各种研究中没有针对中文字符本身字形特性进行分析的遗憾和空缺，且对于加密后的结果依然以中文字符的形式存在，无形中提高了密文自身的安全性．

对于未来的研究方向，主要还是要着手解决重码的问题，由于个人能力有限，本文最后共对GB2312-80规定的一、二级字库共计6763个常用和次常用中文字符进行加解密的字库设计，尚未遇到不能解决的重码单字(遇到重码单字在最后一位改写成序列码)，但这依然不是治本之道，后期的研究中将扩展字库、字根编码以及重新研究更加可靠的编码方案，同时也将涉及各种异体字、罕用字、甚至繁体字的领域，扩大算法的使用范围．

最后，本文所提出的密码算法除了可用于日常中文信息的隐写处理，亦可用于机要部门网络通信，金融行业银行系统的重要信息保密，以及电子邮件、手机短信等涉及中文密码的领域．

[1]吴业福.用VB6实现汉字的加密方法探讨[J].计算机应用研究,2001，(3):143～145.

[2]崔艳荣.字符型密码随机加密与解密算法的设计与实现[J].计算机工程与设计,2013，(3):826～830.

[3]胡善岳,李俊山,吴 娅.汉字加密的新思路——汉字混合加密技术研究与实现[J].计算机安全,2004，(12):21～23.

[4]王道平,黄文丽.关于两个汉字部件规范的一点思考[J].中文信息学报,2013，(2):74～78.

[5]韩布新.部件组合──潜在的汉字结构层次[J].中文信息学报,1995，(3):27～32.

[6]晓 东.现代汉字部件分析的规范化[J].语言文字应用,1995，(3):56～59.

[7]李 丽.现代汉字部件研究述评[D].长春:东北师范大学,2012.

[8]王永民.计算机汉字输入五笔字形编码方案简介[J].冶金自动化,1984，(6):27～30.

[9]张德劭.汉字部件规范的目的和部件拆分标准——兼评《基础教学用现代汉语常用字部件规范》[J].中国文字研究,2007，(2):229～233.

[10]王 宁.汉字构形理据与现代汉字部件拆分[J].语文建设,1997，(3):4～9.

[11]卢遂现.汉字的科学研究[M].北京:光明日报出版社，1987．

[12]冯志伟.现代汉字和计算机[M].北京:北京大学出版社，1989．

[13]宋秀丽.现代密码学原理与应用[M].北京:机械工业出版社，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]陈钦梧,彭小忠.新音形编码汉字输入法设计[J].计算机工程与应用,2014，(1):36～40.