CN101867474B - Digital signature method - Google Patents

Abstract

The invention relates to the technical field of information security, in particular to a digital signature method. The present invention is based on the difficulty of matrix decomposition and a new lightweight digital signature scheme constructed in combination with hash function authentication technology, which can be widely used in the fields of information security systems such as network security, e-commerce, bills and identity authentication. This scheme has the advantages of high efficiency, no need for a cryptographic algorithm coprocessor, high security, and anti-quantum computer attacks when performing signature authentication. It is especially suitable for information such as smart cards, wireless sensor networks, cellular phones, and radio frequency tags. security area.

Description

digital signature method

technical field

The invention relates to the technical field of information security, in particular to a digital signature method.

Background technique

The 21st century is the age of information. In addition to the continuous rapid development of electronic information science and technology, new information sciences such as quantum and biology are being established and developed. The research and development of quantum information science has given birth to the emergence of quantum computer, quantum communication and quantum cryptography. At present, breakthroughs have been made in the research and development of quantum computers. For example, in 2001, IBM Corporation took the lead in successfully developing an exemplary quantum computer with 7 qubits. In 1994, Shor proposed the famous Shor algorithm, which is a dedicated password search and deciphering algorithm. Its extended algorithm can attack all public key ciphers that can be converted into generalized discrete Fourier transform in polynomial time, including RSA, ElGamal and ECC. . This means that once quantum computers become practical, these widely used public key cryptography systems will no longer be secure.

With the development of integer decomposition technology (such as quadratic sieve method and number field sieve method), RSA-like systems must use gradually increasing parameters in order to ensure their security. The RSA system using a large modulus requires a large amount of calculation, which reduces the encryption and decryption efficiency of the system. Therefore, this system is not suitable for resource-limited computing devices such as cellular phones, smart cards, etc., let alone wireless sensor networks and radio frequency tags RFID. Secondly, in order to improve the security of services, the next-generation Internet IPv6 introduces a large number of encryption and authentication technologies. For users, the efficiency of traditional public key cryptography algorithms is low, and the CPU time consumed by encryption and decryption will slow down the corresponding service speed of users. .

Contents of the invention

For the above-mentioned technical problems, the purpose of this invention is to provide a lightweight new digital signature method, which is characterized by a new digital signature method based on the difficulty of matrix decomposition and combined with hash function authentication technology.

To achieve the above object, the present invention adopts the following technical solutions:

(I) System establishment: select a standard hash function H(·) and a finite field GF(q) with an output of at least 160 bits, where q=2 ^k and the integer k is less than the length of the output value of the hash function H(·);

Specify the values of the integer parameters n, δ and r according to user security requirements (0<δ, r<n);

Randomly select the n-dimensional affine bijective transformation T on GF(q);

Construct a reversible compression transformation L based on the hash function H( ): (z ₁ ,…,z _n )←(x ₁ ,…,x _n ,x _n+1 ,…,x _n+δ ),

Where A is an n-δ-dimensional reversible square matrix, coefficient γ _i ≠ 0 (1≤i≤2δ), and coefficient a _ij (1≤i≤δ, 1≤j≤n-1) and constant term α _i (1 ≤i≤n) is a random selection; x _n+i (1≤i≤δ) is an extended variable, which is the hash of the first (n-δ+i-1) components of the vector (x ₁ ,…, x _n ) Greek value, ie

x _n+i ＝H _k (x ₁ ||x ₂ ||…||x _n-δ+i-1 ), 1≤i≤δ

Among them, H _k ( ) means to take out the first k bits of the output value of H ( ) in turn, and "||" means to connect two bit strings;

Let T ^- denote the transformation formed by sequentially taking out nr rows of T,

以及γ_i(δ+1≤j≤2δ)组成。The public key of the system is the composite of the above two mappings ^T- and L, G=T ^- οL, and the public key G is a linear indeterminate equation system with n+δ input variables and nr outputs on the finite field GF(q); The key is composed of the inverse transformation of mapping T and L, D={T ^-1 , L ^-1 }; where, the inverse transformation L ^-1 consists of A ^-1 , B, α _i (1≤i≤n),

And γ _i (δ+1≤j≤2δ) composition.

(II) The signature process is as follows: Assume that user A signs the message vector (y ₁ ,...,y _nr ) of user B, then the signature process of user A is divided into the following two steps:

①Randomly select r variables y _n-r+i ∈GF(q) (1≤i≤r) and concatenate them with the message vector to form an n-dimensional vector (y ₁ ,...,y _n ) on GF(q) , and use the private key T ^-1 to calculate (z ₁ ..., z _n ) = T ^-1 (y ₁ ..., y _n );

②Calculate with the private key L ^-1 to get the corresponding signature (x ₁ ..., x _n+δ ) = L ^-1 (z ₁ , ..., z _n );

(Ⅲ) Signature verification process: After user B receives user A's signature on the message, it divides into the following two steps:

①Use the hash function to authenticate the signature (x ₁ ,...,x _n+δ ), that is, each component must satisfy:

x _n+i ＝H _k (x ₁ ||x ₂ ||…||x _n-δ+i-1 ), 1≤i≤δ

Otherwise refuse to sign;

② If step ① passes the authentication, continue to use the public key G of user A to verify, that is

If the left and right sides of the above equation are equal, the signature is accepted, otherwise the signature is rejected.

Standard hash functions such as MD5, SHA-1, SHA-2, and SHA-3 can be selected for the hash function H(·) respectively.

The present invention has the following advantages and positive effects:

1) The present invention is a highly secure digital signature scheme. Its security performance mainly depends on the hash function used. At present, the widely used hash functions are constructed by a large number of logical operations, which have high security and can resist the attack of quantum computers;

2) The present invention is an efficient and light-weight digital signature scheme. Its operations are mainly hash value operations and multiplication operations on finite fields. Currently, widely used hash functions are constructed using a large number of logical operations, so they have a relatively low If we choose a smaller field parameter such as GF(2 ⁸ ), the multiplication can use look-up table, which is more efficient. This scheme can be widely used in embedded devices with limited computing power;

3) The signature method of the present invention has great flexibility, and the hash function can be freely selected.

Detailed ways

The present invention will be further described below with specific embodiment:

The security of the digital signature scheme of the present invention is based on the difficulty of matrix decomposition, that is, it is computationally infeasible to successfully decompose the private key information T and L from the public key G=T ^- οL. In essence, L is a nonlinear reversible transformation based on a hash function, and the linear transformation T plays the role of hiding L. Therefore, through the combination of the two transformations, the security of the system is transformed into the security that depends on the hash function.

In order to fully understand the signature scheme of the present invention, we give a security level of about A concrete example of:

(I) System establishment: select standard hash function SHA-1 as H(·), system parameters n=31, δ=12, r=10 and k=8. Randomly select the 31-dimensional affine bijective transformation T on the finite field GF(2 ⁸ );

Construct a reversible compression transformation L based on SHA-1: (z ₁ ,…,z ₃₁ )←(x ₁ ,…,x ₃₁ ,x ₃₂ ,…,x ₄₃ ),

Among them, A is a 19-dimensional reversible square matrix, coefficient γ _i ≠0 (1≤i≤24), and coefficient a _ij (1≤i≤12, 1≤j≤30) and constant term α _i (1≤i≤31 ) is a random selection; x _n+i (1≤i≤12) is an extended variable, which is the hash value of the first (18+i) components of the vector (x ₁ ,...,x ₃₁ ), namely

x _31+i ＝H ₈ (x ₁ ||x ₂ ||…||x _18+i ), 1≤i≤12

Among them, H ₈ ( ) means to take out the first 8 bits of the output value of H ( ) in turn, and "||" means to connect two bit strings;

Let T ^- denote the transformation consisting of taking out the 21 rows of T in sequence.

The public key of the system is the composite of the above two mappings T ^- and L, G=T ^- οL, and the public key G is a linear indeterminate equation system with 43 input variables and 21 outputs on the finite field GF (2 ⁸ );

以及γ_i(13≤j≤24)组成。根据上述基于SHA-1的可逆变换L可得其逆变换L^-1：(x₁，…，x₃₁，x₃₂，…，x₄₃)←(z₁，…，z₃₁)，The system private key is composed of the inverse transformation of mapping T and L, D={T ^-1 , L ^-1 }; where, the inverse transformation L ^-1 consists of A ^-1 , B, α _i (1≤i≤31),

And γ _i (13≤j≤24) composition. According to the above reversible transformation L based on SHA-1, its inverse transformation L ^-1 can be obtained: (x ₁ ,...,x ₃₁ , x ₃₂ ,...,x ₄₃ )←(z ₁ ,...,z ₃₁ ),

(II) The signature process is as follows: Assuming that user A signs the message vector (y ₁ ,...,y ₂₁ ) of user B, the signature process of user A is divided into the following two steps:

① Randomly select 10 variables y _21+i ∈ GF(2 ⁸ ) (1≤i≤10) and concatenate them with the message vector to form a 31-dimensional vector (y ₁ ,...,y ₃₁ ) on GF(2 ⁸ ) , and use the private key T ^-1 to calculate (z ₁ ..., z ₃₁ ) = T ^-1 (y ₁ ..., y ₃₁ );

②Calculate with the private key L ^-1 to get the corresponding signature (x ₁ ..., x ₄₃ ) = L ^-1 (z ₁ , ..., z ₃₁ );

(Ⅲ) Signature verification process: After user B receives user A's signature on the message, it divides into the following two steps:

①Use the hash function to authenticate the signature (x ₁ ,...,x ₄₃ ), that is, each component must satisfy:

x _31+i ＝H ₈ (x ₁ ||x ₂ ||…||x _18+i ), 1≤i≤12

Otherwise refuse to sign;

② If step ① passes the authentication, continue to use the public key G of user A to verify, that is

并且主要的运算是有限域GF(2⁸)上的乘法运算，由于有限域较小可以预运算并造表存储，于是乘法运算可转化为查表运算；其次大约10次SHA-1运算。因此实现效率高，适合软硬件实现。When the system parameters n=31, δ=12, r=10 and k=8, the public key size of the system is about 0.88Kbyte, the public key size is about 1.65Kbyte, and the security level is about

And the main operation is the multiplication operation on the finite field GF(2 ⁸ ). Since the finite field is small, it can be pre-calculated and stored in a table, so the multiplication operation can be converted into a table lookup operation; followed by about 10 SHA-1 operations. Therefore, the implementation efficiency is high, and it is suitable for software and hardware implementation.

Claims (2)

1. A digital signature method, characterized in that, comprising the following steps: (1) System establishment: select a standard hash function H(·) and a finite field GF(q) with an output of at least 160 bits, where q= ^2k and integer k are less than the output value length of the hash function H(·); Specify the values of the integer parameters n, δ and r according to user security requirements (0<δ, r<n); Randomly select the n-dimensional affine bijective transformation T on GF(q); Construct a reversible compression transformation L based on the hash function H( ): (z ₁ ,…,z _n )←(x ₁ ,…,x _n ,x _n+1 ,…,x _n+δ ), Where A is an n-δ-dimensional reversible square matrix, coefficient γ _i ≠ 0 (1≤i≤2δ), and coefficient a _ij (1≤i≤δ, 1≤j≤n-1) and constant term α _i (1 ≤i≤n) is a random selection; x _n+i (1≤i≤δ) is an extended variable, which is the hash of the first (n-δ+i-1) components of the vector (x ₁ ,…, x _n ) Greek value, ie x _n+i ＝H _k (x ₁ ||x ₂ ||…||x _n-δ+i-1 ), 1≤i≤δ Among them, H _k ( ) means to take out the first k bits of the output value of H ( ) in turn, and "||" means to connect two bit strings; Let T ^- denote the transformation formed by sequentially taking out nr rows of T, The public key of the system is the compound of the above two mappings T ^- and L, G=T ^- οL, the public key G is a linear indeterminate equation system on the finite field GF(q), the number of input variables is n+δ, and the number of output variables is nr; the private key is composed of the inverse transformation of mapping T and L, D={T ^-1 , L ^-1 }; where, the inverse transformation L ^-1 consists of A ^-1 , B, α _i (1≤i≤n) , And γ _j (δ+1≤j≤2δ) composition; (II) The signature process is as follows: Assuming that user A signs the message vector (y ₁ , ..., y _nr ) of user B, the signature process of user A is divided into the following two steps: ①Randomly select r variables y _n-r+i ∈GF(q) (1≤i≤r) and concatenate them with the message vector to form an n-dimensional vector (y ₁ ,...,y _n ) on GF(q) , and use the private key T ^-1 to calculate (z ₁ ..., z _n ) = T ^-1 (y ₁ ..., y _n ); ②Calculate with the private key L ^-1 to get the corresponding signature (x ₁ ..., x _n+δ ) = L ^-1 (z ₁ , ..., z _n ); (III) Signature verification process: After user B receives user A's signature on the message, it divides into the following two steps: ①Use the hash function to authenticate the signature (x ₁ ,...,x _n+δ ), that is, each component must satisfy: x _n+i ＝H _k (x ₁ ||x ₂ ||…||x _n-δ+i-1 ), 1≤i≤δ Otherwise refuse to sign; ② If step ① passes the authentication, continue to use the public key G of user A to verify, that is

If the left and right sides of the above equation are equal, the signature is accepted, otherwise the signature is rejected. 2. The digital signature method according to claim 1, characterized in that: The hash function H(·) selects hash function standards MD5, SHA-1, SHA-2, and SHA-3 respectively.