Abstract:
An optimized hardware architecture and method introducing a simple arithmetic processor that allows efficient implementation of an Elliptic Curve Cryptography point addition algorithm for mixed Affine-Jacobian coordinates. The optimized architecture additionally reduces the required storage for intermediate values.

Description:
BACKGROUND 
       [0001]    Electronic devices are becoming a ubiquitous part of everyday life. The number of smartphones and personal tablet computers in use is rapidly growing. A side effect of the increasing use of smartphones and personal tablets is that increasingly the device are used for storing confidential data such as personal and banking data. Protection of this data against theft is of paramount importance. 
         [0002]    The field of cryptography offers protection tools for keeping this confidential data safe. Based on hard to solve mathematical problems, cryptography typically requires highly computationally intensive calculations that are the main barrier to wider application in cloud and ubiquitous computing (ubicomp). If cryptographic operations cannot be performed quickly enough, cryptography tools are typically not accepted for use on the Internet. In order to be transparent while still providing security and data integrity, cryptographic tools need to follow trends driven by the need for high speed and the low power consumption needed in mobile applications. 
         [0003]    Public key algorithms are typically the most computationally intensive calculations in cryptography. For example, take the case of Elliptic Curve Cryptography (ECC), one of the most computationally efficient public key algorithms. The 256 bit version of ECC provides security that is equivalent to a 128 bit symmetric key. A 256 bit ECC public key should provide comparable security to a 3072 bit RSA public key. The fundamental operation of ECC is a point multiplication which is an operation heavily based on modular multiplication, i.e. approximately 3500 modular multiplications of 256 bit integers are needed for performing one ECC 256 point multiplication. Higher security levels (larger bit integers) require even more computational effort. 
         [0004]    Building an efficient implementation of ECC is typically non-trivial and involves multiple stages.  FIG. 1  illustrates stages  101 ,  102  and  103  that are needed to realize the Elliptical Curve Digital Signature Algorithm (ECDSA), which is one of the applications of ECC. Stage  101  deals with finite field arithmetic that comprises modular addition, inversion and multiplication. Stage  102  deals with point addition and point doubling which comprises the Joint Sparse Form (JSF), Non-Adjacent Form (NAF), windowing and projective coordinates. Finally, stage  103  deals with the ECDSA and the acceptance or rejection of the digital signature. 
         [0005]    Any elliptic curve can be written as a plane geometric curve defined by the equation of the form (assuming the characteristic of the coefficient field is not equal to 2 or 3): 
         [0000]        y   2   =x   3   +ax+b   (1)
 
         [0000]    that is non-singular; that is it has no cusps or self-intersections and is known as the short Weierstrass form where a and b are integers. The case where a=−3 is typically used in several standards such as those published by NIST, SEC and ANSI which makes this the case of typical interest. 
         [0006]    Many algorithms have been proposed in the literature for efficient implementation of the Point Addition (PADD) and Point Doubling (PDBL) operations. Many of these algorithms are optimized for software implementation. While these are typically efficient on certain platforms, the algorithms are typically not optimal once the underlying hardware can be tailored to the algorithm. 
         [0007]    A PADD algorithm for mixed affine-Jacobian coordinates has been described by Cohen, Miyaji and Ono in Proceedings of the International Conference on the Theory and Applications of Cryptography and Information Security; Advances in Cryptology, ASIACRYPT 1998, pages 51-65, Springer-Verlag, 1998. Jacobian coordinates are projective coordinates where each point is represented as three coordinates (X, Y, Z) where x=X/Z 2 , y=Y/Z 3  and affine coordinates are the familiar (x,y) coordinates. Note the coordinates are all integers. PADD algorithm  200  requires 8 modular multiplications, 3 modular squarings, 6 modular subtractions, and one modular multiplication by 2 and is shown in  FIG. 2 . In order to perform the PADD, the algorithm further requires a minimum of 4 temporary registers, which for ECC 256 bit each need to be 256 bits in size. All operations are done in the finite field K over which the elliptic curve E is defined. The finite arithmetic field K is defined over the prime number p so that all arithmetic operations are performed modulo p. The additive identity element is the point at infinity. 
       SUMMARY 
       [0008]    An optimized hardware architecture and method reduces storage requirements and speeds up the execution of the ECC PADD algorithm by requiring only two temporary storage registers and by introducing a simple arithmetic unit for performing modular subtraction and modular multiplication by 2. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]      FIG. 1  shows stages  101 ,  102  and  103  that are needed to realize the Elliptical Curve Digital Signature Algorithm (ECDSA). 
           [0010]      FIG. 2  shows a prior art point addition algorithm. 
           [0011]      FIG. 3  shows an embodiment in accordance with the invention. 
           [0012]      FIG. 4  show an embodiment in accordance with the invention. 
           [0013]      FIG. 5  shows an embodiment in accordance with the invention. 
           [0014]      FIG. 6  shows an embodiment in accordance with the invention. 
           [0015]      FIG. 7  shows an embodiment in accordance with the invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0016]    PADD algorithm  300  in accordance with the invention is shown in  FIG. 3 . PADD algorithm  300  requires fewer steps and reduces the storage requirements compared to PADD algorithm  200  for the same modular addition of two points. PADD algorithm  300  requires only two temporary storage registers, T 1  and T 2 . Note, PADD algorithm  300  performs modular point addition using mixed affine-Jacobian coordinates to avoid the need for a modular inversion operation that is typically one to two orders of magnitude slower than a modular multiplication operation. The use of mixed coordinates provides a speed advantage over performing the point addition solely in Jacobian coordinates that also obviates the need for a modular inversion operation. PADD algorithm  300  is implemented over an optimized hardware architecture shown in  FIG. 6  and  FIG. 7  and specifically designed to take advantage of PADD algorithm  300 . 
         [0017]    As input in step  301 , PADD algorithm  300  shown in  FIG. 3  takes point P=(X 1 , Y 1 , Z 1 ) in Jacobian coordinates and point Q=(x 2 , y 2 ) in affine coordinates as the two points to be added together as P+Q. T 1  and T 2  are temporary storage variables. Note that all mathematical operations shown are in modular arithmetic. In step  302  of PADD algorithm  300 , the value of point P is returned as the result of the modular addition of P+Q if Q=∞, as a point at infinity is the identity element. Similarly, in step  303 , the value of point Q is returned as the result of the modular addition of P+Q if P=∞, as a point at infinity is the additive identity element. In step  304 , the Jacobian coordinate Z 1  is squared and the resulting value stored in temporary register T 1 . In step  305 , Z 1 *T 1  is calculated and the resulting value stored in temporary register T 2 . In step  306 , T 2 *y 2 −Y 1  is calculated, where y 2  is in affine coordinates and Y 1  is in Jacobian coordinates, the result being stored in temporary register T 2 . In step  307 , the value stored in temporary register T 1  is multiplied by x 2  and X 1  is then subtracted from the result, where x 2  is in affine coordinates and X 1  is in Jacobian coordinates, the result being stored in temporary register T 1 . Step  308  provides for a return if T 1  and T 2  are both zero as this means P=Q and step  309  provides for a return if T 1  is zero and T 2  is not zero as this means P=−Q. In step  310 , the Jacobian coordinate Z 1  is multiplied by the value in temporary register T 1  and the result is stored as Jacobian coordinate Z 3 . In step  311 , the value stored in temporary register T 1  is squared and stored as Jacobian coordinate Y 3 . In step  312 , the value stored in temporary register T 2  is squared and stored as Jacobian coordinate X 3 . In step  313 , Y 3 *T 1  is calculated and the result is stored in temporary register T 1 . In step  314 , T 1 +2Y 3 *X 1  is calculated and subtracted from Jacobian coordinate X 3  with the result stored as Jacobian coordinate X 3 . In step  315 , Y 3 *X 1 −X 3  is calculated and multiplied by T 2  and stored as Jacobian coordinate Y 3 . Note that Y 3 *X 1  was calculated in step  314  and that value is used in step  315  and is not calculated again in step  315 . In step  316 , T 1 *Y 1  is calculated and subtracted from Jacobian coordinate Y 3  and the result is stored as Jacobian coordinate Y 3 . Finally, in step  317  the result of the point addition of P+Q: (X 3 , Y 3 , Z 3 ) is returned in Jacobian coordinates. 
         [0018]    The most computationally intensive operation in PADD algorithm  300  in  FIG. 3  is modular multiplication denoted by “*”. Because most of the steps described in PADD algorithm  300  depend on the previous steps of the algorithm, it is typically most efficient to implement PADD algorithm  300  in hardware using a single modular multiplier although more than one modular multiplier may be used in accordance with the invention. Using only one modular multiplier restricts each step in PADD algorithm  300  to having no more than one modular multiplication. While step  315  appears to contain two modular multiplications, the result of Y 3 *X 1  has already been calculated in step  314  and is fed in directly into the input of the hardware modular multiplier. 
         [0019]    It is important to note that besides the modular multiplication steps performed in steps  306 ,  307 ,  314 ,  315  and  316  of PADD algorithm  300 , two additional, comparatively simple operations are performed as well: modular subtraction and modular multiplication by 2. Note that multiplication or division by a power of 2 in binary is merely a shift operation. In order to speed up execution of PADD algorithm  300  and eliminate the need for additional temporary registers, an embodiment in accordance with the invention of simple arithmetic unit (SAU)  400  with the inputs and outputs as shown in  FIG. 4 . 
         [0020]      FIG. 5  shows how steps  306 ,  307 ,  314 ,  315  and  316  of PADD  300  in  FIG. 3  are broken down for utilization of SAU  400  which has inputs A, B and C with output D. Note that the input and output labels of SAU  400  correspond to the respective variable names in  FIG. 5 . Block  501  shows how step  306  of PADD algorithm  300  is broken down using SAU  400  and involves setting inputs A=T 2 *y 2  and B=Y 1  with output D=A−B. Output D is written to temporary register T 2 . Block  501  shows how step  307  of PADD algorithm  300  is broken down using SAU  400  and involves setting inputs A=T 1 *x 2  and B=X 1  with output D=A−B. Output D is then written to temporary register T 1 . Block  503  shows how step  314  of PADD algorithm  300  is broken down using SAU  400  and involves setting inputs A=X 3 , B=T 1 , C=y 2 *X 1  with output D=A−B−2C. Output D is written to Jacobian coordinate X 3 . Block  504  shows how step  315  of PADD algorithm  300  is broken down using SAU  400  and involves setting inputs A=Y 3 *X 1  and B=X 3  with output D=A−B. Output D is written to Jacobian coordinate Y 3 . Block  505  shows how step  316  of PADD algorithm  300  is broken down using SAU  400  and involves setting inputs A=Y 3  and B=T 1 *Y 1  with output D=A−B. Output D is written to Jacobian coordinate Y 3 . Note that “don&#39;t care” indicates the value is irrelevant to the calculation being performed in the respective steps. 
         [0021]      FIG. 6  shows embodiment 600 in accordance with the invention comprising multi-cycle multiplier  610  with output register (not shown), SAU  400 , multiplexer (MUX)  620  and MUX  630  with input registers X 1 , Y 1 , Z 1 , x 2 , y 2 , output registers X 3 , Y 3 , Z 3  and temporary registers T 1  and T 2  that are all part of register memory  695 . Note the individual register labels correspond to variable names in  FIGS. 3 and 5 . MUX  620 ,  630  and  740  (part of SAU  400 , see  FIG. 7 ) are controlled by the microprocessor (not shown) which executes PADD algorithm  300 . As noted above, each step in PADD algorithm  300  involve at most one modular multiplication (not counting multiplication or division by 2 which in binary representation is merely a shift operation). 
         [0022]    SAU  400  shown in  FIG. 7  comprises subtractors  710  and  720 , logical one bit left shifter  715  and MUX  720 . Input A connects to the minuend input of subtractor  710  on line  670  and input B connects to the subtrahend input of subtractor  710  on line  675 . Input C connects to logical one bit left shifter  715  on line  650  where logical one bit left shifter  715  performs a multiplication of the input C by two. Subtractor  710  outputs A−B on line  730  which connects to the minuend input of subtractor  720  and the “0” input for MUX  740 . Logical one bit left shifter  715  outputs 2C on line  735  to the subtrahend input of subtractor  720 . Subtractor  720  outputs A−B−2C on line  750  to the “1” input for MUX  740 . MUX  740  sends D on line  690 . 
         [0023]    Multi-cycle multiplier  610  functions by multiplying the values on inputs  635  and  640  together and outputting the result. Steps  301 - 303  are performed in the microprocessor (not shown) without using multi-cycle multiplier  610  and SAU  400 . 
         [0024]    Step  304  utilizes multi-cycle multiplier  610 . Register memory  695  provides Z 1  on both inputs  635  and  640  of multi-cycle multiplier  610  and multi-cycle multiplier  610  computes Z 1   2  which is sent on line  650  to register memory  695  and stored in temporary register T 1 . 
         [0025]    Step  305  utilizes multi-cycle multiplier  610 . Register memory  695  provides T 1  on input  635  and Z 1  on input  640  of multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes T 1 *Z 1  which is sent on line  650  to register memory  695  where it is stored in temporary register T 2 . 
         [0026]    Step  306  utilizes both multi-cycle multiplier  610  and SAU  400 . Register memory  695  provides T 2  and y 2  on lines  635  and  640 , respectively, to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes T 2 *y 2  which is output on line  650  to input “1” of MUX  620  with MUX  620  set to “1”. MUX  630  input is set to “0”. MUX  620  sends T 2 *y 2  to input A of SAU  400  on line  670 . Line  670  is directly connected to the minuend input of subtractor  710 . Register memory  695  provides Y 1  on line  660  to input “0” of MUX  630  and MUX  630  is set to “0”. MUX  630  sends Y 1  to input B of SAU  400  on line  675 . Line  675  is directly connected to the subtrahend input of subtractor  710 . Subtractor  710  computes A−B (which is T 2 *y 2 −Y 1 ) and outputs A−B on line  730  to input “0” of MUX  740  with MUX  740  set to “0”. MUX  740  sends D (which is A−B) on line  690  to register memory  695  where it is stored in temporary register T 2 . 
         [0027]    Step  307  utilizes both multi-cycle multiplier  610  and SAU  400 . Register memory  695  provides T 1  and x 2  on lines  635  and  640 , respectively, to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes T 1 *x 2  which is output on line  650  to input “1” of MUX  620  with MUX  620  set to “1”. MUX  620  sends T 1 *x 2  to input A of SAU  400  on line  670 . Line  670  is directly connected to the minuend input of subtractor  710 . Register memory  695  provides X 1  on line  660  to input “0” of MUX  630  and MUX  630  is set to “0”. MUX  630  sends X 1  to input B of SAU  400  on line  675 . Line  675  is directly connected to the subtrahend input of subtractor  710 . Subtractor  710  computes A−B (which is T 1 *x 2 −X 1 ) and outputs A−B on line  730  to input “0” of MUX  740  with MUX  740  set to “0”. MUX  740  sends D (which is A−B) on line  690  to register memory  695  where it is stored in temporary register T 1 . 
         [0028]    Steps  308 - 309  are performed in the microprocessor (not shown) without using multi-cycle multiplier  610  and SAU  400 . 
         [0029]    Step  310  utilizes multi-cycle multiplier  610 . Register memory  695  provides T 1  on line  635  and Z 1  on line  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes T 1 *Z 1  and the result is output on line  650  to register memory  695  where it is stored in temporary register T 2 . 
         [0030]    Step  311  utilizes multi-cycle multiplier  610 . Register memory  695  provides T 1  on both lines  635  and  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes T 1   2  and the result is output on line  650  to register memory  695  Y 3  where it is stored in Y 3 . 
         [0031]    Step  312  utilizes multi-cycle multiplier  610 . Register memory  695  provides T 2  on both lines  635  and  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes T 2   2  and the result is output on line  650  to register memory  695  where it is stored in X 3 . 
         [0032]    Step  313  utilizes multi-cycle multiplier  610 . Register memory  695  provides T 1  on line  635  and Y 3  on line  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes T 1 *Y 3  and the result is output on line  650  to register memory  695  where it is stored in temporary register T 1 . 
         [0033]    Step  314  utilizes both multi-cycle multiplier  610  and SAU  400 . Register memory  695  provides X 3  on line  665  to input “0” of MUX  620  with MUX  620  set to “0”. MUX  620  sends X 3  to input A of SAU  400  on line  670 . Line  670  is directly connected to the minuend input of subtractor  710 . Register memory  695  provides T 1  on line  660  to input “0” of MUX  630  with MUX  630  set to “0”. MUX  630  sends T 1  on line  675  to input B of SAU  400 . Line  650  is directly connected to the subtrahend input of subtractor  710 . Subtractor  710  computes and outputs A−B (which is X 3 −T 1 ) on line  730  to the minuend input of subtractor  720 . Register memory  695  provides X 1  on line  635  and Y 3  on line  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes Y 3 *X 1 . The result is output on line  650  to input C of SAU  400  which is directly connected to logical one bit left shifter  715  which multiplies input C by two and outputs 2C (which is 2Y 3 *X 1 ) on line  735  to the subtrahend output of subtractor  720 . Subtractor  720  computes and outputs A−B−2C on line  750  to input “1” of MUX  740  with MUX  740  set to “1”. MUX  740  sends D (which is A−B−2C=X 3 −T 1 −2Y 3 *X 1 ) on line  690  to register memory  695  where it is stored in X 3 . 
         [0034]    Step  315  utilizes both multi-cycle multiplier  610  and SAU  400 . In step  314 , Y 3 *X 1  was computed by multi-cycle multiplier  610 . Hence, Y 3 *X 1  is still present in the output register (not shown) of multi-cycle multiplier  610  and in Step  315  is sent on line  650  to input “1” of MUX  620  and MUX  620  is set to “1”. MUX  620  sends Y 3 *X 1  on line  670  to input A of SAU  400 . Line  670  is connected directly to the minuend input of subtractor  710 . Register memory  695  provides X 3  on line  660  to input “0” of MUX  630  with MUX  630  set to “0”. MUX  630  sends X 3  on line  675  to input B of SAU  400 . Line  675  is directly connected to the subtrahend input of subtractor  710 . Subtractor  710  calculates A−B and sends the result on line  730  to input “0” of MUX  740  with MUX  740  set to“0”. MUX  740  sends D (which is A−B=Y 3 *X 1 −X 3 ) on line  690  to register memory  695  which passes D through on line  635  and provides T 2  on line  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes D*T 2  (which is (Y 3 *X 1 −X 3 )*T 2 ) and outputs the result on line  650  to register memory  695  where the result is stored in Y 3 . 
         [0035]    Step  316  utilizes both multi-cycle multiplier  610  and SAU  400 . Register memory  695  provides Y 3  on line  665  to input “0” of MUX  620  with MUX  620  set to “0”. MUX  620  sends Y 3  on line  670  to input A of SAU  400 . Line  670  is directly connected to the minuend of subtractor  710 . Register memory  695  provides T 1  on line  635  and Y 1  on line  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes and outputs T 1 *Y 1  on line  650  to input “1” of MUX  630  with MUX  630  set to “1”. MUX  630  sends T 1 *Y 1  on line  675  to input B of SAU  400 . Line  675  is directly connected to the subtrahend of subtractor  710 . Subtractor  710  computes A−B (which is Y 3 −T 1 *Y 1 ) and provides the result on line  730  to input “0” of MUX  740  with MUX  740  set to “0”. MUX  740  sends D (which is Y 3 −T 1 *Y 1 ) on line  690  to register memory  695  where the result is stored in Y 3 . 
         [0036]    Step  317  returns the result of the addition of P+Q in Jacobian coordinates which is (X 3 , Y 3 , Z 3 ).