素域F2上的遍历矩阵及其在密码学中的应用

周晓谊^[1]2005年在《遍历矩阵及其在密码学中的应用》文中提出密码技术创新的关键便在于如何选取特定的困难问题。为此,本文构造基于遍历矩阵的单向函数,然后提出了基于遍历矩阵的困难问题,并且根据该问题对遍历矩阵进行扩展,引出遍历矩阵的强壮矩阵。本文重点叙述了基于有限域上的遍历矩阵和遍历矩阵的单向函数在密码学中的应用及其实现方法,并且分析各应用中可能出现的攻击以及针对攻击的解决方法。然后初步讨论了遍历矩阵在伪随机数的生成,对称密钥密码体系和混合加密体系及STS 协议和Shamir 叁次传输协议等方面的应用,并给出了具体的实现方法,最后简单的介绍了用于验证上述理论的测试程序。本论文的创新之处在于,将已有的遍历矩阵在密码学中的应用方法进行改进,如伪随机数的生成一节;以及将遍历矩阵的单向函数应用于各加密体系以及其它加密协议中。

毕建华^[2]2005年在《基于有限域上遍历矩阵的单向函数构造》文中提出本文以离散数学中群、环、域为理论基础,提出了基于有限域上遍历矩阵的概念,给出了遍历矩阵的性质定理以及寻找算法,并对遍历矩阵的密码学特性进行了分析。证实了遍历矩阵的密码学特性可以使它应用到很多密码学领域,例如:公钥密码、伪随机数、一次一密、动态加密器、零知识的身份认证等。为了增加问题的困难程度,提出了“强壮矩阵”的概念,并对于给定的两个遍历矩阵Q1和Q2,给出了关于Q1,Q2的强壮矩阵的判别标准和寻找算法;由?Q1?, ?Q2?以及关于Q1,Q2的强壮矩阵,可以构造相应的单向(陷门)函数B=x?A?y,该问题已被证明是一个NP 完全问题。它属于有限域中的多元二次多项式问题(Multivariate Quadratic Problem, MQP),虽然Shamir 和Courtois 等人分别提出了对MQP 的高级攻击方案[10][11][12][13][14][15],但它仍被认为是最具前景的。应用此单向函数模拟了Shamir叁次传递协议、Diffie_Hellman密钥约定算法。

吴德胜^[3]2004年在《素域F_2上的遍历矩阵及其在密码学中的应用》文中指出随着互联网和电子商务的迅猛发展,信息安全的重要性日渐突出。加密技术是互联网和电子商务采取的主要安全保密措施,是最常用的安全保密手段,利用技术手段把重要的数据变为乱码(加密)传送,到达目的地后再用相同或不同的手段还原(解密)。加密技术包括两个元素:算法和密钥。算法是将普通的文本(或者可以理解的信息)与一串数字(密钥)的结合,产生不可理解的密文的步骤,密钥是用来对数据进行编码和解码的一种特殊信息。在安全保密中,可通过适当的密钥加密技术和管理机制来保证网络的信息通讯安全。随着计算机硬件性能的不断提升,现有的密码体系将受到强大的冲击。因此,对加密算法的研究和改进,具有很重大的现实意义。本文提出了素域上阶遍历矩阵的概念。所谓素域上的阶遍历矩阵,是指一个阶满秩方阵,周期为。令,则的幂所构成的集合()=在的矩阵乘法下做成循环群,任取群集里面所有元素的特定一行(一列),所得的向量恰好遍历1到这个数。素域上的阶遍历矩阵简称遍历矩阵。遍历矩阵有很多适用于加密的特性,如遍历性,随机性等。本文从素数阶群构造入手,引入了素域上阶遍历矩阵的概念。素数阶群必是循环群且除单位元之外皆为生成元,故在基于离散对数的密码系统中有重要的应用。典型的素数阶群是在模加法下所构成的加法群(p是素数),但该素数阶群中的离散对数问题却很容易求解。所以实际应用中常选择=在模乘法下所构成的循环群,且应避免使仅有小的素数因子。当时(这里q也是素数),共有个生成元,生成元的比率趋于50%。而对于素数阶群,生成元所占比率则趋于100%。所以寻找具有理想离散对数特性的大素数阶群对密码学来说有很重要的意义。由伽罗瓦理论可知,任意有限域的阶必为 (这里是素数,是一个正整数),对于任意的素数和正整数,在同构的角度下存在唯一的阶有限域。又中的()个非零元在该有限域的乘法下做成循环群,所以如果()为素数,便可得到素数阶乘法群(-)。当时,()为素数只有当时才可。故对素数=(),如果能构造出,则便可得到素数阶群(-)。而的构造又可归结为如何找到素域上的一个次不可约多项式。由于对给定的素数和任意的正整数,目前还没有一个能行的方法来快速地找到素域上的一个次不可约多项式。所以构造上述素数阶群的关键便是如何有效地寻找上的次不可约多项式(这里为素数)。本文完成了如下工作:提出了一种用循环节寻找上次不可约多项式的算法,当<32时,该算法可以迅速找到次不可约多项式,算法的复杂度为。由于上面的算法在比较大时,不再可行,因而定义了上阶遍历矩阵的概念,提出利用遍历矩阵来改进次不可约多项式的求法。并给出了构造遍历矩阵的递推关系式,采用该关系式,算法的复杂度为,现实中可以求解的不可约多项式。此关系式可以用一个维向量来产生一个的遍历矩阵。这样,就可以使用一个比特的整数向量来代表一个比特的遍历矩阵(即遍历矩阵的生成与次不可约多项式的构成是等同的),同时节省了空间复杂度和时间复杂度。给出了遍历矩阵的若干性质定理,如遍历矩阵的幂加法封闭性、遍历矩阵的判定定理、遍历矩阵的生成数目定理等,并给出了定理的详细证明。对遍历矩阵在信息安全中的应用进行了初步的探讨。分别对遍历矩阵在伪随机序列生成、公钥加密体系、对称密钥加密体系和Shamir叁次传递协议以及身份验证等方面的应用进行了研究,并给出实现方法和算法强度分析。用程序对上述应用和遍历矩阵的遍历性进行了实现和验证。从研究和试验结果可以看出,遍历矩阵的加密特性良好。利用遍历矩阵的随机性和遍历性,可以生成在密码学中具有重要意义的特征良好的伪随机序列;利用遍历矩阵的双向加密,可以实现理论上安全的对称密钥体系;利用遍历矩阵的周期性,可以实现利用随机密钥进行加密的公钥加密体系,其算法难破解性的依据是离散对数问题的难解性,强度等价于RSA算法与椭圆曲线加密算法;遍历矩阵遵从有限域上的矩阵乘法规则,可以实现Shamir叁次传递协议;利用遍历矩阵求得的素数阶群,在信息安全中也有着重要的应用。综上所述,遍历矩阵是一种加密特性良好的加密矩阵,对遍历矩阵的进一步的研究和完善,将会促进信息安全的发展,因而具有重要的现实意义。

张威^[4]2004年在《素域F_2上的遍历矩阵及其在密码学中的应用》文中指出随着互联网和电子商务的迅猛发展，信息安全的重要性日渐突出。加密技术是互联网和电子商务采取的主要安全保密措施，是最常用的安全保密手段，利用技术手段把重要的数据变为乱码（加密）传送，到达目的地后再用相同或不同的手段还原（解密）。加密技术包括两个元素：算法和密钥。算法是将普通的文本（或者可以理解的信息）与一串数字（密钥）的结合，产生不可理解的密文的步骤，密钥是用来对数据进行编码和解码的一种特殊信息。在安全保密中，可通过适当的密钥加密技术和管理机制来保证网络的信息通讯安全。随着计算机硬件性能的不断提升，现有的密码体系将受到强大的冲击。因此，对加密算法的研究和改进，具有很重大的现实意义。本文提出了素域F_2上n阶遍历矩阵的概念。所谓素域F_2上的n阶遍历矩阵，是指一个n阶满秩方阵m，周期为2~n-1。令d=2~n-1,则m的幂所构成的集合(m)＝{m,m~1,m~2……,m~(d-1),m~d=E}在F_2的矩阵乘法下做成循环群，任取群集里面所有元素的特定一行(一列)，所得的向量恰好遍历1到2~n-1这2~n-1个数。素域F_2上的n阶遍历矩阵简称遍历矩阵。遍历矩阵有很多适用于加密的特性，如遍历性，随机性等。本文从素数阶群构造入手，引入了素域F_2上n阶遍历矩阵的概念。素数阶群必是循环群且除单位元之外皆为生成元，故在基于离散对数的密码系统中有重要的应用。典型的素数阶群是{1,2,3,……,p-1}在模p加法下所构成的加法群(p是素数)，但该素数阶群中的离散对数问题却很容易求解。所以实际应用中常选择Z~*_P={1,2,3,……,p-1}在模P乘法下所构成的循环群，且应避免使(P-1)仅有小的素数因子。当P=2q+1时(这里q也是素数)，Z~*_p共有(q-1)个生成元，生成元的比率趋于50%。而对于素数阶群，生成元所占比率则趋于100%。所以寻找具有理想离散对数特性的大素数阶群对密码学来说有很重要的意义。由伽罗瓦理论可知，任意有限域的阶必为p~n (这里p是素数，n是一个正整数)，对于任意的素数p和正整数n，在同构的角度下存在唯一的p~n阶有限域GF(P~n)。又GF(P~n)中的(p~n-1)个非零元在该有限域的乘法下做成循环群，所以如果(p~n-1)为素数，便可得到素数阶乘法群。当时，为素数只有当时才可。故对素数，如果能构造出，则便可得到素数阶群。而的构造又可归结为如何找到素域上的一个次不可约多项式。由于对给定的素数和任意的正整数，目前还没有一个能行的方法来快速地找到素域上的一个次不可约多项式。所以构造上述素数阶群的关键便是如何有效地寻找上的次不可约多项式(这里为素数)。本文完成了如下工作：1．提出了一种用循环节寻找上次不可约多项式的算法,当<32时，该算法可以迅速找到次不可约多项式，算法的复杂度为。2．由于上面的算法在比较大时，不再可行，因而定义了上阶遍历矩阵的概念，提出利用遍历矩阵来改进次不可约多项式的求法。并给出了构造遍历矩阵的递推关系式，采用该关系式，算法的复杂度为,现实中可以求解的不可约多项式。此关系式可以用一个维向量来产生一个的遍历矩阵。这样，就可以使用一个比特的整数向量来代表一个比特的遍历矩阵(即遍历矩阵的生成与次不可约多项式的构成是等同的)，同时节省了空间复杂度和时间复杂度。3．给出了遍历矩阵的若干性质定理，如遍历矩阵的幂加法封闭性、遍历矩阵的判定定理、遍历矩阵的生成数目定理等，并给出了定理的详细证明。4．对遍历矩阵在信息安全中的应用进行了初步的探讨。分别对遍历矩阵在伪随机序列生成、公钥加密体系、对称密钥加密体系和Shamir叁次传递协议以及身份验证等方面的应用进行了研究，并给出实现方法和算法强度分析。5．用程序对上述应用和遍历矩阵的遍历性进行了实现和验证。从研究和试验结果可以看出，遍历矩阵的加密特性良好。利用遍历矩阵的随机性和遍历性，可以生成在密码学中具有重要意义的特征良好的伪随机序列；利用遍历矩阵的双向加密，可以实现理论上安全的对称密钥体系；利用遍历矩阵的周期性，可以实现利用随机密钥进行加密的公钥加密体系，其算法难破解性的依据是离散对数问题的难解性，强度等价于RSA算法与椭圆曲线加密算法；遍历矩阵遵从有限域上的矩阵乘法规则，可以实现Shamir叁次传递协议；利用遍历矩阵求得的素数阶群，在信息安全中也有着重要的应用。综上所述，遍历矩阵是一种加密特性良好的加密矩阵，对遍历矩阵的进一步的研究和完善，将会促进信息安全的发展，因而具有重要的现实意义。

王丽鸥^[5]2004年在《有限域GF（2～k）上的遍历矩阵及其在密码学中的应用》文中研究表明网络安全依赖于两种技术。一是传统意义上的存取控制和授权，如存取控制表技术、口令验证技术等；二是利用密码技术实现对信息的加密、身份鉴别等。前者从理论和技术上是完全可以攻破的，而后者是有条件的。所以，网络安全的核心仍将建立在密码学理论与技术上。数据加密技术是最基本的网络安全技术，被誉为信息安全的核心。只有有限个元素的域称为有限域，或Galois域，它在方程式实验设计和编码理论等方面有很广泛的应用。有很多构造元素个数为素数方幂的有限域的方法，常见的是多项式基表示等方法。设F为有限域，g∈F~*，F~*是F的乘法群F~*=F-{0}。并且对于任意正整数x，计算g~*是容易的；但是已知g和y求x使得y=g~x，是计算上基本不可能的。这一问题称为有限域F上的离散对数问题，因为其在密码学中的应用特性，对于有限域的研究在计算机科学中显得非常重要。1. GF(2~k)上的遍历矩阵及其特性在同构的意义下，我们把GF(2~k)看成是所有K位二进制数在特定加、乘运算下所构成的有限域。令M_n是GF(2~k)上的所有n阶满秩方阵所构成的集合，C_n为GF(2~k)中所有非0的n维列矩阵所构成的集合。定义映射f_m:C_n→C_n，使对有f(x)=mx，则f为C的一个置换。因此可将F唯一地表为如下不相杂的轮换之乘积（包括长度为1的轮换）：f_m=(a_(11)a_(12)……a_(1n_1))（a_(21)a_(22)……a_(2n_2)）……(a_(t1)a_(t2)a_(t3)) (1)对分解式中任一轮换之长度必整除m在GF(2~k)矩阵乘法下的周期。当f_m分解式中只有一个长度为(2~(kn)-1)的轮换时，可知对恰好取遍C_n。故称M_n中具有这样性质的n阶方阵m为“遍历矩阵”。对为遍历矩阵当且仅当m在GF(2~K)矩阵乘法下的周期为(2~(kn)-1)。如果m∈M_n为遍历矩阵，则(m)={m.m~2……，m~(2~(kn)-1} 中恰有φ(2~(kn)-1)个遍历矩阵。GF(2~k)上的遍历矩阵m的性质充分显示，作成一个有限域GF(2~(kn))，GF(2~(kn))中的加法和乘法即是通常的矩阵加法和乘法，并且m是它的一个生成元。通过对GF(2~(kn))上n阶遍历矩阵的讨论，可知其对C_n中的向量有良好的发散性。由GF(2~(kn))上n阶遍历矩阵的特性可知，用其左乘GF(2~(n))上一个n阶方阵M相当于对M的每一列作了相应的变换；而用其右乘M，则对M的每一行作了相应的变换。所以用不同的遍历矩阵在两边同时乘上一个矩阵可充分地“弄乱”该矩阵的各元素。这一过程可重复多次以达到所需的复杂变换，这在密码学中的有很重要的应用价值。2. 构造GF(2~(n))上的遍历矩阵为了构造遍历矩阵，对,定义递推关系如下：上面定义中所用的加法和乘法均为GF(2~(k))中的加法和乘法。易知，由递推关系（1）所得诸的序列必以循环的形式出现，且循环节的长度由唯一地确定。那么由所确定的循环节长度正是使的最小整正数L，我们称其为关于递推关系(1)的循环节长度。将关于递推关系(1)的循环节首尾相连便能够得到由位二进制数构成的圆环。且在该圆环上任取连续的n位，紧接其后的下一个n位(b_n……b_2b_1)满足：上面GF(2~(k))中的n阶方阵Q由g_n……g_2g_1唯一地确定，称上述的n阶方阵Q为(g_n……g_2g_1)关于递推关系(1) 的“生成矩阵”。当n和(2~(kn)-1)互素时，对于g=(g_n……g_2g_1)∈GF（2~k）~n，(g_n……g_2g_1)的生成矩阵Q_g为遍历矩阵，当且仅当Q_g在GF(2~k)矩阵乘法下的周期是(2~(kn)-1)。F=GF(2~k)中n阶遍历矩阵的寻找（生成）算法：特别的，当F=GF(2)并且(2~(kn)-1)为素数（梅森素数）时，算法的第⑥步可以省略，并且最多只需做F上的n次n阶矩阵乘法运算便可完成一次判断。易知这样的Q_g恰为个。故在GF(2~k)较大时，可利用上述算法找到GF(2~k)中足够多的n阶遍历矩阵，每一个这样的 n×n 矩阵可用一个n维向量来表示。此外，该算法也可用来快速地寻找GF(~2k)中的一个n次不可约多项式。信息交换主要涉及到信息收发双方如何在非安全的通道上安全地传递信息。其常用的手段主要有：1 基于SKC(secret key cryptography)的信息交换2 基于PKC(public key cryptography)的信息交换3 基于其他技术的信息交换利用遍历矩阵的特性，我们可以实现多种密码学应用模式。例如可以用如下方法实现对称加密：设F=GF(2~k)，将要交换的信息 M 看成是F 中元素的序列，并按kn~2位来分块，每一块对应于F上的一个n阶方阵M_1,M_2,……。则A，B双方可按如下方式来进行通讯：A，B事先约定密钥Q_1,Q_2和s_0,t_0∈C_N.这里Q_1和Q_2为F上的m阶遍历矩阵；A 计算并将每个都看成一个位无符号整数。然后计算密文序列：最后将C_1,C_2……发送给B；B 计算然后计算并得到明文序列：M_1,M_2……A，B都用最后一次的s_j和t_j来更新s_0和t_0。利用GF(2~k)上的遍历矩阵，我们还可以实现基于离散对数的数据交换，Shamir叁次传递协议以及生成伪随机数，不对称加密等很多密码学应用模式。还可以根据本文推导和证明出的GF(2~k)上遍历矩阵的特性，得到更普遍的有限域GF(p~k)上的遍历矩阵，并可以进一步利用它的密码学特性。

刘鑫^[6]2009年在《基于矩阵的单向函数构造及其在密码学中的应用》文中研究表明目前的加密算法的安全度随着计算机技术(如云计算,量子计算机)的发展逐渐降低。本文正是基于此根据有限域上遍历矩阵的特点结合BMQ问题,提出了一个属于我国自己的公钥密钥加密算法。本文首先通过对有限域上遍历矩阵的研究,发现到很多可以应用到密码学中的特性和性质。其次,结合BMQ问题的提出了新的困难问题。然后,基于此困难问题构造了一个新的单向函数,以及应用此单向函数的公钥加密算法。最后,给出了此公钥加密算法的实现。本文所提出的新的加密算法,具有安全度高,密钥空间大,运算速度的优点。

参考文献：

[1]. 遍历矩阵及其在密码学中的应用[D]. 周晓谊. 吉林大学. 2005

[2]. 基于有限域上遍历矩阵的单向函数构造[D]. 毕建华. 吉林大学. 2005

[3]. 素域F_2上的遍历矩阵及其在密码学中的应用[D]. 吴德胜. 吉林大学. 2004

[4]. 素域F_2上的遍历矩阵及其在密码学中的应用[D]. 张威. 吉林大学. 2004

[5]. 有限域GF（2～k）上的遍历矩阵及其在密码学中的应用[D]. 王丽鸥. 吉林大学. 2004

[6]. 基于矩阵的单向函数构造及其在密码学中的应用[D]. 刘鑫. 吉林大学. 2009

标签：电信技术论文;  密码学论文;  矩阵论文;  矩阵乘法论文;  有限域论文;  离散对数论文;  矩阵管理论文;  素数定理论文;  信息安全论文;  密钥管理论文;  矩阵分解论文;  椭圆曲线密码学论文;  遍历论文;  矩阵加法论文;  对称密钥论文;  高级加密标准论文;  生成函数论文;  素数论文;