CN104468100A - Improved sliding window modular exponentiation computing method - Google Patents

Abstract

The present invention relates to the fields of cryptography and information security. In order to propose a pre-calculation method for improving efficiency, which can effectively reduce the computational complexity of the sliding window algorithm, the technical solution adopted by the present invention is to improve the sliding window modular exponentiation calculation The method includes the following steps: firstly, a maximum window length d needs to be determined, and the window is defined as a group that divides numbers by bits, and the number of bits in each group is not greater than d, and then according to a specific strategy, the index e is divided into zero windows and non- Zero window; when the scanning index encounters a zero window during calculation, the modular square operation is performed, and when a non-zero window is encountered, the modular square operation is performed first, and then the corresponding modular exponent value is obtained from the pre-calculated storage value to perform the modular multiplication operation. The invention is mainly applied to data processing and confidential communication.

Description

An Improved Calculation Method of Modular Exponentiation with Sliding Window

technical field

The invention relates to the fields of cryptography and information security; it is mainly used for improving the calculation efficiency of large number modular power calculation in the public key cryptosystem. Specifically, it relates to an improved sliding window modular exponentiation calculation method.

technical background

Public key cryptosystem is a kind of cryptosystem widely used at present. In information system security, especially in digital signature, authentication and key distribution and management, public key cryptography plays an essential role. The emergence of public key cryptography stems from two problems in symmetric cryptography. The first is the distribution of keys. Symmetric cryptography requires both communication parties to share the same key and a key distribution center. The second is the issue of digital signatures. Diffie and Hellman came up with an idea in 1976 that was fundamentally different from all previous cryptosystems.

Public-key cryptography is an asymmetric cryptography that relies on an encryption key and a different decryption key. A complete public key cryptosystem encryption and decryption process roughly includes six elements: public key, private key, encryption algorithm, decryption algorithm, plaintext, and ciphertext.

In this cryptographic system, all users can obtain the public keys of other users, and each user generates and retains a private key without sharing it with a specific user. Users keep their private keys safe, so the exchange of information is safe. Users can change the private key at any time, and only need to distribute the public key generated with the replacement to replace the old public key.

The new cryptographic idea proposed by Diffie and Hellman has led cryptographers to propose many algorithms to satisfy the properties of public key cryptosystem, but many of them are unsound. In 1977, three scientists at MIT, Ron Rivest, Adi Shamir, and Len Adleman, proposed an algorithm named after their initials, the RSA algorithm, and published it in 1978. The RSA algorithm is one of the most widely used public key cryptography schemes at present, and it is also the first algorithm that can be used for both information encryption, decryption and digital signature. The security of the RSA algorithm is based on the fact that it is very easy to calculate the product of two large prime numbers, but it is very difficult to factorize the product of two large prime numbers. That is, if a large number contains only two large prime factors, it will be very difficult to factorize it. However, due to the complexity and slow speed of the modular exponentiation calculation in the encryption and decryption of the public key cryptography, the speed of the encryption and decryption algorithm of the public key cryptography mainly depends on the efficiency of the modular exponentiation and modular multiplication algorithms, which makes the modular exponentiation algorithm Computational efficiency has become the bottleneck of public-key cryptosystems, so how to implement fast modular exponentiation algorithms is a common concern in the field of cryptography.

The research object of modular exponentiation is: assuming that N, M, and e are all k-bit binary integers, and when k is very large (such as k>256), fast calculation:

C＝M ^e mod N (1)

Equation (1) is generally transformed into a series of modular multiplication and modular square calculations. If calculating M ¹⁵ , you can pass the sequence:

M→ ^M2 → ^M3 → ^M4 → ^M5 →… ^M15

calculated. Obviously, the efficiency of this calculation method is very low. Therefore, research on the accelerated implementation of large integer modular exponentiation and modular multiplication algorithms has important theoretical significance and practical value.

In practical applications, the RSA algorithm is widely used in the encryption and decryption of emails. The email system automatically assigns a pair of key pairs (e ₁ , e ₂ ) to each user, where e ₁ is the user’s public key and e ₂ is the user’s private key, and then the system publishes the public key. And keep the private key properly. When user B sends an email to user A, the plaintext M of the email is encrypted by user A's public key e ₁ to obtain ciphertext C, and the ciphertext C is sent out. Due to the nature of the RSA encryption algorithm, the ciphertext C can only be decrypted by user A who has the corresponding private key, thus ensuring the security and privacy of the email.

The specific process is as follows:

(1) Encryption process: Let M be the original email content, _e1 be the public key of user A, and N be the modulus uniformly stipulated by the system, then user B can obtain the ciphertext C by calculating M ^e1 mod N;

(2) Decryption process: After receiving the ciphertext C, user A uses his own private key e ₂ to perform modular exponentiation calculation with N specified by the system: C ^e2 mod N, to obtain plaintext M.

Contents of the invention

In order to overcome the deficiencies of the prior art, a pre-calculation method for improving efficiency is proposed, which can effectively reduce the computational complexity of the sliding window algorithm. For this reason, the technical solution adopted by the present invention is that the improved sliding window modular exponentiation calculation method includes The following steps are as follows: First, a maximum window length d needs to be determined. The window is defined as a group that divides numbers by bits. The number of bits in each group is not greater than d. Then, according to the specific strategy, the index e is divided into zero windows and non-zero windows; When the scanning index encounters a zero window during calculation, the modular square operation is performed, and when a non-zero window is encountered, the modular square operation is performed first, and then the corresponding modular exponent value is obtained from the pre-calculated storage value to perform the modular multiplication operation; among them, the sliding window method is given. The window division strategy is specifically: use ZW to represent a zero window, NW to represent a non-zero window, and set the window length to d:

The initial state S is ZW:

When S=ZW, scan the first bit, if 0, belong to ZW, S=ZW; if 1, belong to new NW, S=NW;

When S=NW, scan d-1 bits, set this NW to end at the last non-zero bit as i bit, the i+1 to d-1 bits of this scan belong to ZW, S=ZW.

The improved sliding window modular power calculation method is further refined as:

Input: M, e, n, d;

Output: C = M ^e mod n;

Among them, M represents the message to be sent, expressed in binary numbers, e represents the exponent, n represents the modulus, d represents the maximum length of the sliding window, C is the calculation result, and mod represents the modulo operation, that is, the remainder obtained by dividing Me by n ;

(1) Set the maximum length of the sliding window to d;

(2) Divide the index e from left to right according to the following strategy:

(2.1) The initial state S is represented by ZW for the zero window state, and NW for the non-zero window state;

(2.2) When S=ZW, scan 1 bit, if 0, belong to ZW, S=ZW; If 1, belong to new NW, S=NW;

(2.3) When S=NW, scan d-1 bits backward, and trace back to the first non-zero bit, set it as i, return the 1st bit to the i-th bit (including i) of this scan into the current NW, the i+1 to d-1 bits are classified into ZW, S=ZW;

(2.4) Loop (2.2) and (2.3) until all bits of the exponent e are scanned, and finally get non-zero windows F ₁ , F ₂ ,…,F _s , and zero windows Z ₁ , Z ₂ ,…,Z _k , where s indicates the number of scanned non-zero windows, and k indicates the number of scanned zero windows;

(3) Precompute the non-zero window according to the following strategy to obtain the addition chain:

(3.1) Arrange F ₁ , F ₂ ,...,F _s in ascending order and record each value only once, and obtain the sequence W ₀ =w ₀₁ ,w ₀₂ ,...,w _0i ;

(3.2) save a ₀ =w _0i , calculate t ₀ =w _0i -w _0i-1 ;

If t ₀ has appeared in W ₀ or t ₀ =1, then delete w _0i in W ₀ to obtain W ₁ =w ₀₁ ,w ₀₂ ,...,w _0i-1 ;

Otherwise, replace w _0i with t ₀ in W ₀ to get W ₁ =w ₀₁ ,w ₀₂ ,...,w _0i-1 ,t ₀ ;

(3.3) The W _i-1 sequence obtained in the previous step is used as input, and steps (3.1)-(3.2) are repeated until only one element w _i1 remains in W _i ;

(3.4) Use any computationally feasible method to find an addition chain of w _i1 to get a _i , a _i+1 ,..., a _s ;

(3.5) Arrange A=a ₀ , a ₁ ,..., a _s in ascending order;

(4) Use the addition chain A=a ₀ ,a ₁ , _... ,as to calculate the value of M ^Fi , where F _i is a non-zero window, i=1,2,...,s;

(5) Initial C=M ^F1 , i loops from 2 to s:

(5.1) C = (C*M ^Fi ) mod n;

(6) For zero windows Z ₁ , Z ₂ ,…, Z _k , loop i from 1 to k:

(6.1) C=C ^Ei mod n, where E _i =2 ^Li , _Li is the length of the window F _i ;

(7) Output ciphertext C.

As the length of the index increases, the length of the sliding window should also increase accordingly to obtain better computational efficiency; when the length of the index is 3, the length of the sliding window should be 4 bits, and when the length of the index increases to 1024, the length of the sliding window 6 is selected, and when the index length is 4096, the sliding window length is 7.

Compared with prior art, technical characteristic and effect of the present invention:

Based on the traditional sliding window method, the present invention realizes high-efficiency modular exponentiation calculation through window selection strategy and pre-calculation improvement, and can effectively improve the operating efficiency of large-number modular exponentiation calculation.

Description of drawings

The two flowcharts on the left and right of Fig. 1 are respectively the process of using the method of the present invention to perform public key encryption and decryption, wherein the left figure is the encryption process, and the right figure is the decryption process. The characters next to the arrows in the figure indicate the output of the previous process and the input of the next process.

Detailed ways

The sliding window method first needs to determine a maximum window length d, and then divides the index e into a zero window and a non-zero window F _i according to a specific strategy. The sliding window method divides the index into zero windows and non-zero windows F _i with different lengths according to different strategies. During calculation, when the scanning index encounters a zero window, the modular square operation is performed. When a non-zero window is encountered, the modular square operation is performed first, and then Obtain the corresponding modular power value from the pre-calculated storage value to perform the modular multiplication operation.

First, the window division strategy of the sliding window method is given, ZW is used to represent the zero window, NW is used to represent the non-zero window, and the window length is set to d:

Strategy sliding window method:

The initial state S is ZW:

When S=ZW, scan 1 bit, if 0, classify into ZW, S=ZW; if 1, classify into new NW, S=NW.

When S=NW, scan d-1 bits backward, and trace back to the first non-zero bit, set it as i, and classify the 1st bit to the i-th bit (including i) of this scan into the current NW, put i+1 to d-1 into the new ZW, S=ZW;

Perform the above steps in a loop until all bits of the exponent e are scanned, and finally obtain the window F ₁ , F ₂ ,...,F _s ;

Example 1: Utilize this strategy, scan and divide e=(111010100100101) from left to right, make the window length d=4, then divide as follows:

e=111 0 101 00 1001 0 1.

Combined with this strategy, the algorithm of the sliding window method is expressed as follows:

Second, is the improvement of precomputation. In Algorithm 1, the precomputation is step (1), and M ^w mod n is calculated, w=3,5,...,2 ^d -1, and its computational complexity is 2 ^d-1 . However, to determine the optimal window size for any index with a given number of digits, it is usually necessary to collect large-scale samples, that is, the traditional brute force search method; or to test one by one within a certain range. Both are quite resource intensive. On the other hand, when the window size d is too large, the amount of pre-computation increases exponentially, and the pre-computation results may not be fully utilized, resulting in waste of resources. The invention provides a pre-computing method using the addition sequence idea, so that the pre-calculated results can be fully utilized. Its main idea is to remove the repeated values in the non-zero windows F ₁ , F ₂ ,...,F _s , so as to transform the problem into an additive sequence of non-zero window values, that is to say, to find a sequence that passes through all given values. Addition chain. If the sequence S=(a ₀ ,a ₁ ,…,as ₎ satisfies the following properties, then S is called an addition chain of e(e=a _s ):

(1) S is a monotonically increasing sequence;

(2) a ₀ =1, a _s =e;

(3) a _i =a _j +a _k , 0≤j≤k<i≤s.

The algorithm is expressed as follows:

The A calculated by Algorithm 2 is an addition chain including all non-zero window values. Afterwards, M ^ai is sequentially calculated according to A, i=0, 1, .

Example 2: Select window length d=6, input F ₁ ,...,F _s =19,7,21,61,35,7,35,47,35,55.

(1) Arrange the F ₁ , F ₂ ,..., F _i sequences in ascending order, and record the repeated value only once, and get W ₀ =7, 19, 21, 35, 47, 55, 61;

(2) a ₀ =61, t ₀ =61-55=6;

(3) replace 61 with 6, and arrange in ascending order to obtain W ₁ =6,7,19,21,35,47,55;

(4) Repeat (1)-(3) steps:

After the 1st loop:

W ₁ =6,7,19,21,35,47,55, A=61;

After the 2nd loop:

W ₂ =6,7,8,19,21,35,47, A=61,55;

After the 3rd loop:

W ₃ =6,7,8,12,19,21,35, A=61,55,47;

…

After the 13th loop:

W ₁₃ = 2, A = 61, 55, 47, 35, 21, 19, 14, 12, 8, 7, 6, 5, 4;

(5) The last addition chain is 1, 2, added to A;

(6) Arranged in ascending order to get:

A=1,2,4,5,6,7,8,12,14,19,21,35,47,55,61;

(7) Return to A.

A total of 14 calculations are required to calculate all non-zero window values according to the addition chain A, while the traditional method needs to calculate all the values, a total of 2 ^{6 −1} =32 calculations.

Let’s analyze the effect of this method through experiments, select 512-bit, 1024-bit, 2048-bit, and 4096-bit indices for comparison, and select shorter 3-bit, 6-bit, 7-bit, 8-bit and longer 12-bit There are 7 window lengths. The 1,000,000 randomly generated numbers for each unit are divided to obtain various actual complexities, and the formula programming calculation is used to obtain various theoretical complexities. The experimental data are shown in Table 1 and Table 2.

In Table 1, BC represents the complexity of the binary method, WLEN represents the length of the leftmost window, NWIN represents the number of non-zero windows, OPRE represents the precomputation complexity of the traditional sliding window method, OC represents the total complexity of the traditional sliding window method, and APRE represents the improved method The precomputational complexity of , AC represents the total complexity of the improved method.

Table 1 Comparison between the improved method and the traditional sliding window method

Table 2 Pre-computation improvement percentage

bit length\d 3 6 7 8 12 512 0.00% 5.83% 30.58% 57.53% 96.09% 1024 0.00% 0.13% 10.53% 37.04% 93.92% 2048 0.00% 0.00% 0.65% 14.78% 90.54% 4096 0.00% 0.00% 0.00% 1.98% 84.25%

Experiments show that when the selected window length is smaller than the optimal window length, the efficiency of the improved method is equivalent to that of the traditional sliding window method; when the selected window length is greater than the optimal window length, it can be seen that the complexity of the improved method increases relatively slowly. However, the complexity of the traditional sliding window method increases exponentially. That is to say, when the optimal window length is unknown, the application of the improved method does not need to worry about the complexity skyrocketing caused by too large window selection.

Therefore, on the basis of the traditional sliding window method, the present invention realizes high-efficiency modular exponentiation calculation through the window selection strategy and the improvement of pre-computation, which can effectively improve the efficiency of large-number modular exponentiation calculation at runtime.

1. Selection of window length

In the experiment, exponents of 6 lengths of 128 bits, 256 bits, 512 bits, 1024 bits, 2048 bits, and 4096 bits were selected for comparison, and six window lengths of 3 to 8 bits were selected. Randomly generate 1,000,000 numbers for each unit and divide them to obtain the actual computational complexity. The experimental results are shown in the table below.

Table 3 The actual complexity of the sliding window method

d\ bit length 128 256 512 1024 2048 4096 3 161.19 321.19 641.18 1281.18 2561.17 5121.15 4 157.92 311.51 618.71 1233.11 2461.90 4919.50 5 160.72 310.05 608.72 1206.05 2400.72 4790.06 6 172.70 318.99 611.56 1196.70 2366.97 4707.52 7 201.44 345.44 633.44 1209.44 2361.44 4665.47 8 262.67 404.90 689.33 1258.24 2395.97 4671.53

It can be seen from the above table that as the length of the index increases, the length of the sliding window should also increase accordingly to obtain better computational efficiency. For example, when the exponent length is 3, the length of the sliding window should be 4 bits, and when the exponent length increases to 1024, the sliding window length is selected as 6, and when the exponent length is 4096, the sliding window length of 7 works best.

2. Implemented algorithm

Claims (3)

1. An improved sliding window modular exponentiation calculation method is characterized in that it comprises the following steps: at first it is necessary to determine a maximum window length d, and then according to a specific strategy, the index e is divided into zero window sequences Z ₁ ,..., Z _i and Non-zero window sequence F ₁ ,...,F _i ; when the scanning index encounters a zero window during calculation, the modular square operation is performed, and when a non-zero window is encountered, the modular square operation is performed first, and then the corresponding modular exponent value is obtained from the pre-calculated storage value. Modular multiplication operation; wherein, the window division strategy of the sliding window method is given as follows: use ZW to represent a zero window, NW to represent a non-zero window, and the window length is set to d: The initial state S is ZW: When S=ZW, scan the first bit, if 0, belong to ZW, S=ZW; if 1, belong to new NW, S=NW; When S=NW, scan d-1 bits, set this NW to end at the last non-zero bit as i bit, the i+1 to d-1 bits of this scan belong to ZW, S=ZW. 2. the improved sliding window modular power calculation method as claimed in claim 1, is characterized in that, described improved sliding window modular power calculation method is further refined as: Input: M, e, n, d; Output: C = M ^e mod n; Among them, M represents the message to be sent, expressed in binary numbers, e represents the exponent, n represents the modulus, d represents the maximum length of the sliding window, C is the calculation result, mod represents the modulus operation, that is, the result obtained by dividing M ^e by n remainder; (1) Set the maximum length of the sliding window to d; (2) Divide the index e from left to right according to the following strategy: (2.1) The initial state S is represented by ZW for the zero window state, and NW for the non-zero window state; (2.2) When S=ZW, scan 1 bit, if 0, belong to ZW, S=ZW; If 1, belong to new NW, S=NW; (2.3) When S=NW, scan d-1 bits backward, and trace back to the first non-zero bit, set it as i, return the 1st bit to the i-th bit (including i) of this scan into the current NW, the i+1 to d-1 bits are classified into ZW, S=ZW; (2.4) Loop (2.2) and (2.3) until all bits of the exponent e are scanned, and finally get non-zero windows F ₁ , F ₂ ,…,F _s , and zero windows Z ₁ , Z ₂ ,…,Z _k , where s indicates the number of scanned non-zero windows, and k indicates the number of scanned zero windows; (3) Precompute the non-zero window according to the following strategy to obtain the addition chain: (3.1) Arrange F ₁ , F ₂ ,...,F _s in ascending order and record each value only once, and obtain the sequence W ₀ =w ₀₁ ,w ₀₂ ,...,w _0i ; (3.2) save a ₀ =w _0i , calculate t ₀ =w _0i -w _0i-1 ; If t ₀ has appeared in W ₀ or t ₀ =1, then delete w _0i in W ₀ to obtain W ₁ =w ₀₁ ,w ₀₂ ,...,w _0i-1 ; Otherwise, replace w _0i with t ₀ in W ₀ to get W ₁ =w ₀₁ ,w ₀₂ ,...,w _0i-1 ,t ₀ ; (3.3) The W _i-1 sequence obtained in the previous step is used as input, and steps (3.1)-(3.2) are repeated until only one element W _i1 remains in W _i ; (3.4) Use any computationally feasible method to find an addition chain of w _i1 to get a _i , a _i+1 ,..., a _s ; (3.5) Arrange A=a ₀ , a ₁ ,..., a _s in ascending order; (4) Use the addition chain A=a ₀ ,a ₁ , _... ,as to calculate the value of M ^Fi , where F _i is a non-zero window, i=1,2,...,s; (5) Initial C=M ^F1 , i loops from 2 to s: (5.1) C = (C*M ^Fi ) mod n; (6) For zero windows Z ₁ , Z ₂ ,…, Z _k , loop i from 1 to k: (6.1) C=C ^Ei mod n, where E _i =2 ^Li , _Li is the length of the window F _i ; (7) Output ciphertext C. 3. the improved sliding window modular exponent calculation method as claimed in claim 2, is characterized in that, along with the increase of exponent length, the length of sliding window also should correspondingly increase to obtain better computational efficiency; When exponent length is 3 , the length of the sliding window should be 4 bits, and when the length of the index increases to 1024, the length of the sliding window is selected as 6, and when the length of the index is 4096, the length of the sliding window is 7.