Abstract:
A method of scalar multiplication for use in elliptic curve-based cryptosystems (ECC) is provided. Scalars are represented using a generic multibase form combined with the non-adjacency property, which greatly reduces the nonzero density in the representation. The method allows for flexibly selecting an unrestricted number of bases and their weight in the representation according to the particular characteristics of a setting, in such a way that computing costs are minimized. A simple, memory-friendly conversion process from binary to multibase representation and an inexpensive methodology to protect the multibase scalar multiplication against simple-side channel attacks are also provided.

Description:
TECHNICAL FIELD 
       [0001]    The present invention relates to security technology, specifically, it relates to the computation of elliptic curve scalar multiplication. 
       BACKGROUND 
       [0002]    Elliptic curve cryptosystems (ECC) are public-key cryptosystems that have attracted increasing attention in recent years due to their shorter key length requirement in comparison with other public-key cryptosystems such as RSA. 
         [0003]    Public-key cryptosystems make use of a pair of keys, called public and private keys, to perform cryptographic operations such as encryption/decryption of data and signing/verification of digital signatures. In particular for ECC, in some protocols private keys are scalar values that are kept in secret, and public keys are points on the elliptic curve that are made public. Given a secret scalar k and points P and kP on a elliptic curve, where kP is a multiple of the point P, the elliptic curve discrete logarithm problem (ECDLP) is defined as the problem of determining k, with P and kP known. The ECDLP problem is thought to be hard to solve, and the difficulty to solve it is precisely the security foundation of EC-based systems. 
         [0004]    ECC can be defined over different finite fields. Most important finite fields used to date to implement this cryptosystem have been binary, prime and extension fields. Finite fields are denoted by GF(q), where q is a prime power of the form p m  (p prime) and also represents the number of elements (order) of the field. If m=1, this field is referred to as prime field. If, otherwise, m≧2 then it is known as extension field. The particular case m=2 among extension fields is also known as binary field. 
         [0005]    For the case of prime fields, the generic equation to represent an elliptic curve is given by: 
         [0000]    
       
      
       E: y 
       2 
       =x 
       3 
       +ax+b,  
      
     
         [0000]    where: a,bεGF(p) and Δ=4a 3 +27b 2 ≢0(mod p) (Δ denotes the discriminant of the curve E). 
         [0006]    For the case of binary fields, the generic equation to represent an elliptic curve is given by: 
         [0000]    
       
      
       E: y 
       2 
       +xy=x 
       3 
       +ax 
       2 
       +b,  
      
     
         [0000]    where: a,bεGF(2 m ) and Δ=b≠0. 
         [0007]    Other variants of elliptic curve forms that also use prime, extended and/or binary fields can be found in the literature. Some examples are: Hessian and Jacobi forms, Edwards curves, Montgomery curves, elliptic curves of degree ⅔ isogenies, among others. 
         [0008]    The central and most time-consuming operation in ECC is scalar multiplication, which is generally represented by kP. This operation can be interpreted as the result of adding the point P to itself (i.e., P+P+ . . . +P) (k−1) times, where k is a scalar of very large value. Currently, a secure ECC system uses scalars with bit lengths in the range [160,512], where larger values provide higher security level. 
         [0009]    Another important aspect related to the deployment of a cryptosystem is its vulnerability to attacks exploiting side-channel information. 
         [0010]    Side-channel information, such as power dissipation and electromagnetic emission, leaked by real-world devices has been shown to be highly useful for revealing private keys and effectively breaking the otherwise mathematically-strong ECC cryptosystem. 
         [0011]    There are two main strategies to these attacks: simple (SSCA) and differential (DSCA) side-channel attacks. SSCA is based on the analysis of a single execution trace of a scalar multiplication to guess the secret key by revealing the sequence of operations used in the execution of ECC point arithmetic. 
         [0012]    Extensive research has been carried out to yield effective countermeasures to deal with SSCA. Among them, side-channel atomicity dissolves point operations into small homogenous blocks, known as atomic blocks, which cannot be distinguished from one another through simple side-channel analysis because each one contains the same pattern of basic field operations. Furthermore, atomic blocks are made sufficiently small to make this approach inexpensive. For example the structure M-A-N-A (field multiplication, addition, negation, addition) has been proposed to build SSCA-protected point operations over prime fields. 
         [0013]    However, the main drawback of the traditional M-A-N-A structure is that it relies on the assumption that field multiplication and squaring are indistinguishable from each other. In software implementations, timing and power consumption have been shown to be quite different for these operations, making them directly distinguishable through power analysis. Furthermore, from a performance viewpoint, the M-A-N-A structure is not optimal in several settings where the increased number of field additions that it requires becomes non-negligible. 
         [0014]    Nowadays, embedded computers dominate the marketplace. They are used in almost every new application requiring certain computing capabilities, especially in those involving consumer devices. A very important issue involves providing adequate security to these applications. However, this task seems to contrast with the effort by manufacturers of reducing product cost, size and power consumption. It is therefore a challenging task to make possible the implementation of cryptographic systems on these constrained devices. In particular for ECC, there is a need for accelerating the scalar multiplication without impacting memory and keeping it protected against side-channel attacks, in such a way that its implementation can be realized in the myriad of new devices with limited resources. 
       SUMMARY 
       [0015]    The disclosure provides a method for accelerating scalar multiplication by representing the scalar value with a short multibase representation. A method that converts any positive integer (scalar) to such representation without requiring additional memory resources is also provided. 
         [0016]    In accordance with the present disclosure there is provided a method of accelerating scalar multiplication in an elliptic curve-based cryptosystem by representing a scalar value with a multibase representation comprising the steps of: a) selecting a set of bases and corresponding set of window values for performing an ECC scalar multiplication; b) calculating precomputed values according to selected bases and window values wherein the precomputed values are points of a form d i P, where d i εD + \{0} and P is a point on a elliptic curve for which a ECC scalar multiplication kP is computed; c) determining a multibase representation of the selected scalar value; and d) scanning digits of the multibase representation from left to right until all the digits of the multibase representation are exhausted, performing a point operation of the form a j Q for every scanned digit with associated, base a j εA, and performing an additional point addition of a form Q=Q±d i P if a digit has nonzero value d i , where d i P is a point of the precomputed table and Q is a partial result of the scalar multiplication. 
         [0017]    In accordance with the present disclosure there is provided an apparatus for accelerating scalar multiplication in an elliptic curve-based cryptosystem by representing a scalar value with a multibase representation, the apparatus comprising: a memory; a processor for performing the steps of: a) selecting a set of bases and corresponding set of window values for performing an ECC scalar multiplication; b) calculating precomputed values according to selected bases and window values wherein the precomputed values are points of a form d i P, where d i εD + \{0} and P is a point on a elliptic curve for which a ECC scalar multiplication kP is computed; c) determining a multibase representation of the selected scalar value; and d) scanning digits of the multibase representation from left to right until all the digits of the multibase representation are exhausted, performing a point operation of the form a j Q for every scanned digit with associated base a j εA, and performing an additional point addition of a form Q=Q±d i P if a digit has nonzero value d i , where d i P is a point of the precomputed table and Q is a partial result of the scalar multiplication. 
         [0018]    In accordance with the present disclosure there is provided a computer readable medium containing instructions for accelerating scalar multiplication in an elliptic curve-based cryptosystem by representing a scalar value with a multibase representation, the instructions which when executed by a processor perform the steps of: a) selecting a set of bases and corresponding set of window values for performing an ECC scalar multiplication; b) calculating precomputed values according to selected bases and window values wherein the precomputed values are points of a form d i P, where d i εD + \{0} and P is a point on a elliptic curve for which a ECC scalar multiplication kP is computed; c) determining a multibase representation of the selected scalar value; and d) scanning digits of the multibase representation from left to right until all the digits of the multibase representation are exhausted, performing a point operation of the form a j Q for every scanned digit with associated base a j εA, and performing an additional point addition of a form Q=Q±d i P if a digit has nonzero value d i , where d i P is a point of the precomputed table and Q is a partial result of the scalar multiplication. 
         [0019]    The multibase representation may be of the form: 
         [0000]    
       
         
           
             
               k 
               = 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   m 
                 
                  
                 
                   
                     s 
                     i 
                   
                    
                   
                     
                       ∏ 
                       
                         j 
                         = 
                         1 
                       
                       J 
                     
                      
                     
                         
                     
                      
                     
                       a 
                       j 
                       
                         
                           c 
                           j 
                         
                          
                         
                           ( 
                           j 
                           ) 
                         
                       
                     
                   
                 
               
             
             , 
           
         
       
       
         
           
             where: positive prime integers a 1 ≠a 2 ≠ . . . ≠a J  are selected bases determining the set A={a 1 , . . . , a J }, global base a=a 1   w     1   a 2   w     2    . . . a J   w     J    is set using a selected window set Ω={w 1 , w 2 , . . . , w J }, where w j≧ 0 for 1≦j≦J,
           s i  are signed digits from the set D\{0}, s.t. |s i |≧1 and s i εD\{0}, where the digit set is given by:   
         
           
         
       
     
         [0000]    
       
         
           
             
               D 
               = 
               
                 
                   
                     { 
                     
                       0 
                       , 
                       
                         ± 
                         1 
                       
                       , 
                       
                         ± 
                         2 
                       
                       , 
                       … 
                        
                       
                           
                       
                       , 
                       
                         ± 
                         
                           ⌊ 
                           
                             
                               a 
                               - 
                               1 
                             
                             2 
                           
                           ⌋ 
                         
                       
                     
                     } 
                   
                    
                   \ 
                    
                   
                       
                   
                    
                   … 
                 
                  
                 
                     
                 
                  
                 … 
                  
                 
                     
                 
                  
                 
                   { 
                   
                     
                       
                         ± 
                         1 
                       
                        
                       
                           
                       
                        
                       
                         a 
                         1 
                       
                     
                     , 
                     
                       
                         ± 
                         2 
                       
                        
                       
                           
                       
                        
                       
                         a 
                         1 
                       
                     
                     , 
                     … 
                      
                     
                         
                     
                     , 
                     
                       
                         ± 
                         
                           ⌊ 
                           
                             
                               a 
                               - 
                               1 
                             
                             
                               2 
                                
                               
                                   
                               
                                
                               
                                 a 
                                 1 
                               
                             
                           
                           ⌋ 
                         
                       
                        
                       
                         a 
                         1 
                       
                     
                     , 
                     
                       
                         ± 
                         1 
                       
                        
                       
                           
                       
                        
                       
                         a 
                         2 
                       
                     
                     , 
                     
                       
                         ± 
                         2 
                       
                        
                       
                           
                       
                        
                       
                         a 
                         2 
                       
                     
                     , 
                     … 
                      
                     
                         
                     
                     , 
                     
                       
                         ± 
                         
                           ⌊ 
                           
                             
                               a 
                               - 
                               1 
                             
                             
                               2 
                                
                               
                                   
                               
                                
                               
                                 a 
                                 2 
                               
                             
                           
                           ⌋ 
                         
                       
                        
                       
                         a 
                         2 
                       
                     
                     , 
                     … 
                      
                     
                         
                     
                     , 
                     
                       
                         ± 
                         1 
                       
                        
                       
                           
                       
                        
                       
                         a 
                         J 
                       
                     
                     , 
                     
                       
                         ± 
                         2 
                       
                        
                       
                           
                       
                        
                       
                         a 
                         J 
                       
                     
                     , 
                     … 
                      
                     
                         
                     
                     , 
                     
                       
                         ± 
                         
                           ⌊ 
                           
                             
                               a 
                               - 
                               1 
                             
                             
                               2 
                                
                               
                                 a 
                                 J 
                               
                             
                           
                           ⌋ 
                         
                       
                        
                       
                         a 
                         J 
                       
                     
                   
                   } 
                 
               
             
             , 
           
         
       
       
         
           
             c i (j) are decreasing exponents, s.t. c i (j)≧c i+1 (j)+w j ≧w j  for 1≦i≦m−1 and each 1≦j≦J, and m is the length of the expansion. 
           
         
       
     
         [0023]    In addition there is provided for protecting scalar multiplication against simple side-channel attacks using atomic structures that offer higher security level and/or lower computational overhead. 
         [0024]    Other aspects and features will become apparent to those ordinarily skilled in the art upon review of the following description in conjunction with the accompanying figures. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0025]    Further features and advantages will become apparent from the following detailed description, taken in combination with the appended drawings, in which: 
           [0026]      FIG. 1  is a flow diagram for computing scalar multiplications using multibase-number representation; 
           [0027]      FIG. 2  is a flow diagram for converting any scalar value to multibase representation; 
           [0028]      FIG. 3  is a flow diagram showing the method of protecting against simple side-channel attacks; 
           [0029]      FIG. 4  is a flow diagram showing the method of replacing multiplication by squarings and other cheaper field operations; and 
           [0030]      FIG. 5  is a block diagram illustrating an execution environment. 
       
    
    
       [0031]    It should be noted that throughout the appended drawings, like features are identified by like reference numerals. 
       DETAILED DESCRIPTION 
       [0032]    Embodiments are described below, by way of example only, with reference to  FIGS. 1-5 . A system and method are provided for accelerating scalar multiplication by representing the scalar value with a short multibase representation, which is obtained by means of a conversion methodology that does not require additional memory resources. 
         [0033]    A direct calculation of a scalar multiplication of the form kP would involve adding P to itself (i.e., P+P+ . . . +P) (k−1) times. This procedure is highly time consuming for typical sizes of k. A straightforward improvement would be representing the scalar value using a binary representation with elements {0,1}. Thus, scalar multiplication becomes more efficient by using the two basic ECC point operations, namely doubling (2P) and addition (P+Q) of points, where P and Q are points on the elliptic curve. The nonzero density of the binary representation is about ½. Hence, the average cost of a scalar multiplication in this case is approximately (n−1)D+(n/2)A, where n is the average bit length of a randomly chosen scalar k, and D and A represent cost of point doubling and addition, respectively. 
         [0034]    By observing that additive inverses of ECC points (e.g., −P) are very inexpensive to compute, one can make use of a signed binary representation. Among different signed radix-2 representations using elements in the set D={0,±}, Non-Adjacent Form (NAF) is a canonical representation with the fewest number of nonzero digits for any scalar value. The NAF representation of a scalar contains at most one nonzero digit among any two successive digits. The expected nonzero density of this representation is ⅓. Hence, the average cost of a scalar multiplication using NAF is approximately (n−1)D+(n/3)A. 
         [0035]    If there is memory available, one can make use of precomputations to reduce the computing time further. This method is known as Window-w NAF (wNAF), and it basically exploits the availability of precomputed values to “insert” windows of width w, which permits the consecutive execution of several doublings to reduce the density of the expansion. The wNAF representation of a scalar contains at most one nonzero digit among any w successive digits. The average density of nonzero digits for a window of width w is D wNAF =1/(w+1), and the number of required precomputed points is (2 w−2 −1) (hereafter we refer as precomputed points to non-trivial points not including {O,P}). Thus, the cost using this method is approximately (n−1)D+(n/(w+1))A. 
         [0036]    Other alternative methods exist. However, they provide mixed results because may achieve lower computing costs but involve very expensive requirements in terms of memory. For instance, although the evaluation stage of the scalar multiplication using the double-base number system (DBNS) can be sped up by reducing the required number of point additions, converting a number to DBNS representation is very costly in terms of speed and memory. The latter is especially impractical in constrained devices such as smartcards, RFIDs and many others. 
         [0037]    In the present disclosure, a system and method is described that computes the scalar multiplication using a generic multibase representation with the objective of reducing the time execution by utilizing short multibase representations without impacting memory is also provided. 
         [0038]    The following multibase representation is provided for the representation of a given scalar k: 
         [0000]    
       
         
           
             
               
                 
                   
                     k 
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         m 
                       
                        
                       
                         
                           s 
                           i 
                         
                          
                         
                           
                             ∏ 
                             
                               j 
                               = 
                               1 
                             
                             J 
                           
                            
                           
                               
                           
                            
                           
                             a 
                             j 
                             
                               
                                 c 
                                 i 
                               
                                
                               
                                 ( 
                                 j 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where:
       bases a 1 ≠a 2 ≠ . . . ≠a J  are positive prime integers from a set of bases A={a 1 , . . . , a J },   s i  are signed digits from a given set D\{0}, i.e., |s i |≧1 and s i εD\{0}.   c i (j) are decreasing exponents, and   m is the length of the expansion.       
 
         [0043]    In addition, a global base a=a 1   w     1   a 2   w     2    . . . a J   w     J    is defined, using window set Ω={w 1 , w 2 , . . . , w J }, where w j ≧0 for 1≦j≦J, and impose the following restriction: 
         [0000]        c   i ( j )≧ c   i+1 ( j )+ w   j   ≧w   j  for 1≦ i≦m− 1 and each 1≦j≦J. 
         [0044]    The previous condition guarantees that an expansion of the form (1) is efficiently executed by a scalar multiplication using Horner&#39;s method as follows: 
         [0000]    
       
         
           
             
               
                 
                   kP 
                   = 
                     
                    
                   
                     
                       ( 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           m 
                         
                          
                         
                           
                             s 
                             i 
                           
                            
                           
                             
                               ∏ 
                               
                                 j 
                                 = 
                                 1 
                               
                               J 
                             
                              
                             
                                 
                             
                              
                             
                               a 
                               j 
                               
                                 
                                   c 
                                   i 
                                 
                                  
                                 
                                   ( 
                                   j 
                                   ) 
                                 
                               
                             
                           
                         
                       
                       ) 
                     
                      
                     P 
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       ∏ 
                       
                         j 
                         = 
                         1 
                       
                       J 
                     
                      
                     
                         
                     
                      
                     
                       a 
                       j 
                       
                         
                           d 
                           m 
                         
                          
                         
                           ( 
                           j 
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                     
                    
                   
                     ( 
                     
                       
                         
                           
                             
                               ∏ 
                               
                                 j 
                                 = 
                                 1 
                               
                               J 
                             
                              
                             
                                 
                             
                              
                             
                               a 
                               j 
                               
                                 
                                   d 
                                   m 
                                 
                                  
                                 
                                   ( 
                                   j 
                                   ) 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                   
                               
                                
                               
                                 
                                   … 
                                    
                                   
                                       
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         
                                           ∏ 
                                           
                                             j 
                                             = 
                                             1 
                                           
                                           J 
                                         
                                          
                                         
                                             
                                         
                                          
                                         
                                           
                                             a 
                                             j 
                                             
                                               
                                                 d 
                                                 1 
                                               
                                                
                                               
                                                 ( 
                                                 j 
                                                 ) 
                                               
                                             
                                           
                                            
                                           
                                             ( 
                                             
                                               
                                                 s 
                                                 1 
                                               
                                                
                                               P 
                                             
                                             ) 
                                           
                                         
                                       
                                       + 
                                       
                                         
                                           s 
                                           2 
                                         
                                          
                                         P 
                                       
                                     
                                     ) 
                                   
                                 
                                 + 
                                 … 
                                 + 
                                 
                                   
                                     s 
                                     
                                       m 
                                       - 
                                       1 
                                     
                                   
                                    
                                   P 
                                 
                               
                               ) 
                             
                             + 
                             
                               
                                 s 
                                 m 
                               
                                
                               P 
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    where d m (j)≧0, and d i (j)≧w j  for 1≦i≦m−1 and 1≦j≦J. 
         [0045]    For efficiency purposes, the multibase representation requires a digit set of the form 
         [0000]    
       
         
           
             
               
                 
                   D 
                   = 
                   
                     
                       
                         { 
                         
                           0 
                           , 
                           
                             ± 
                             1 
                           
                           , 
                           
                             ± 
                             2 
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           
                             ± 
                             
                               ⌊ 
                               
                                 
                                   a 
                                   - 
                                   1 
                                 
                                 2 
                               
                               ⌋ 
                             
                           
                         
                         } 
                       
                        
                       \ 
                        
                       
                           
                       
                        
                       … 
                     
                      
                     
                         
                     
                      
                     … 
                      
                     
                       { 
                       
                         
                           
                             ± 
                             1 
                           
                            
                           
                               
                           
                            
                           
                             a 
                             1 
                           
                         
                         , 
                         
                           
                             ± 
                             
                                 
                             
                              
                             2 
                           
                            
                           
                             a 
                             1 
                           
                         
                         , 
                         … 
                          
                         
                             
                         
                         , 
                         
                           
                             ± 
                             
                               ⌊ 
                               
                                 
                                   a 
                                   - 
                                   1 
                                 
                                 
                                   2 
                                    
                                   
                                       
                                   
                                    
                                   
                                     a 
                                     1 
                                   
                                 
                               
                               ⌋ 
                             
                           
                            
                           
                             a 
                             1 
                           
                         
                         , 
                         
                           
                             ± 
                             1 
                           
                            
                           
                               
                           
                            
                           
                             a 
                             2 
                           
                         
                         , 
                         
                           
                             ± 
                             2 
                           
                            
                           
                               
                           
                            
                           
                             a 
                             2 
                           
                         
                         , 
                         … 
                          
                         
                             
                         
                         , 
                         
                           ± 
                           
                               
                             
                                 
                             
                              
                             
                               
                                 
                                   ⌊ 
                                   
                                     
                                       a 
                                       - 
                                       1 
                                     
                                     
                                       2 
                                        
                                       
                                           
                                       
                                        
                                       
                                         a 
                                         2 
                                       
                                     
                                   
                                   ⌋ 
                                 
                                  
                                 
                                   a 
                                   2 
                                 
                               
                               , 
                               … 
                                
                               
                                   
                               
                               , 
                               
                                 
                                   ± 
                                   1 
                                 
                                  
                                 
                                     
                                 
                                  
                                 
                                   a 
                                   J 
                                 
                               
                               , 
                               
                                 
                                   ± 
                                   2 
                                 
                                  
                                 
                                     
                                 
                                  
                                 
                                   a 
                                   J 
                                 
                               
                               , 
                               … 
                                
                               
                                   
                               
                               , 
                               
                                 
                                   ± 
                                   
                                     ⌊ 
                                     
                                       
                                         a 
                                         - 
                                         1 
                                       
                                       
                                         2 
                                          
                                         
                                             
                                         
                                          
                                         
                                           a 
                                           J 
                                         
                                       
                                     
                                     ⌋ 
                                   
                                 
                                  
                                 
                                   a 
                                   J 
                                 
                               
                             
                             } 
                           
                         
                         , 
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where there are only considered digits that are not multiples of the bases. 
         [0046]    The multibase representation provided permits to flexibly define the set of bases that are the most efficient for a given setting. Also, it permits to specify well-defined distances between exponents by means of the highly flexible global base. It will become evident in the following paragraphs that the latter allows for devising efficient methods to convert numbers to short multibase representations. 
         [0047]      FIG. 1  illustrates a method for computing the scalar multiplication using a representation of the form (1). At step  102 , the method involves first defining or selecting the set of bases and windows to use according to the characteristics of a given setting. In particular, to include a given base a j  in the representation it is determined whether or not performing an operation of the form a j Q, where Q is a point on the elliptic curve, is relatively efficient. For instance, doubling (i.e., a j =2) is a highly efficient operation in most common elliptic curve forms, so it should be included to achieve the highest performance when working with these specific curves. 
         [0048]    In the case of the window set, the window values should be defined for each base a j  according to the relative performance of the corresponding operation a j Q and also taking into account memory restrictions. 
         [0049]    Once the set of bases has been defined, and according to the particular application, at step  104  it is determined if SSCA protection is required. If it is required, YES at step  104 , at step  106  the method depicted by  FIG. 3  is executed to protect all the operations of the form a j Q, and also point addition. 
         [0050]    If SSCA is not required, NO at step  104 , at step  108  the values of the precomputed table are calculated. Specifically, in the case of multibase representation, the table consists of all the points of the form d i P, where d i εD + \{0} (see (2)). 
         [0051]    At step  110 , the procedure depicted by  FIG. 2  is executed to determine the multibase representation of the scalar value. Then, the value of the scalar multiplication is computed by scanning the obtained multibase representation digit by digit. Per digit scanned, a step  112 , one operation of the form a j Q is executed, where a j  is the specific base associated to the current digit at step  114 . 
         [0052]    If the digit scanned is nonzero, YES at step  116 , then one addition of the form Q±d i P is performed at step  118 , where Q is the current value of the scalar multiplication and d i P is a point from the precomputed table. Note that the value ±d i  corresponds to the value of the scanned digit. Although, the precomputed table only contains positive values, it has been stated previously that computing inverses of points (in this case, −d i P) is inexpensive and can be calculated on-the-fly. 
         [0053]    If the scanning is complete, YES at step  120 , all the digits in the multibase representation has been scanned, and the result of the scalar multiplication is provided at step  122 . 
         [0054]    In the following, a method is described that determines short multibase representations of scalar values. 
         [0055]    Referring to  FIG. 2 , short multibase representations of the scalar value are determined. Inputs the scalar value are provided at step  210 , and then at step  220  begins the execution while the initial or partial value of the scalar is different from zero and any value of the precomputed table. Once it reaches zero, YES at step  220 , the method ends and gives the multibase representation of the input scalar at step  230 . 
         [0056]    At each iteration, and while the partial value of the scalar is other than zero, NO at step  220 , it is determined at step  240  if the scalar is divisible by one of the bases. For a given set of bases A={a 1 , . . . , a J  }, the test of divisibility begins with j=1 and stops when j=J or if a base divides the scalar value. If one of the bases is successfully selected, YES at step  240 , then a zero digit is set at step  250  together with its corresponding base, and the scalar value is updated by dividing it by the base in step  290 . 
         [0057]    If, otherwise, NO at step  240 , the scalar is not divisible by any of the bases, at step  260  its value is approximated to the closest extreme in the predefined window by performing an addition of the form k=k±d i  where d i εD + \{0} (see (2)), For this approximation to guarantee a successive execution of at least (w 1 +w 2 + . . . +w J ) operations of the form a j Q in posterior executions, the window is delimited by the two closest integers to the partial scalar value that are multiples of the global base. Then, the corresponding digit is set to the nonzero value ±d i  in step  270 . 
         [0058]    At step  280 , it is performed again the test of divisibility as was described previously. The base selected is associated to the nonzero digit from step  270 . Note that, although the test of divisibility has a predetermined order, the set of bases is efficiently specified by according to the characteristics of the particular setting. 
         [0059]    Finally, the scalar value is updated by dividing it by the selected base in step  290 . It is then determined at step  220  if the scalar is equivalent to zero or one of the values of the precomputed table. 
         [0060]    By way of example only, and to illustrate the way methods of  FIGS. 1 and 2  work during a scalar multiplication execution, two kinds of parameter selections are distinguished that are efficient for different settings, and explain their particular characteristics through examples. 
         [0000]    Multibase Non-Adjacent Form (mbNAF) 
         [0061]    In the first case, it is assumed that a given application has very constrained memory resources. Thus, the use of precomputations should be minimized. For the disclosed multibase representation, the latter can be achieved by imposing the following additional restrictions to exponents c i (j) in (1): 
         [0000]    c i (j) are decreasing exponents, such that c 1 (j)≧c 2 (j)≧ . . . ≧c m (j)≧0 for each j from 2 to J, and
 
c i (1) are decreasing exponents for the main base a 1  (i.e., j=1), such that c i (1)≧c i+1 (1)+2≧2, for 1≧i≧m−1.
 
         [0062]    Assuming the previous extra conditions implies that Ω={2, 0, . . . , 0}, where only the first base a 1  (which is referred to as main base) has nonzero window value, and consequently, the global base becomes a=a 1   2 a 2   0  . . . a J   0 =a 1   2 . From (2), it can be seen that these parameters reduces the digit set to: 
         [0000]    
       
         
           
             
               
                 
                   
                     D 
                     = 
                     
                         
                     
                      
                     
                       
                         { 
                         
                           0 
                           , 
                           
                             ± 
                             1 
                           
                           , 
                           
                             ± 
                             2 
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           
                             ± 
                             
                               ⌊ 
                               
                                 
                                   
                                     a 
                                     1 
                                     2 
                                   
                                   - 
                                   1 
                                 
                                 2 
                               
                               ⌋ 
                             
                           
                         
                         } 
                       
                        
                       \ 
                        
                       
                           
                       
                        
                       
                         { 
                         
                           
                             
                               ± 
                               1 
                             
                              
                             
                                 
                             
                              
                             
                               a 
                               1 
                             
                           
                           , 
                           
                             
                               ± 
                               
                                   
                               
                                
                               2 
                             
                              
                             
                               a 
                               1 
                             
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           
                             
                               ± 
                               
                                 ⌊ 
                                 
                                   
                                     
                                       a 
                                       1 
                                     
                                     - 
                                     1 
                                   
                                   
                                     2 
                                      
                                     
                                         
                                     
                                   
                                 
                                 ⌋ 
                               
                             
                              
                             
                               a 
                               1 
                             
                           
                         
                         } 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    which minimizes the required number of precomputations to only 
         [0000]    
       
         
           
             
               
                 ( 
                 
                   
                     a 
                     1 
                   
                   - 
                   2 
                 
                 ) 
               
                
               
                 ( 
                 
                   
                     a 
                     1 
                   
                   + 
                   1 
                 
                 ) 
               
             
             2 
           
         
       
     
         [0000]    precomputed points without considering {O,P}. 
         [0063]    Consider the computation of 3750P, where k=3750 is the selected scalar and P is a point on a generic elliptic curve over a prime field. First, we select the set of bases A={2,3} and windows Ω={2,0} as per step  102 ,  FIG. 1 . Note that a 1 =2 and a 2 =3 are selected as bases because point doubling (2Q) and tripling (3Q) are relatively efficient in the chosen curve form. In particular, doubling is the most efficient operation and hence selected as main base. 
         [0064]    Assuming that SSCA protection is not required, in step  108  the precomputed table d i P is built. In this case, d 1 εD + \{0}={1} (see (3)), so that it is only required to store nil non-trivial points and the trivial points {O,P}. 
         [0065]    Then, the multibase representation is determined as per  FIG. 2 . In the example, the procedure to find the representation follows the next sequence 
         [0000]    
       
         
           
             
               3750 
               2 
             
             → 
             
               
                 1875 
                 3 
               
               → 
               
                 
                   625 
                   - 
                   1 
                 
                 → 
                 
                   
                     624 
                     2 
                   
                   → 
                   
                     
                       312 
                       2 
                     
                     → 
                     
                       
                         156 
                         2 
                       
                       → 
                       
                         
                           78 
                           2 
                         
                         → 
                         
                           
                             39 
                             3 
                           
                           → 
                           
                             
                               13 
                               - 
                               1 
                             
                             → 
                             
                               
                                 12 
                                 2 
                               
                               → 
                               
                                 
                                   6 
                                   2 
                                 
                                 → 
                                 
                                   
                                     3 
                                     3 
                                   
                                   → 
                                   1 
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    which sets the following digit-wise representation using digits from D (see (3)) (2,3)NAF 2 (3750)=1 (2) 0 (3) 0 (2) 1 (2) 0 (3) 0 (2) 0 (2) 0 (2) 1 (2) 0 (3) 0 (2) ,
 
where the superscript (a j ) represents the base associated with a given digit. Note that the notation (a 1 ,a 2 )NAF w     1   (k) is used to represent the mbNAF representation of k using bases A={a 1 ,a 2 } and windows w 1 ≠0 and w 2 =0.
 
         [0066]    In a scalar multiplication the execution consists of scanning the multibase representation from left to right, and performing a doubling if the digit is 0 (2) , a tripling if it is 0 (3) , and a doubling or tripling followed by an addition if it is ±1 (2)  or ±1 (3) , respectively, as described previously for steps  112 - 122 ,  FIG. 1 . The correctness of the procedure can be verified by checking that the previous execution is equivalent to the following using Horner&#39;s method, where the execution begins in the most inner parentheses 
         [0000]      3750 P= 2×3(2 4 ×3(2 2 ×3 P+P )+ P ). 
         [0067]    According to the example above, the scalar multiplication 3750P costs 7D+3T+2A, which translates to a cost of 107.2M if 1S=0.8M. The cost of doubling (D) is 3 multiplications (M) and 5 squarings (S), the cost of tripling (T) is 7M+7S and the cost of addition is 7M+4S. In contrast a traditional NAF method would cost 12D+5A=135M, which is significantly more expensive in terms of computational effort. 
         [0000]    Window-w Multibase Non-Adjacent Form (wmbNAF) 
         [0068]    In another scenario, assume that the application has additional memory resources that can be exploited to store precomputations and, thus, speed up the execution of the multibase scalar multiplication. This variation is referred as Window-w Multibase NAF (or simply wmbNAF). 
         [0069]    The proposed multibase representation is achieved by imposing the following additional restrictions to exponents c i (j) in (1): 
         [0000]    c i (j) are decreasing exponents, such that c 1 (j)≧c 2 (j)≧ . . . ≧c m (j)≧0 for each j from 2 to J, and c 1 (1) are decreasing exponents for the main base a 1  (i.e., j=1), such that c i (1)≧c i+1 (1)+w 1 ≧w 1 , for 1≦i≦m−1, where w 1 &gt;2εZ + . 
         [0070]    Assuming the previous extra conditions implies that Ω={w 1 , 0, . . . , 0}, where only the first base a 1 , (which is referred to as main base) has nonzero window value, and consequently, the global base becomes a=a 1   w     1   a 2   0  . . . a J   0 =a 1   w     1   . From (2), it can be seen that these parameters reduces the digit set to: 
         [0000]    
       
         
           
             
               
                 
                   
                     D 
                     = 
                     
                       
                         { 
                         
                           0 
                           , 
                           
                             ± 
                             1 
                           
                           , 
                           
                             ± 
                             2 
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           
                             ± 
                             
                               ⌊ 
                               
                                 
                                   
                                     a 
                                     1 
                                     
                                       w 
                                       1 
                                     
                                   
                                   - 
                                   1 
                                 
                                 2 
                               
                               ⌋ 
                             
                           
                         
                         } 
                       
                        
                       \ 
                        
                       
                           
                       
                        
                       
                         { 
                         
                           
                             
                               ± 
                               1 
                             
                              
                             
                                 
                             
                              
                             
                               a 
                               1 
                             
                           
                           , 
                           
                             
                               ± 
                               
                                   
                               
                                
                               2 
                             
                              
                             
                               a 
                               1 
                             
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           
                             
                               ± 
                               
                                 ⌊ 
                                 
                                   
                                     
                                       a 
                                       1 
                                       
                                         
                                           w 
                                           1 
                                         
                                         - 
                                         1 
                                       
                                     
                                     - 
                                     1 
                                   
                                   2 
                                 
                                 ⌋ 
                               
                             
                              
                             
                               a 
                               1 
                             
                           
                         
                         } 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    which requires to precompute a table with 
         [0000]    
       
         
           
             
               
                 a 
                 1 
                 
                   w 
                   1 
                 
               
               - 
               
                 a 
                 1 
                 
                   
                     w 
                     1 
                   
                   - 
                   1 
                 
               
               - 
               2 
             
             2 
           
         
       
     
         [0000]    points without considering {O,P}. Although this parameter selection does not minimize the number of precomputations, it will enable further reductions in the number of nonzero terms appearing in the multibase representation. This makes the computation even faster. 
         [0071]    Consider again the computation of 3750P on a generic elliptic curve over a prime field. First, the set of bases A={2,3} and windows Ω={5,0} were selected as per step  102 ,  FIG. 1 . 
         [0072]    Assuming that SSCA protection is not required, in step  108  the precomputed table d i P is built. In this case, d i εD + \{0}={1, 3, 5, . . . , 15} (see(4)), so that it is required to store 7 non-trivial points and the trivial points {O,P}. 
         [0073]    Then, the multibase representation is determined as per  FIG. 2 . In the example, the procedure to find the representation follows the next sequence 
         [0000]    
       
         
           
             
               3750 
               2 
             
             → 
             
               
                 1875 
                 3 
               
               → 
               
                 
                   625 
                   + 
                   15 
                 
                 → 
                 
                   
                     640 
                     2 
                   
                   → 
                   
                     
                       320 
                       2 
                     
                     → 
                     
                       
                         160 
                         2 
                       
                       → 
                       
                         
                           80 
                           2 
                         
                         → 
                         
                           
                             40 
                             2 
                           
                           → 
                           
                             
                               20 
                               2 
                             
                             → 
                             
                               
                                 10 
                                 2 
                               
                               → 
                               5 
                             
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    which sets the following digit-wise representation using digits from D (see (4)) (2,3)NAF 5 (3750)=5 (2) 0 (2) 0 (2) 0 (2) 0 (2) 0 (2) 0 (2) −15 (2) 0 (3) 0 (2) ,
 
where again the superscript (a j ) represents the base associated with a given digit. The notation (a 1 ,a 2 )NAF w     1   (k) is used to represent the wmbNAF representation of k using bases A={a 1 ,a 2 } and windows w 1 &gt;2 and w 2 =0.
 
         [0074]    As previously described, following procedure for steps  112 - 122 ,  FIG. 1 , the execution of the scalar multiplication would be performed by scanning digits from left to right, and performing a doubling if the digit is 0 (2) , a tripling if it is 0 (3) , and a doubling or tripling followed by an addition if it is ±d i   (2)  or ±d i   (3) , respectively, where d i εD + \{0}={1, 3, 5, . . . , 15}. This procedure is equivalent to the following using Horner&#39;s method 
         [0000]      3750 P= 2×3(2 7 ×5 P− 15 P ). 
         [0075]    According to the example above, the scalar multiplication 3750P costs 8D+1T+1A =78.8M, if 1S=0.8M. Compare this cost to the traditional wNAF method with window w=5: 12D+2A=104.4M, which is significantly more expensive in terms of computational effort although requires the same amount of memory. 
         [0076]      FIG. 3  presents a methodology for the case where protection against SSCA needs to be implemented. The procedure is described in the following. 
         [0077]    According to the particular application, if it is determined that protection is to be implemented, at step  310  it is determined if ECC point operations such as doubling, tripling or addition are to be implemented either by distinguishing field squarings from multiplications or by assuming that these operations are equivalent. The decision mainly depends on the chosen platform. In general terms, in software implementations, squarings are usually faster and distinguishable from multiplications. To have strong protection against SSCA, then an adequate approach should involve atomic blocks that include squarings. 
         [0078]    If squarings are to be distinguished from multiplications, YES at step  310 , at step  320  the number of field multiplications and squarings found in an ECC point operation are determined. 
         [0079]    At step  330 , a balanced number of field multiplications and squarings should be determined in such a way that the minimum number of atomic blocks is required for the given ECC point operation. Such decisions should take into consideration the atomic structure to be used (and also considering that the same atomic structure should be applied to all the available ECC point operations). For instance, the following atomic structures: S-N-A-M-N-A-A (squaring-negation-addition-multiplication-negation-addition-addition) or S-N-A-A-M-N-A-A (squaring-negation-addition-addition-multiplication-negation-addition-addition) may be utilized. Note that squaring is included into the atomic structure, which not only speeds up computations since squaring is usually faster than multiplication, but also protects against potential attacks that are able of distinguishing multiplication from squaring. At this step, the method detailed in  FIG. 4  and disclosed in pending U.S. application Ser. No. 11/855,563 filed Sep. 14, 2007 can be used to achieve the balanced number of multiplications and squarings. Thus, multiplications are traded by 1, 2 or more squarings according to the given ECC point operation. 
         [0080]    Now referring to  FIG. 4 , at step  410 , the method involves first identifying field multiplications a.b that can be replaced by 1, 2 or 3 squarings as given by: 
         [0000]        ab= ½[( a+b ) 2   −a   2   −b   2 ]  (5) 
         [0081]    Determining which multiplications fall in this category if using (5) mainly depends on whether values a 2 , b 2  or both pre-exist in the ECC point operation. For instance, in sequential implementations replacing one multiplication by one squaring is of benefit since the former is generally more time consuming than the latter. However, if 2 or 3 squarings replace one multiplication, then the execution becomes slower. Hence, in this setting both a 2  and b 2  should pre-exist in the ECC point operation to make practical the aforementioned substitution and essentially trade a.b for (a+b) 2 . 
         [0082]    At step  420 , it is determined if some of the multiplications to be traded are not even (i.e., do not contain a multiple of 2 in their execution). If at least one of the multiplications is not even at decision step  430 , the current point representation is replaced by an equivalent one that inserts the necessary multiple of 2 into the odd multiplication(s). The equivalent point is taken from the equivalence class for projective coordinates given by: 
         [0000]      ( X:Y:Z )={(λ c   X,λ   d   Y,λZ ):λε K*,c,dεZ   + }, 
         [0000]    where λ=2t, tεZ + . 
         [0083]    Once multiplications to be traded are even, at step  450  they are replaced by applying the following algebraic substitutions, which hold for prime fields: 
         [0000]      2 ab =( a+b ) 2   −a   2   −b   2   (6) 
         [0084]    For instance, for the point addition in generic elliptic curves traditionally containing 8 multiplications and 3 squarings: 
         [0000]        X   3 =α 2 −β 3 −2 X   1 β 2 , 
         [0000]        Y   3 =α( X   1 β 2   −X   3 )− Y   1 β 3 , 
         [0000]      Z 3 =Z 1 β, 
         [0000]    where: α=Z 1   3 Y 2 −Y 1 , β=Z 1   2 X 2 −X 1 , it is possible to achieve a balanced number of multiplications and squarings by following the method described previously, which yields the following: 
         [0000]        X   3 =α 2 −4β 3 −2θ, 
         [0000]        Y   3 =α(θ− X   3 )−8 Y   1 β 3 , 
         [0000]        Z   3 =( Z   1 +β) 2   −Z   1   2 −β 2 , 
         [0000]    where: α=Z 1   3 Y 2 −Y 1 , β=Z 1   2 X 2 −X 1 , θ=(X 1 −β 2 ) 2 . This formula costs 6 multiplications and 6 squarings. 
         [0085]    In the previous example, the new point representation (4X 3 , 8Y 3 , 2Z 3 ), equivalent to (X 3 , Y 3 , Z 3 ), uses multiples of 2 and makes possible substitutions of the form 2ab=(a+b) 2 −a 2 −b 2  for Z 3  and θ, respectively. 
         [0086]    Balancing and fixing the computing cost to 6 multiplications and 6 squarings makes the point addition require only 6 S-N-A-M-N-A-A atomic blocks in contrast to the original 11 M-A-N-A atomic blocks, which represents a significant reduction in execution time. 
         [0087]    Returning to  FIG. 3 , if NO at step  310 , squarings are presumed not to be distinguishable from multiplications, as can be the case of hardware platforms where usually a multiplier executes both kinds of operations, then an approach assuming that squarings and multiplications are equivalent is more flexible and faster. 
         [0088]    Following the latter, at step  350 , the number of field multiplications (including squarings) should be determined in such a way that the minimum number of field operations is required for the given ECC point operation. Such determination takes into consideration the atomic structure to be used (and also considering that the same atomic structure is to be applied to all the required ECC point operations). For instance, the following new atomic structure: M-N-A-M-N-A-A (multiplication-negation-addition-multiplication-negation-addition-addition) may be utilized. Note that the previous structure permits to reduce the number of required additions when compared to the traditional M-A-N-A structure, so it would be particularly attractive for applications where the cost ratio field addition/multiplication is relatively high. For instance, the traditional doubling formula on generic curves over prime fields costs 4 multiplications and 4 squarings. Protecting it using M-A-N-A would require 8 blocks and a total cost of 8 multiplications and 16 additions. In contrast, by using M-N-A-M-N-A-A, the implementation of doubling reduces to only 4 blocks with a total cost of 8 multiplications and 12 additions. 
         [0089]    In  FIG. 5 , a computing environment  500  is provided in which an elliptic curve cryptosystem may be implemented as computer software in the form of computer readable code executed. The computing environment may be any number of computing or computer based platforms such as mobile devices, personal computer, notebook computers, personal digital assistants, networking devices such as routers, or be resident in application specific processors devices such as smart cards, security cards or radio frequency identification (RFID) devices requiring security implementations. 
         [0090]    The computer  502  comprises central processing unit (CPU)  504  and memory  506 . The CPU may be a single processor or multiprocessor system. In addition a multiprocessor implementation of the elliptic curve cryptosystem may utilize more than one computing environment for execution of a parallel architecture. In various computing environments, main memory  506  and storage  512  can reside wholly on computer environment  500 , or they may be distributed between multiple computers. 
         [0091]    Input devices  510  such as a keyboard and mouse may be coupled to a bi-directional system bus of a computer  502 . The keyboard and mouse are for introducing user input to a computer  502  and communicating that user input to processor  504  if required. Computer  502  may also include a communication interface  514 . Communication interface  514  provides a two-way data communication coupling via a network link to a network  516  by wired or wireless connection or may provide an interface to other host device  518  by a direct radio frequency connection. In any such implementation, communication interface  514  sends and receives electrical, electromagnetic or optical signals which carry digital data streams representing various types of information. 
         [0092]    Communication between the communication interface unit  514  and the network  516  or host  518  use electrical, electromagnetic or optical signals which carry digital data streams. The signals through the various networks and the signals on network link and through communication interface, which carry the digital data to and from computer, are exemplary forms of carrier waves transporting the information. The computer  502  may also be able to display the results of the computation to a user in the form of output. 
         [0093]    The computer processor  504  or similar device may be programmed in the manner of method steps, or may be executed by an electronic system which is provided with means for executing these steps. The storage device  512  provides a computer readable medium which may include both fixed and removable media, such as magnetic, optical or magnetic optical storage systems, Random Access Memory (RAM), Read Only Memory (ROM) or any other available mass storage technology. The storage device or media may be programmed to execute such method steps. As well, electronic signals representing these method steps may also be transmitted via a communication network. 
         [0094]    Application code may be embodied in any form of computer program product. A computer program product comprises a medium configured to store or transport computer readable code, or in which computer readable code may be embedded. Some examples of computer program products are CD-ROM disks, ROM cards, floppy disks, magnetic tapes, computer hard drives, servers on a network, and carrier waves. 
         [0095]    The method steps of the present disclosure may be embodied in sets of executable machine code stored in a variety of formats such as object code or source code. Such code is described generically herein as programming code, or a computer program for simplification. Clearly, the executable machine code or portions of the code may be integrated with the code of other programs, implemented as subroutines, plug-ins, add-ons, software agents, by external program calls, in firmware or by other techniques as known in the art. It will be apparent to persons skilled in the art that a number of variations and modifications can be made without departing from the scope of the invention as defined in the claims.