Abstract:
An optimized hardware architecture and method introducing a simple arithmetic processor that allows efficient implementation of an Elliptical Curve Cryptography point doubling algorithm for 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 (PDBL) 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 PDBL algorithm for 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). Note the coordinates are all integers. PDBL algorithm  200  requires 4 modular multiplications, 4 modular squarings, 4 modular subtractions, one modular addition, one modular multiplication by 2 and one modular division by 2 and is shown in  FIG. 2 . In order to perform the PDBL, the algorithm further requires a minimum of 3 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 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 PDBL algorithm by requiring only two temporary storage registers and by introducing a simple arithmetic unit for performing modular addition, subtraction and multiplication and division 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 doubling algorithm. 
           [0011]      FIG. 3  shows an embodiment in accordance with the invention. 
           [0012]      FIG. 4  shows 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]    PDBL algorithm  300  in accordance with the invention is shown in  FIG. 3 . PDBL algorithm  300  requires fewer steps and reduces the storage requirements compared to PDBL algorithm  200  for the same modular point doubling. PDBL algorithm  300  requires only two temporary storage registers, T 1  and T 2 . PDBL algorithm  300  is implemented over an optimized hardware architecture shown in  FIG. 6  and  FIG. 7  and specifically designed to take advantage of PDBL algorithm  300 . 
         [0017]    As input in step  301 , PDBL algorithm  300  shown in  FIG. 3  takes point P=(X 1 , Y 1 , Z 1 ) in Jacobian coordinates. T 1  and T 2  are temporary storage variables. Note that all mathematical operations shown are in modular arithmetic and all coordinates are Jacobian. In step  302  of PDBL algorithm  300 , if P=∞ (the identity element) the value ∞ is returned. In step  303 , the coordinate Z 1  is squared (Z 1 *Z 1 ) and subtracted from X 1  with the resulting value stored in temporary register T 2 . In step  304 , 3T 2 *(2X 1 −T 2 ) is calculated and the resulting value stored in temporary register T 2 . In step  305 , T 2  is squared and the result stored in X 3 . In step  306 , 2Y 1 *Z 1  is calculated, the result stored in Z 3 . In step  307 , 2Y 1  is calculated and squared (2Y 1 *2Y 1 ) with the result stored in Y 3 . In step  308 , X 3 −2Y 3 *X 1  is calculated and the result stored in X 3 . In step  309 , (Y 3 *X 1 −X 3 ) is calculated and multiplied by T 2  and the result is stored in T 1 . Note that the quantity Y 3 *X 1  was already calculated in step  308  so step  309  only requires a single modular multiplication (by T 2 ). In step  310 , T 1 −Y 3 *Y 3 /2 is calculated and the result is stored in Y 3 . Finally, in step  311  the result of the point doubling of P is returned in Jacobian coordinates as (X 3 , Y 3 , Z 3 ). 
         [0018]    The most computationally intensive operation in PDBL algorithm  300  in  FIG. 3  is modular multiplication denoted by “*”. Because most of the steps described in PDBL algorithm  300  depend on the previous steps of the algorithm, it is typically most efficient to implement PDBL algorithm  300  in hardware using a single modular multiplier although more than one modular multiplier may be used in accordance with the invention which allows more than one modular multiplication to be performed in a step. Using only one modular multiplier restricts each step in PDBL algorithm  300  to having no more than one modular multiplication. 
         [0019]    It is important to note that besides the modular multiplication steps performed in steps  303 ,  308  and  309  of PDBL algorithm  300 , additional, comparatively simple operations are performed as well: modular subtraction and addition and modular multiplication and division by 2. Note that multiplication or division by a power of 2 in binary is merely a shift operation. In order to accelerate execution of PDBL 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  is used. 
         [0020]      FIG. 5  shows how steps  303 ,  304 ,  306 ,  307 ,  308 ,  309  and  310  are broken down to take advantage of SAU  400  which has inputs A, B and C with outputs D and E. Note that the input and output labels of SAU  400  correspond to the respective variable names in  FIG. 5 . Block  501  shows how step  303  of PDBL algorithm  300  is broken down using SAU  400  and involves setting inputs A=X 1  and B=Z 1   2  with output E=A−B. Block  502  shows how step  304  of PDBL algorithm  300  is broken down using SAU  400  and involves setting inputs A=X 1 , B=T 2  and C=T 2  with outputs D=3C and E=2A−B. Outputs D and C are then multiplied together and the result is stored in temporary register T 2 . Block  503  shows how step  306  of PDBL algorithm  300  is broken down using SAU  400  and involves setting A=Y 1  and B=0 with output E=2A−B. Output E is then multiplied by Z 1  and the result is stored in Z 3 . Block  504  shows how step  307  of PDBL algorithm  300  is broken down using SAU  400  and involves setting inputs A=Y 1  and B=0 with output E=2A−B. Output E is then multiplied by itself and the result is stored in Y 3 . Block  505  shows how step  308  of PDBL algorithm  300  is broken down using SAU  400  and involves setting inputs A=X 3  and B=X 1 *Y3 with output E=A−2B. Output E is stored in X 2 . Block  506  shows how step  309  of PDBL algorithm  300  is broken down using SAU  400  and involves setting input A=X 1 *Y 3  and B=X 3  with output E=A−2B. Note that step  309  reuses the result of step  308  for X 1 *Y 3  (stored in the output register of the multiplier). Output E is stored in X 3 . Block  507  shows how step  310  of PDBL algorithm  300  is broken down using SAU  400  and involves setting inputs A=T 1  and B=Y 3   2  with output E=A−B/2. 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 —not used), 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 schedules the steps of PDBL algorithm  300 . As noted above, each step in PDBL algorithm  300  involve at most one modular multiplication by multi-cycle multiplier  610  (not counting multiplication or division by 2 which in binary representation is merely a shift operation). 
         [0022]    SAU  400  shown in  FIG. 7  comprises subtractor  710  and adder  711 , logical one bit left shifter  715  (multiplication by 2), logical one bit right shifter  716  (division by 2), logical one bit left shifter  717  (multiplication by 2), logical one bit left shifter  718  (multiplication by 2), MUX  720  and MUX  725 . 
         [0023]    Input A goes to both input “0” of MUX  720  and logical one bit left shifter  715  on line  671 . Logical one bit left shifter  715  multiplies input A by two and outputs 2A on line  771  to the “1” input of MUX  720 . Output line  776  of MUX  720  provides the minuend input for subtractor  710 . Input B goes to logical one bit right shifter  716 , logical one bit left shifter  717  and input “1” of MUX  725  on line  672 . Logical one bit right shifter  716  divides input B by two and outputs B/2 on line  772  to input “0” of MUX  725 . Logical one bit left shifter  717  multiplies input B by two and outputs 2B on line  774  to input “2” of MUX  725 . Output line  777  of MUX  725  connects to the subtrahend input of subtractor  710 . Input C connects to adder  722  and to logical one bit left shifter  718  on line  673 . Logical one bit left shifter  718  multiplies input C by two and outputs 2C to adder  722  on line  775 . Subtractor  710  outputs E (see  FIG. 4 ) on line  696 . Adder  722  outputs D (=3C) on line  690 . 
         [0024]    Multi-cycle multiplier  610  functions by multiplying the values on lines  635  and  640  together and outputting the result on lines  650  and  650 . Steps  301 - 302  of PDBL algorithm  300  are performed on the microprocessor (not shown) without using multi-cycle multiplier  610  and SAU  400 . 
         [0025]    Step  303  utilizes both multi-cycle multiplier  610  and SAU  400 . Register memory  695  provides X 1  on line  665  to input “0” of MUX  620  with MUX  620  set to “0” and Z 1  is provided from register memory  695  on both lines  635  and  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes Z 1   2  which is output on line  650  to input “1” of MUX  630  with MUX  630  set to “1”. MUX  620  sends X 1  to input A of SAU  400  on line  671  and MUX  630  sends Z 1   2  to input B of SAU  400  on line  672 . MUX  720  in SAU  400  is set to “0” and MUX  720  sends A on line  776  from line  671  to the minuend input of subtractor  710  on line  776 . MUX  725  in SAU  400  is set to “1” and MUX  725  sends on line  777  B from line  672  to the subtrahend input of subtractor  710  on line  777 . Subtractor  710  computes E (which is A−B=X 1 −Z 1   2 ) of which is passed to register memory  695  on line  696  and stored in temporary register T 2 . 
         [0026]    Step  304  utilizes both multi-cycle multiplier  610  and SAU  400 . Register memory  695  provides X 1  on line  665  to input “0” of MUX  620  and MUX  620  is set to “0”. MUX  620  sends X 1  to input A of SAU  400  on line  671 . Register memory  695  provides T 2  on line  660  to input “0” of MUX  630  with MUX  630  set to “0” and register memory  695  also provides T 2  to input C of SAU  400  on line  673 . MUX  720  in SAU  400  is set to “1” and MUX  720  sends 2A from line  771  on line  776  to the minuend input of subtractor  710 . MUX  725  in SAU  400  is set to “1” and MUX  725  sends B from input line  672  on line  777  to the subtrahend input of subtractor  710  on line  777 . Input C (T 2 ) of SAU  400  on line  673  is sent to both logical one bit left shifter  718  and adder  720 . The output 2C on line  775  from logical one bit left shifter  718  goes to adder  720 . Adder  720  outputs D (which is 3C=3T 2 ) on line  690  and subtractor  710  computes E (which is 2A−B=2X 1 −T 2 ) on line  696  to register memory  695  which passes E and D on lines  635  and  640 , respectively, to multi-cycle multiplier  610  which computes E*D and sends the result on line  650  to register memory  695  where the result is stored in temporary register T 2 . 
         [0027]    Step  305  utilizes multi-cycle multiplier  610 . T 2  is provided from register memory  695  to both lines  635  and  640  to multi-cycle multiplier  610  which computes and outputs T 2   2  on line  650  to register memory  695  where the result is stored in X 3 . 
         [0028]    Step  306  utilizes both multi-cycle multiplier  610  and SAU  400 . Register memory  695  provides Y 1  on line  665  to input “0” of MUX  620  and MUX  620  is set to “0”. MUX  620  sends Y 1  to input A of SAU  400  on line  671 . Logical one bit left shifter  718  takes input A on line  671 , multiplies input A by two and outputs 2A on line  771  to MUX  720 . MUX  720  in SAU  400  is set to “1” and MUX  720  sends 2A on line  776  to the minuend input of subtractor  710 . Binary 0 is supplied on line  660  to input “0” of MUX  630  with MUX  630  set to “0”. MUX  630  sends binary 0 from line  660  to input B of SAU  400  on line  672 . MUX  725  in SAU  400  is set to “1” and MUX  725  sends binary 0 on line  777  to the subtrahend input of subtractor  710 . Subtractor  710  computes 2A−B on line  696  to register memory  695  as E (which is 2A−B=2Y 1 ) which passes the value through on line  635  to multi-cycle multiplier  610  and register memory  695  provides Z 1  on line  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes E*Z 1  (2Y 1 *Z 1 ) and sends the result on line  650  to register memory  695  where it is stored in Z 3 . 
         [0029]    Step  307  utilizes both multi-cycle multiplier  610  and SAU  400 . Register memory  695  provides Y 1  on line  665  to input “0” of MUX  620  and MUX  620  is set to “0”. MUX  620  sends Y 1  to input A of SAU  400  on line  671 . Logical one bit left shifter  715  takes input A on line  671 , multiplies input A by two and outputs 2A on line  771  to input “1” of MUX  720 . MUX  720  in SAU  400  is set to “1” and MUX  720  sends 2A on line  776  to the minuend input of subtractor  710 . Binary 0 is supplied on line  660  to input “0” of MUX  630  with MUX  630  set to “0”. MUX  630  sends binary 0 from line  660  to input B of SAU  400  on line  672 . MUX  725  in SAU  400  is set to “1” and MUX  725  sends binary 0 on line  777  to the subtrahend input of subtractor  710 . Subtractor  710  computes 2A−B (which is 2Y 1 ) as E on line  696  to register memory  695  which passes E through both on line  635  and on line  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes E 2  (which is (2Y 1 ) 2 ) and sends the result to register memory  695  on line  650  where it is stored in Y 3 . 
         [0030]    Step  308  utilizes both multi-cycle multiplier  610  and SAU  400 . Register memory  695  provides X 3  on line  665  to input “0” of MUX  620  and MUX  620  is set to “0”. MUX  620  sends X 3  to input A of SAU  400  on line  671  which connects to input “0” of MUX  720  with MUX  720  set to “0”. MUX  720  sends A on line  776  to the minuend input of subtractor  710 . Register memory  695  provides Y 3  on line  635  to multi-cycle multiplier  610  and provides X 1  on line  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes Y 3 *X 1  and sends the result to input “1” of MUX  630  and MUX  630  is set to “1”. MUX  630  sends Y 3 *X 1  to input B of SAU  400  on line  672 . Logical one bit left shifter  717  takes input B on line  672 , multiplies input B by two and outputs 2B (2Y 3 *X 1 ) on line  774  to input “2” of MUX  720 . MUX  720  is set to “2” and sends 2B on line  777  to the subtrahend input of subtractor  710 . Subtractor  710  computes E (which is A−2B=X 3 −2Y 3 *X 1 ) on line  696  to register memory  695  where it is stored in X 3 . 
         [0031]    Step  309  utilizes both multi-cycle multiplier  610  and SAU  400 . In step  308 , 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  309  is sent on line  650  to input “1” of MUX  620  and MUX  620  is set to “1”. MUX  620  provides Y 3 *X 1  to input A of SAU  400  on line  671  which connects to input “0” of MUX  720 . MUX  720  in SAU  400  is set to “0” and MUX  720  sends A (which is Y 3 *X 1 ) on line  776  to the minuend input of subtractor  710 . Register memory  695  provides X 3  on line  660  to input “0” of MUX  630  and MUX  630  is set to “0”. MUX  630  sends X 3  to input B of SAU  400  on line  672  which connects to input “1” of MUX  725 . MUX  725  is set to “1” and provides B on line  777  to the subtrahend input of subtractor  710 . Subtractor  710  computes E (A−B=Y 3 *X 1 ) which is sent on line  696  to register memory  695  which passes the value through on line  635  to multi-cycle multiplier  610  and register memory  695  provides T 2  on line  640  to multi-cycle multiplier  610 . Multi-cycle multiplier  610  computes E*T 2  (which is (Y 3 *X 1 −X 3 )*T 2 ) and sends the result on line  650  to register memory  695  where it is stored in temporary register T 1 . 
         [0032]    Step  310  utilizes both multi-cycle multiplier  610  and SAU  400 . Register memory  695  provides T 1  on line  665  to input “0” of MUX  620  and MUX  620  is set to “0”. MUX  620  sends T 1  to input A of SAU  400  on line  671  which connects to input “0” of MUX  720 . MUX  720  in SAU  400  is set to “0” and MUX  720  sends A (T 1 ) on line  776  to the minuend input of subtractor  710 . Y 3  is provided from register memory  695  to both lines  635  and  640  to multi-cycle multiplier  610  which computes Y 3   2  and which is output on line  650  to input “1” of MUX  630  with MUX  630  set to “1”. MUX  630  provides Y 3   2  on line  672  to input B of SAU  400 . Logical one bit right shifter  716  takes input B on line  672 , divides input B by two and outputs B/2 (Y 3   2 /2) to input “0” of MUX  725  and MUX  725  is set to “0”. MUX  725  sends B/2 on line  777  to the subtrahend input of subtractor  710 . Subtractor  710  computes E (A−B/2=T 1 −Y 3   2 /2) which is sent on line  696  to register memory  695  where it is stored in Y 3 . 
         [0033]    Step  311  is performed in the microprocessor and returns the result of PDBL algorithm  300  which is (X 3 , Y 3 , Z 3 ) for input (X 1 , Y 1 , Z 1 ).