Abstract:
A scheduling method for ECC computation processed in a plurality of arithmetic units comprises a coarse-grained scheduling step for systematically scheduling an ECC computation operation and a fine-grained scheduling step for refining the scheduled ECC computation operation.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    (A) Field of the Invention 
         [0002]    The present invention relates to a scheduling method, and more particularly, to a method for scheduling an elliptic curve cryptography (ECC) computation process. 
         [0003]    (B) Description of the Related Art 
         [0004]    As the demand for wired and wireless communication explodes, data security has become an urgent issue for modern vital applications such as financial services, private and healthcare information, personal identification, confidential communication and storage, etc. Among various data security schemes, the public key cryptosystem is robust and effective for secure data transaction and messaging. The robustness typically relies on the difficulty of integer factorization or on finding a discrete logarithm in a finite field. 
         [0005]    However, the crucial challenge to implementation of the most popular public-key cryptosystem, RSA cryptography, is the rapid growth of the key length. Therefore, another cryptosystem, ECC, which is based on point operations on elliptic curves over a finite field, either the prime field GF(p) or the binary field GF(2 m ), has recently been considered as an attractive alternative to RSA. ECC is regarded as mature with higher security with the same key size as that used by most of the traditional public-key cryptosystem. 
         [0006]    Among the proposed ECC improvements and architectures, some propose new projective coordinates to effectively reduce the complexity of the elliptic curve arithmetic over GF(2 m ). Others focus on improving the processing hardware such as introducing a programmable hardware accelerator to speed up point scalar multiplication for specific and generic curves over GF(2 m ), an FPGA co-processor using a special integer representation to implement point scalar multiplication, a scalable GF(p) ECC architecture with high-radix Montgomery multiplication, a parallel architecture with two multipliers for a specific curve, a low-cost GF(2 m ) coprocessor with RAM, and a 256-bit ECC processor over GF(p). Other proposed developments focus on improving the algorithm such as introducing an improved Karatsuba multiplication algorithm, a reordered partial multiplication sequence and a pipelined computation of scalar multiplication in the ECC cryptosystem. 
         [0007]    However, none of the aforesaid proposals focus on scheduling the ECC computation process. The scheduling method of the present invention not only schedules the ECC computation process, but also schedules via a plurality of arithmetic units (AU) such that the processing time is dramatically reduced. 
       SUMMARY OF THE INVENTION 
       [0008]    A scheduling method for ECC computation processed in a plurality of arithmetic units according to one embodiment of the present invention comprises the steps of: decomposing arithmetic operations of the ECC computation into atomic finite field operations; determining constraints of the atomic finite field operations, wherein the constraints include start times and required times of the atomic finite field operations, data precedence relation of the atomic finite field operations and the maximum number of operations in each stage of the ECC computation according to the number of the arithmetic units; and establishing the schedule of the ECC computation based on the integer linear programming technique by considering the constraints of the atomic finite field operations. 
         [0009]    In some embodiments of the present invention, an operand rescheduling technique is applied to the established schedule of the ECC computation after the aforesaid scheduling method is executed. 
         [0010]    In some embodiments of the present invention, an atomic rescheduling technique is applied to the established schedule of the ECC computation after the aforesaid scheduling method is executed. 
         [0011]    In some embodiments of the present invention, a loop folding technique is applied to the established schedule of the ECC computation after the aforesaid scheduling method is executed. 
         [0012]    A scheduling method for ECC computation processed in a plurality of arithmetic units according to another embodiment of the present invention comprises a coarse-grained scheduling step for systematically scheduling an ECC computation operation and a fine-grained scheduling step for refining the scheduled ECC computation operation. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0013]    The objectives and advantages of the present invention will become apparent upon reading the following description and upon reference to the accompanying drawings in which: 
           [0014]      FIG. 1  shows the flow chart of a scheduling method for ECC computation according to embodiments of the present invention; 
           [0015]      FIG. 2  shows a plurality of atomic finite field operations according to an embodiment of the present invention; 
           [0016]      FIG. 3  shows the precedence relation of a plurality of atomic finite field operations according to an embodiment of the present invention; 
           [0017]      FIG. 4  shows the start times and required times of a plurality of atomic finite field operations according to an embodiment of the present invention; 
           [0018]      FIG. 5  shows the equations of a second constraint according to an embodiment of the present invention; 
           [0019]      FIG. 6  shows the equations of a third constraint according to an embodiment of the present invention; 
           [0020]      FIG. 7  shows a scheduled result according to an embodiment of the present invention; 
           [0021]      FIG. 8  shows the flow chart of another scheduling method for ECC computation according to embodiments of the present invention; 
           [0022]      FIG. 9  shows another scheduled result according to an embodiment of the present invention; 
           [0023]      FIG. 10  shows another scheduled result according to an embodiment of the present invention; and 
           [0024]      FIG. 11  shows another scheduled result according to an embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0025]    Embodiments of the present invention will now be described more fully with reference to the accompanying drawings. The present invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the present invention to those skilled in the art. 
         [0026]      FIG. 1  shows the flow chart of a scheduling method for ECC computation according to embodiments of the present invention. In step  101 , arithmetic operations of the ECC computation are decomposed into atomic finite field operations. In Step  102 , the data precedence relation between the atomic finite field operations is established. In Step  103 , the start times and the required times of each atomic finite field operation are calculated. In Step  104 , constraints of the atomic finite field operations such as the start times and required times, the data precedence relation and the maximum number of operations in each stage of the ECC computation according to the number of the arithmetic units are determined. In Step  105 , the ECC computation is scheduled based on the integer linear programming (ILP) technique by considering the constraints of the atomic finite field operations. In Step  106 , the number of stages in the schedule is checked. If the number of stages in the schedule exceeds a threshold value, Step  107  is executed. Otherwise, the scheduling process is finished. In Step  107 , the number of the arithmetic units is increased, and Step  104  is executed. 
         [0027]    In one embodiment of the present invention, a part of the elliptic curve point arithmetic over GF(p) of the ECC computation is listed as follows: 
         [0000]        x   2   =p −( x   0   z   1   2   +x   1   z   0   2 )( x   0   z   1   2   −x   1   z   0   2 ) 2 , and  z   2   =z   0   z   1 ( x   0   z   1   2   −x   1   z   0   2 ). 
         [0028]    Following Step  101  in  FIG. 1 , these two arithmetic operations are decomposed into eleven atomic finite field operations o i , 1≦i≦11, as shown in  FIG. 2 . Following Step  102 , the data precedence relation is established as shown in  FIG. 3  according to the atomic finite field operations. Following Step  103 , the start times and the required times of each atomic finite field operation are calculated as shown in  FIG. 4  according to the data precedence relation. For example, operation o 2  should not be started before the second stage and should be finished no later than the sixth stage. It can be seen that in this embodiment, the finite field addition and subtraction are omitted during the scheduling procedure since they serve minor roles compared with the multiplication operations. That is, o 5 , o 6  and o 11  are omitted as shown in  FIG. 4 , while the data precedence relation is still maintained. Following Step  104 , constraints of the atomic finite field operations are determined. The first constraint, also shown in  FIG. 4 , describes the stages of each atomic finite field operation to be executed, and is shown as follows: 
         [0000]    
       
         
           
             
               
                 
                   ∑ 
                   
                     j 
                     = 
                     
                       s 
                       i 
                     
                   
                   
                     r 
                     i 
                   
                 
                  
                 
                   x 
                   
                     i 
                     , 
                     j 
                   
                 
               
               = 
               1 
             
             , 
             
               ∀ 
               
                 1 
                 ≤ 
                 i 
                 ≤ 
                 n 
               
             
             , 
           
         
       
     
         [0000]    where s i  denotes the start time, or the start stage, r i  denotes the required time, x i,j  is a zero-one variable, and n is the number of the atomic finite field operations, which is 11 as shown in  FIG. 2 . That is, if o i  is scheduled in stage m, then x i,m =1 and x i,j =0 for j≠m. 
         [0029]    The second constraint ensures that the data precedence relations are preserved, and is shown as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       j 
                       = 
                       
                         s 
                         i 
                       
                     
                     
                       r 
                       i 
                     
                   
                    
                   
                     ( 
                     
                       j 
                       × 
                       
                         x 
                         
                           i 
                           , 
                           j 
                         
                       
                     
                     ) 
                   
                 
                 - 
                 
                   
                     ∑ 
                     
                       j 
                       = 
                       
                         s 
                         k 
                       
                     
                     
                       r 
                       i 
                     
                   
                    
                   
                     ( 
                     
                       j 
                       × 
                       
                         x 
                         
                           k 
                           , 
                           j 
                         
                       
                     
                     ) 
                   
                 
               
               ≤ 
               
                 - 
                 K 
               
             
             , 
             
               ∀ 
               
                 
                   o 
                   i 
                 
                 → 
                 
                   o 
                   k 
                 
               
             
             , 
           
         
       
     
         [0000]    where K is the number of stages required for executing o i . In this embodiment, each operation takes one stage and therefore K is assigned as 1.  FIG. 5  shows the equations according to the second constraint. Taking the first equation in  FIG. 5  for example, 
         [0000]    
       
         
           
             
               
                 
                   ∑ 
                   
                     j 
                     = 
                     1 
                   
                   5 
                 
                  
                 
                   ( 
                   
                     j 
                     × 
                     
                       x 
                       
                         1 
                         , 
                         j 
                       
                     
                   
                   ) 
                 
               
               - 
               
                 
                   ∑ 
                   
                     j 
                     = 
                     2 
                   
                   6 
                 
                  
                 
                   ( 
                   
                     j 
                     × 
                     
                       x 
                       
                         2 
                         , 
                         j 
                       
                     
                   
                   ) 
                 
               
             
             ≤ 
             
               - 
               1 
             
           
         
       
     
         [0000]    indicates that o 1  should be executed before o 2  for at least one stage ahead. 
         [0030]    The third constraint describes the number of operations in each stage of the ECC computation according to the number of arithmetic units, and is shown as follows: 
         [0000]    
       
         
           
             
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                   x 
                   
                     i 
                     , 
                     j 
                   
                 
               
               ≤ 
               
                 
                   N 
                   
                     au 
                     , 
                   
                 
                  
                 
                   ∀ 
                   
                     1 
                     ≤ 
                     j 
                     ≤ 
                     
                       N 
                       s 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where N au  denotes the number of arithmetic units and N s  denotes the number of stages after the scheduling.  FIG. 6  shows the equations according to the third constraint. 
         [0031]    Following Step  105 , the ECC computation is scheduled based on the ILP technique based on the constraint equations shown above, wherein the initial N au  is 1. After the scheduled process, eight stages are required to perform the ECC computation, while the threshold in Step  106  is 4. Therefore, N au  is incremented to 2, and Steps  104  to  106  are re-executed.  FIG. 7  shows the scheduled result based on the ILP technique for N au  being 2. As can be seen in  FIG. 7 , the total required stages is 4, the number of stages does not exceed the threshold value, and the omitted finite field addition and subtraction operations are inserted back into the schedule. 
         [0032]    In some embodiments of the present invention, after performing the scheduling method shown in  FIG. 1 , the ECC computation is further refined by utilizing other scheduling methods.  FIG. 8  shows a flow chart of another scheduling method for ECC computation according to embodiments of the present invention. In Step  801 , the operand rescheduling technique is performed. That is, each atomic finite field operation is checked to determine whether it can be combined with the following atomic finite field operation to further reduce redundant operations. In Step  802 , the atomic rescheduling technique is performed. That is, each atomic finite field operation is checked to determine whether it can be shifted to another stage and executed by another arithmetic unit to further reduce the number of stages required by the ECC computation. In Step  803 , the loop folding technique is performed. That is, each atomic finite field operation is checked to determine whether it can be shifted to the same stage and executed by another arithmetic unit in a different iteration to further reduce the number of stages required by the ECC computation. 
         [0033]      FIG. 9  shows a scheduled result of an ECC computation after performing the scheduling method shown in  FIG. 1  according to another embodiment of the present invention. The ECC computation is based on the standardized elliptic curve over GF(p) as follows y 2 =x 3 +αx+β, where x, y∈GF(p) and β≠0. Following Step  801 , the operand rescheduling technique is performed. As shown in  FIG. 9 , the first arithmetic unit in the last stage produces 2y 2 , wherein the result y 2  is then substituted as y 0  in the next iteration. From the scheduled result shown in  FIG. 9 , it can be deduced that since p 3 =y 0   2 , p 6 =x 0 p 3  and s=4p 6 , then s=4x 0 y 0   2 =x 0 (2y 0 ) 2 . Therefore, 2y 2  is substituted as y 0  in the next iteration instead of dividing 2y 2  by 2 to produce y 2  in the last stage, and the operation of multiplying by 4 as indicated by s=4P 6  can be omitted. 
         [0034]      FIG. 10  shows a scheduled result of an ECC computation after performing the scheduling method shown in  FIG. 1  according to another embodiment of the present invention. The ECC computation is based on the standardized elliptic curve over GF(2 m ) as follows y 2 +xy=x 3 +αx 2 +β, where x, y∈GF(2 m ) and β≠0. Following Step  802 , the atomic rescheduling technique is performed. As shown in  FIG. 10 , the first arithmetic unit in the fifth stage executes the operations of P 8 =p 5 z q  and y q =p 7 +p 8 , while the second arithmetic unit is idle in the fourth stage. Therefore, the operations of the production of p 8  and y q  are shifted from the fifth stage by the first arithmetic unit to the fourth stage by the second arithmetic unit, while the precedence relation remains the same. It can be seen that the number of stages is reduced from 5 to 4 after the atomic rescheduling technique is performed. 
         [0035]    Following the scheduling result of  FIG. 10 , Step  803  is executed to further reduce the amount of stages of the ECC computation. As shown in 
         [0036]      FIG. 10 , the third and fourth arithmetic units are idled in the first stage and the fourth stage. Therefore, after executing Step  803 , the operations in the first stage by the first and second arithmetic units are shifted to the third and fourth arithmetic units, as shown in  FIG. 11 . That is, two consecutive iterations, such as the operations in the fourth stage by the first and second arithmetic units in the current iteration and the operations in the first stage by the third and fourth arithmetic units in the next iteration, can be overlapped in one stage. It can be seen that the effective number of stages for one iteration is reduced from 4 to 3 after the loop folding technique is performed. 
         [0037]    In conclusion, the scheduling methods according to embodiments of the present invention schedule the ECC computation process via a plurality of arithmetic units such that the ECC arithmetic over both GF(p) and GF(2 m ) are both optimized. In addition, in some embodiments of the present invention, a coarse-grained scheduling method, such as the method shown in  FIG. 1 , is first applied to an ECC computation operation. Afterward, a fine-grained scheduling method, such as the method shown in  FIG. 8 , is further applied to and refines the scheduled ECC computation operation. 
         [0038]    The above-described embodiments of the present invention are intended to be illustrative only. Those skilled in the art may devise numerous alternative embodiments without departing from the scope of the following claims.