Digital Signature Scheme Based On The Ergodic Matrix Over Finite Field

With the advance of the Internet, many traditional off-line services such as voting, cash, and auction, are moving to online services over the Internet. To provide such online services safely, cryptography and information security technologies should be used. Digital signature which acts as one of the absolutely necessarily technology of information security become an important problem of modern cryptography.Digital signature is the digitalization form of the concept of handwritten signature, and also is an important method of certificating information in modern telecommunication. On one hand, Digital Signature has the same functions with handwritten signature: receivers could recognize the signature of senders but could not forge, and the sender could not deny the information he had sent to the receiver. And on the other hand, Digital Signature is different from handwritten signature: first, hand signature is imitable, but Digital Signature is hard to forge. Second, everyone's string composed of 0 and 1; every piece of information is particular and could never change. Digital signature is approaches that we can sign a message storaged in electronic style. So the messages signed can be transferred in Internet. A digital signature scheme of a message is consist of two parts: signing algorithm and verifying algorithm, digital signature technology has many kinds of variants from practical requirements. On the one hand, the privacy of user's must keep secret in the system of e-cash. On the other hands, the identification of signers is secret for users in the multi-bank e-cash system. So from these requirements, blind signature, group signature, and group blind signature appear. For the large group, we must consider forward and revocable properties, for the scenario of transferring the signature power we call for proxy signature technology.The Digital Signature has become focus in the field of cryptograph since the concept of digital signature appeared. From then on, the researchers of cryptograph have designed several kinds of digital signature scheme to meet different circumstances, and these schemes have been used in some protocols (SET, IPsec) electronic cash systems are confronting with more and more secure threat. Digital signature technology in the identification and authentication, data integrity. Non-repudiation and so is the role of which can not be replaced by other technologies, in the military, e-commerce and e-government and other fields have a very wide range of applications. These areas are closely related to national security. So it requires signature schemes have higher secure qualities. And it is precisely the lack of such key areas still our country's independent encryption products. Also long-term foreign export restrictions for cryptographic products, even if we have no restrictions should be used with caution. Therefore, we urgently need their own passwords system, and its digital signature scheme based on the creation, to ensure that these vital areas of communications security.At present, a substitutable scheme is based on multivariate quadratic polynomial question over finite fields. This question has already been proved to be an NP-complete problem. But different hard problems correspond to different crypto technology. So the key of creating different crypto technological lies in how to select a specific hard problem. For this reason, this thesis provides a new way to construct a hard problem. The basic thought is as follows:Suppose there is a non-empty set M, K_L K_R, where K_L(?)M, K_r(?)M, if there is a binary operation·to make that:(1) (M,·) is a monoid, its identity unit is e(2) (K_L·) and (K_R,·) are Abelian groups, their identity units are also e(3) for a,b∈M, we usually have: (a·b)≠(b·a), i.e. operation·has no commutative law in Mthen we can construct a function f: K_L×M×K_Râ†'M (f(a,x,b)=a·x·b), then we have:(1) known that x∈M,a∈K_L,b∈K_R; it's easy to compute y =f(a,x,b)(2) if |K_l| and |K_r| are relatively big, known that x,y∈M, it's probably hard tofind a∈K_L,b∈K_R and make y=f(a,x,b)(3) for any x∈M, a₁,a₂∈K_L, b₁,b₂∈K_R; we always have: f(a₂, f(a₁,x,b₁),b₂)=(4) known that a∈K_L and b∈K_R, it's easy to deduce a^-1∈K_L and b^-1∈K_R, and for any x∈M, we always have:If property (2) is true, then by (1) and (2) we know that the function f has one-way property. (2) And (3) indicate that f can implement techniques like Diffie-Hellman key exchange. (2), (3) and (4) indicate that f can implement Shamir's three-pass protocol. Moreover, by (3) and (4), we can use (a, b) as a "trapdoor" of the one-way function f, thereby we can implement normal public-key cryptography. Obvious that if we can construct a hard problem satisfies conditions above, then we can get the corresponding one-way function and thus the cryptography techniques based on that can be developed.Therefore, let M_n×n^F_q be a set of n×n matrix over finite field F_q, then (M_n×n^F_q,+,×) is a 1-ring, here + and×are addition and multiplication over F_q, respectively. We arbitrarily select two nonsingular matrices Q₁ and Q₂(here Q₁, Q₂∈M_n×n^F_q) and let the generation sets, which are generated under the multiplication of Q₁ and Q₂ over F_q, be 1> and 2>, then we have:(1) (M_n×n^F_q,×) is a monoid, its identity unit is I_n×n(2) (1>,×) and (2>,×) are Abelian group, their identity units are also I_n×n(3) for Q₁ and Q₂(hert Q₁,Q₂∈M_n×n^F_q) generally we have: Q₁×Q₂≠Q₂×Q₁. i.e. the multiplication operation has no commutative law in M_n×n^F_q.Let M=M_n×n^F_q, K_L=1>, K_r = 2>, we know that they nicely satify the conditions that needed. By experiment result, we also know that the ergodic matrices in M_n×n^F_q have a biggest generation set(whose order is qⁿ-1) under multiplication over F_q. Meanwhile, the result of multiplying any nonzero n-column vector over F_q on the left with an ergodic matrix of all power nicely takes over all nonzero n-column vectors over F_q; And the result is the same to row vectors over F_q. Moreover, the ergodic matrices in M_n×n^F_q have many important properties, therefore, we naturally think of choosing Q₁ and Q₂ as ergodic matrices in M_n×n^F_q and put forward the following question:Question 1. Let Q (here Q∈M_n×n^F_q) be Ergodic Matrix, and x be the Integer which between 0 and qⁿ-1, we know that Q and Q^x∈M_nxn^F_q, it is hard to looking for x which make them equivalent.Question 2. Let Q₁, Q₂(here Q₁, Q₂∈M_n×n^F_q) and M(here M∈M_nxn^F_q\{O}) be Ergodic Matrices, and x and y be the Integers between 0 and qⁿ-1, we know that Q₁, Q₂, M and Q₁^xMQ₂^y, looking for Q₁^x∈1> and Q₂^y∈2> that makes it hard to equal to Q₁^xMQ₂^y.Question 3. Let Q(here Q∈M_n×n^F_q) and M(here M∈M_n×n^F_q\{O}) be Ergodic Matrices, and x and y be the Integers between 0 and qⁿ-1, we know that Q, M and Q^xMQ^y, looking for Q^x and Q^y∈ that makes it hard to equal to Q^xMQ^y.Question 4. Let Q₁,Q₂(here Q₁,Q₂∈M_n×n^F_q) and M(here M∈M_n×n^F_q\{O}) be Ergodic Matrices, and x and y be the Integers between 0 and qⁿ-1, we know that Q₁, Q₂, M and Q₁^xMQ₂^y, looking for x and y that makes it hard to equal to Q₁^xMQ₂^y.Question 5. Let Q(here Q∈M_n×n^F_q) and M(here M∈M_n×n^F_q\{O}) be Ergodic Matrices, and x and y be the Integers between 0 and qⁿ-l, we know that Q, M and Q^xMQ^y, looking for x and y that makes it hard to equal to Q^xMQ^y.Through analysis we find that the Difficult of Question 1 is equal to DLP, for any given Ergodic Matrices Q₁ and Q₂, if Q₁,Q₂∈M_n×n^F_q, then the Difficult of Question 2 is specially relative to the selection of A(here A∈M_nxn^F_q). For most As in M_nxn^F_q, Question 2 is easy, but there also many As to make Question 2 hard; and the Question 3,4,5 is mixed up with the Question 1 and 2. We call such A "strong matrix for Q₁ andQ₂".Thereafter we discuss how to look for such a strong matrix and how to structure digital signature scheme under these difficult issues. Finally, introduced a Digital Signature scheme based on the Question 1 and 2.1. Parameters chosen:Let Q₁,Q₂(here Q₁,Q₂∈M_n×n^F_q) Ergodic Matrices, and M(here M∈M_n×n^F_q\{O}) be Strong Matrix, and k1 and k2 be the Integers between 0 and qⁿ-1, calculate K = Q₁^k₁MQ₂^k₂ as the public key of the text m, kl,k2 as the secret key. H( ),h( ) are the safety Hash function, use the MD5 as the h(), and H( ) is a hash function based on the Ergodic Matrix.2. Signature Generation:The man Alice who signature the text m uses the chosen parameters:(1) Alice calculates the e = h(m);(2) Alice chooses t1 and t2 be the Integers between 0 and qⁿ-1, andcalculates the T = Q₁^t₁MQ₂^t₂;(3) Alice calculates the r = H(T);(4) Alice calculates S₂^-1 = (t₂e-t₁k₂r+t₂k₁r)/(e(e+k₁r+k₂r)) , S₂ and S₂^-1 are themultiplication converses. If S₂ is not existent then go to (2). (5) Alice calculates S₁^-1 = (t₁k₂-t₂k₁)/(ek₂)+k₁/_k2S₂^-1 , S₁ and S₁^-1 are themultiplication converses. If S₁ is not existent then go to (2). Then sign(m) = (r, S₁, S₂) is the digital signature of the text m.3. Signature Certification:The man Bob who want to certificate the (r, S₁, S₂) is or not the digital signature of text m which is signed by Alice.(1) Bob calculates the g(K, S₁^-1r ) = Q₁^S₁-1k₁rMQ₂^S₁-1k₂r;(2) Bob calculates the g(K, S₂^-1r ) = Q₁^S₂-1k₁rMQ₂^S₂-1k₂r;(3) Bob calculates the e = h(m);(4) Bob calculates the Q₁^S₁-1e ,Q₂^S₂-1e;(5) Bob calculates f(g(K,S₁^-1,g(K,S₂^-1r)=Q₁^{S₁-1k₁r+S₂-1k₁r}MQ₂^{S₁-1k₂r+S₂-1k₂r};(6) Bob calculates T' = Q₁^S₁-1eQ₁^{S₁-1k₁r+S₂-1k₁r}MQ₂^{S₁-1k₂r+S₂-1k₂r}Q₂^S₂-1e;(7) Bob calculates the H(T'), if that is equal to r then accept the signature, else refuse it.In the Chapter 4, using the program to achieve the scheme and give the demo of it.From what we have discussed above, Ergodic Matrix has favorable encipher properties, and the Digital Signature scheme based on the Ergodic Matrix over the finite fields is Feasible in security, Effectiveness and complexity. So further research of it will advance the development of information security and have important realistic meanings.