Method for implementation of post-quantum key exchange protocol and application thereof

Abstract

The disclosure proposes a novel method for generating public polynomials. The method simplifies key exchange processes, reduces the time required for key exchange and reduces the bandwidth required for data transmission from a server to a client. Secondly, the method keeps the calculation processes at both sides synchronized through a novel data exchange solution, particularly through handshaking signals, to ensure that the server and the client are always in the same key exchange process. In addition, the method further reduces a transmission bandwidth by sending information of the client twice. A state synchronization mechanism of the client and the server is proposed in the disclosure to ensure that Trivium modules at both sides are in the same state at the beginning of each key exchange, thereby avoiding reinitializing the modules and improving the operation efficiency of the whole system.

Claims

1. A method for implementation of a post-quantum key exchange protocol, comprising: a client generating a public polynomial â.sub.1 based on a Trivium module therein and generating a polynomial û based on the polynomial â.sub.1, then sending a data request signal to a server to receive a polynomial {circumflex over (b)} sent by the server for secured key transmission, and receiving data request signal sent by the server to send the polynomial û to the server, wherein a public polynomial â.sub.2 for calculating the polynomial {circumflex over (b)} is generated by the server with adoption of a random number sequence generated by a Trivium module in the server, and â.sub.1=â.sub.2; and the client generating a key μ and a polynomial c based on the Trivium module therein, and sending the polynomial c to the server based on another received data request signal sent by the server, so that the server generates the key μ based on the polynomial c and adjusts a state of the Trivium module in the server to be synchronized with a current state of the Trivium module in the client; wherein the public polynomials â.sub.1 and â.sub.2 are generated based on the Trivium module of the client and the Trivium module of the sever, respectively, and wherein the Trivium module of the client and the Trivium module of the server operate separately and the public polynomials â.sub.1 and â.sub.2 are generated separately and independently of each other.

2. The method according to claim 1, wherein the step of generating the polynomial û based on the polynomial â.sub.1 comprises: the client adopting the random number sequence generated by the Trivium module in the client to generate polynomials s′ and e′ respectively, and calculating number-theoretic transformation polynomials of the polynomials s′ and e′ respectively, and calculating a sum of the number-theoretic transformation polynomial of the polynomial e′ and a product of the number-theoretic transformation polynomial of the polynomial s′ and the public polynomial â.sub.1 to obtain the polynomial û, wherein the Trivium module in the client generates a 64 bit random number in one cycle.

3. The method according to claim 1, wherein the client generating the key μ and the polynomial c based on the Trivium module therein comprises: the client respectively calculating the key μ and a polynomial e″ based on the random number sequence generated by the Trivium module therein, calculating a product of the number-theoretic transformation polynomial of the polynomial s′ and the polynomial {circumflex over (b)}, and performing inverse number-theoretic transformation to the product, wherein the key μ is obtained in a manner that the client performs first secure hash algorithm 3 (SHA3) to the random number sequence generated by the Trivium module therein to obtain ν′ and performs second SHA3 on the ν′; the client encoding the ν′ to obtain a polynomial k; and calculating a sum of the polynomial e″, the polynomial k and the result of the inverse number-theoretic transformation to obtain a polynomial c, and compressing data of the polynomial c to obtain the polynomial c.

4. The method according to claim 3, wherein all the polynomials are stored in memories, wherein the polynomials obtained at the same step are stored in different memories respectively.

5. A method for implementation of a post-quantum key exchange protocol, comprising: a server generating a public polynomial â.sub.2 based on a Trivium module therein and generating a polynomial {circumflex over (b)} based on the polynomial â.sub.2, then receiving a data request signal sent by a client to send the polynomial {circumflex over (b)}, and sending a data request signal to the client to receive a polynomial û, wherein a polynomial â.sub.1 for calculating the polynomial û is generated by the client with adoption of a random number sequence generated by a Trivium module in the client, and â.sub.1=â.sub.2; the server generating a polynomial m based on the polynomial û, sending another data request signal to the client to receive a polynomial c corresponding to a key μ sent by the client, and generating the key μ based on the polynomial m and the polynomial c; the server controlling the Trivium module therein to continue working for a certain time so that a state of the Trivium module in the server is the same as a state of the Trivium module in the client; wherein the public polynomials â.sub.1 and â.sub.2 are generated based on the Trivium modules of the client and the server, respectively, and wherein the Trivium module of the client and the Trivium module of the server operate separately and the public polynomials â.sub.1 and â.sub.2 are generated separately and independently of each other.

6. The method according to claim 5, wherein the Trivium module in the server generates a 64 bit random number in one cycle.

7. The method according to claim 5, wherein all the polynomials are stored in memories, and the polynomials obtained at the same step are stored in different memories respectively.

8. A system for implementation of a post-quantum key exchange protocol, comprising a client and a server, wherein the client is configured to generate a public polynomial â.sub.1 with adoption of a random number sequence generated by a Trivium module in the client and generate a polynomial û based on the polynomial â.sub.1, send a first data request signal to the server, and send the polynomial û to the server according to a second data request signal from the server; the client is further configured to generate a key μ and a polynomial c based on the Trivium module therein, and send the polynomial c to the server according to a third data request signal sent by the server; the server is configured to generate a public polynomial â.sub.2 with adoption of a random number sequence generated by a Trivium module in the server, generate a polynomial {circumflex over (b)} based on the polynomial â.sub.2, send the polynomial {circumflex over (b)} to the client according to the first data request signal and send the second data request signal to the client; and â.sub.1=â.sub.2; the server is further configured to generate a polynomial m based on the polynomial û, send the third data request signal to the client, and generate the key μ based on the polynomial m and the polynomial c; and steps that the client generates the polynomial û and the server generates the polynomial {circumflex over (b)} are synchronized; and the steps that the client generates the key μ and the polynomial c based on the Trivium module in the client and the server generates the polynomial m based on the polynomial û are synchronized; wherein the public polynomials â.sub.1 and â.sub.2 are generated based on the Trivium modules of the client and the server, respectively, and wherein the Trivium module of the client and the Trivium module of the server operate separately and the public polynomials â.sub.1 and â.sub.2 are generated separately and independently of each other.

9. The system according to claim 8, wherein the Trivium module in the client and the Trivium in the server are configured to generate a 64 bit random number in one cycle.

10. The system according to claim 8, the client and the system each comprises memories, all the polynomials are stored in memories, and the polynomials obtained at the same step are stored in different memories respectively.

Description

DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a flow block diagram of a method for implementation of a post-quantum key exchange protocol according to an embodiment of the disclosure;

(2) FIG. 2 is a diagram of a processor for implementation of a post-quantum key exchange protocol in a server according to an embodiment of the disclosure; and

(3) FIG. 3 is a diagram of a processor for implementation of a post-quantum key exchange protocol in a client according to an embodiment of the disclosure.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

(4) In order to make purposes, technical solutions and advantages of the disclosure clearer, the disclosure will be further described in detail with reference to the accompanying drawings and embodiments below. It shall be understood that embodiments described herein are only used for explaining the disclosure and are not intended to limit the disclosure. In addition, the technical features involved in various embodiments of the disclosure described below can be combined with each other as long as the technical features do not conflict with each oilier.

Embodiment 1

(5) Referring to FIG. 1, a method 100 for implementation of a post-quantum key exchange protocol comprises:

(6) Step 110, a client generates the public polynomial â.sub.1 based on a Trivium module therein and generates the polynomial û based on the polynomial â.sub.1, then sends data request signal to a server to receive the polynomial {circumflex over (b)} sent by the server, and receives data request signal sent by the server to send the polynomial û to the server. The public polynomial â.sub.2 for calculating the polynomial {circumflex over (b)} is generated by the server with adoption of a random number sequence generated by a Trivium module in the server, and â.sub.1=â.sub.2.

(7) Step 120, the client generates the key μ and the polynomial c based on the Trivium module therein, and sends the polynomial c to the server based on another received data request signal sent by the server, so that the server generates the key μ based on the polynomial c and adjusts a state of the Trivium module in the server to be synchronized with a current state of the Trivium module in the client.

(8) When the method is carried out for the first time, the Trivium modules of the client and the server shall be initialized; a random number sequence outputted by the module will be used as a random number source of coefficients for binary sampling and public polynomial; and no additional algorithm or system is required for generating the public polynomial coefficients, thereby reducing the complexity of the system.

(9) The random number sequence is obtained by the Trivium module (i.e., a Trivium stream cipher algorithm). 16 bit numbers in the random number sequence are selected for calculation to obtain 14 bit numbers, which satisfy the requirements on polynomial coefficients, i.e., less than q, as the coefficients of the public polynomial â.

(10) In addition, it should be noted that the client can receive the data request signal sent by the server after sending the data request signal to the server and receiving the polynomial {circumflex over (b)} sent by the server, to send the polynomial û to the server.

(11) The Trivium modules of the server and the client have a state synchronization mechanism, so that the system can automatically complete multiple key exchange processes without additional input data.

(12) Preferably, the step of generating the polynomial û based on the polynomial â.sub.1 comprises:

(13) A step that the client side adopts the random number sequence generated by the Trivium module therein to generate polynomials s′ and e′ respectively, calculates number-theoretic transformation polynomials of the polynomials s′ and e′ respectively, and

(14) A step of calculating a sum of the number-theoretic transformation polynomial of the polynomial e′ and a product of the number-theoretic transformation polynomial of the polynomial s′ and the public polynomial â.sub.1 to obtain the polynomial û.

(15) The Trivium module in the client generates a 64 bit random number in one cycle.

(16) Since the existing Trivium module used for implementing the post-quantum key exchange protocol outputs a 1 bit random number in a single cycle and the coefficients of the polynomial is 14 bit, it takes at least 64 cycles to generate coefficients of two polynomials, while the Trivium module in the present disclosure can generate a 64 bit random number in one cycle and can generate the coefficients of two polynomials in one cycle according to a binomial sampling algorithm. Therefore, the method has high polynomial generation efficiency.

(17) The coefficients of the polynomials s′ and e′ are obtained by performing binary sampling on the random number sequence generated by the Trivium module in the client, and the aforementioned number-theoretic transformation polynomials refer to new polynomials obtained by number-theoretic transformation of the polynomials.

(18) Further, the step that the client generates the key μ and the polynomial c based on the Trivium module therein comprises:

(19) A step that the client synchronously calculates the key μ and the polynomial e″ based on the random number sequence generated by the Trivium module therein, calculates a product of the number-theoretic transformation polynomial of s′ and the polynomial {circumflex over (b)}, and performs inverse number-theoretic transformation to the product, wherein the key μ is obtained in a manner that the client performs first SHA3 on the random number sequence generated by the Trivium module in the client to obtain ν′ and performs the second SHA3 on ν′; and the client encodes ν′ to obtain the polynomial k, calculates a sum of the polynomial e″, the polynomial k and a result of the inverse the number-theoretic transformation to obtain the polynomial c, and compresses data of the polynomial c to obtain the polynomial c.

(20) A 256 bit random number, as an original key ν, is selected from the random number sequence generated by the Trivium module. The original key is hashed twice by the SHA3 to obtain the final key μ.

(21) Preferably, all the polynomials are stored in memories, and the polynomials obtained at the same step are stored in different memories respectively.

Embodiment 2

(22) A client comprises a processor for implementation of a post-quantum key exchange protocol according to the method for implementation of the post-quantum key exchange protocol described in the Embodiment 1. The related technical solution is the same as that of the Embodiment 1 and thus is not repeated herein.

Embodiment 3

(23) A method for implementation of a post-quantum key exchange protocol comprises:

(24) A step that a server generates the public polynomial â.sub.2 based on a Trivium module therein and generates the polynomial {circumflex over (b)} based on the polynomial â.sub.2, then receives the data request signal sent by a client to send the polynomial {circumflex over (b)} to the client, and sends the data request signal to the client to receive the polynomial û sent by the client, wherein the polynomial â.sub.1 for calculating the polynomial û is generated by the client with adoption of a random number sequence generated by the Trivium module in the client, and â.sub.1=â.sub.2;

(25) A step that the server generates the polynomial m based on the polynomial û, sends another data request signal to the client to receive the polynomial c corresponding to a key μ sent by the client, and generates the key μ based on the polynomial m and the polynomial c; and

(26) A step that the server controls the Trivium module therein to continue working for a certain time so that a stale of the Trivium module in the server is the same as a state of the Trivium module in the client.

(27) When the method is carried out for the first time, the Trivium modules of the client and the server shall be initialized; random number sequences outputted by the Trivium modules will be used as random number sources of coefficients for binary sampling and public polynomials; and no additional algorithm or system is required for generating the public polynomial coefficients, thereby reducing the complexity of the system. After completing implementing the post-quantum key exchange protocol each lime, the Trivium module of the server continues to work for a period of time to make the state of the Trivium module in the server is the same as that of the Trivium module in the client. Therefore, the Trivium modules in the server and the client in the method have a state synchronization mechanism, so that the system can automatically perform multiple key exchange processes without additional data input or initialization operations.

(28) The coefficients of the polynomials s and e are obtained by performing binary sampling on the random numbers generated by the Trivium module; and the polynomials s and e are respectively subjected to number-theoretic transformation to obtain ŝ=NTT(s) and ê=NTT(e). The public polynomial â.sub.2 and polynomial ŝ are subjected to dot product to obtain a result; and the obtained result is added to the result obtained after number-theoretic transformation of the polynomial e to obtain the polynomial {circumflex over (b)}, which is denoted as {circumflex over (b)}=â.sub.2.Math.ŝ+NTT(e).

(29) In addition, the server performs inverse number-theoretic transformation on the result obtained after dot product of the polynomial û and the polynomial ŝ to obtain the polynomial m, which is denoted as m=NTT.sup.−1(û.Math.ŝ).

(30) Preferably, the Trivium module generates a 64 bit random number in one cycle.

(31) Since the existing Trivium module uses for implementing the post-quantum key exchange protocol outputs a 1 bit random number in a single cycle and the coefficients of the polynomial is 14 bit, it lakes at least 64 cycles to generate coefficients of two polynomials, while the Trivium module of the present method can generate a 64 bit random number in one cycle and can generate the coefficients of two polynomials in one cycle according to a binomial sampling algorithm. Therefore, the method has high polynomial generation efficiency.

(32) Preferably, all the polynomials are stored in memories, and the polynomials obtained at the same step are stored in different memories respectively.

Embodiment 4

(33) A server comprises a processor for implementation of a post-quantum key exchange protocol according to the method for implementation of the post-quantum key exchange protocol described in the Embodiment 3. The related technical solution is the same as that of the Embodiment 3 and thus is not repeated herein.

Embodiment 5

(34) A system for implementation of a post-quantum key exchange protocol comprises the client and the server described in the Embodiment 2 and the Embodiment 4. The steps that the client generates the polynomial û and the server generates the polynomial {circumflex over (b)} are synchronized; and the steps that the client generates a key μ and the polynomial c based on the Trivium module therein and the server generates the polynomial m based on the polynomial û are synchronized.

(35) The client and the server can synchronously generate the public polynomial â and the polynomials s, e, s′ and e′, synchronously calculate the polynomials {circumflex over (b)} and ū, and synchronously calculate the polynomials m and n.

(36) In order to belter illustrate the disclosure, specific examples of the processors for implementation of the post-quantum key exchange protocol in the server and the client are given.

(37) A circuit structure of the processor corresponding to the server is shown in FIG. 2; and the working process is as follows:

(38) 1. The Trivium module generates a 64 bit random number in every cycle and sends the 64 bit random number to a binary sampling module (i.e. Samper); and the Samper divides the 64 bit random number into four 16 bit random number, calculates a difference between hamming weights of a first random number and a second random number as the coefficients of the polynomial s, and calculates a difference between hamming weights of a third random number and a fourth random number as the coefficients of the polynomial e. The polynomials s and e have 1024 coefficients; and each coefficient is 64 bit. The polynomial s is stored in a dual-port random access memory 0 (DPRAM0); and the polynomial e is stored in a DPRAM1.

(39) 2. The Trivium module generates a 64 bit random number in every cycle and sends the 64 bit random number to a parse module. Since all the calculations in the key exchange protocol are performed on an integer ring with modulo q=12289, each coefficient of the polynomial shall be less than q. The parse module divides the 64 bit random number into four 16 bit numbers in sequence, compares each number with 5q, discards the random number if the random number is greater than 5q, converts the 16 bit random number into a 14 bit random number after modulo q if the random number is less than 5q, and stores the 14 bit number in a DPRAM3 as the coefficients of the public polynomial â, which is denoted as â hereafter due to â.sub.1=â.sub.2.

(40) While generating the public polynomial â, an FNTT module is connected with the DPRAM0 and a DPRAM2 to calculate the polynomial ŝ=NTT(s); and the ŝ obtained will be stored in the DPRAM0.

(41) 3. The FNTT module is connected with the DPRAM1 and the DPRAM2 to calculate the number-theoretic transformation of the polynomial e; and the obtained result will be stored in the DPRAM1.

(42) 4. The FNTT module is connected with the DPRAM0 and a DPRAM3 to calculate a dot product of the polynomials â and ŝ by using a dot product mode of the FNTT module, and the result will be stored in the DPRAM3. Then, the output data ports of the DPRAM3 and the DPRAM1 are connected with the modulo addition module (MA) to calculate the polynomial {circumflex over (b)}=â.Math.ŝ+NTT(e), wherein the obtained polynomial {circumflex over (b)} is stored in the DPRAM2.

(43) 5. The server sends the polynomial {circumflex over (b)} to the client, and receives the polynomial {circumflex over (μ)} from the client to store the polynomial û in the DPRAM3.

(44) 6. The FNTT module is connected with the DPRAM0 and the DPRAM3 to calculate the dot product of the polynomial š and the polynomial û by using the dot product mode of the FNTT module, and the result will be stored in the DPRAM3.

(45) 7. The FNTT module is connected with the DPRAM3 and the DPRAM1 to calculate the polynomial m=NTT.sup.−1(û.Math.ŝ). by using the calculation mode for the inversion number-theoretic transformation of the FNTT module, and the obtained polynomial m will be stored in the DPRAM1.

(46) 8. The server receives the polynomial c from the client and receives the input connection between the data port and a data decompress module. Output of the Decompress module and output of DPRAM1 are connected with the input of a modulo subtraction module (MS) to calculate the polynomial k′=c′−m; and the obtained polynomial k′ is divided into two parts, which are stored at addresses 0 to 511 of the DPRAM2 and addresses 512 to 1023 of the DPRAM0.

(47) 9. The outputs of the DPRAM0 and the DPRAM2 are connected with the input of data decode module (Decode); the output of the decode module is connected with an SHA3 module; and the output of the SHA3 module is the final key.

(48) A circuit structure of the processor corresponding to the client is shown in FIG. 3; and the working process is as follows:

(49) 1-4. The first four steps of the client and the server are basically the same, except that in tire second step, the Samper module of the client uses the difference between the hamming w eights of the first random number and the third random number as the coefficients of the polynomial s′, and calculates the difference between the hamming weights of the second random number and the fourth random number as the coefficients of the polynomial e′, to ensure that the polynomials s and s′ as well as the polynomials e and e′ are different.

(50) 5. The client sends the polynomial û to the server, and receives the polynomial {circumflex over (b)} from the server and stores it in the DPRAM1.

(51) 6. The output of the Trivium module is connected with the SHA3 module to obtain ν′ after performing the first hash transformation on the original key ν generated by the Trivium module.

(52) 7. The FNTT module is connected with the DPRAM0 and the DPRAM1 to calculate the dot product of the polynomial {circumflex over (b)} and the polynomial {circumflex over (t)} by using the dot product function of the FNTT module, and the result will be stored in the DPRAM1. The output of the Trivium module is connected with the Samper module while performing dot product calculation, to generate the polynomial e″, which is stored in the DPRAM2.

(53) The output ν′ of the SHA3 is connected with a data encode module while performing dot product calculation, and the output of the encode module is the coefficients of the polynomial k and is stored in the DPRAM3.

(54) 8. The FNTT module is connected with the DPRAM1 and the DPRAM0 to calculate the polynomial n=NTT.sup.−1({circumflex over (b)}.Math.{circumflex over (t)}) by using a calculation function for the inversion number-theoretic transformation of the FNTT module, and the obtained polynomial n will be stored in the DPRAM0.

(55) 9. The outputs of the DPRAM0 and the DPRAM2 are connected with an MA2 module; the output of MA2 is connected with the input of an MA1; and the output of the DPRAM3 is connected with the input of the MA1. The output of the MA1 is connected with the input of the DPRAM2 and the compress module. The output of the compress module is connected with the input of the DPRAM1. After completing calculation, the polynomial c=n+e″+k is stored in the DPRAM, and the polynomial c=NHSCompress(c) is stored in the DPRAM1.

(56) 10. The client sends the polynomial c to the server.

(57) 11. The output of ν′ is used as the input of the SHA3 module; and the Hash transformation is performed on ν′ once to obtain the output of the SHA3 module as the final key.

(58) The related technical solution is the same as that in the Embodiment 1 to the Embodiment 4 and thus is not repeated herein.

(59) Obviously, the above only describes preferred embodiments of the disclosure and is not intended to limit the disclosure; and any modification, equivalent substitution and improvement made within the spirit and principles of the disclosure shall be included within the protection scope of the disclosure.