-
传统的Hill加密算法将英文字母、数字以及常见的符号构成编码字符集.编码字符集的基数为p,以一定的编码规则进行编码,并对应0到p-1之间的整数,但是如果编码字符集的基数p不为素数[1],还必须使得加密矩阵行列式的值在模p下有乘法逆元;文献[2-3]给出了在模26情况下的数字方阵作为密钥矩阵需要满足的要求,并给出了在模26意义下选取密钥矩阵以及MATLAB求解逆矩阵的方法;文献[4]针对密钥矩阵在模26意义下的逆矩阵可能是分数的问题提出了行列变换的改进,当p为素数时,可以得到一个具有p个元素的有限域GF(p),但其上的Hill加密的密钥矩阵易受到暴力攻击.
有限域GF(28)是一种特殊的有限域[5],其具有28个元素,而不是像有限域GF(p)上必须有p个元素(p为素数).有限域GF(28)上每个元素都可以表示为8位的二进制数,并可以将元素唯一地映射为一个系数为0,1的8次以下的一元多项式,其有限域上的多项式的加法和乘法等运算具有封闭性,在密码学、信息编码等领域都是很重要的数学工具[6].有限域GF(28)的算术运算具有一定的复杂性和特殊性(表中的space表示空格符).
本文论述有限域GF(28)上的Hill加密是对传统Hill加密的衍生,把有限域GF(28)上互为伪逆的一对矩阵作为加密和解密密钥,能满足安全密码系统的基本条件.本文选取空格和255个互异的可见字符进行字符编码,如表 1所示,并按照0~255的顺序对表格中的字符按照行优先进行编码.
全文HTML
-
定义1 有限域GF(2)[x]指二元域GF(2)上的一元多项式的全体的集合.
设p(x)是GF(2)上的一个8次不可约多项式,GF(2)[x]/(p(x))=〈S,+,*,p(x)〉是一个代数结构,满足
且GF(2)[x]/(p(x))关于域上的加法″+″构成阿贝尔群,其单位元为零多项式,GF(2)[x]/(p(x))-{0}关于有限域上的乘法″*″构成阿贝尔群,且″*″对″+″满足分配律,也即对∀a(x),b(x),c(x)∈S,记
其中ai,bi,ci∈{0,1},满足左右分配律
成立.考虑到GF(28)与GF(2)[x]/(p(x))上的元素及其元素间相应的运算具有一一对应的性质,所以下文重点讨论GF(2)[x]/(p(x))上的Hill加密衍生算法.有限域GF(2)[x]/(p(x))上相应运算定义如下:
1) $\mathit{a}(\mathit{x}) + \mathit{b}(x) = \sum\limits_{i = 0}^7 {\left({\left({{a_\mathit{i}} + {b_\mathit{i}}} \right)\bmod 2} \right){x^\mathit{i}}} $
2) a(x)-b(x)=a(x)+b(x)
3) $a(\mathit{x}) * \mathit{b}(\mathit{x}) = \left({\sum\limits_{i = 0}^7 {\sum\limits_{j = 0}^7 {\left({\left({{a_\mathit{i}} \times {b_\mathit{j}}} \right)\bmod 2} \right){x^{i + j}}} } } \right)\bmod \mathit{p}\left(x \right)$
4) a(x)-1:当且仅当a(x)*a(x)-1=1
5) a(x)/b(x)=a(x)*b(x)-1
-
对∀a(x)∈GF(2)[x]/(p(x)),a(x)≠0,因为p(x)为不可约多项式,显然有
根据代数性质,必然存在有限域上的唯一多项式b(x)使得b(x)=a(x)-1为a(x)的乘法逆元,可用如下方法求多项式a(x)的逆多项式.
1) 令a(x)=akxk+…+a2x2+a1x+a0,其中ai∈{0,1},k≤7.
2) 设b(x)是a(x)在模p(x)下的逆多项式,令b(x)=b7x7+…+b2x2+b1x+b0,其中bi∈{0,1}.
3) 由多项式的乘法可得
也即有
其中的二维矩阵是一个(k+8)×8的矩阵,可以把c(x)中方次大于7的项xm(m>7)用模p(x)的余式替换掉,也即在有限域GF(2)[x]/(p(x))用xmmodp(x)得到的结果替换掉xm,从而消去x的方次大于7的项,替换后合并同类项得到降幂的多项式
其中ci包含未知数b7,b6,…,b1,b0. 4)由于设b(x)是a(x)在模p(x)下的逆多项式,所以
也即可以得到
又因为
所以可以得
因此有下面的方程组成立
可以用模2意义下的高斯消元法解此方程组,最后即可得b(x)中各项的系数,得到a(x)的逆多项式b(x).
-
有限域上的n阶多项式方阵
根据代数学方法求Key(x)在有限域GF(2)[x]/(p(x))上的行列式
|Key(x)|为矩阵Key(x)的普通n阶行列式.定义伴随矩阵
其伴随矩阵中的Aij(x)为多项式方阵Key(x)中元素aij(x)在模p(x)意义下的代数余子式.如果有det(Key(x))≠0,则根据上节有限域GF(2)[x]/(p(x))上多项式求逆的方法可以求得多项式det(Key(x))的逆多项式|Key(x)|-1,最后可得逆矩阵
-
高矩阵是指列线性无关的矩阵[8].可逆方阵为高矩阵的一种特例.
有限域GF(2)[x]/(p(x))上的多项式高矩阵:GF(2)[x]/(p(x))上的高矩阵指列满秩的多项式矩阵,其中多项式矩阵的元素属于GF(2)[x]/(p(x)),p(x)是GF(2)上的一个8次不可约多项式.
根据一般数字高矩阵A求左伪逆的公式pinv(A)=(A′*A)-1*A′[9](其中A为列满秩的数字矩阵),可得有限域GF(2)[x]/(p(x))上高矩阵求左伪逆的方法,设高矩阵
是列满秩的矩阵,且满足k≥l,则有
然后利用上节有限域GF(2)[x]/(p(x))上多项式方阵求逆的方法可求得A′(x)*A(x)在模p(x)意义下的逆多项式矩阵(A′(x)*A(x))-1,最后用求得的(A′(x)*A(x))-1与A′(x)做模p(x)的多项式矩阵的乘法,即可求得高矩阵A(x)的左伪逆矩阵pinv(A(x)).
2.1. 有限域GF(2)[x]/(p(x))的多项式求逆[7]
2.2. 有限域GF(2)[x]/(p(x))的n阶方阵求逆
2.3. 有限域GF(2)[x]/(p(x))的多项式高矩阵左伪逆求解
-
文献[10-12]提出了有限域上有关衍生的Hill加密以及分组加密的思想,其中包括利用有限域上圆锥曲线密码体制等结合Hill分组加密来保证数据的安全,本文对一般的Hill加密算法做了如下衍生.
-
假设由字符编码集中的字符构成明文字符串M=M1M2…Mm,现需要对明文进行加密发送,首先选取有限域上合适的列满秩的加密矩阵
(其中k>l)和一个8次不可约多项式p(x),若明文字符串的长度m不满足l|m,则根据文献[13]处理哑元的方法,添加i个空格字符作为哑元构成新的明文字符串M=M1M2…Mk…Mm…Mm+i,使l|(m+i),其中i<l,加密时对字符串M按l个字符为一组进行分组,然后对每一组进行Hill加密,对加密后的字符串不做更改.
不妨取分组中的第一组字符进行加密,取M的前l个字符M1M2…Ml,对其中的每个字符Mj(1≤j≤l)在字符编码表 1中查询其对应位置的索引值Indexj,并将索引值Indexj转换成对应的二进制的表达式,也即有
把式中的2替换为x得到多项式
最后可以得到一个明文字符串M1M2…Ml所对应的一个多项式向量
在有限域上左乘加密矩阵G(x),并选取密钥矩阵的第l列(也可以随机选取密钥矩阵的其他列)作为平移增量,利用加密矩阵进行Hill加密后的密文向量e(x),其中
向量的分量满足
用矩阵的形式来表示即
其中a. l(x)表示抽取矩阵G(x)中的第l列.将密文多项式向量中每个多项式中的x用2替换,并求多项式的值,也即得到加密后密文字符在字符编码表中所对应的索引值,通过查表转换即可得到密文字符串C1C2…Cl…Ck.
-
先根据上节的方法求加密矩阵G(x)在有限域GF(2)[x]/(p(x))的左伪逆矩阵,并记左伪逆矩阵为GL(x),作为解密矩阵.
其中,由于加密时已经对相应的哑元进行了替换处理,因此加密后的密文字符串的长度必然为k(m+i)/l,且有l|(m+i),因此可以直接对密文字符串C=C1C2…Ck…Cm…Ck(m+i)/l以k个字符为一组进行分组,再对每一组进行解密运算.
现在对分组中的其中一组密文字符讨论解密算法,不妨取C的第1组的k个字符C1C2…Ck,对其中的每个字符Cj(1≤j≤k)在字符编码表中查询其对应位置的索引值Indexj,并将索引值Indexj转换成对应的二进制的表达式,也即有
把式中的2替换为x得到多项式
最后可以得到一个密文字符串C1C2…Ck所对应的一个多项式向量
在有限域上先减去平移增量(即密钥矩阵的第l列),再用得到的结果右乘解密矩阵GL(x),然后可以得明文向量d(x),其中
向量的分量满足
用矩阵形式来表示即d(x)=(GL(x)*(g(x)-a. l(x)))modp(x),其中a. l(x)表示抽取矩阵G(x)中的第l列.将明文多项式向量中每个多项式中的x用2替换,并求多项式的值,即得到解密后明文字符在字符编码表中所对应的索引值,通过查表转换即可得到明文字符串M1M2…Ml.
3.1. 有限域GF(2)[x]/(p(x))上的Hill加密衍生算法
3.2. 有限域GF(2)[x]/(p(x))上的Hill加密衍生算法的解密
-
GF(2)[x]中的8次不可约多项式是指系数只能为0,1的8次不可约的一元多项式,即8次不可约多项式p(x)=x8+a7x7+…+a1x+a0(其中a7,…,a1,a0∈{0,1}),满足不能分解成GF(2)[x]上7次及以下的多项式的乘积.为了求解GF(2)[x]上的8次不可约多项式的集合A,可以先通过遍历相乘的方法求出多项式环GF(2)[x]上的8次可约多项式的集合B:通过分析,GF(2)[x]上的8次可约多项式的集合可以表示为B=B1∪B2∪B3∪B4,其中B1为任意1次和任意7次多项式乘积的集合,B2为任意2次和任意6次多项式乘积的集合,B3为任意3次和任意5次多项式乘积的集合,B4为任意两个4次多项式乘积的集合.然后利用GF(2)上的8次多项式的全集S对B作差集运算,即可得相应的8次不可约多项式的集合A=S-B.
通过Python程序实现以上思想,即可求得多项式环GF(2)[x]上的所有8次不可约多项式,其降幂排列时对应的系数向量如表 2所示.
-
本文提出了一种新的有限域GF(2)[x]/(p(x))上的Hill加密衍生算法,其中p(x)是多项式环GF(2)[x]上随机选取的一个8次不可约多项式,密钥矩阵为有限域GF(2)[x]/(p(x))上随机选取的多项式高矩阵,并将随机选取密钥矩阵的其中一列作为加解密时的平移增量,在不知道p(x)、密钥矩阵以及随机抽取的平移向量的情况下求多项式高矩阵左伪逆比单纯的数字矩阵求左伪逆更困难,因此很难求得相应解密矩阵,密文破解得到明文的难度更大,从而提高了有限域GF(2)[x]/(p(x))上Hill加密的抗攻击能力.本文采用的是3×2的高矩阵作为加密的密钥矩阵,在实际应用中可以采用更高阶的密钥矩阵,当密钥矩阵是k×l的规模时,其对应的k×l的多项式矩阵多达256k×l种(k>l),从而可选的密钥矩阵的数目也越多,并且加密后密文的长度和明文的长度并不一致,从而使得暴力破解密钥矩阵更难,因此其上的Hill加密具有更高的安全性,适合大量数据的分组加密.