高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

GF(28)上高矩阵为密钥矩阵的Hill加密衍生算法

,  , 

上一篇

下一篇

刘海峰, 卢开毅, 梁星亮. GF(28)上高矩阵为密钥矩阵的Hill加密衍生算法[J]. 西南大学学报（自然科学版）, 2018, 40(11): 41-47. doi: 10.13718/j.cnki.xdzk.2018.11.007
引用本文: 刘海峰, 卢开毅, 梁星亮. GF(28)上高矩阵为密钥矩阵的Hill加密衍生算法[J]. 西南大学学报（自然科学版）, 2018, 40(11): 41-47. doi: 10.13718/j.cnki.xdzk.2018.11.007
shu
Hai-feng LIU, Kai-yi LU, Xing-liang LIANG. Hill Encryption Derivative Algorithm in Finite Field GF(28) with High-Matrix as Key Matrix[J]. Journal of Southwest University Natural Science Edition, 2018, 40(11): 41-47. doi: 10.13718/j.cnki.xdzk.2018.11.007
Citation: Hai-feng LIU, Kai-yi LU, Xing-liang LIANG. Hill Encryption Derivative Algorithm in Finite Field GF(28) with High-Matrix as Key Matrix[J]. Journal of Southwest University Natural Science Edition, 2018, 40(11): 41-47. doi: 10.13718/j.cnki.xdzk.2018.11.007
shu

GF(28)上高矩阵为密钥矩阵的Hill加密衍生算法

  • 1.

    陕西科技大学 电气与信息工程学院, 西安 710021

  • 2.

    陕西科技大学 文理学院, 西安 710021

  • 基金项目: 陕西省自然科学基础研究计划青年项目（2017JQ1026）；陕西省教育厅专项科学研究计划项目（17JK0102）
详细信息
    作者简介:

    刘海峰(1964-), 男, 副教授, 硕士, 主要从事计算机网络与信息安全及代数编码与密码学的研究 .

  • 中图分类号: O151.21

Hill Encryption Derivative Algorithm in Finite Field GF(28) with High-Matrix as Key Matrix

  • 1.

    College of Electrical and Information Engineering, Shannxi University of Science and Technology, Xi'an 710021, China

  • 2.

    College of Arts and Sciences, Shannxi University of Science and Technology, Xi'an 710021, China

  • 摘要: 针对传统的Hill加密算法仅是利用有限域GF（p）上可逆的数字方阵作为密钥矩阵与明文向量做模P乘法进行加密运算，提出了一种新的在有限域GF（28）上以多项式高矩阵作为密钥矩阵的Hill加密衍生算法.在Hill加密衍生算法中，明文向量为明文字符对应的多项式构成的多项式向量，随机选取密钥矩阵的一列作为加密时的平移增量，在GF（28）上进行密钥矩阵与明文向量的模8次不可约多项式p（x）的乘法和加法，然后获得元素为多项式的密文向量，从而实现明文信息加密.由于在不知道有限域的8次不可约多项式、密钥矩阵以及随机抽取的平移向量的情况下由密文破解得到明文的难度更大，从而提高了有限域GF（28）上Hill加密衍生算法的抗攻击能力.
    Abstract: In traditional Hill encryption algorithm, the modulo P multiplication of the invertible matrix and plaintext vector in finite field GF(P) are used to calculate ciphertext vector. This paper proposes a new Hill encryption derivative algorithm in finite field GF(28), which takes polynomial high-matrix as the key matrix. In this new Hill encryption derivative algorithm, plaintext vector is composed of the polynomial derived from the corresponding plaintext, a column of key matrix is selected as translation increment randomly modulo eighth degree irreducible polynomial p(x) multiplication of the polynomial high-matrix and plaintext vector in finite field GF(28) is done. Then modulo eighth degree irreducible polynomial p(x) addition of the product and translation increment in finite field GF(28) is carried out, thus the polynomial ciphertext vector is obtained, and the purpose of encrypting the plaintext messages is achieved. Because it is more difficult to get plaintext from ciphertext under the condition that eighth degree irreducible polynomial, key matrix and random selected translation vector are unknown, the new Hill encryption derivative algorithm in finite field GF(28) improves the capability for anti-attack.
  • 加载中

  • 表 1  字符编码表

    space a b c d e f g h i j k l m n o p q
    r s t u v w x y z A B C D E F G H I
    J K L M N O P Q R S T U V W X Y Z 0
    1 2 3 4 5 6 7 8 9 ! @ # $ % ^ & * (
    ) - _ = + ~ ` [ ] \ ； ， . / { } ： "
    ’ ＜ ＞ ? α β γ δ ε ζ η θ ι κ λ μ ν ξ
    ο π ρ σ τ υ φ χ ψ ω Α Β Γ Δ Ε Ζ Η Θ
    Ι Κ ∧ Μ Ν Ξ Ο ∏ Ρ ∑ Τ Υ Φ Χ Ψ Ω ℃ ℉
    Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ Ⅷ Ⅸ Ⅹ Ⅺ Ⅻ ⅰ ⅱ ⅲ ⅳ ⅴ ⅵ
    ⅶ ⅷ ⅸ ⅹ А Б В Г Д Е Ё Ж З И Й К Л М
    Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю
    Я ★ ☆ ▲ △ ◆ ◇ ■ □ ⊙ ○ ▽ 『 』 〖 〗 《 》
    〔 〕 「 」 【 】 ￡ ￠ ￥ ← ↑ → ↓ ↖ ↗ ↘ ↙ ∈
    √ ∞ ∽ ≈ ∵ ∷ ※ ≌ ∫ ≦ ≧ ≮ ≯ ≡ ≠ × ÷ ±
    · ≤ ≥ §
    下载: 导出CSV

    表 2  多项式环GF(2)[x]上所有8次不可约多项式的系数向量

    [1，0，0，0，1，1，0，1，1]， [1，0，0，0，1，1，1，0，1]， [1，0，0，1，0，1，0，1，1]
    [1，0，0，1，0，1，1，0，1]， [1，0，0，1，1，1，0，0，1]， [1，0，0，1，1，1，1，1，1]
    [1，0，1，0，0，1，1，0，1]， [1，0，1，0，1，1，1，1，1]， [1，0，1，1，0，0，0，1，1]
    [1，0，1，1，0，0，1，0，1]， [1，0，1，1，0，1，0，0，1]， [1，0，1，1，1，0，0，0，1]
    [1，0，1，1，1，0，1，1，1]， [1，0，1，1，1，1，0，1，1]， [1，1，0，0，0，0，1，1，1]
    [1，1，0，0，0，1，0，1，1]， [1，1，0，0，0，1，1，0，1]， [1，1，0，0，1，1，1，1，1]
    [1，1，0，1，0，0，0，1，1]， [1，1，0，1，0，1，0，0，1]， [1，1，0，1，1，0，0，0，1]
    [1，1，0，1，1，1，1，0，1]， [1，1，1，0，0，0，0，1，1]， [1，1，1，0，0，1，1，1，1]
    [1，1，1，0，1，0，1，1，1]， [1，1，1，0，1，1，1，0，1]， [1，1，1，1，0，0，1，1，1]
    [1，1，1，1，1，0，0，1，1]， [1，1，1，1，1，0，1，0，1]， [1，1，1，1，1，1，0，0，1]
    下载: 导出CSV
  • [1] 万福永, 戴浩晖. Hill 2密码体系加密过程中的哑元问题[J].数学的实践与认识, 2007, 37(8):87-90. doi: 10.3969/j.issn.1000-0984.2007.08.016
    [2] 杨淑菊. Hill密码的加密解密矩阵的求法[J].价值工程, 2016, 35(26):285-287. doi: http://d.old.wanfangdata.com.cn/Periodical/jzgc201626113
    [3] 徐小华, 黎民英. Hill密码加密解密时矩阵的求法[J].电脑与信息技术, 2010(02):31-33. doi: 10.3969/j.issn.1005-1228.2010.02.011
    [4] 王容, 廖群英, 王云莹, 等. Hill加密算法的改进[J].四川师范大学学报(自然科学版), 2015, 38(1):8-14. doi: 10.3969/j.issn.1001-8395.2015.01.002
    [5] 付卫平, 陈继业.有限域GF(2~n)的一种除法运算算法[J].邵阳学院学报(自然科学版), 2015, 12(2):3-10. doi: 10.3969/j.issn.1672-7010.2015.02.001
    [6] 蒲保兴, 王伟平.线性网络编码运算代价的估算与分析[J].通信学报, 2011, 32(5):47-55. doi: 10.3969/j.issn.1000-436X.2011.05.007
    [7] 焦占亚, 曾永莹, 刘海峰.一次一密的密码算法研究[J].西安科技大学学报, 2005, 25(4):477-480. doi: 10.3969/j.issn.1672-9315.2005.04.017
    [8] 谢邦杰.线性代数[M].北京:人民教育出版社, 1978.
    [9] 王松桂, 杨振海.广义逆矩阵及其应用[M].北京:北京工业大学出版社, 1996.
    [10] 张玉安, 冯登国.一种实用的仿一次一密分组加密方案[J].北京邮电大学学报, 2005, 28(2):101-104. doi: 10.3969/j.issn.1007-5321.2005.02.025
    [11] 刘海峰, 吴鹏, 马令坤.基于有限域上圆锥曲线的分组加密算法及实现[J].吉林大学学报(理学版), 2012, 50(1):54-58. doi: http://d.old.wanfangdata.com.cn/Periodical/jldxzrkxxb201201010
    [12] 卢开澄.计算机密码学:计算机网络中的数据保密与安全[M]. 3版.北京:清华大学出版社, 2003.
    [13] 刘海峰, 何立勇, 郭改慧, 等. Hill密码体系中的加密矩阵与哑元[J].西南大学学报(自然科学版), 2014, 36(11):138-142. doi: http://xbgjxt.swu.edu.cn/jsuns/jsuns/ch/reader/view_abstract.aspx?file_no=2014-11-138&flag=1
  • 加载中
表( 2)
计量
  • 文章访问数:  908
  • HTML全文浏览数:  608
  • PDF下载数:  198
  • 施引文献:  0
出版历程
  • 收稿日期:  2017-12-13
  • 刊出日期:  2018-11-20

GF(28)上高矩阵为密钥矩阵的Hill加密衍生算法

    作者简介: 刘海峰(1964-), 男, 副教授, 硕士, 主要从事计算机网络与信息安全及代数编码与密码学的研究
  • 1. 陕西科技大学 电气与信息工程学院, 西安 710021
  • 2. 陕西科技大学 文理学院, 西安 710021
  • 收稿日期:  2017-12-13
基金项目:  陕西省自然科学基础研究计划青年项目（2017JQ1026）；陕西省教育厅专项科学研究计划项目（17JK0102）

摘要: 针对传统的Hill加密算法仅是利用有限域GF（p）上可逆的数字方阵作为密钥矩阵与明文向量做模P乘法进行加密运算，提出了一种新的在有限域GF（28）上以多项式高矩阵作为密钥矩阵的Hill加密衍生算法.在Hill加密衍生算法中，明文向量为明文字符对应的多项式构成的多项式向量，随机选取密钥矩阵的一列作为加密时的平移增量，在GF（28）上进行密钥矩阵与明文向量的模8次不可约多项式p（x）的乘法和加法，然后获得元素为多项式的密文向量，从而实现明文信息加密.由于在不知道有限域的8次不可约多项式、密钥矩阵以及随机抽取的平移向量的情况下由密文破解得到明文的难度更大，从而提高了有限域GF（28）上Hill加密衍生算法的抗攻击能力.

English Abstract

    全文HTML

  • 传统的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的顺序对表格中的字符按照行优先进行编码.

1.   有限域GF(2)[x]/(p(x))的定义

  • 定义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

2.   有限域GF(2)[x]/(p(x))上多项式和多项式矩阵的求逆

    2.1.   有限域GF(2)[x]/(p(x))的多项式求逆[7]

  • 对∀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).

    • 2.2.   有限域GF(2)[x]/(p(x))的n阶方阵求逆

  • 有限域上的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，最后可得逆矩阵

    • 2.3.   有限域GF(2)[x]/(p(x))的多项式高矩阵左伪逆求解

  • 高矩阵是指列线性无关的矩阵[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)).

3.   有限域GF(2)[x]/(p(x))上的Hill加密衍生算法及其解密算法

  • 文献[10-12]提出了有限域上有关衍生的Hill加密以及分组加密的思想，其中包括利用有限域上圆锥曲线密码体制等结合Hill分组加密来保证数据的安全，本文对一般的Hill加密算法做了如下衍生.

    • 3.1.   有限域GF(2)[x]/(p(x))上的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.

    • 3.2.   有限域GF(2)[x]/(p(x))上的Hill加密衍生算法的解密

  • 先根据上节的方法求加密矩阵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.

4.   多项式环GF(2)[x]中的8次不可约多项式

  • 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所示.

5.   结束语

  • 本文提出了一种新的有限域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加密具有更高的安全性，适合大量数据的分组加密.

参考文献 (13)

目录

版权所有：西南大学学报（自然科学版）

地址：重庆市北碚区西南大学 电话：023-68254576, 68252540, 68366165,68366917 电子邮箱：lkxb@swu.edu.cn

本系统由北京仁和汇智信息技术有限公司开发

/

返回文章
返回