CN-121980113-A - Elliptic curve batch scalar multiplication acceleration method based on optimized Jacobian coordinate conversion

CN121980113ACN 121980113 ACN121980113 ACN 121980113ACN-121980113-A

Abstract

The application relates to the field of electric digital data processing, in particular to an elliptic curve batch scalar multiplication acceleration method based on optimized Jacobian coordinate conversion, which comprises the steps of generating a scalar set K to be processed and an elliptic curve point set P, executing batch scalar multiplication operation on the K and the P by using a Jacobian coordinate system, extracting Z coordinates of all points in a calculation result set, constructing a Z coordinate set, and constructing a multiplication tree according to the Z coordinate set For multiplication tree Performing modular inversion operation on the root node value to obtain a modular inversion element of the root node, and constructing an inversion element tree based on the modular inversion element of the root node from top to bottom Based on inverse element tree The application optimizes n times of modular inverse operation into 1 time of modular inverse operation and 3n-3 times of modular multiplication operation, thereby remarkably improving the batch scalar multiplication efficiency of the whole elliptic curve and reducing the calculation cost of an elliptic curve cryptographic scheme.

Inventors

TANG FEI
HU CHUNXI
CHEN YU
LING GUOWEI
ZHU HUIHUI
SHAN JINYONG
XIAO YUNPENG

Assignees

重庆邮电大学

Dates

Publication Date: 20260505
Application Date: 20260120

Claims (10)

1. An elliptic curve batch scalar multiplication acceleration method based on optimized jacobian coordinate transformation is characterized by comprising the following steps: S1, generating a scalar set K to be processed and an elliptic curve point set P; S2, performing batch scalar multiplication operation on the scalar set K and the elliptic curve point set P by using a jacobian coordinate system; S3, extracting Z coordinates of all points in the calculation result set R, constructing a Z coordinate set, and constructing a multiplication tree according to the Z coordinate set ; S4, multiplying tree Performing modular inversion operation on the root node value to obtain a modular inversion element of the root node, and constructing an inversion element tree from top to bottom based on the modular inversion element of the root node ; S5, based on inverse element tree And (3) carrying out batch conversion on the jacobian coordinates, and converting the calculation result set from the jacobian coordinates to affine coordinates.
2. The optimized jacobian coordinate transformation-based elliptic curve batch scalar multiplication acceleration method according to claim 1, wherein the building multiplication tree Includes using n Z coordinates as leaf nodes and storing them in order in array The method comprises the steps of carrying out modular multiplication operation on two adjacent leaf nodes to obtain n/2 father nodes, repeating the processes of storing the nodes and carrying out modular multiplication operation, constructing upwards layer by layer to finally obtain root nodes, and completing the construction of multiplication trees.
3. The optimized jacobian coordinate transformation-based elliptic curve batch scalar multiplication acceleration method according to claim 1, wherein the pair of multiplication trees And (3) performing modular inverse operation on the root node value of the tree, and adopting an extended Euclidean algorithm.
4. The optimized jacobian coordinate transformation-based elliptic curve batch scalar multiplication acceleration method according to claim 1, wherein the top-down construction of an inverse tree The method comprises starting from a root node, calculating the starting position of a current layer for each layer, positioning the brother node of the current node for each node of the layer through exclusive OR operation, and calculating that the inverse value of the current node is equal to that of the parent node inverse and the brother node And (3) updating the hierarchical parameters to continue the calculation of the next layer until all leaf nodes are calculated, storing the leaf nodes and completing the construction of the inverse tree.
5. The method for accelerating the batch scalar multiplication of elliptic curves based on optimized jacobian coordinate conversion according to claim 1, wherein the batch conversion of jacobian coordinates comprises: s51, from the inverse meta tree Acquisition of Is the modulus inverse of (2) ; S52, calculating affine coordinate x components respectively And affine coordinate y component ; S53, pair And Normalization processing is carried out, and the converted affine coordinates are processed And storing the result array.
6. The optimized jacobian coordinate conversion-based elliptic curve batch scalar multiplication acceleration method according to claim 1, wherein the number of Z coordinate sets is not a power of 2.
7. The optimized jacobian coordinate transformation-based elliptic curve batch scalar multiplication acceleration method according to claim 6, wherein a multiplication tree is constructed Includes using n Z coordinates as leaf nodes and storing them in array in order The method comprises the steps of carrying out modular multiplication operation on two adjacent leaf nodes to obtain n/2 father nodes, repeating the processes of storing the nodes and carrying out modular multiplication operation, adding a node with a value of 1 at the tail of a current layer when the number of the leaf nodes of the current layer cannot be divided by 2, constructing upwards layer by layer to finally obtain a root node, and completing construction of a multiplication tree.
8. The optimized jacobian coordinate transformation-based elliptic curve batch scalar multiplication acceleration method according to claim 1, wherein the multiplication tree And inverse element tree Sharing the same memory array, inverse meta tree The construction process of the system adopts an in-situ coverage mode, and only leaf nodes are reserved in the process of batch coordinate conversion.
9. The method for accelerating the batch scalar multiplication of elliptic curves based on optimized jacobian coordinate transformation according to claim 1, wherein the generating a scalar set K and an elliptic curve point set P to be processed, and the relationship between the scalar set K and the elliptic curve point set P includes: The type I is that different scalars correspond to different elliptic curve points and are marked as batch variable point scalar multiplication; The second type is that different scalars correspond to the same elliptic curve points and are marked as batch fixed base point scalar multiplication; The same scalar corresponds to different elliptic curve points and is marked as batch fixed scalar point multiplication; when executing batch scalar multiplication operations, different optimization strategies are adopted according to different types.
10. The method of elliptic curve batch scalar multiplication acceleration based on optimized jacobian coordinate conversion of claim 9, wherein the different optimization strategies include: for type one, a standard binary expansion or windowing method is used for each scalar Performing decomposition and respectively calculating ; For the type II, pre-calculating the fixed base point P to construct a pre-calculation table storage Of (2), wherein Index representing window size correlation, accelerating scalar multiplication computation using a pre-computation table; for type three, a fixed scalar k is binary extended and calculated simultaneously by a point-add operation , ,..., 。

Description

Elliptic curve batch scalar multiplication acceleration method based on optimized Jacobian coordinate conversion Technical Field The application relates to the field of electric digital data processing, in particular to an elliptic curve batch scalar multiplication acceleration method based on optimized Jacobian coordinate conversion. Background Elliptic Curve Cryptography (ECC) has become a core technology of modern cryptosystems due to its high security and short key length. Elliptic curve scalar multiplication is used as the most basic and computationally intensive operation in ECC, whose efficiency directly affects the performance of the overall cryptosystem. The prior art generally uses a projective coordinate system (e.g., jacobian coordinates) to represent points on an elliptic curve to avoid frequent modulo inversion operations. However, in a batch scalar multiplication scenario, it is ultimately necessary to convert the result from projective coordinates back to affine coordinates. Coordinate transformation generally requires performing modulo inversion operation on each point separately, and the computational complexity of modulo inversion operation is much higher than that of modulo multiplication, which becomes a key bottleneck limiting the performance of batch scalar multiplication. How to combine efficient scalar multiplication algorithm and optimize the conversion process from jacobian coordinates to affine coordinates is a technical problem to be solved in the art. Disclosure of Invention In view of the above, the application discloses an elliptic curve batch scalar multiplication acceleration method based on optimized jacobian coordinate transformation, so as to solve the problems in the prior art, comprising the following steps: S1, generating a scalar set K to be processed and an elliptic curve point set P; S2, performing batch scalar multiplication operation on the scalar set K and the elliptic curve point set P by using a jacobian coordinate system; S3, extracting Z coordinates of all points in the calculation result set R, constructing a Z coordinate set, and constructing a multiplication tree according to the Z coordinate set ; S4, multiplying treePerforming modular inversion operation on the root node value to obtain a modular inversion element of the root node, and constructing an inversion element tree from top to bottom based on the modular inversion element of the root node; S5, based on inverse element treeAnd (3) carrying out batch conversion on the jacobian coordinates, and converting the calculation result set from the jacobian coordinates to affine coordinates. The beneficial effects of the application include: Through the rapid batch jacobian coordinate to affine coordinate conversion based on the tree Montgomery skill, n times of modular inversion operation is optimized into 1 time of modular inversion operation and 3n-3 times of modular multiplication operation, compared with the traditional coordinate conversion method, the coordinate conversion efficiency is improved by 93.3% under the scale of n=2 7, the efficiency is still improved by 94.2% under the scale of n=2 20, the optimization is not limited by the batch scale, and the applicability is wide; A flexible tree construction strategy is designed, and any number of batch operations are supported by adding filling nodes with the value of 1, so that the method designed by the application is not limited by the power of 2; Designs a corresponding shared storage array strategy to make the multiplication tree And inverse element treeThe same storage space is shared, only necessary leaf nodes are reserved in the coordinate conversion stage, the space complexity is optimized to O (n), and the memory optimization design is particularly suitable for embedded systems with limited resources and large-scale password operation scenes; The method designed by the application can be directly applied to various elliptic curve cryptography application scenes such as Exp-ElGamal encryption, ECDSA signature verification, ECDH-PSI privacy set intersection and the like, wherein homomorphic addition efficiency is improved by 81.75-89.03% in an Exp-ElGamal scheme, ciphertext multiplication efficiency is improved by 8.94-13.82%, verification efficiency is improved by 12.68-21.8% in ECDSA batch verification, overall efficiency is improved by 7.21-11.09% in an ECDH-PSI scheme, actual performance of a cryptography system is remarkably improved, and important engineering application value is realized; A design concept is provided for those skilled in the art. Drawings FIG. 1 is a schematic diagram of a flow of an elliptic curve batch scalar multiplication acceleration method in an embodiment of the present application; FIG. 2 is a multiplication tree in an embodiment of the application And inverse element treeA schematic of the construction; FIG. 3 is a non-2 power multiplication tree in an embodiment of the application And inverse element treeSc