DE10156708B4 - Method and apparatus for multiplying and method and apparatus for adding on an elliptic curve - Google Patents

Abstract

A method for adding two points on an elliptic curve y ² = x ³ + a x + b within a cryptographic algorithm, where x and y are coordinates of points on the elliptic curve, and wherein the elliptic curve is over a body having a characteristic larger 3, wherein a first point of the two points has a first projective coordinate X _P and a third projective coordinate Z _P , the second point having a first projective coordinate X _Q and a third projective coordinate Z _Q , comprising the following steps:
Calculating (31) a first projective coordinate X _{P 'of} a result point on the elliptic curve by the following equation: X P ' = 2 (X P Z Q + X Q Z P ) (X P X Q + aZ P Z Q ) + 4bZ P 2 Z Q 2 + x D (X P Z Q - X Q Z P ) 2 ; and Calculating (30) a third projective coordinate Z _{P 'of} a result point on the elliptic curve by the following equation: Z P ' = (X P Z Q - X Q Z P ) 2 . where a and b are parameters of the elliptic curve, and where x _{D is} an affine ...

Description

The The present invention relates to cryptographic algorithms and in particular elliptic curve cryptography.

in the Contrary to classical cryptography, such as B. the RSA method, where the modular exponentiation is a central arithmetic operation In elliptic curve cryptography, the multiplication of a Point P on the elliptic curve with an integer factor the corresponding essential operation.

For example can the classic DSA (DSA = Digital Signature Algorithm), such as he in the "Handbook of Applied Cryptography ", Menezes u. a., CRC Press, to EC-DSA (EC-DSA = Elliptic Curve Digital Signature Algorithm) as modified in the IEEE P 13.63 is described.

One another cryptographic algorithm that also works on elliptical Curves can be extended is the so-called Diffie-Hellman Key Exchange method, as described in the Handbook of Applied Cryptography.

Want two parties A, B a shared secret key over one If you have an unsafe channel, you can proceed as follows.

First, choose both Parties an elliptic curve as well as a generating point P this curve.

Party A now chooses a constant factor d _A and calculates the product Q _A = d _A P and sends this point Q _A over the unsafe channel to B.

Analogously, the party B now selects a constant factor d _B and calculates the product Q _B = d _B P and sends this point Q _B over the unsafe channel to A.

According to this, both parties have a secret key, namely the product d _A d _B P. The two parties can now basically use this secret key for a symmetric block encryption method.

It is not possible to calculate the constant factors d _A and d _B from the knowledge of Q _A , Q _B , P and the elliptic curve more efficiently than by mere trial and error. In other words, this means that the constant factors d _A , d _{B must be} protected from attacks on party A or party B.

The following is on 6 Reference is made to illustrate the known double-and-add algorithm that can also be used to calculate the multiplication of a point on the elliptic curve with a constant factor. In contrast to the usual arithmetic, in elliptic curve arithmetic the formulas for adding two points on the elliptic curve and the formulas for multiplying a point on the elliptic curve differ by a factor of 2. These addition formulas or multiplication formulas depend on the each selected elliptic curve.

The double-and-add algorithm generally calculates, as result E, the multiplication of an integer d by a point B on the elliptic curve, as in a block 100 in 6 is shown. As input, the algorithm requires the length n of the multiplier d, an increment size i, and a register E which is initialized to the value 0 at the beginning of the algorithm, as in a block 102 is shown. First, it is examined whether the considered bit i of the multiplier is 0 or 1 (block 104 ). If it is determined that the bit currently being considered is 1, the right branch of 6 taken. On the other hand, if it is determined that the bit under consideration is 0, the left branch is taken. The double & add algorithm, in the event that the bit of the multiplier under consideration is 1, causes the current contents of the register E to be doubled (block 106 ), and then adding to the value E the point B of the elliptic curve to obtain the new value E of the result E register (block 108 ). If, on the other hand, it is found that the current bit d _i currently being considered is 0, only one doubling step (Block 110 ), and there is no addition step.

After the termination of the loop or after the calculation of E, the run variable i is incremented by 1 (block 112 ). Then it is checked if i is smaller than n (block 114 ). If i is smaller than n, then the Loop (blocks 104 . 106 . 108 . 110 ) go through again. On the other hand, if it is determined that all the bits of the integer multiplier d have been processed, the current value of the register E is output as the result of multiplying the integer factor d by the point B on the elliptic curve (Block 116 ). As is known, the most significant bit of the multiplier d is considered first, whereupon the second highest bit is considered in the next pass, etc. The bits of the integer multiplier are therefore processed from most significant bits to least significant bits until the least significant bit is reached, which in the block 114 is detected. After processing the least significant bit, the result may be passed through the block 116 be issued.

A disadvantage of the in 6 The double-and-add algorithm described above is the fact that the calculation in the two branches is different in the number of steps, depending on whether the currently considered bit d _{i is} equal to 1 or equal to 0. Therefore, for certain attacks on the cryptographic algorithm, it is possible to determine from the power consumption or the time required for the calculation of an iteration, whether the bit currently being considered was a 1 or a 0. As has been stated, the scalar that is multiplied by a point on the elliptic curve is typically the secret information or secret key of a party to be protected from attack.

As a countermeasure against such an attack on the cryptographic algorithm could be in the double & add algorithm in the left branch of 6 a dummy addition 118 inserted, whose result is not used. This dummy addition 118 ensures that the time and power consumption of the crypto chip are the same for both cases, ie for d _i = 1 and d _i = 0, so that timing attacks or simple power analysis attacks will fail.

Calculation rules for calculating the sum of two points on an elliptic curve or for calculating the multiplication of a point on an elliptic curve by a factor of 2 or multiplying a point on the elliptic curve by a constant factor are for general elliptic curves of the form y ² = x ³ + a · x + b in Carl Pomerance, "Prime Numbers", Springer-Verlag, 2001, Chapter 7.2.) This book also gives an overview of the various coordinates, in which affine coordinates, projective coordinates, are modified projective coordinates as well as X, Z coordinates, also referred to as Montgomery coordinates Projective coordinates [X, Y, Z] can be converted into affine coordinates (x, y) as follows: x = X / Z and y = Y / Z.

Furthermore, in the same textbook, the so-called Lucas chain is explained, which consists in calculating the product k times P by means of a addition chain, wherein whenever two unequal points P ₁ , P ₂ are added together, the difference P ₁ - P _{2 is} known. Intermediate steps therefore involve a pair [m] P, [m + 1] P. From this pair, either the pair [2m] P, [2m + 1] P or the pair [2m + 1] P, [2m + 2] P is formed, depending on the bits of the scalar k. In any case, a doubling and an addition are performed. For the addition itself, the difference of the two points added is already known, namely P itself.

The Lucas chain allows it that the x-coordinate of a result point on the elliptic curve independent of the y-coordinate of this point can be calculated. For example, there exist Cryptographic methods that do not need the y-coordinate, such as The EC-DSA procedure, while Again, there are other cryptographic methods in which the y coordinate needed is, such. For example, the Diffie-Hellman method.

However, a disadvantage of the classic double-and-add algorithm is that no parallelization is possible. That is how the step can be 108 only be executed when the step 106 is calculated. The Double & Add algorithm can therefore be used in its in 6 not be parallelized form shown. In addition, through the dummy step 118 For reasons of security, computing resources are "wasted" without the result, for which the computational resources have been spent, being used.

However, in particular, in cryptographic algorithms on smart cards, where there are tight computational resource and storage capacity constraints, the algorithm's security as well as the algorithm's efficiency are essential. For example, the area of a chip on a smart card is limited by "outer" specifications to a specific chip area, leaving the developer free to use this total available chip area for its applications as a memory or as an arithmetic unit the. On the other hand, an acceptance of smart cards will only be present if digital signatures are of course certainly generated but also fast, because a customer does not want to wait several minutes for authentication, for example, at a cash machine.

The WO 00/25204 A1 apparently a cryptographic concept, the against Performance signature attacks is resistant. A multiple of a point on an elliptic curve defined over a field, is being computed. For this, the number that is the multiple of the point determined, as a binary vector represented, wherein an ordered pair of points is formed, where the dots are different from each other and where the bits of the vector chosen in sequence become. A new set of points is calculated by adding a first point is doubled and then the doubled point with the second point is added. The doublings and additions are always in the same order for every bit performed, which avoids timing attacks.

The WO 99/49386 A1 relates to accelerated operations on one elliptic curve. To multiply a point on an elliptical Curve with a value k, the value k is represented as a vector of binary numbers. Furthermore, a sequence of pairs of points is formed. The calculations are performed without using the y-coordinate of the points. The y-coordinate is then extracted at the end of the calculations, thereby no inversion operations are necessary.

The US Pat. No. 6,263,081 B1 discloses a rapid calculation of Multiple on an elliptic curve. A multiplication calculation unit generates precalculation tables for multiple of numbers at one-word intervals and for multiples of numbers at half-word intervals. Multiple points on an elliptic curve are set Using a doubling process calculated, but with a reduced number of additions.

The Specialist publication "A Small and Fast Software Implementation of Elliptic Curve Cryptosystems over GF (p) on a 16-Bit Microcomputer ", T. Hasegawa et al., IEICE Trans. Fundamentals, Vol. I82-A, No. 1, January 1999, pages 98-106 a new type of prim characteristic of a basic field, the for small and fast implementations is suitable. This prim characteristic is used to do a Galois field multiplication with a smaller one Code.

The Object of the present invention is to provide a concept for Multiply a number by one point on an elliptical one To create a curve as part of a cryptographic calculation, that is both efficient and safe.

These Problem is solved by a method for adding two points according to claim 1, a method for multiplying according to claim 2, a device for adding according to claim 3, an adding device according to claim 5, a device for multiplying according to claim 6 or a method for adding according to claim 7 solved.

Of the The present invention is based on the finding that of the Double & Add algorithm gone away must become, and that instead its the multiplication of a scalar with a point on the elliptic curve calculated using two auxiliary quantities must become, where an auxiliary size is always the same is twice the previous value of the auxiliary size while the other auxiliary size is always is equal to the sum of the two previous auxiliary quantities. Depending on if that just considered bit of the scalar, d. H. of the multiplier, one 1 or a 0, twice the one auxiliary size is calculated, or is charged twice the other auxiliary size. This means, that for both Cases, So for the case that that Bits of the scalar equal 0 or that the scalar's bit is equal 1, always one addition and one multiplication by 2 is performed. Thus, timing attacks or power-analysis attacks are a priori not effective. About that can out the two auxiliary variables independently of each other, ie be calculated in parallel, which leads to a performance gain. For this Although two parallel arithmetic units are needed. If these two parallel However, arithmetic units anyway in the crypto processor, for example the smart card for other reasons are present, this does not matter. What remains is the doubling of the Throughput over the simple double & add algorithm at elevated Safety.

The inventive method for multiplying a number by a dot refers to a elliptic curve y ² = x ³ + a x + b, where x is a first coordinate of the elliptic curve, where y is a second coordinate of the elliptic curve, and where the elliptic curve defines over a body with a characteristic p greater than 3 is. In this context, this means that all coordinates on the elliptic curve are subjected to a modulo operation with the characteristic p. It should be noted that the method according to the invention is not applicable to elliptic curves with characteristics of 3 or smaller than 3.

One Advantage of the present invention is that no Timing attacks or performance attacks are expedient because of the processing overhead for a Bit of the multiplier independent that's whether the bit has a 0 or a 1.

One Another advantage of the present invention is that the first and the second auxiliary point on the elliptic curve in each iteration step can be calculated in parallel, so that one Speed gain with a factor of the order of magnitude of 1.9 (theoretically 2) opposite the double & add algorithm can be reached with dummy addition.

Furthermore the invention is advantageous in that explicit addition formulas to calculate the first and second auxiliary points can, which in turn can be parallelized, which Overall, a performance gain with a factor of the order of 2.6 results.

Furthermore the invention is advantageous in that its applicability to any elliptic curves is applicable as long as the characteristics of the underlying body the elliptic curve is larger than 3 is.

preferred embodiments The present invention will be described below with reference to FIG the accompanying drawings explained in detail. Show it:

1 a block diagram of the inventive method for multiplying a number with a point on an elliptic curve;

2 a schematic block diagram of an adder for adding two points on the elliptic curve to obtain the first auxiliary point;

3 a principle block diagram of a multiplier for multiplying a point on the elliptic curve by a factor of 2 to obtain the second auxiliary point;

4 a block diagram of an arithmetic unit for adding and multiplying by a factor of 2 and parallelized functionality;

5 an overview diagram of the functionality of the flow control of 4 ; and

6 an overview diagram of the double & add algorithm with and without dummy addition.

1 FIG. 4 shows an overview diagram of the algorithm according to the invention for multiplying a number d by a point B on an elliptic curve of the following form: y 2 = x 3 + a · x + b, where a and b are constants. The elliptic curve is defined for characteristics p greater than 3 (block 10 ). In addition, two different points P and Q are considered, both of which are not equal to zero. The affine coordinates for the point P are (x _P , y _P ). The projective coordinates of the point P are (X _P : Y _P : Z _P ), where the point P is A ² = P ² -P ¹ . For these coordinates, inter alia, there are the relations X _P = x _P * Z _P and Y _P = y _P * Z _P.

In an initialization block 12 First, the length is set in bits n of the multiplier d (d ₀ , d ₁ , d ₂ , ..., d _n ), where d _{0 is} the most significant bit of the multiplier. Furthermore, a run variable i is initialized to zero. In addition, the first auxiliary point P is initialized to the zero point of the elliptic curve, and becomes the second auxiliary point Q initialized to B. This is followed in the iteration of 1 occurred.

alternative the first iteration step of the above method may already be described in the initialization will be taken because bits are above the most significant one Bits in the multiplier register are zero and the most significant Bit of the multiplier is always equal to one. In this case will P is initialized to B, and Q is initialized to 2B.

In a block 14 First, it is checked whether the currently considered bit of the multiplier d is equal to 0 or not. If this question is answered with Yes, then the right loop of 1 occurred. If, on the other hand, this question is answered with no, then the left loop of 1 occurred.

If the bit d _{i of} the multiplier equals 0, the new value P _{new of} the first auxiliary point is calculated by adding the two current auxiliary points P and Q (block 16 ). The second auxiliary point Q _new is calculated by multiplying the old second auxiliary point Q by a factor of 2 (block 18 ).

Will against it in the block 14 determines that the current bit d _{i of} the multiplier d is equal to 1, the new first auxiliary point P _new is calculated by multiplying the old first auxiliary point P by a factor of 2 ( 20 ). The new value of the second auxiliary point Q _new is calculated by summing the old first auxiliary point P and the old second auxiliary point Q (block 22 ).

The count variable i is then incremented by 1 at the output of the iteration loop (block 24 ), then in a block 26 to check if i is less than n. If this question is answered in the affirmative, it will, as in 1 is returned to examine the next bit of the multiplier d. Will the question of block 26 on the other hand answered No, the result E results in the first auxiliary point P in a block 28 output.

As already stated, for certain cryptographic algorithms only the x-coordinate of the result point E on the elliptic curve is needed. The in the blocks 12 . 16 . 18 . 20 and 22 In this case, the calculations shown above only have to be performed for the x-coordinate, which can be calculated independently of the y-coordinates of the auxiliary points P, Q due to the laws of the Lucas chain.

ever according to whether the y-coordinate of the point E is needed, this can be efficient Be calculated as it will be explained later.

For the sake of completeness, it is once again pointed out that an elliptic curve over a field of characteristic greater than 3 is based on the following equation of determination. y 2 = x 3 + ax + b (1)

The two auxiliary points P 'or P _new and Q' or Q _new calculated from the old auxiliary points P and Q in the case of a bit d _{i as} follows (right branch of the algorithm of 1 ): (P ', Q'): = (P + Q, 2Q) (2)

It should be noted that the same calculation is analogous to the left iteration branch of 1 can be performed by coordinate exchange.

In addition will introduced a value D equal to the difference between P and Q, and Q and P, respectively It should be noted that the Sign of the difference D not needed and therefore in the following not considered becomes. It should also be noted that the difference in each iteration step is the same and furthermore always B is itself, since in the first iteration step the difference between P and Q is equal to B.

The affine x-coordinate x _{P 'of} the first auxiliary point on the elliptic curve is calculated as follows from the affine x-coordinates of the old auxiliary points P and Q:

The affine x-coordinate x _{D of} the difference between P and Q is calculated as follows:

The affine x-coordinate x _{Q 'of} the second auxiliary point Q' is calculated as follows:

Now, when equations 3 and 4 are added together and y 2 / P and y 2 / Q are substituted using equation (1), the following expression is obtained: (x P ' + x D ) (X P - x Q ) 2 = 2 (x P + x Q ) (X P x Q + a) + 4b (6)

Finally, y 2 / P is substituted by equation (1), resulting in the following equation from equation (5): 4x Q ' (x Q 3 + ax Q + b) = (x Q 2 - a) 2 - 8bx Q (7)

Now _P X / Z _P is substituted for x _{P, Q} and X / Z _{Q Q} substituted for x. Thus, equation (6) yields the following equation: X P ' (X P Z Q - X Q Z P ) 2 = Z P ' (2 (X P Z Q + X Q Z P ) (X P X Q + aZ P Z Q ) + 4b 2 P Z 2 Q - x D (X P Z Q - X Q Z P ) 2 ) (8th)

With the same substitutions, equation (7) yields the following equation: X Q ' 4 (X Q Z Q (X 2 Q + aZ 2 Q ) + bZ 4 Q ) = Z Q ' ((X 2 Q - aZ 2 Q ) 2 - 8bX Q Z 3 Q (9)

This results in the following explicit formulas for the addition, ie for X _{P '} and Z _P' , ie for the first and third projective coordinates of the first auxiliary point: X P ' = 2 (X P Z Q + X Q Z P ) (X P X Q + aZ P Z Q ) + 4bZ P 2 Z Q 2 - x D (X P Z Q - X Q Z P ) 2 Z P ' = (X P Z Q - X Q Z P ) 2 (10a)

For the double formula, ie for the calculation of the second auxiliary point Q ', the following equations result: X Q ' = (X Q 2 - aZ Q 2 ) 2 - 8bX Q Z Q 3 Z Q ' = 4 (X Q Z Q (X Q 2 + aZ Q 2 ) + bZ Q 4 ) (10b)

By equations (10a) and (10b), explicit formulas are given to calculate the projective X, Z coordinates of the first auxiliary point P and the second auxiliary point Q. These coordinates depend only on known quantities, namely the corresponding coordinates of the "old" auxiliary points P, Q from the previous iteration step, if 1 is looked at.

In accordance with another aspect of the present invention, reference will now be made to FIGS 2 an adder is shown to add two points P and Q on an elliptic curve to calculate a current auxiliary point P '. The adder needs, as it is in 1 is shown means for calculating X _{P '} and Z _P' using as inputs X _P , Z _P , X _Q , Z _Q and the parameters a and b of the elliptic curve. It should also be noted that also the value x _{D used} in the computation of x _{P '} depends on the affine coordinates x _P , y _P as well as x _Q and y _{Q of} the two points P and Q, as shown in Equation (4) becomes apparent.

The adder according to the invention thus comprises a device 30 for calculating Z _{P '} and a device 31 for computing X _{P '} , where the in 2 shown explicit formulas either hardware be evaluated moderately or by software.

3 shows a multiplier according to the invention for multiplying a point on an elliptic curve by a factor of 2. The multiplier according to the invention comprises means for calculating the projective X-coordinate of the result point Q ', which in 3 with the reference number 32 is designated as well as a device 34 for calculating Z _Q ', where the facilities 32 and 34 a software or hardware configuration of in 3 perform the formulas shown.

As has already been stated, the in 1 The multiplication algorithm according to the invention has the advantage that the two auxiliary points P _new and P 'and Q _new or Q' can be calculated in parallel, since Q 'does not depend on P' and vice versa.

4 shows an arithmetic unit for this purpose. The calculator includes a parallel ALU 40 consisting of two SUB ALUs, each SUB ALU having an adding ability, a subtraction ability and a multiplication ability.

The parallel ALU 40 is via an input bus 41 supplied with input data and delivers their results on an output bus 42 , The entrance bus 41 is with a register output bus 43 (RAUS) coupled while the output bus 42 the ALU 40 with a register input bus 44 (PURE) is coupled. The processor according to the invention further comprises a register block 45 with eight registers R0, R1, R2, R3, R4, R5, R6 and R7. The processor further includes an initializer 48 for loading the registers R0 to R7 of the register block 45 before the beginning of an addition and / or a multiplication by a factor of 2 on the elliptic curve.

As a central element, the processor finally includes a flow control 46 for controlling the parallel ALU 40 , the register input bus 44 , the register output bus 43 and the initializer 45 , The parallel ALU 40 also has access to a register memory 47 for storing the parameters a, b of the elliptic curve and further for storing the affine x-coordinate x _{D of} the difference of P and Q according to equation (4). The value for x _D can be given either by the parallel ALU 40 can be calculated by itself, or can be calculated in each iteration step, for example by a separate CPU, if the in 4 shown cryptoprocessor is a coprocessor in an overall system.

The following is based on 5 to a preferred embodiment of the flow control 46 in which the calculation of the coordinates X _{P '} , Z _P' , X _{Q '} and Z _Q' using the eight registers R0 to R7 of the register block 45 is carried out in parallel. In 5 shows a block 50 first a register initialization step. The register R0 is loaded with the current projective coordinate X _{P of} the first auxiliary point P. The register R1 is loaded with the projective z-coordinate Z _{P of} the first auxiliary point P. The register R2 is loaded with the projective x-coordinate X _{Q of} the second auxiliary point Q. Finally, the register R3 is loaded with the projective z-coordinate Z _{Q of} the second auxiliary point Q. The other registers R4 to R7 can be initialized to 0.

In a block 51 from 5 are the arithmetic operations for the parallel ALU 40 having a first SUB ALU 1 and a second SUB ALU 2 given. In the left half of the block 51 are consecutively given the steps to be processed by the SUB ALU 1, while in the right half of block 51 the steps to be taken for the SUB ALU 2 are given. In particular, the in 5 Processed next to each other parallel steps of both ALUs. The example of the first line of 5 this means that the SUB ALU 1 multiplies the contents of registers R1 and R2 and loads them into register R6. In parallel, the SUB ALU 2 multiplies the contents of the register R0 by the contents of the register R3 and loads the result into the register R7. In a next step, the SUB ALU 1 then loads the sum of the contents of the register R7 and the register R6 into the register R4. In parallel, the SUB ALU 2 loads the contents of the register R7, from which the content of the register R6 is subtracted, into the register R5. This procedure is described in the block 51 from 5 given order until the SUB ALU 1 loads in a last step the difference of the register R6 and the register R0 in the register R6, and the SUB ALU 2 loads the sum of the register R7 and the register R1 into the register R7. Then, in one step 52 , the results are output. The projective x-coordinate X _{P 'of} the updated first auxiliary point P' can be found in the register R4. The projective z-coordinate Z _{P 'of} the updated first auxiliary point can be found in register R5. The projective x-coordinate X _{Q 'of} the updated second auxiliary point is found in register R6 and the projective z-coordinate of the updated second auxiliary point, ie Z _Q' , can be found in register R7.

Of course, the sequence of steps in the block 51 is represented, even by a Se riell ALU, the sequence being given by the respective number in parentheses after a register operation. A serial ALU could then, if no parallel ALU is available, follow the steps ( 1 ) to ( 33 ) in the given order and would produce the same results as in the block 52 are shown, arrive.

The algorithm of the invention requires to compute an iteration step (either the left branch or the right branch in FIG 1 ) has only eight registers R0 to R7 and, as has been stated, is suitable for a parallel ALU via the register output bus 43 or the register input bus 44 has access to all registers.

The in 5 in the block 51 The algorithm shown, comprising 19 multiplications and 14 additions, when executed on a parallel ALU, ie implemented by means of a parallel architecture, requires the time of ten multiplications and eight additions. When in block 51 As shown, the algorithm shown is executed on a serial ALU with a single arithmetic unit, the 33 steps are performed, ie a time of 19 multiplies and 14 additions is needed.

After the scalar multiplication k · P or d · P, the projective X coordinate and the projective Z coordinate of the point are on the elliptic curve given by k · P. The following applies: k · P = (X kP : Y kP : Z kP )

To obtain the affine coordinates of k · P, the following transformation is used: kP = (X kP , Y kP , Z kP ) ↦ kP = (X kP / Z kP , Y kP / Z kP ) = (x kP , y kP )

Similarly, the affine x-coordinate of (k + 1) · P can be obtained: (k + 1) P = (X (K + 1) P / Z (K + 1) P , Y (K + 1) P / Z (K + 1) P)

In order to obtain the affine y-coordinate of the point k · P, the following equation is used when substituting y _kP ² and y _P ^{2 for} equation (1) in equation (3) using the following equation: (k + 1) P = kP + P

The equation of determination for y _kP is thus as follows: 2y P y kP = - (x P - x kP ) 2 x (K + 1) P + (a + x 2 P ) x kP + (a + x kP 2 ) x P + 2b (11)

If it is now substituted x _kP by X _kP / Z _kP, and further if x _{(k + 1) P} by X _{(k + 1) P} / Z _{(k + 1) P} is substituted, the following equation for y _kP is obtained, where the letter P has been omitted:

As stated, the y coordinate is needed only with some algorithms. If the y coordinate is needed, it is much more efficient in the 1 to perform the iteration shown only for the x-coordinate and then to calculate the y-coordinate of the result point on the elliptic curve using equations (11) and (12), ie, using the point (k + 1) P on the elliptic Curve.

The present invention is advantageous in that the time and current profile are given by the in 1 be homogenized and further that a parallel implementation is possible without dummy operations are needed. In comparison to the classical standard method with dummy addition, a more efficient method is also achieved since, according to the invention, only 19 multiplications are required in comparison to 26 multiplications per bit of the scalar multiplier.

Furthermore, as has been pointed out, the inventive concept is in contrast to the standard method, which in 6 parallelisierbar, so that compared to the safe standard method with dummy addition, a performance gain of an additional factor of 1.9 is achieved, which in Total results in a factor of 2.6.

Finally is the inventive concept for any elliptic curves applicable as long as the characteristic of the curve p greater than 3 is.

Although it is not detailed at any point, it should be noted that all described calculations are related to a residual class with respect to a modulus, the modulus being equal to the characteristic p of the underlying elliptic curve. The modular reduction can be performed after each addition, multiplication, etc., which is advantageous because the intermediate results are not large numbers. Alternatively, it would also be possible, for. B. perform an addition or the entire multiplication and only at the end with the given module to reduce. However, this would require immense large registers for the intermediate results, which is why it is preferred, for. For example, after each of the block 51 from 5 shown steps with the module to reduce. A modular reduction at the end of each iteration serves to minimize the intermediate results and thus also the registers for their storage.

10

multiplication operation on the elliptic curve

12

initialization

14

examination step

16

Calculate the first auxiliary point if d _i equals 0

18

Calculate the second auxiliary point if d _{i is} equal to 0

20

Calculating the first auxiliary point if d _{i is} equal to 1

22

Calculate the second auxiliary point if d _{i is} equal to 1

24

incrementing the count variable

26

termination criterion

28

output step

30

To calculate the projective z-coordinate of the first

auxiliary point

31

To calculate the projective x-coordinate of the first

auxiliary point

32

To calculate the projective x-coordinate of the second

auxiliary point

34

To calculate the projective z-coordinate of the second

auxiliary point

40

Parallel ALU

41

ALU input bus

42

ALU output bus

43

Register output bus

44

Register input bus

45

register block

46

flow control

47

Register for a, b, x _D

48

initialization

50

initialization for sequence control

51

working sequence the flow control

52

output step the flow control

100

Double - & - add algorithm

102

initialization

104

Multiplier investigation

106

Doubling step if d _{i is} equal to 1

108

Adding step if d _{i is} equal to 1

110

Doubling step, if d _{i is} equal to 0

112

incrementing

114

termination criterion

116

output step

118

Dummy addition step if d _{i is} equal to 0

Claims (9)

A method for adding two points on an elliptic curve y ² = x ³ + a x + b within a cryptographic algorithm, where x and y are coordinates of points on the elliptic curve, and wherein the elliptic curve is over a body having a characteristic larger 3, wherein a first point of the two points has a first projective coordinate X _P and a third projective coordinate Z _P , the second point having a first projective coordinate X _Q and a third projective coordinate Z _Q , comprising the following steps: To calculate ( 31 ) of a first projective coordinate X _{P 'of} a result point on the elliptic curve by the following equation: X P ' = 2 (X P Z Q + X Q Z P ) (X P X Q + aZ P Z Q ) + 4bZ P 2 Z Q 2 + x D (X P Z Q - X Q Z P ) 2 ; and To calculate ( 30 ) of a third projective coordinate Z _{P 'of} a result point on the elliptic curve by the following equation: Z P ' = (X P Z Q - X Q Z P ) 2 . where a and b are parameters of the elliptic curve, and where x _{D is} an affine coordinate of a point on the elliptic curve that results when a difference of the first point (P) and the second point (Q) is calculated. A method for multiplying a point on an elliptic curve y ² = x ³ + a x + b by a factor of 2 within a cryptographic algorithm, where x and y are coordinates of points on the elliptic curve, and wherein the elliptic curve is above a Body having a characteristic greater than 3, the point having a first projective coordinate X _P and a third projective coordinate Z _P , comprising the following steps: calculating ( 32 ) of a first projective coordinate X _{Q 'of} a result point by the following equation: X Q ' = (X Q 2 - aZ Q 2 ) 2 - 8bX Q Z Q 3 ; and To calculate ( 34 ) a third projective coordinate Z _{Q 'of} a result point (Q') by the following equation: Z Q ' = 4 (X Q Z Q (X Q 2 + aZ Q 2 ) + bZ Q 4 ) where a and b are parameters of the elliptic curve. Apparatus for adding two points on an elliptic curve y ² = x ³ + a x + b within a cryptographic algorithm, where x and y are coordinates of points on the elliptic curve, and wherein the elliptic curve is over a body having a characteristic larger is defined as 3, wherein a first point (P) is given by a projective x-coordinate X _P and by a projective z-coordinate Z _P , the second point being defined by a projective x-coordinate X _Q and a projective z-coordinate Z _Q , and multiplying the second point (Q) by a factor of 2 to obtain, as a result of the addition, a first result point (P ') defined by a first projective x coordinate X _P' and a projective x z-coordinate Z _{P '} , and to obtain, as a result of the multiplication, a second result point (Q') given by a projective x-coordinate X _{Q '} and a projective z-coordinate Z _Q' , with the following M to draw: a calculator ( 40 ) for multiplying, adding and subtracting two input values; a number of eight registers R0, R1, R2, R3, R4, R5, R6, R7; and a flow control ( 46 ) for controlling the registers and the arithmetic unit according to the following steps: (0) initializing the register R0 with X _P , the register R1 with Z _P , the register R2 with X _Q and the register R3 with Z _Q ; (1) R6 ← R2 · R1; (2) R7 ← R3 · R0; (3) R4 ← R7 + R6; (4) R5 ← R7 - R6; (5) R5 ← R5 * R5; (6) R7 ← R1 · R3; (7) R1 ← a · R7; (8) R6 ← R7 * R7; (9) R0 ← R0 * R2; (10) R6 ← b · R6; (11) R0 ← R0 + R1; (12) R6 ← R6 + R6; (13) R0 ← R0 * R4; (14) R1 ← x _D · R5; (15) R4 ← R0 + R6; (16) R4 ← R4 + R4; (17) R6 ← R2 + R2; (18) R4 ← R4 - R1; (19) R7 ← R3 + R3; (20) R0 ← R6 * R7; (21) R1 ← R3 · R3; (22) R2 ← R2 · R2; (23) R3 ← a · R1; (24) R6 ← R2 - R3; (25) R7 ← R2 + R3; (26) R1 ← R1 + R1; (27) R2 ← b · R1; (28) R7 ← R7 * R0; (29) R1 ← R2 · R1; (30) R0 ← R0 * R2; (31) R6 ← R6 * R6; (32) R6 ← R6 - R0; (33) R7 ← R7 + R1; (34) outputting a content of R4 to obtain the projective x-coordinate X _{P 'of} the result point of the addition, outputting the content of R5 to obtain the projective z-coordinate Z _{P' of} the addition, outputting the register R6 to obtain the projective x-coordinate X _{Q '} of the multiplication result point and output the contents of the register R7 to obtain the projective z-coordinate Z _Q' of the multiplication result point, where the symbol "·" represents a multiplication, where the symbol "+" represents an addition, where the symbol "-" represents a subtraction, where a, b are parameters of the elliptic curve, where x _{D is} an affine x-coordinate of a point that results when the first point P is subtracted from the second point Q, and wherein the symbol "←" means that the register to which the arrowhead is directed is loaded with a value resulting from the arithmetic operation st at a foot point of the arrow eht. Apparatus according to claim 3, further comprising a further calculating unit, and wherein the sequence control ( 46 ) is arranged to cause the arithmetic unit (SUB-ALU 1) and the further computation unit (SUB-ALU 2) to carry out the following steps in parallel: 1 ) parallel to step ( 2 ); - step ( 3 ) parallel to step ( 4 ); - step ( 5 ) parallel to step ( 6 ); - step ( 7 ) parallel to step ( 8th ); - step ( 9 ) parallel to step ( 10 ); - step ( 11 ) parallel to step ( 12 ); - step ( 13 ) parallel to step ( 14 ); - step ( 16 ) parallel to step ( 17 ); - step ( 18 ) parallel to step ( 19 ); - step ( 20 ) parallel to step ( 21 ); - step ( 22 ) parallel to step ( 23 ); - step ( 24 ) parallel to step ( 25 ); - step ( 27 ) parallel to step ( 28 ); - step ( 29 ) parallel to step ( 30 ); and - step ( 32 ) parallel to step ( 33 ). Apparatus for adding two points on an elliptic curve y ² = x ³ + a x + b within a cryptographic algorithm, where x and y are coordinates of points on the elliptic curve, and wherein the elliptic curve is over a body having a characteristic larger 3, wherein a first point of the two points has a first projective coordinate X _P and a third projective coordinate Z _P , the second point having a first projective coordinate X _Q and a third projective coordinate Z _Q , comprising: means for calculating ( 31 ) of a first projective coordinate X _{P 'of} a result point on the elliptic curve by the following equation: X P ' = 2 (X P Z Q + X Q Z P ) (X P X Q + aZ P Z Q ) + 4bZ P 2 Z Q 2 - x D (X P Z Q - X Q Z P ) 2 ; and a facility ( 30 ) for calculating a third projective coordinate Z _{P 'of} a result point on the elliptic curve by the following equation: Z P ' = (X P Z Q - X Q Z P ) 2 . where a and b are parameters of the elliptic curve, and where x _{D is} an affine coordinate of a point on the elliptic curve that results when a difference of the first point (P) and the second point (Q) is calculated. Apparatus for multiplying a point on an elliptic curve y ² = x ³ + a x + b by a factor of 2 within a cryptographic algorithm, where x and y are coordinates of points on the elliptic curve, and wherein the elliptic curve is over a body having a characteristic greater than 3, the point having a first projective coordinate X _P and a third projective coordinate Z _P , comprising: means for calculating ( 32 ) of a first projective coordinate X _{Q 'of} a result point by the following equation: X Q ' = (X Q 2 - aZ Q 2 ) 2 - 8bX Q Z Q 3 ; and a means for calculating ( 32 ) a third projective coordinate Z _{Q 'of} a result point (Q') by the following equation: Z Q ' = 4 (X Q Z Q (X Q 2 + aZ Q 2 ) + bZ Q 4 ) where a and b are parameters of the elliptic curve. A method for adding two points on an elliptic curve y ² = x ³ + a x + b within a cryptographic algorithm, where x and y are coordinates of points on the elliptic curve, and wherein the elliptic curve is over a body having a characteristic larger is defined as 3, wherein a first point (P) is given by a projective x-coordinate X _P and by a projective z-coordinate Z _P , the second point being defined by a projective x-coordinate X _Q and a projective z-coordinate Z _Q , and multiplying the second point (Q) by a factor of 2 to obtain, as a result of the addition, a first result point (P ') defined by a first projective x coordinate X _P' and a projective x z-coordinate Z _{P '} , and to obtain, as a result of the multiplication, a second result point (Q') given by a projective x-coordinate X _{Q '} and by a projective z-coordinate Z _Q' , using of eight registers R0, R1, R2, R3, R4, R5, R6 and R7, comprising the following steps: (0) initializing the register R0 with X _P , the register R1 with Z _P , the register R2 with X _Q and the register R3 with Z _Q ; Performing the following register operations: (1) R6 ← R2 * R1 (2) R7 ← R3 * R0 (3) R4 ← R7 + R6 (4) R5 ← R7-R6 (5) R5 ← R5 * R5 (6) R7 ← R1 * R3 (7) R1 ← a * R7 (8) R6 ← R7 * R7 (9) R0 ← R0 * R2 (10) R6 ← b * R6 (11) R0 ← R0 + R1 (12) R6 ← R6 + R6 (13) R0 ← R0 * R4 (14) R1 ← x _D * R5 (15) R4 ← R0 + R6 (16) R4 ← R4 + R4 (17) R6 ← R2 + R2 (18) R4 ← R4 - R1 (19) R7 ← R3 + R3 (20) R0 ← R6 * R7 (21) R1 ← R3 * R3 (22 ) R2 ← R2 · R2 (23) R3 ← a · R1 (24) R6 ← R2 - R3 (25) R7 ← R2 + R3 (26) R1 ← R1 + R1 (27) R2 ← b · R1 (28) R7 ← R7 · R0 (29) R1 ← R2 · R1 (30) R0 ← R0 · R2 (31) R6 ← R6 · R6 (32) R6 ← R6 - R0 (33) R7 ← R7 + R1; and (34) outputting a content of R4 to obtain the projective x-coordinate of the result point of the addition, outputting the content of R5 to obtain the projective z-coordinate Z _{P 'of} the addition, outputting the register R6 to obtain the projective x Coordinate X _{Q 'of} the result point of the multiplication, and outputting the content of the register R7 to obtain the projective z-coordinate Z _{Q' of} the result point of the multiplication, where the symbol "·" represents a multiplication where the symbol " + "represents an addition, where the symbol" - "represents a subtraction, where a, b are parameters of the elliptic curve, where x _{D is} an affine x-coordinate of a point that results when the first point P is from the second point Q is subtracted, and wherein the symbol "←" means that the register on which the arrowhead is directed is loaded with a value resulting from the arithmetic operation standing at a foot point of the arrow t. Method according to Claim 7, in which the following steps are carried out in parallel: 1 ) parallel to step ( 2 ) - step ( 3 ) parallel to step ( 4 ) - step ( 5 ) parallel to step ( 6 ) - step ( 7 ) parallel to step ( 8th ) - step ( 9 ) parallel to step ( 10 ) - step ( 11 ) parallel to step ( 12 ) - step ( 13 ) parallel to step ( 14 ) - step ( 16 ) parallel to step ( 17 ) - step ( 18 ) parallel to step ( 19 ) - step ( 20 ) parallel to step ( 21 ) - step ( 22 ) parallel to step ( 23 ) - step ( 24 ) parallel to step ( 25 ) - step ( 27 ) parallel to step ( 28 ) - step ( 29 ) parallel to step ( 30 ) - step ( 32 ) parallel to step ( 33 ). The method of claim 7 or 8, wherein after a Addition, multiplication and / or subtraction a modular reduction is performed with the characteristic of the elliptic curve as a module.