一种多维度的加密密文编码算法

一种多维度的加密密文编码算法

0数据库加密算法随着计算机网络的快速发展，许多应用程序已经包含数据库。数据库加密是防止数据库记录不被泄露的有效手段。通常使用某种加密算法对数据库中的记录实施加密运算后,还要对加密后的记录进行编码,之所以要进行编码是因为加密后的数据库记录中很可能包含不可打印字符甚至字符“/0”。由于数据库系统对字符的读写只支持可打印字符,如果记录中出现不可打印字符,读写数据库记录时就要发生错误,所以加密后的数据记录如果没有经过编码,在读写过程中就很可能产生错误,导致数据库操作失败。目前很多基于数据库的应用系统中对数据库记录进行编码使用的是标准的Base64编码,实际上这种对数据库记录的保护方式存在明显的安全隐患。通常一个数据库文件中包括很多条记录,所有记录通常使用同一个对称密钥进行加密,一旦加密算法选择得不好,密钥很容易被得到,攻击者可以首先使用标准的Base64编码对数据库记录进行解码,然后使用加密密钥对密文解密从而恢复出原始的数据库记录。文献研究了最新的数据库安全系统及技术,但均未解决数据库记录密文编码问题;文献总结分析了当前的数据库加密算法并提出新的算法,但这些算法都存在自身缺陷不能与编码运算很好地结合。针对这个问题,本文利用Hill密码的思想提出了一种数据库密码编码算法。新算法弥补了同类算法存在的安全缺陷,而且算法将加密与编码融合为一体,加密的过程既是编码过程,大大加快了处理速度,提高了运行效率,实际上该算法提供给数据库一种双重安全保护机制。1预备知识1.1编码字符表的编码Base64编码字符表的编码对象是二进制消息,表1所示的64个基本字符构成它的编码字符集。在编码过程中,待编码的二进制消息被分成一个个6比特的单元,每个单元转换成十进制数字后对照表1进行编码。标准Base64编码字符表的字符与数字对应关系如表1所示。本文提出的算法中,笔者没有使用标准的Base64编码字符表,而是对标准表中的字符进行了随机排列,形成新的字符与数字对应表,称之为重排的Base64编码表,如表2所示,这样做的目的是为了增加统计分析的难度,最终增加了破译难度。1.2模p同余同余接下来给出如下定义:定义1设p(p≥2)是给定的正整数,称之为模,正整数r满足0≤r<m,对任意整数a,存在唯一的整数r及唯一的整数q,使等式a=pq+r成立。其中r称为a模p的余数。称全体整数关于模p的全体余数组成的集合为模p的余数集,记作Zp。例如Z6={0,1,2,3,4,5}。定义2若整数矩阵A和B的行、列数相同,并且同一位置的数据关于模p同余,称矩阵A与B关于模p同余,记作:A≡Bmodp例如,=mod6=mod6。推论1给定模p,任意整数矩阵必与由模p的余数集Zp中的元素构成的某一矩阵同余。定义3设α是Zp中的元素,若存在β∈Zp使得αβ≡1modp称β为α关于模p的逆元,记作β=α-1modp定义4设A是n阶整数方阵,若n阶方阵B满足:(1)B的全部元素属于Zp;(2)AB≡BA≡I(modp),I为n阶单位方阵。称B是A模p的逆矩阵,记作B=A-1modp定理1n阶整数方阵A有模p逆矩阵的充分必要条件是行列式|A|关于模p的余数r存在Zp上的逆元r-1。如表1,可以将Base64编码表看作64个字符与余数集Z64的元素的一一对应,每个数字编号可以看作相应字符的代码。一般,如果Zp中的元素a与p是互素的,那么a的逆元a-1存在,反之不存在。根据这一性质,可以计算出Z64中32个元素有逆元,其对应的逆元表如表3所示。2基于平滑密码概念的密码编码算法2.1编码编码和编码该算法借鉴了Hill密码的思想,将加密运算和编码运算有机地融为一体,加密的同时就进行编码运算,因此加密的结果就是编码的结果。算法过程如下:(1)重排标准Base64编码字符表中的字符顺序,得到类似表2的重排后的Base64编码字符表;(2)随机或离线生成Z64上n阶方阵A,满足|A|在Z64上存在逆元,并求出A模64的逆矩阵A-1。将A用作加密矩阵,A-1用作解密矩阵;(3)将待编码的数据库记录从ASCII字符集映射到新Base64编码表上,然后分为若干分组,其中分组大小为A的阶数n。分组向量记作α,计算A×αmod64,对照新Base64编码表查找计算结果中各分量对应的字符,将所有分量对应的字符排列起来便得到原始记录的密文编码;(4)重复执行第(3)步直到所有的记录被加密和编码。下面举例说明该算法的执行过程,为叙述方便不妨假设该例中使用的是如表2所示的重排的Base64编码字符表。不妨设A为Z64上的三阶矩阵:A==⎡⎣⎢201012101⎤⎦⎥计算|A|,得到|A|=1mod64查表3知1在Z64上的逆元为1,故A为Z64上的可逆矩阵。求得A模64的逆矩阵如下(A*为A的伴随矩阵):A-1=1×A*=[10-121-4-102]A−1=1×A∗=⎡⎣⎢10−121−4−102⎤⎦⎥假设当前待编码的数据库记录为:RMB680,其对应的ASCII字符编号为:82,77,66,36,38,30转化为二进制:1010010,1001101,1000010,0100100,0100110,0011110按6位重新分组得到:101001,010011,011000,010010,010001,001100,011110转化为十进制:41,19,24,18,17,12,30将其分为大小为3的三个分组Pi(i=1,2,3),最后一个分组字符数量不足3,可以按照事先规定的规则添加特定字符,不妨本例中添加字符选定为‘0’,在表2中对应的编号为36。如下:(41,19,24),(18,17,12),(30,36,36)利用公式P′i=A×Pi(P′i表示Pi对应的密文),对分组分别进行加密计算:Ρ′1=×=mod64P′1=⎡⎣⎢201012101⎤⎦⎥×⎡⎣⎢411924⎤⎦⎥=⎡⎣⎢4231⎤⎦⎥mod64Ρ′2=×=mod64P′2=⎡⎣⎢201012101⎤⎦⎥×⎡⎣⎢181712⎤⎦⎥=⎡⎣⎢484130⎤⎦⎥mod64Ρ′2=×=mod64对照表2得到原数据库记录“RMB680”经加密编码后对应的字符串为“F39cT8QC+”。到此,一条记录的加密编码过程完成。解密过程就是加密过程的逆过程,解密公式为:Pi=A-1×P′i,再将解密后的字符串映射到ASCII集中即可恢复原始记录。2.2算法分析2.2.1时间复杂度分析设待加密的数据库记录数为n,每条记录的长度为m,那么该算法的时间复杂性是O(mn),在n≫m的情况下,时间复杂度是O(n)。当数据库越大、记录数越多时该算法的时间效率体现得越高。2.2.2重新排列编码字符的编码与映射该算法的安全性基于所使用编码字符集的大小与加密矩阵的阶数,实际上通过双重保密机制来实现对数据库的安全保护,其一是随机排列的Base64编码表,其二是加密矩阵。安全强度分析如下:第一点,编码字符集越大就越安全。本算法使用的是经过重排处理的Base64字符集,共有64个字符,重排的目的是为了增加破译难度。编码字符集越大,重新排列可能得到的字符与序号的对应关系越多,Base64编码字符表经重新排列后可能产生的新的字符与序号映射表的数目为:64!≈1.2687×1089(个)第二点,加密矩阵的阶数越大越安全。为了兼顾运算的时间效率,同时有重新排列的编码字符表作保证,加密矩阵的阶数不必取得太大,满足安全性够用的原则就可以了。做到以上两点,该算法可以达到计算上的安全性,满足实际应用的要求。不妨假设采用的加密矩阵是5阶上三角矩阵,并且满足:主对角线上的元素取自Z64中有逆元的元素(保证该矩阵在Z64中必然存在模64逆矩阵),其逆矩阵也是主对角线元素有逆元的矩阵。按照这种加密矩阵构造方式,在Z64中可能作为加密矩阵的5阶上三角矩阵有325×6410=1024×3215(个)假如某台超级计算机每秒可以判断100万亿个加密矩阵,使用穷举法来搜索需要:1.26887×1089×1024×3215÷(1014×3600×24×365)≈1.55654×1093(年)通常,被保护的数据库都具有时效性,短则数月长则数十年后就失效了,因此在使用期内这种算法的安全度是足够高的。3数据库编码算法数据库的安全问题一直是一个研究的热点,数据库加密必然涉及到编码问题。一个好的