Optimized hardward architecture and method for ECC point addition using mixed affine-jacobian coordinates over short weierstrass curves

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.

Claims

1. A data cryptographic apparatus comprising: computational logic configured to perform an elliptic curve cryptography (ECC) point addition operation using mixed affine-Jacobian coordinates over a short Weierstrauss curve of the form y=x.sup.3+ax+b where a=3; a register memory configured to store a first point in affine coordinates and a second point in Jacobian coordinates, wherein the register memory is configured for two temporary storage variables, T.sub.1 and T.sub.2; a modular multiplier electrically coupled to the register memory, wherein the modular multiplier is configured to perform at most one modular multiplication for each step in a sequence of steps in the ECC point addition operation; and a simple arithmetic processor configured to perform modular subtraction and modular multiplication by two in support of the ECC point addition operation utilizing two modular subtractors, a logical one bit left shifter to either output AB2C for an input of variables A, B, and C or AB for an input of variables A and B, wherein the simple arithmetic processor is electrically coupled to the computational logic, the register memory, and the modular multiplier to output a result of the ECC point addition operation in the Jacobian coordinates.

2. A mobile device comprising the data cryptographic apparatus of claim 1.

3. A smartcard comprising the data cryptographic apparatus of claim 1.

4. The mobile device of claim 2, wherein the mobile device is a smartphone.

5. A method for performing an elliptic curve cryptography (ECC) point addition operation using mixed affine-Jacobian coordinates over a short Weierstrauss curve of the form y=x.sup.3+ax+b where a=3 comprising: accepting, with a computational device, as variable input a first point in affine coordinates and a second point in Jacobian coordinates using a simple arithmetic processor; configuring the simple arithmetic processor for modular subtraction and modular multiplication by two utilizing two modular subtractors, a logical one bit left shifter to either output AB2C for an input of variables A, B, and C or AB for an input of variables A and B; enabling a modular multiplier of the computational device to execute a sequence of steps to perform the ECC point addition operation of the first point and the second point, wherein the modular multiplier performs at most one modular multiplication for each step in the sequence of steps, wherein the sequence of steps requires no more than two temporary variables; and outputting, by the computational device, a result of the ECC point addition operation in the Jacobian coordinates.

6. The method of claim 5, wherein the computational device is part of a mobile device.

7. The method of claim 6, wherein the mobile device is a smartphone.

8. The method of claim 5, wherein the computational device is part of a smartcard.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows stages 101, 102 and 103 that are needed to realize the Elliptical Curve Digital Signature Algorithm (ECDSA).

(2) FIG. 2 shows a prior art point addition algorithm.

(3) FIG. 3 shows an embodiment in accordance with the invention.

(4) FIG. 4 show an embodiment in accordance with the invention.

(5) FIG. 5 shows an embodiment in accordance with the invention.

(6) FIG. 6 shows an embodiment in accordance with the invention.

(7) FIG. 7 shows an embodiment in accordance with the invention.

DETAILED DESCRIPTION

(8) 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.sub.1 and T.sub.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.

(9) As input in step 301, PADD algorithm 300 shown in FIG. 3 takes point P=(X.sub.1, Y.sub.1, Z.sub.1) in Jacobian coordinates and point Q=(x.sub.2, y.sub.2) in affine coordinates as the two points to be added together as P+Q. T.sub.1 and T.sub.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.sub.1 is squared and the resulting value stored in temporary register T.sub.1. In step 305, Z.sub.1*T.sub.1 is calculated and the resulting value stored in temporary register T.sub.2. In step 306, T.sub.2*y.sub.2Y.sub.1 is calculated, where y.sub.2 is in affine coordinates and Y.sub.1 is in Jacobian coordinates, the result being stored in temporary register T.sub.2. In step 307, the value stored in temporary register T.sub.1 is multiplied by x.sub.2 and X.sub.1 is then subtracted from the result, where x.sub.2 is in affine coordinates and X.sub.1 is in Jacobian coordinates, the result being stored in temporary register T.sub.1. Step 308 provides for a return if T.sub.1 and T.sub.2 are both zero as this means P=Q and step 309 provides for a return if T.sub.1 is zero and T.sub.2 is not zero as this means P=Q. In step 310, the Jacobian coordinate Z.sub.1 is multiplied by the value in temporary register T.sub.1 and the result is stored as Jacobian coordinate Z.sub.3. In step 311, the value stored in temporary register T.sub.1 is squared and stored as Jacobian coordinate Y.sub.3. In step 312, the value stored in temporary register T.sub.2 is squared and stored as Jacobian coordinate X.sub.3. In step 313, Y.sub.3*T.sub.1 is calculated and the result is stored in temporary register T.sub.1. In step 314, T.sub.1+2Y.sub.3*X.sub.1 is calculated and subtracted from Jacobian coordinate X.sub.3 with the result stored as Jacobian coordinate X.sub.3. In step 315, Y.sub.3*X.sub.1X.sub.3 is calculated and multiplied by T.sub.2 and stored as Jacobian coordinate Y.sub.3. Note that Y.sub.3*X.sub.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.sub.1*Y.sub.1 is calculated and subtracted from Jacobian coordinate Y.sub.3 and the result is stored as Jacobian coordinate Y.sub.3. Finally, in step 317 the result of the point addition of P+Q: (X.sub.3, Y.sub.3, Z.sub.3) is returned in Jacobian coordinates.

(10) 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.sub.3*X.sub.1 has already been calculated in step 314 and is fed in directly into the input of the hardware modular multiplier.

(11) 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.

(12) 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.sub.2*y.sub.2 and B=Y.sub.1 with output D=AB. Output D is written to temporary register T.sub.2. Block 501 shows how step 307 of PADD algorithm 300 is broken down using SAU 400 and involves setting inputs A=T.sub.1*x.sub.2 and B=X.sub.1 with output D=AB. Output D is then written to temporary register T.sub.1. Block 503 shows how step 314 of PADD algorithm 300 is broken down using SAU 400 and involves setting inputs A=X.sub.3, B=T.sub.1, C=y.sub.2*X.sub.1 with output D=AB2C. Output D is written to Jacobian coordinate X.sub.3. Block 504 shows how step 315 of PADD algorithm 300 is broken down using SAU 400 and involves setting inputs A=Y.sub.3*X.sub.1 and B=X.sub.3 with output D=AB. Output D is written to Jacobian coordinate Y.sub.3. Block 505 shows how step 316 of PADD algorithm 300 is broken down using SAU 400 and involves setting inputs A=Y.sub.3 and B=T.sub.1*Y.sub.1 with output D=AB. Output D is written to Jacobian coordinate Y.sub.3. Note that don't care indicates the value is irrelevant to the calculation being performed in the respective steps.

(13) 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.sub.1, Y.sub.1, Z.sub.1, x.sub.2, y.sub.2, output registers X.sub.3, Y.sub.3, Z.sub.3 and temporary registers T.sub.1 and T.sub.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).

(14) 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 AB 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 AB2C on line 750 to the 1 input for MUX 740. MUX 740 sends D on line 690.

(15) 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.

(16) Step 304 utilizes multi-cycle multiplier 610. Register memory 695 provides Z.sub.1 on both inputs 635 and 640 of multi-cycle multiplier 610 and multi-cycle multiplier 610 computes Z.sub.1.sup.2 which is sent on line 650 to register memory 695 and stored in temporary register T.sub.1.

(17) Step 305 utilizes multi-cycle multiplier 610. Register memory 695 provides T.sub.1 on input 635 and Z.sub.1 on input 640 of multi-cycle multiplier 610. Multi-cycle multiplier 610 computes T.sub.1*Z.sub.1 which is sent on line 650 to register memory 695 where it is stored in temporary register T.sub.2.

(18) Step 306 utilizes both multi-cycle multiplier 610 and SAU 400. Register memory 695 provides T.sub.2 and y.sub.2 on lines 635 and 640, respectively, to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes T.sub.2*y.sub.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.sub.2*y.sub.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.sub.1 on line 660 to input 0 of MUX 630 and MUX 630 is set to 0. MUX 630 sends Y.sub.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 AB (which is T.sub.2*y.sub.2Y.sub.1) and outputs AB on line 730 to input 0 of MUX 740 with MUX 740 set to 0. MUX 740 sends D (which is AB) on line 690 to register memory 695 where it is stored in temporary register T.sub.2.

(19) Step 307 utilizes both multi-cycle multiplier 610 and SAU 400. Register memory 695 provides T.sub.1 and x.sub.2 on lines 635 and 640, respectively, to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes T.sub.1*x.sub.2 which is output on line 650 to input 1 of MUX 620 with MUX 620 set to 1. MUX 620 sends T.sub.1*x.sub.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.sub.1 on line 660 to input 0 of MUX 630 and MUX 630 is set to 0. MUX 630 sends X.sub.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 AB (which is T.sub.1*x.sub.2X.sub.1) and outputs AB on line 730 to input 0 of MUX 740 with MUX 740 set to 0. MUX 740 sends D (which is AB) on line 690 to register memory 695 where it is stored in temporary register T.sub.1.

(20) Steps 308-309 are performed in the microprocessor (not shown) without using multi-cycle multiplier 610 and SAU 400.

(21) Step 310 utilizes multi-cycle multiplier 610. Register memory 695 provides T.sub.1 on line 635 and Z.sub.1 on line 640 to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes T.sub.1*Z.sub.1 and the result is output on line 650 to register memory 695 where it is stored in temporary register T.sub.2.

(22) Step 311 utilizes multi-cycle multiplier 610. Register memory 695 provides T.sub.1 on both lines 635 and 640 to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes T.sub.1.sup.2 and the result is output on line 650 to register memory 695 Y.sub.3 where it is stored in Y.sub.3.

(23) Step 312 utilizes multi-cycle multiplier 610. Register memory 695 provides T.sub.2 on both lines 635 and 640 to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes T.sub.2.sup.2 and the result is output on line 650 to register memory 695 where it is stored in X.sub.3.

(24) Step 313 utilizes multi-cycle multiplier 610. Register memory 695 provides T.sub.1 on line 635 and Y.sub.3 on line 640 to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes T.sub.1*Y.sub.3 and the result is output on line 650 to register memory 695 where it is stored in temporary register T.sub.1.

(25) Step 314 utilizes both multi-cycle multiplier 610 and SAU 400. Register memory 695 provides X.sub.3 on line 665 to input 0 of MUX 620 with MUX 620 set to 0. MUX 620 sends X.sub.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.sub.1 on line 660 to input 0 of MUX 630 with MUX 630 set to 0. MUX 630 sends T.sub.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 AB (which is X.sub.3T.sub.1) on line 730 to the minuend input of subtractor 720. Register memory 695 provides X.sub.1 on line 635 and Y.sub.3 on line 640 to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes Y.sub.3*X.sub.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.sub.3*X.sub.1) on line 735 to the subtrahend output of subtractor 720. Subtractor 720 computes and outputs AB2C on line 750 to input 1 of MUX 740 with MUX 740 set to 1. MUX 740 sends D (which is AB2C=X.sub.3T.sub.12Y.sub.3*X.sub.1) on line 690 to register memory 695 where it is stored in X.sub.3.

(26) Step 315 utilizes both multi-cycle multiplier 610 and SAU 400. In step 314, Y.sub.3*X.sub.1 was computed by multi-cycle multiplier 610. Hence, Y.sub.3*X.sub.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.sub.3*X.sub.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.sub.3 on line 660 to input 0 of MUX 630 with MUX 630 set to 0. MUX 630 sends X.sub.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 AB and sends the result on line 730 to input 0 of MUX 740 with MUX 740 set to0. MUX 740 sends D (which is AB=Y.sub.3*X.sub.1X.sub.3) on line 690 to register memory 695 which passes D through on line 635 and provides T.sub.2 on line 640 to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes D*T.sub.2 (which is (Y.sub.3*X.sub.1X.sub.3)*T.sub.2) and outputs the result on line 650 to register memory 695 where the result is stored in Y.sub.3.

(27) Step 316 utilizes both multi-cycle multiplier 610 and SAU 400. Register memory 695 provides Y.sub.3 on line 665 to input 0 of MUX 620 with MUX 620 set to 0. MUX 620 sends Y.sub.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.sub.1 on line 635 and Y.sub.1 on line 640 to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes and outputs T.sub.1*Y.sub.1 on line 650 to input 1 of MUX 630 with MUX 630 set to 1. MUX 630 sends T.sub.1*Y.sub.1 on line 675 to input B of SAU 400. Line 675 is directly connected to the subtrahend of subtractor 710. Subtractor 710 computes AB (which is Y.sub.3T.sub.1*Y.sub.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.sub.3T.sub.1*Y.sub.1) on line 690 to register memory 695 where the result is stored in Y.sub.3.

(28) Step 317 returns the result of the addition of P+Q in Jacobian coordinates which is (X.sub.3, Y.sub.3, Z.sub.3).