基于矩阵的困难问题及其密码学应用
摘要
现有的基于数学理论的密码系统具体实现所采用的困难问题大多为非多项式时间可解。但如果量子计算机实际可行的话,则这类困难问题为不安全的。
本文简单介绍了密码学研究的现状,并对密码学的基础知识和数论的基本理论作了概要性阐述。由于有限域上的遍历矩阵在乘法下周期最大,基于遍历矩阵的密码学特性可构造出密码学所需的困难问题。所以详细研究了遍历矩阵和关于遍历矩阵的强壮矩阵的概念及特性。提出了基于矩阵的密码学困难问题,对困难问题的困难度进行了分析。
文章根据遍历矩阵的特性,提出了一些基于矩阵的困难问题。并引入有限域上的“BMQ-问题”,即有限域上的“二等分多变量二次方程组的求解问题(Bisectional Multivariate Quadratic equations Problem)对所提出问题的困难度从理论上进行了研究。
本文还探讨了强壮矩阵的特性,依据定理,得出了寻找强壮矩阵的算法。
最后,文章提出了困难问题在构造单向函数,密钥交换,Shamir三次传递协议等应用的方案。
The thesis proposes several hard problems in cryptography based on matrix,analyzing the degree of these hard problems and also the method of how touse them in application. Besides, the concept and properties of strong matrixare discussed. Before this, there is a brief introd uction about current research,basic knowledge of cryptography as well as fundamental of number theory.As ergodic matrix in finite field has the longest period under multiplication,this property can be used for constructing hard problem sincryp tography.
Most hard problems on mathem atical theory used in current cryptosystem arenondeterministic polynomial-time.But they are unsecure if quantum computerscome into practical. We prepair to find hard problems from n*n matrix ring(Mnxn~(Fq) ,+,·) in finite field F_q . Here are several properties of ergodicmatrix as following:1)m∈M_(n×n)~(F_q) is ergodic matrix if and only if the period of m undermatrixmultiplicationin F_q equals ( q~n-1)2) F_q [m]can comes into a finite field with q nelement in matrixaddition and multiplication if m∈M_(n×n)~(F_q) is ergodic matrix.3) All the equivalent ergodic matrix have the same generating sets.4) [m~0=I ,m,…, m~(n-1)]becomes the base of q~n elements finite fieldF_q [m]about q elements finite field F_q if m∈M_(n×n)~(F_q) is ergodicmatrix.
According to the above properties,the following problems are proposed:
Problem 1: Let Q∈M_(n×n)~(Fq) be a ergodic matrix,and x be a positive integersmaller than q~n-1.GivenQ、Q~x,to calculate integerx.
Problem 2:Given ergodic matrix Q_1,Q_2∈M_(n×n)~(Fq),A,B∈M_(n×n)~(Fq),x,y are positive integer smaller than q~n-1, find Q_1~x∈,Q_2~y in order tomakeB=Q_1~xAQ_2~y hard.
Problem 3:Let Q∈M_(n×n)~(Fq) be a ergodic matrix, m∈M_(n×n)~(F_q){0},x,y∈{1,2,…, q~n-1}. Given (Q,M,Q~xMQ~y);to calculatematrix Q~x and Q~y。
Problem 4:Let Q_1, Q_2∈M_(n×n)~(F_q) be a ergodic matrix,and m∈M_(n×n)~(F_q)\{0},x, y∈{ 1,2,…, q~n-1}. Given (Q_1 ,Q_2,M,Q_1~xMQ_2~y);to calculateinteger x and y.
Problem 5:Let Q∈M_(n×n)~(Fq) be a ergodic matrix,and m∈M_(n×n)~(F_q)\{0},x, y∈{1,2,…, q~n-1}. Given (Q, M,Q~xMQ~y); to calculateinteger x and y.
Forproblem 1,it’s not difficult to prove the hardness equals to the problem ofdiscrete logarithm in finite field F_q .It’s the discrete logarithm problem ofmatrix multiplicative (semi)group in F_q . So new cryptosystem with morestrength than the current RSA and ElGmal system can be constructed basedon problem 1 as any discrete logarithm problem of matrix multiplicative(semi)group in ring field is harder than the corresponding problem ofmultiplicative (semi) group.
Bisectional Multivariate Quadratic equations Problem—the so calledBMQ-problem is introduced to analyze the degree of problem 2 and 3.
BMQ-problem in finite field is a special case of Multivariate Quadraticproblem.The differences arethe variablein BMQ aredivided intotwo groupwith same number of elements and there is only one quadratic item in eachequation, every quadratic item is composed by the product of two variables—each from one side of both variable groups. So there are n~2different quadratic items from 2 nvariables and MQ problem in finite fieldis proved to be NP-hard problem.We can come to conclusion that BMQproblem is also NP-hard by analyzing NP-complete 3-coloring problem.
Relinearization method can be used to solve BMQ problem as BMQ problemis a special case of MQ problem in finite field. The thesis covers how to userelinearization method to solve BMQ aswell.
Though BMQ problem in finite field is NP-complete in theory, it doesn’tmean that any BMQ problem is NP-complete.The degree of hard solving thisproblem relates with the number of both variables and equations, also withthe chosen of F_q .The value of q effects the representation and storage ofvariable.
As to the problem 4 and 5, problem 4 is hard if and onlyif problem 1 is hardor problem 2 is hard; problem 5 is hard if and only if problem 1 is hard orproblem 3 is hard. So they are at least NP-complete. So the mesure ofhardness analyzing them is done in theory.
If there is matrix Ain problem 2, it’s called strong matrix about Q1 and Q2.The key to construct one-way function is to find the strong matrix about thegiven ergodic matrix Q_1 and Q_2.
In the end, how these hard problems could be used in constructing one wayfunction,key exchanging and Shamir protocol are proposed.
本文简单介绍了密码学研究的现状,并对密码学的基础知识和数论的基本理论作了概要性阐述。由于有限域上的遍历矩阵在乘法下周期最大,基于遍历矩阵的密码学特性可构造出密码学所需的困难问题。所以详细研究了遍历矩阵和关于遍历矩阵的强壮矩阵的概念及特性。提出了基于矩阵的密码学困难问题,对困难问题的困难度进行了分析。
文章根据遍历矩阵的特性,提出了一些基于矩阵的困难问题。并引入有限域上的“BMQ-问题”,即有限域上的“二等分多变量二次方程组的求解问题(Bisectional Multivariate Quadratic equations Problem)对所提出问题的困难度从理论上进行了研究。
本文还探讨了强壮矩阵的特性,依据定理,得出了寻找强壮矩阵的算法。
最后,文章提出了困难问题在构造单向函数,密钥交换,Shamir三次传递协议等应用的方案。
The thesis proposes several hard problems in cryptography based on matrix,analyzing the degree of these hard problems and also the method of how touse them in application. Besides, the concept and properties of strong matrixare discussed. Before this, there is a brief introd uction about current research,basic knowledge of cryptography as well as fundamental of number theory.As ergodic matrix in finite field has the longest period under multiplication,this property can be used for constructing hard problem sincryp tography.
Most hard problems on mathem atical theory used in current cryptosystem arenondeterministic polynomial-time.But they are unsecure if quantum computerscome into practical. We prepair to find hard problems from n*n matrix ring(Mnxn~(Fq) ,+,·) in finite field F_q . Here are several properties of ergodicmatrix as following:1)m∈M_(n×n)~(F_q) is ergodic matrix if and only if the period of m undermatrixmultiplicationin F_q equals ( q~n-1)2) F_q [m]can comes into a finite field with q nelement in matrixaddition and multiplication if m∈M_(n×n)~(F_q) is ergodic matrix.3) All the equivalent ergodic matrix have the same generating sets.4) [m~0=I ,m,…, m~(n-1)]becomes the base of q~n elements finite fieldF_q [m]about q elements finite field F_q if m∈M_(n×n)~(F_q) is ergodicmatrix.
According to the above properties,the following problems are proposed:
Problem 1: Let Q∈M_(n×n)~(Fq) be a ergodic matrix,and x be a positive integersmaller than q~n-1.GivenQ、Q~x,to calculate integerx.
Problem 2:Given ergodic matrix Q_1,Q_2∈M_(n×n)~(Fq),A,B∈M_(n×n)~(Fq),x,y are positive integer smaller than q~n-1, find Q_1~x∈
Problem 3:Let Q∈M_(n×n)~(Fq) be a ergodic matrix, m∈M_(n×n)~(F_q){0},x,y∈{1,2,…, q~n-1}. Given (Q,M,Q~xMQ~y);to calculatematrix Q~x and Q~y。
Problem 4:Let Q_1, Q_2∈M_(n×n)~(F_q) be a ergodic matrix,and m∈M_(n×n)~(F_q)\{0},x, y∈{ 1,2,…, q~n-1}. Given (Q_1 ,Q_2,M,Q_1~xMQ_2~y);to calculateinteger x and y.
Problem 5:Let Q∈M_(n×n)~(Fq) be a ergodic matrix,and m∈M_(n×n)~(F_q)\{0},x, y∈{1,2,…, q~n-1}. Given (Q, M,Q~xMQ~y); to calculateinteger x and y.
Forproblem 1,it’s not difficult to prove the hardness equals to the problem ofdiscrete logarithm in finite field F_q .It’s the discrete logarithm problem ofmatrix multiplicative (semi)group in F_q . So new cryptosystem with morestrength than the current RSA and ElGmal system can be constructed basedon problem 1 as any discrete logarithm problem of matrix multiplicative(semi)group in ring field is harder than the corresponding problem ofmultiplicative (semi) group.
Bisectional Multivariate Quadratic equations Problem—the so calledBMQ-problem is introduced to analyze the degree of problem 2 and 3.
BMQ-problem in finite field is a special case of Multivariate Quadraticproblem.The differences arethe variablein BMQ aredivided intotwo groupwith same number of elements and there is only one quadratic item in eachequation, every quadratic item is composed by the product of two variables—each from one side of both variable groups. So there are n~2different quadratic items from 2 nvariables and MQ problem in finite fieldis proved to be NP-hard problem.We can come to conclusion that BMQproblem is also NP-hard by analyzing NP-complete 3-coloring problem.
Relinearization method can be used to solve BMQ problem as BMQ problemis a special case of MQ problem in finite field. The thesis covers how to userelinearization method to solve BMQ aswell.
Though BMQ problem in finite field is NP-complete in theory, it doesn’tmean that any BMQ problem is NP-complete.The degree of hard solving thisproblem relates with the number of both variables and equations, also withthe chosen of F_q .The value of q effects the representation and storage ofvariable.
As to the problem 4 and 5, problem 4 is hard if and onlyif problem 1 is hardor problem 2 is hard; problem 5 is hard if and only if problem 1 is hard orproblem 3 is hard. So they are at least NP-complete. So the mesure ofhardness analyzing them is done in theory.
If there is matrix Ain problem 2, it’s called strong matrix about Q1 and Q2.The key to construct one-way function is to find the strong matrix about thegiven ergodic matrix Q_1 and Q_2.
In the end, how these hard problems could be used in constructing one wayfunction,key exchanging and Shamir protocol are proposed.
引文
[1] 蔡吉人, 信息安全与密码学, 信息安全与通信保密, 2001 年第 3 期,15-17.
[2] 冯登国, 国内外信息安全研究现状及发展趋势, 通信学报,2002/23/5,18-26.
[3] 冯登国, 国内外密码学研究现状及发展趋势, 通信学报 2002 年 05期.
[4] 卿斯汉, Three KeyFactors in Network Security-Ciphers, Protocols andFirewalls, 计算机工程 1999年10月.
[5] 孙吉贵, 杨凤杰等, 离散数学, 高等教育出版社,2002.
[6] 冯登国, 裴定一, 密码学导引, 科学出版社,1999.
[7] 胡予濮, 张玉清, 对称密码学, 机械工业出版社,2002.
[8] 杨波, 现代密码学, 清华大学出版社,2003.
[9] Adi Shamir, Jacques Patarin, Nicolas Courtois, Alexander Klimov,“Efficient Algorithms for solving Overdefined Systems of MultivariatePolynomial Equations”, Eurocrypt’2000, LNCS 1807, Springer, pp.392-407.
[10] 冯登国, 卿斯汉, 信息安全一核心理论与实践, 国防工业出版社,2000.
[11] 赵永哲, 黄声烈等, GF(2k)上的遍历矩阵及其特性分析[J], 小型微型计算机系统, 2005.12(26),2135-2139.
[12] 赵永哲, 裴士辉, 王洪军等, 利用有限域上的遍历矩阵构造动态加密器, 小型微型计算机系统,2007 年 11 期.
[13] 陈克非, 门限RSA密码体制, 电子学报,1999年06期.
[14] 陶仁骥, 陈世华, 一种有限自动机公开钥密码体制和数字签名, 计算机学报,1985 年 06 期.
[15] Nicolas T, Courtois and Jacques Patarin, “About the XLalgorithm overGF(2)”,Cryptographers’TrackRSA,SpringerVerlag2003:13-17.
[16] 戴大为, 吴逵等, 有限自动机公钥密码体制的密码分析, 中国科学,1995年11期.
[17] 孙燮华, 计算机密码学的新进展, 中国计量学院学报,2001年01期.
[18] Bruce Schneier, Aplied Cryptography: protocols algorithms and sourcecodeinC,USA,JohnWiley&Sons,Inc.1996.
[19] 张焕国, 冯秀涛, 演化密码与DES密码的演化设计, 通信学报,2002年 05 期.
[20] Nicolas Courtois, “HigherOrderCorrelationAttacks, XLalgorithm andCryptanalysisofToyocrypt”,ICISC2002,LNCS2587,Springer.
[21] 陈克非, 冯登国, 吴文玲, 信息和通信安全—CCICS’2001,科学出版社,2001 年 05 月.
[22] WadeTrappeLawrenceC, 密码学概论, 人民邮电出版社,2004.
[23] 裴定一, 王学理, 基于有限域圆锥曲线的加密认证码, 中国科学(E辑), 第 26 卷,1996.10,385-394.
[24] 吴昌银, 岳青松, 等, AES安全性及其影响研究, 信息安全与通信保密,2006No.ll.
[25] Randall K. Nichols著, 吴世忠译, ICSA密码学指南, 机械工业出版社,2004.
[26] Aviad Kipnis, Adi Shamir, Cryptanalysis of the HFE Public KeyCryptosystem,LetureNotesinComputerScience,1999,1666:19-30.
[27] G.Maze,C.Monico, Public key cryptography based on simple modulesover simple rings Mathematical Theory of Networks and Systems,August2002.
[2] 冯登国, 国内外信息安全研究现状及发展趋势, 通信学报,2002/23/5,18-26.
[3] 冯登国, 国内外密码学研究现状及发展趋势, 通信学报 2002 年 05期.
[4] 卿斯汉, Three KeyFactors in Network Security-Ciphers, Protocols andFirewalls, 计算机工程 1999年10月.
[5] 孙吉贵, 杨凤杰等, 离散数学, 高等教育出版社,2002.
[6] 冯登国, 裴定一, 密码学导引, 科学出版社,1999.
[7] 胡予濮, 张玉清, 对称密码学, 机械工业出版社,2002.
[8] 杨波, 现代密码学, 清华大学出版社,2003.
[9] Adi Shamir, Jacques Patarin, Nicolas Courtois, Alexander Klimov,“Efficient Algorithms for solving Overdefined Systems of MultivariatePolynomial Equations”, Eurocrypt’2000, LNCS 1807, Springer, pp.392-407.
[10] 冯登国, 卿斯汉, 信息安全一核心理论与实践, 国防工业出版社,2000.
[11] 赵永哲, 黄声烈等, GF(2k)上的遍历矩阵及其特性分析[J], 小型微型计算机系统, 2005.12(26),2135-2139.
[12] 赵永哲, 裴士辉, 王洪军等, 利用有限域上的遍历矩阵构造动态加密器, 小型微型计算机系统,2007 年 11 期.
[13] 陈克非, 门限RSA密码体制, 电子学报,1999年06期.
[14] 陶仁骥, 陈世华, 一种有限自动机公开钥密码体制和数字签名, 计算机学报,1985 年 06 期.
[15] Nicolas T, Courtois and Jacques Patarin, “About the XLalgorithm overGF(2)”,Cryptographers’TrackRSA,SpringerVerlag2003:13-17.
[16] 戴大为, 吴逵等, 有限自动机公钥密码体制的密码分析, 中国科学,1995年11期.
[17] 孙燮华, 计算机密码学的新进展, 中国计量学院学报,2001年01期.
[18] Bruce Schneier, Aplied Cryptography: protocols algorithms and sourcecodeinC,USA,JohnWiley&Sons,Inc.1996.
[19] 张焕国, 冯秀涛, 演化密码与DES密码的演化设计, 通信学报,2002年 05 期.
[20] Nicolas Courtois, “HigherOrderCorrelationAttacks, XLalgorithm andCryptanalysisofToyocrypt”,ICISC2002,LNCS2587,Springer.
[21] 陈克非, 冯登国, 吴文玲, 信息和通信安全—CCICS’2001,科学出版社,2001 年 05 月.
[22] WadeTrappeLawrenceC, 密码学概论, 人民邮电出版社,2004.
[23] 裴定一, 王学理, 基于有限域圆锥曲线的加密认证码, 中国科学(E辑), 第 26 卷,1996.10,385-394.
[24] 吴昌银, 岳青松, 等, AES安全性及其影响研究, 信息安全与通信保密,2006No.ll.
[25] Randall K. Nichols著, 吴世忠译, ICSA密码学指南, 机械工业出版社,2004.
[26] Aviad Kipnis, Adi Shamir, Cryptanalysis of the HFE Public KeyCryptosystem,LetureNotesinComputerScience,1999,1666:19-30.
[27] G.Maze,C.Monico, Public key cryptography based on simple modulesover simple rings Mathematical Theory of Networks and Systems,August2002.