Optimized hardware architecture and method for ECC point doubling using jacobian coordinates over short weierstrass curves
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.
Term
8.2 yearsto projected expiry
Projected expiry 18 December 2034, counted from filing; an application has no term until it is granted.
- Priority
- Filed
- Published
- Today
- Projected expiry
14 claims: 10 independent, 4 dependent
- 1An apparatus for performing an elliptic curve cryptography point doubling operation using Jacobian coordinates comprising:- a register memory for storing a point in Jacobian coordinates;- a modular multiplier electrically coupled to the register memory;and - a simple arithmetic processor electrically coupled to the register memory and the modular multiplier, wherein the simple arithmetic processor is configured to perform modular subtraction, modular multiplication by two and modular division by two in support of the point doubling operation comprising a plurality of steps in Jacobian coordinates.
- 2The apparatus of Claim 1 wherein the simple arithmetic processor comprises three logical one bit left shifters.
- 4The apparatus of any preceding Claim wherein the point doubling operation is performed over a short Weierstrass curve of the form y = x 3 + ax + b where a = -3.
- 5The apparatus of any preceding Claim wherein the register memory is configured for two temporary storage variables, T 1 and T 2 .
- 6A mobile device comprising the apparatus of any preceding Claim.
- 7A smartcard comprising the apparatus of any preceding Claim.
- 8The mobile device of any preceding Claim wherein the mobile device is a smartphone.
- 9The apparatus of any preceding Claim 1 wherein the modular multiplier is configured to perform at most one modular multiplication for each one of the plurality of steps.
- 10The apparatus of any preceding Claim wherein the simple arithmetic processor is configurable to output A - B/2 for an input of variables A and B.
- 11A method for performing an elliptic curve cryptography point doubling operation using Jacobian coordinates comprising:- accepting the input of a point in Jacobian coordinates into a computational device having a register memory, a modular multiplier and a simple arithmetic processor configured for modular subtraction, modular division by two and modular multiplication by two;- enabling the computational device to execute a sequence of steps to perform the elliptic curve cryptography point doubling operation of the point wherein the modular multiplier performs at most one modular multiplication per step.
- 12The method of Claim 11 wherein the simple arithmetic processor is configurable to output A - B/2 for an input of variables A, B.
Independent claims14
27 paragraphs in 4 sections, as filed
BACKGROUND
0001Electronic 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.
0002The 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.
0003Public 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.
0004Building an efficient implementation of ECC is typically non-trivial and involves multiple stages. <figref idref="f0001">FIG. 1</figref> 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.
0005Any 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): <maths id="math0001" num="(1)"><math display="block"><msup><mi>y</mi><mn>2</mn></msup><mo>=</mo><msup><mi>x</mi><mn>3</mn></msup><mo>+</mo><mi>a</mi><mo></mo><mi>x</mi><mo>+</mo><mi>b</mi></math><img file="EP2887342A2_D0001.tif" /></maths> that is non-singular; that is it has no cusps or self-intersections and is known as the short Weierstrass form where <i>a</i> and <i>b</i> are integers. The case where <i>a</i> = -3 is typically used in several standards such as those published by NIST, SEC and ANSI which makes this the case of typical interest.
0006Many 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.
0007A PDBL algorithm for Jacobian coordinates has been described by <nplcit id="ncit0001" npl-type="b"><text>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</text></nplcit>. 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 <figref idref="f0002">FIG. 2</figref>. 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 <i>p</i> so that all arithmetic operations are performed modulo <i>p</i>. The identity element is the point at infinity.
SUMMARY
0008An 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<ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIG. 1</figref> shows stages 101, 102 and 103 that are needed to realize the Elliptical Curve Digital Signature Algorithm (ECDSA).</li><li><figref idref="f0002">FIG. 2</figref> shows a prior art point doubling algorithm.</li><li><figref idref="f0003">FIG. 3</figref> shows an embodiment in accordance with the invention.</li><li><figref idref="f0003">FIG. 4</figref> shows an embodiment in accordance with the invention.</li><li><figref idref="f0004">FIG. 5</figref> shows an embodiment in accordance with the invention.</li><li><figref idref="f0005">FIG. 6</figref> shows an embodiment in accordance with the invention.</li><li><figref idref="f0006">FIG. 7</figref> shows an embodiment in accordance with the invention.</li></ul>
DETAILED DESCRIPTION
0010PDBL algorithm 300 in accordance with the invention is shown in <figref idref="f0003">FIG. 3</figref>. 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<sub>1</sub> and T<sub>2</sub>. PDBL algorithm 300 is implemented over an optimized hardware architecture shown in <figref idref="f0005">FIG. 6</figref> and <figref idref="f0006">FIG. 7</figref> and specifically designed to take advantage of PDBL algorithm 300.
0011As input in step 301, PDBL algorithm 300 shown in <figref idref="f0003">FIG. 3</figref> takes point P = (X<sub>1</sub>, Y<sub>1</sub>, Z<sub>1</sub>) in Jacobian coordinates. T<sub>1</sub> and T<sub>2</sub> 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<sub>1</sub> is squared (Z<sub>1</sub> * Z<sub>1</sub>) and subtracted from X<sub>1</sub> with the resulting value stored in temporary register T<sub>2</sub>. In step 304, 3T<sub>2</sub> * (2X<sub>1</sub> - T<sub>2</sub>) is calculated and the resulting value stored in temporary register T<sub>2</sub>. In step 305, T<sub>2</sub> is squared and the result stored in X<sub>3</sub>. In step 306, 2Y<sub>1</sub> * Z<sub>1</sub> is calculated, the result stored in Z<sub>3</sub>. In step 307, 2Y<sub>1</sub> is calculated and squared (2Y<sub>1</sub> * 2Y<sub>1</sub>) with the result stored in Y<sub>3</sub>. In step 308, X<sub>3</sub> - 2Y<sub>3</sub> * X<sub>1</sub> is calculated and the result stored in X<sub>3</sub>. In step 309, (Y<sub>3</sub> * X<sub>1</sub> - X<sub>3</sub>) is calculated and multiplied by T<sub>2</sub> and the result is stored in T<sub>1</sub>. Note that the quantity Y<sub>3</sub> * X<sub>1</sub> was already calculated in step 308 so step 309 only requires a single modular multiplication (by T<sub>2</sub>). In step 310, T<sub>1</sub> - Y<sub>3</sub> * Y<sub>3</sub>/2 is calculated and the result is stored in Y<sub>3</sub>. Finally, in step 311 the result of the point doubling of P is returned in Jacobian coordinates as (X<sub>3</sub>, Y<sub>3</sub>, Z<sub>3</sub>).
0012The most computationally intensive operation in PDBL algorithm 300 in <figref idref="f0003">FIG. 3</figref> 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.
0013It 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 <figref idref="f0003">FIG. 4</figref> is used.
0014<figref idref="f0004">FIG. 5</figref> 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 <figref idref="f0004">FIG. 5</figref>. Block 501 shows how step 303 of PDBL algorithm 300 is broken down using SAU 400 and involves setting inputs A = X<sub>1</sub> and B = Z<sub>1</sub><sup>2</sup> 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<sub>1</sub>, B = T<sub>2</sub> and C = T<sub>2</sub> 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<sub>2</sub>. Block 503 shows how step 306 of PDBL algorithm 300 is broken down using SAU 400 and involves setting A = Y<sub>1</sub> and B = 0 with output E = 2A - B. Output E is then multiplied by Z<sub>1</sub> and the result is stored in Z<sub>3</sub>. Block 504 shows how step 307 of PDBL algorithm 300 is broken down using SAU 400 and involves setting inputs A = Y<sub>1</sub> and B = 0 with output E = 2A - B. Output E is then multiplied by itself and the result is stored in Y<sub>3</sub>. Block 505 shows how step 308 of PDBL algorithm 300 is broken down using SAU 400 and involves setting inputs A = X<sub>3</sub> and B = X<sub>1</sub> * Y3 with output E = A - 2B. Output E is stored in X<sub>2</sub>. Block 506 shows how step 309 of PDBL algorithm 300 is broken down using SAU 400 and involves setting input A = X<sub>1</sub> * Y<sub>3</sub> and B = X<sub>3</sub> with output E = A - 2B. Note that step 309 reuses the result of step 308 for X<sub>1</sub> * Y<sub>3</sub> (stored in the output register of the multiplier). Output E is stored in X<sub>3</sub>. Block 507 shows how step 310 of PDBL algorithm 300 is broken down using SAU 400 and involves setting inputs A = T<sub>1</sub> and B = Y<sub>3</sub><sup>2</sup> with output E = A - B/2. Note that "don't care" indicates the value is irrelevant to the calculation being performed in the respective steps.
0015<figref idref="f0005">FIG. 6</figref> 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</sub>, Y<sub>1</sub>, Z<sub>1</sub>, (x<sub>2</sub>, y<sub>2</sub> - not used), output registers X<sub>3</sub>, Y<sub>3</sub>, Z<sub>3</sub> and temporary registers T<sub>1</sub> and T<sub>2</sub> that are all part of register memory 695. Note the individual register labels correspond to variable names in <figref idref="f0003">FIGs. 3</figref> and <figref idref="f0004">5</figref>. MUX 620, 630 and 740 (part of SAU 400, see <figref idref="f0006">FIG. 7</figref>) 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).
0016SAU 400 shown in <figref idref="f0006">FIG. 7</figref> 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.
0017Input 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 <figref idref="f0003">FIG. 4</figref>) on line 696. Adder 722 outputs D ( = 3C) on line 690.
0018Multi-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.
0019Step 303 utilizes both multi-cycle multiplier 610 and SAU 400. Register memory 695 provides X<sub>1</sub> on line 665 to input "0" of MUX 620 with MUX 620 set to "0" and Z<sub>1</sub> is provided from register memory 695 on both lines 635 and 640 to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes Z<sub>1</sub><sup>2</sup> which is output on line 650 to input "1" of MUX 630 with MUX 630 set to "1". MUX 620 sends X<sub>1</sub> to input A of SAU 400 on line 671 and MUX 630 sends Z<sub>1</sub><sup>2</sup> 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<sub>1</sub> - Z<sub>1</sub><sup>2</sup>) of which is passed to register memory 695 on line 696 and stored in temporary register T<sub>2</sub>.
0020Step 304 utilizes both multi-cycle multiplier 610 and SAU 400. Register memory 695 provides X<sub>1</sub> on line 665 to input "0" of MUX 620 and MUX 620 is set to "0". MUX 620 sends X<sub>1</sub> to input A of SAU 400 on line 671. Register memory 695 provides T<sub>2</sub> on line 660 to input "0" of MUX 630 with MUX 630 set to "0" and register memory 695 also provides T<sub>2</sub> 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<sub>2</sub>) 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<sub>2</sub>) on line 690 and subtractor 710 computes E (which is 2A -B = 2X<sub>1</sub> - T<sub>2</sub>) 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<sub>2</sub>.
0021Step 305 utilizes multi-cycle multiplier 610. T<sub>2</sub> is provided from register memory 695 to both lines 635 and 640 to multi-cycle multiplier 610 which computes and outputs T<sub>2</sub><sup>2</sup> on line 650 to register memory 695 where the result is stored in X<sub>3</sub>.
0022Step 306 utilizes both multi-cycle multiplier 610 and SAU 400. Register memory 695 provides Y<sub>1</sub> on line 665 to input "0" of MUX 620 and MUX 620 is set to "0". MUX 620 sends Y<sub>1</sub> 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<sub>1</sub>) which passes the value through on line 635 to multi-cycle multiplier 610 and register memory 695 provides Z<sub>1</sub> on line 640 to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes E * Z<sub>1</sub> (2Y<sub>1</sub> * Z<sub>1</sub>) and sends the result on line 650 to register memory 695 where it is stored in Z<sub>3</sub>.
0023Step 307 utilizes both multi-cycle multiplier 610 and SAU 400. Register memory 695 provides Y<sub>1</sub> on line 665 to input "0" of MUX 620 and MUX 620 is set to "0". MUX 620 sends Y<sub>1</sub> 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<sub>1</sub>) 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<sup>2</sup> (which is (2Y<sub>1</sub>)<sup>2</sup>) and sends the result to register memory 695 on line 650 where it is stored in Y<sub>3</sub>.
0024Step 308 utilizes both multi-cycle multiplier 610 and SAU 400. Register memory 695 provides X<sub>3</sub> on line 665 to input "0" of MUX 620 and MUX 620 is set to "0". MUX 620 sends X<sub>3</sub> 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<sub>3</sub> on line 635 to multi-cycle multiplier 610 and provides X<sub>1</sub> on line 640 to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes Y<sub>3</sub> * X<sub>1</sub> and sends the result to input "1" of MUX 630 and MUX 630 is set to "1". MUX 630 sends Y<sub>3</sub> * X<sub>1</sub> 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<sub>3</sub> * X<sub>1</sub>) 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<sub>3</sub> - 2Y<sub>3</sub> * X<sub>1</sub>) on line 696 to register memory 695 where it is stored in X<sub>3</sub>.
0025Step 309 utilizes both multi-cycle multiplier 610 and SAU 400. In step 308, Y<sub>3</sub> * X<sub>1</sub> was computed by multi-cycle multiplier 610. Hence, Y<sub>3</sub> * X<sub>1</sub> 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<sub>3</sub> * X<sub>1</sub> 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<sub>3</sub> * X<sub>1</sub>) on line 776 to the minuend input of subtractor 710. Register memory 695 provides X<sub>3</sub> on line 660 to input "0" of MUX 630 and MUX 630 is set to "0". MUX 630 sends X<sub>3</sub> 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<sub>3</sub> * X<sub>1</sub>) 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<sub>2</sub> on line 640 to multi-cycle multiplier 610. Multi-cycle multiplier 610 computes E * T<sub>2</sub> (which is (Y<sub>3</sub> * X<sub>1</sub> - X<sub>3</sub>) * T<sub>2</sub>) and sends the result on line 650 to register memory 695 where it is stored in temporary register T<sub>1</sub>.
0026Step 310 utilizes both multi-cycle multiplier 610 and SAU 400. Register memory 695 provides T<sub>1</sub> on line 665 to input "0" of MUX 620 and MUX 620 is set to "0". MUX 620 sends T<sub>1</sub> 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 (Ti) on line 776 to the minuend input of subtractor 710. Y<sub>3</sub> is provided from register memory 695 to both lines 635 and 640 to multi-cycle multiplier 610 which computes Y<sub>3</sub><sup>2</sup> and which is output on line 650 to input "1" of MUX 630 with MUX 630 set to "1". MUX 630 provides Y<sub>3</sub><sup>2</sup> 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<sub>3</sub><sup>2</sup>/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<sub>1</sub> - Y<sub>3</sub><sup>2</sup>/2) which is sent on line 696 to register memory 695 where it is stored in Y<sub>3</sub>.
0027Step 311 is performed in the microprocessor and returns the result of PDBL algorithm 300 which is (X<sub>3</sub>, Y<sub>3</sub>, Z<sub>3</sub>) for input (X<sub>1</sub>, Y<sub>1</sub>, Z<sub>1</sub>).
Contents4
8 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8
Every citation, both ways
| Document | Relation | Office | Cited during |
|---|---|---|---|
| JP2007286380A | Cites | Japan | Search report |
| US2010011047A1 | Cites | United States of America | Search report |
| COHEN; MIYAJI; ONO: "Advances in Cryptology, ASIACRYPT", 1998, SPRINGER-VERLAG, article "Proceedings of the International Conference on the Theory and Applications of Cryptography and Information Security", pages: 51 - 65 | Non-patent | – | Applicant |
7 members in 3 offices
Priority claims4
| Document | Office | Kind | Date |
|---|---|---|---|
| 201314139847 | United States of America | A | |
| 201314139847 | United States of America | – | |
| US201314139847 | – | – | – |
| 201314139847 | – | – | – |
Members7
| Document | Office | Kind | |
|---|---|---|---|
| CN104734841A | China | A | |
| EP2887342A2This record | European Patent Office (EPO) | A2 | |
| US2015180665A1 | United States of America | A1 | |
| EP2887342A3 | European Patent Office (EPO) | A3 | |
| US9929862B2 | United States of America | B2 | |
| EP2887342B1 | European Patent Office (EPO) | B1 | |
| CN104734841B | China | B |
73 legal events, as 9 offices reported them to INPADOC
Over the term
Point at a mark for the eventEvents
| Event | Code | Office | |
|---|---|---|---|
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| Opt-out of the competence of the unified patent court (upc) registeredP01 | P01 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed because of non-payment of the annual feeLapsedMM | MM | BE | |
| Patent lapsedLapsedMM4A | MM4A | IE | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Gb: european patent ceased through non-payment of renewal feeCeasedGBPC | GBPC | EP | |
| Patent ceasedCeasedPL | PL | CH | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| No opposition filedOpposition26N | 26N | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| No opposition filed within time limitOppositionORIGINAL CODE: 0009261PLBE | PLBE | EP | |
| Information on the status of an ep patent application or granted ep patentGrantedSTATUS: NO OPPOSITION FILED WITHIN TIME LIMITSTAA | STAA | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| No opposition filed against granted patent, or epo opposition proceedings concluded without decisionGrantedR097 | R097 | DE | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Deletion acc. to par. 5 (withdrawal of the translation of the ep patent)MK05 | MK05 | AT | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Invalidated european patentMG4D | MG4D | LT | |
| Patent invalid in the netherlands as no translation has been filedMP | MP | NL | |
| Dpma publication of mentioned ep patent grantGrantedR096 | R096 | DE | |
| European patents granted designating irelandGrantedFG4D | FG4D | IE | |
| Reference to at number (ep patent validated in austria)REF | REF | AT | |
| European patent takes effect as a national patent in ch/liEP | EP | CH | |
| Designated contracting statesAK | AK | EP | |
| European patent grantedGrantedFG4D | FG4D | GB | |
| (expected) grantORIGINAL CODE: 0009210GRAA | GRAA | EP | |
| Grant fee paidORIGINAL CODE: EPIDOSNIGR3GRAS | GRAS | EP | |
| Intention to grant announcedINTG | INTG | EP | |
| Despatch of communication of intention to grant a patentORIGINAL CODE: EPIDOSNIGR1GRAP | GRAP | EP | |
| First examination report despatched17Q | 17Q | EP | |
| Request for examination filed (corrected)R17P | R17P | EP | |
| Designated contracting states (corrected)RBV | RBV | EP | |
| Designated contracting statesAK | AK | EP | |
| Request for extension of the european patentAX | AX | EP | |
| Information provided on ipc code assigned before grantRIC1 | RIC1 | EP | |
| Information provided on ipc code assigned before grantRIC1 | RIC1 | EP | |
| Search report despatchedORIGINAL CODE: 0009013PUAL | PUAL | EP | |
| Request for examination filed17P | 17P | EP | |
| Designated contracting statesAK | AK | EP | |
| Request for extension of the european patentAX | AX | EP | |
| Public reference made under article 153(3) epc to a published international application that has entered the european phaseORIGINAL CODE: 0009012PUAI | PUAI | EP |
Numbers
- Publication
- 2887342
- Publication, DOCDB
- 2887342
- Publication, EPODOC
- EP2887342
- Application
- 14198913
- Application, DOCDB
- 14198913
- Application, EPODOC
- EP20140198913
Titles3
- German
- Optimierte Hardware-Architektur und Verfahren zur ECC-Punktverdopplung mit Jacobi-Koordinaten über kurze Weierstraß-Kurven
- English
- Optimized hardware architecture and method for ECC point doubling using jacobian coordinates over short weierstrass curves
- French
- Architecture matérielle optimisée et procédé de doublage de point ECC au moyen des coordonnées jacobiennes sur des courbes de Weierstrass courtes
Classification
- CPC, 4
- H04L9/3066
- G06F7/725
- G09C1/00
- H04L2209/122
- IPC, 2
- G09C1 00
- H04L9 30
Designated states2
- Contracting states, 1
- Türkiye
- Extension states, 1
- Montenegro