AN ONLINE AND OFFLINE CIRCULATING UNBALANCED OIL AND VINEGAR SIGNATURE METHOD

Abstract

The present invention discloses an online and offline circulating unbalanced oil and vinegar signature method, which decomposes the traditional unbalanced oil and vinegar signature process into offline and online parts, wherein the offline step is independent of the signature message, and can be performed in advance, and a combination of circulating calculation methods is used in the calculating process to improve performance. When the online part needs to be signed, the final signature operation is completed by using the calculated result stored in the offline step. The present invention is a multi-variable public key cryptosystem-based unbalanced oil and vinegar signature scheme, which is a lightweight digital signature scheme suitable for low-performance electronic devices. The invention decomposes the unbalanced oil and vinegar signature algorithm into offline and online parts, and the offline step calculation can be performed in advance, which can more fully utilize energy and accelerate the online signature process simultaneously. In the calculation of the offline step, the present invention uses a circulating calculation method, which greatly reduces the size of the secret key and shortens the signature period.

Claims

1. An online and offline circulating unbalanced oil and vinegar signature method, characterized in that the online and offline circulating unbalanced oil and vinegar signature method comprises: offline step: before a signature message arrives, using an energy that cannot be stored at a peak of energy collection by a device to calculate in advance and store intermediate results, and in process, using a circulating calculation method to construct a central mapping matrix, and using a fast inversion method based on a circulant matrix to obtain an inverse matrix; the calculation process comprises: selecting secret parameters, calculating the central mapping matrix and its inverse matrix, generating a public key and a private key and storing calculation results; online step: when the signature message arrives, completing a final signature in combination with the results stored in the offline step; the calculation process comprises: signature message preprocessing, signature operation, and signature verification.

2. The online and offline circulating unbalanced oil and vinegar signature method according to claim 1, characterized in that constructing the central mapping matrix by using the circulating calculation method comprises the following steps: first, calculating a first row of a matrix G by v*B.sub.1+β.sub.1, where visa vinegar variable, B.sub.1 is a cross-term coefficient of the vinegar variable and an oil variable, and β.sub.1 is a linear term coefficient of the oil variable; then obtaining a complete circulant matrix G by rotating (B.sub.1,β.sub.1).

3. The online and offline circulating unbalanced oil and vinegar signature method according to claim 1, characterized in that obtaining the inverse matrix by using the fast inversion method based on the circulant matrix comprises the following steps: first, writing a polynomial form f(x)=Σ.sub.i=o.sup.o-1l.sub.ix.sub.i of a circulant matrix G; then using an extended Euclidean algorithm to find an inverse element g(x) of f(x) on a polynomial ring K[x]/(x.sup.o−1); finally, re-presenting g(x) as a matrix form G.sup.−1.

4. The online and offline circulating unbalanced oil and vinegar signature method according to claim 1, characterized in that the offline step is used for offline key generation, as follows: S101. first, according to a required security level, select a base field K=GF(q), the number of oil variables o, the number of vinegar variables v, and a reversible affine R and S, let n=o+v; S102. convert a central mapping equation of the unbalanced oil and vinegar signature, and decompose into a form that can be calculated online and offline; S103. perform a circulating calculation method, including selecting a vinegar vector v, calculate a circulant matrix G, and solve an inverse matrix G.sup.−1 of G as a polynomial form g(x), and calculate a constant term vector y; S104. calculate a composite map P=SGRK.sup.n.fwdarw.K.sup.o as a public key and store it for verifying a signature process, where K.sup.n.fwdarw.K.sup.o denotes a representation of a mapping from n dimension vector to o dimension vector on the base field K; S105. calculate inverse matrices of the reversible affine R and S, store (R.sup.−1,S.sup.−1) and other basic parameters as a private key, which will be used in the signature process; S106. finally store (v, y, g(x)) in the memory and complete the offline step calculation.

5. The online and offline circulating unbalanced oil and vinegar signature method according to claim 1, characterized in that the online step is used for online signature generations and online signature verifications; wherein a specific process of online signature generations is as follows: S201. first, calculate a hash value h(m)∈K.sup.o of a message m, and then calculate m′=h(m)−y, where K.sup.o denotes a o dimension vector on a base field K=GF(q), and o denotes the number of oil variables; S202. act inverse affine S.sup.−1 to m′, get u=S.sup.−1(m′), and obtain its related polynomial u(x); S203. obtain a solution ({circumflex over (x)}.sub.1, . . . , {circumflex over (x)}.sub.o) of a central mapping oil variable by calculating u(x)*g(x), wherein g(x) is a polynomial form of an inverse matrix G.sup.−1 of a circulant matrix G; S204. splice a vinegar variable (v.sub.1, . . . , v.sub.v), which are selected in the offline calculation stage, and the solution ({circumflex over (x)}.sub.1, . . . , {circumflex over (x)}.sub.o) of the oil variable, to get {circumflex over (x)}=(x.sub.1, . . . , x.sub.n), wherein n=o+v; S205. act inverse affine R.sup.−1 to {circumflex over (x)}, get s=R.sup.−1({circumflex over (x)}), output a signature s∈K.sup.n; Among them, a specific process of online signature verification is as follows: S206. a signer sends a message signature pair (m,s) to a verifier; S207. the verifier uses a public key P to calculate whether P(s) is equal to h(m)−y to verify a correctness of the signature; if they are equal, the signature is legal; otherwise, the signature is illegal.

6. The online and offline circulating unbalanced oil and vinegar signature method according to claim 4, characterized in that the step S102 converts the central mapping equation of the unbalanced oil and vinegar signature, and decomposes into an online and offline calculation form, specifically comprises the following steps: S102a. first unfold an unbalanced oil and vinegar central mapping equation and express it as: $\underset{\underset{\mathrm{constant}}{︸}}{v^T*A_k*v+v^T.Math.{\alpha }_k+c_k}+\underset{\underset{\mathrm{linear}\mathrm{in}o}{︸}}{v^T*B_k*o+{\beta }_k.Math.o}=m_k,v\in K^v,o\in K^o,k=1,2,\mathrm{.Math.}o;$ S102b. let y.sub.k=(v.sup.T*A.sub.k*+v.sup.T.Math.α.sub.k+c.sub.k),k∈[1,2, . . . , o], substitute the vinegar variable into the oil and vinegar equation, then express an unbalanced oil and vinegar signature central mapping equation as Go=u: $\underset{\underset{G}{︸}}{\left(\begin{array}{c}{v}^T*B_1+{\beta }_1\\ v^T*B_2+{\beta }_2\\ \mathrm{.Math.}\\ v^T*B_{o-1}+{\beta }_{o-1}\\ v^T*B_{o-1}+{\beta }_{o-1}\end{array}\right)}\left(\begin{array}{c}{o}_1\\ o_2\\ \mathrm{.Math.}\\ o_{o-1}\\ o_o\end{array}\right)=\underset{\underset{u}{︸}}{\left(\begin{array}{c}{m}_1\\ m_2\\ \mathrm{.Math.}\\ m_{o-1}\\ m_0\end{array}\right)-\left(\begin{array}{c}{y}_1\\ y_2\\ \mathrm{.Math.}\\ y_{o-1}\\ y_o\end{array}\right)}.$

7. The online and offline circulating unbalanced oil and vinegar signature method according to claim 4, characterized in that the step S103, in the execution of circulating calculation method, the circulating calculation method specifically comprises the following steps: S103a. first select a set of vinegar variables (v.sub.1, . . . , v.sub.v); S103b. get a first row of the matrix G by calculating v*B.sub.1+β.sub.1, and then obtain a complete circulant matrix G by rotating (B.sub.1,β.sub.1); S103c. write a polynomial form of the circulant matrix G, f(x)=Σ.sub.i=o.sup.o-1l.sub.ix.sub.i; S103d. use an extended Euclidean algorithm to find an inverse element g(x) of f(x) on a polynomial ring K[x]/(x.sup.o−1), and then re-present g(x) as a matrix form G.sup.−1; if an inverse element g(x) does not exist, indicating that the matrix G is irreversible, then return to step S103a to re-select the vinegar variable v; S103e. according to an effective vinegar variable v, calculate y.sub.k=(v.sup.T*A.sub.k*v+v.sup.T.Math.α.sub.k+c.sub.k)(k∈[1, . . . , o]) to get a constant term vector y.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0044] FIG. 1 is a flow chart of the algorithm for the online and offline circulating unbalanced oil and vinegar signature method disclosed by the present invention.

DETAILED DESCRIPTION

[0045] In order to make the objects, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described in conjunction with the drawings in the embodiments of the present invention. It is obviously a partial embodiment of the invention, and not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those skilled in the art without creative efforts are within the scope of the present invention.

Embodiment

[0046] This embodiment discloses the online and offline circulating unbalanced oil and vinegar signature method, and the wireless sensing network to which the method is applied can automatically collect energy.

[0047] The unbalanced oil and vinegar signature process is broken down into two main steps:

[0048] offline step: The offline step is independent of the message that needs to be signed and is pre-executed before signing. This step uses the wireless sensor network to calculate the energy that cannot be stored at the peak of energy harvesting. The main calculation process comprises: selecting secret parameters, calculating the central mapping matrix and its inverse matrix, generating of public and private keys, and storage of calculation results.

[0049] online step: The online step is related to the message that needs to be signed. This step is performed in conjunction with the results stored in the offline step when the signature message arrives. The main calculation process comprises: signature message preprocessing, signature operation, and signature verification.

[0050] The offline step can be calculated using the excess energy that the wireless sensor network can't continue to store at the peak of energy harvesting.

[0051] The offline step uses the circulating calculation method to construct the central mapping matrix and uses the fast inversion of the circulant matrix method to solve its inverse matrix.

[0052] Wherein, using the circulating calculation method to construct the central mapping matrix specifically comprises the following steps: first, calculating the first row of the matrix G by v*B.sub.1+β.sub.1, where v is the vinegar variable, B.sub.1 is the cross-term coefficient of the vinegar variable and the oil variable, and β.sub.1 is a linear term coefficient of the oil variable; then obtaining a complete circulant matrix G by rotating (B.sub.1,β.sub.1).

[0053] Wherein, using the fast inversion method of the circulant matrix to solve the inverse matrix specifically comprises the following steps: first writing the polynomial form f(x)=Σ.sub.i=o.sup.o-1l.sub.ix.sub.i of the circulant matrix G; then using the extended Euclidean algorithm to find the inverse element g(x) of f(x) on the polynomial ring K[x]/(x.sup.o−1); finally, re-presenting g(x) as a matrix form G.sup.−1.

[0054] The online and offline circulating unbalanced oil and vinegar signature method comprises the following sequence of steps:

[0055] S1, offline step, for offline key generation;

[0056] S101. first, according to the required security level, select the base field K=GF(q), the number of oil variables o, the number of vinegar variables v, and the reversible affine R and S, let n=o+v;

[0057] S102. convert the central mapping equation of the unbalanced oil and vinegar signature, and decompose into the form that can be calculated online and offline;

[0058] S103. perform the circulating calculation method, including selecting the vinegar vector v, calculate the circulant matrix G, and solve the inverse matrix G.sup.−1 of G as the polynomial form g(x), and calculate the constant term vector y;

[0059] S104. calculate the composite map P=SGRK.sup.n.fwdarw.K.sup.o as the public key and store it for verifying the signature process, where K.sup.n.fwdarw.K.sup.o denotes a representation of the mapping from n dimension vector to o dimension vector on the base field K;

[0060] S105. calculate inverse matrices of the reversible affine R and S, store (R.sup.−1,S.sup.−1) and other basic parameters as the private key, which will be used in the signature process;

[0061] S106. finally store (v, y, g(x)) in the memory and complete the offline step calculation.

[0062] S2, the online step for online signature generation and online signature verification; wherein the specific process of online signature generation is as follows:

[0063] S201. first, calculate the hash value h(m)∈K.sup.o of the message m, and then calculate m′=h(m)−y, where K.sup.o denotes the o dimension vector on the base field K=GF(q), and o denotes the number of oil variables;

[0064] S202. act inverse affine S.sup.−1 to m′, get u=S.sup.−1(m′), and obtain its related polynomial u(x);

[0065] S203. obtain the solution ({circumflex over (x)}.sub.1, . . . , {circumflex over (x)}.sub.o) of the central mapping oil variable by calculating u(x)*g(x), wherein g(x) is the polynomial form of the inverse matrix G.sup.−1 of the circulant matrix G;

[0066] S204. splice the vinegar variable (v.sub.1, . . . , v.sub.v), which are selected in the offline calculation stage, and the solution ({circumflex over (x)}.sub.1, . . . , {circumflex over (x)}.sub.o) of the oil variable, to get {circumflex over (x)}=(x.sub.1, . . . , x.sub.n), wherein n=o+v;

[0067] S205. act inverse affine R.sup.−1 to {circumflex over (x)}, get s=R.sup.−1({circumflex over (x)}), output the signature s∈K.sup.n;

[0068] Among them, the specific process of online signature verification is as follows:

[0069] S206. the signer sends the message signature pair (m,s) to the verifier;

[0070] S207. the verifier uses the public key P to calculate whether P(s) is equal to h(m)−y to verify the correctness of the signature; if they are equal, the signature is legal; otherwise, the signature is illegal.

[0071] The abovementioned step S102 converts the central mapping equation of the unbalanced oil and vinegar signature, and decomposes into the online and offline calculation form, specifically comprises the following steps:

[0072] S102a. first unfold the unbalanced oil and vinegar central mapping equation and express it as:

[00003]$\underset{\underset{\mathrm{constant}}{︸}}{v^T*A_k*v+v^T.Math.{\alpha }_k+c_k}+\underset{\underset{\mathrm{linear}\mathrm{in}o}{︸}}{v^T*B_k*o+{\beta }_k.Math.o}=m_k,v\in K^v,o\in K^o,k=1,2,\mathrm{.Math.}o;$

[0073] S102b. let y.sub.k=(v.sup.T*A.sub.k*v+v.sup.T.Math.α.sub.k+c.sub.k),k∈[1, 2, . . . , o], substitute the vinegar variable into the oil and vinegar equation, then express the unbalanced oil and vinegar signature central mapping equation as Go=u:

[00004]$\underset{\underset{G}{︸}}{\left(\begin{array}{c}{v}^T*B_1+{\beta }_1\\ v^T*B_2+{\beta }_2\\ \mathrm{.Math.}\\ v^T*B_{o-1}+{\beta }_{o-1}\\ v^T*B_{o-1}+{\beta }_{o-1}\end{array}\right)}\left(\begin{array}{c}{o}_1\\ o_2\\ \mathrm{.Math.}\\ o_{o-1}\\ o_o\end{array}\right)=\underset{\underset{u}{︸}}{\left(\begin{array}{c}{m}_1\\ m_2\\ \mathrm{.Math.}\\ m_{o-1}\\ m_0\end{array}\right)-\left(\begin{array}{c}{y}_1\\ y_2\\ \mathrm{.Math.}\\ y_{o-1}\\ y_o\end{array}\right)}.$

[0074] In the abovementioned step S103, the execution of circulating calculation method, the circulating calculation method specifically comprises the following steps:

[0075] S103a. first select the set of vinegar variables (v.sub.1, . . . , v.sub.v);

[0076] S103b. get the first row of the matrix G by calculating v*B.sub.1+β.sub.1, and then obtain the complete circulant matrix G by rotating (B.sub.1, β.sub.1);

[0077] S103c. write the polynomial form of the circulant matrix G, f(x)=Σ.sub.i=o.sup.o-1l.sub.ix.sub.i;

[0078] S103d. use an extended Euclidean algorithm to find the inverse element g(x) of f(x) on the polynomial ring K[x]/(x.sup.o−1), and then re-present g(x) as the matrix form G.sup.−1; if the inverse element g(x) does not exist, indicating that the matrix G is irreversible, then return to step S103a to re-select the vinegar variable v;

[0079] S103e. according to an effective vinegar variable v, calculate y.sub.k=(v.sup.T*A.sub.k*v+v.sup.T.Math.α.sub.k+c.sub.k)(k∈[1, . . . , o]) to get the constant term vector y.

[0080] The online and offline circulating unbalanced oil and vinegar signature method disclosed in the present invention is applied to a wireless sensor network at the same time as the signature scheme in the prior art, and Table 1 below shows the comparison results:

TABLE-US-00001 TABLE 1 Comparison table of the present invention with prior art Key Public Private Generation Signature Verification Parameter Key Key Signature Period Period Period Scheme (o, v) (KB) (KB) (bit) (10.sup.3 cycles) (10.sup.3 cycles) (10.sup.3 cycles) UOV (33, 66) 101.7 96.5 495 44,964 1,893 43 Cyclic UOV (33, 66) 17.1 96.5 495 22,291,200 1,893 10 MB UOV (33, 66, d = 3) 101.7 54.1 495 151,284 1,242 43 NT UOV (33, 66) 101.7 67.9 495 136,814 1,287 43 Present (34, 65) 101.7 53.9 495 139,472 252 43 Invention

[0081] It can be seen from Table 1 that the online and offline circulating unbalanced oil and vinegar signature method disclosed in the present invention is optimal in signature time and private key size, and is more suitable for wireless sensor network with low performance but high latency requirements.

[0082] In summary, the abovementioned embodiment provides the online and offline circulating unbalanced oil and vinegar signature method. Under the premise of ensuring information security, the method decomposes the signature process into online and offline parts. Using the energy, which the wireless sensor device cannot store because of exceeding the capacity range at the peak of the energy collection, to calculate in the offline step, it makes full use of the characteristics of current wireless sensor devices that can collect energy to improve energy utilization. In addition, the signature scheme combines the use of the circulating calculation method, which greatly reduces the length of the key and shortens the period of the signature.

[0083] The abovementioned embodiments are preferred embodiments of the present invention, but the embodiments of the present invention are not limited to the above embodiments, and any other changes, modifications, substitutions, combinations, and simplifications that are made without departing from the spirit and scope of the invention should be equivalent replacement means, and are included in the protection scope of the invention.