【作者】 相天时；

【导师】 赵永哲；

【作者基本信息】 吉林大学 ， 软件工程， 2008， 硕士

【摘要】 现有的基于数学理论的密码系统具体实现所采用的困难问题大多为非多项式时间可解。但如果量子计算机实际可行的话,则这类困难问题为不安全的。本文简单介绍了密码学研究的现状,并对密码学的基础知识和数论的基本理论作了概要性阐述。由于有限域上的遍历矩阵在乘法下周期最大,基于遍历矩阵的密码学特性可构造出密码学所需的困难问题。所以详细研究了遍历矩阵和关于遍历矩阵的强壮矩阵的概念及特性。提出了基于矩阵的密码学困难问题,对困难问题的困难度进行了分析。文章根据遍历矩阵的特性,提出了一些基于矩阵的困难问题。并引入有限域上的“BMQ-问题”,即有限域上的“二等分多变量二次方程组的求解问题(Bisectional Multivariate Quadratic equations Problem)对所提出问题的困难度从理论上进行了研究。本文还探讨了强壮矩阵的特性,依据定理,得出了寻找强壮矩阵的算法。最后,文章提出了困难问题在构造单向函数,密钥交换,Shamir三次传递协议等应用的方案。更多还原

【Abstract】 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ⁿ-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⁰=I ,m,…, m^n-1]becomes the base of qⁿ 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ⁿ-1.GivenQ、Q^x,to calculate integerx.Problem 2:Given ergodic matrix Q₁,Q₂∈M_n×n^Fq,A,B∈M_n×n^Fq,x,y are positive integer smaller than qⁿ-1, find Q₁^x∈<Q₁>,Q₂^y<Q₂> in order tomakeB=Q₁^xAQ₂^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ⁿ-1}. Given （Q,M,Q^xMQ^y）;to calculatematrix Q^x and Q^y。Problem 4:Let Q₁, Q₂∈M_n×n^F_q be a ergodic matrix,and m∈M_n×n^F_q\{0},x, y∈{ 1,2,…, qⁿ-1}. Given （Q₁ ,Q₂,M,Q₁^xMQ₂^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ⁿ-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²different 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₁ and Q₂.In the end, how these hard problems could be used in constructing one wayfunction,key exchanging and Shamir protocol are proposed.更多还原