WO2006092448A2 - Verfahren und vorrichtung zum berechnen einer polynom-multiplikation, insbesondere für die elliptische kurven-kryptographie - Google Patents

Verfahren und vorrichtung zum berechnen einer polynom-multiplikation, insbesondere für die elliptische kurven-kryptographie Download PDF

Info

Publication number
WO2006092448A2
WO2006092448A2 PCT/EP2006/060494 EP2006060494W WO2006092448A2 WO 2006092448 A2 WO2006092448 A2 WO 2006092448A2 EP 2006060494 W EP2006060494 W EP 2006060494W WO 2006092448 A2 WO2006092448 A2 WO 2006092448A2
Authority
WO
WIPO (PCT)
Prior art keywords
accumulation
partial
multiplier
polynomial
unit
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/EP2006/060494
Other languages
English (en)
French (fr)
Other versions
WO2006092448A3 (de
Inventor
Peter Langendoerfer
Zoya Dyka
Steffen Peter
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
IHP GmbH
Original Assignee
IHP GmbH
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by IHP GmbH filed Critical IHP GmbH
Priority to US11/885,827 priority Critical patent/US8477935B2/en
Priority to EP06708654A priority patent/EP1859344A2/de
Publication of WO2006092448A2 publication Critical patent/WO2006092448A2/de
Publication of WO2006092448A3 publication Critical patent/WO2006092448A3/de
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/724—Finite field arithmetic
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/52—Multiplying; Dividing
    • G06F7/523—Multiplying only
    • G06F7/53—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel
    • G06F7/5324—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel partitioned, i.e. using repetitively a smaller parallel parallel multiplier or using an array of such smaller multipliers
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3066—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3093—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving Lattices or polynomial equations, e.g. NTRU scheme
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/724—Finite field arithmetic
    • G06F7/725—Finite field arithmetic over elliptic curves
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/12—Details relating to cryptographic hardware or logic circuitry
    • H04L2209/122—Hardware reduction or efficient architectures
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/80—Wireless

Definitions

  • the invention relates to a method and an apparatus for calculating a polynomial multiplication. Furthermore, it relates to a method for encrypting data and an encryption unit.
  • Mobile devices are penetrating more and more areas of everyday life. More and more sensitive information is exchanged between mobile devices or between mobile devices and fixed communication endpoints. Data exchange is normally protected by encryption mechanisms. Due to the scarce resources of mobile devices, however, a comprehensive use of cryptographic methods is not possible. This is especially true for Public Key Cryptography, which is typically used to provide a secure channel between the communication partners and to create digital signatures. Public key cryptography uses so-called asymmetric encryption techniques. In this case, a public key is used to encrypt data, which according to its name is made known to third parties. Decryption of data encrypted with the public key can only be done with a private key that only the recipient of the message has. A decryption of the encrypted message with the public key, however, is virtually impossible.
  • Well-known asymmetric encryption methods are RSA and Diffie-Hellmann methods and the digital signature algorithm DSA based thereon.
  • ECC Elliptic Curve Cryptography
  • the ECC encryption is based on the calculation of a product of two operands called "kP" where P is a point on an elliptic curve (EC) and k is a large number.
  • - Multiplication is based on the point doubling and the point addition. All EC Point operations are based on addition, subtraction, squaring, multiplication and division in a selected Galois field (GF).
  • GF Galois field
  • Hardware accelerators for public-key cryptography operations are ideal tools for reducing computation time and energy consumption.
  • a direct implementation of cryptographic operations leads to a relatively large space requirement on a chip. This complicates the application of hardware accelerators from an economic point of view.
  • the boundary conditions of the design of hardware accelerators are therefore the required calculation time, the energy consumption and the space requirement.
  • Ci n - 3 a "- ⁇ -b" _ 2 ® ⁇ "_ 2 _ n -b ⁇
  • a direct implementation of formula (1) requires n 2 partial multiplications and (n-1) 2 XOR operations of partial products to calculate the coefficients c i. All operands in formula (1) are only one bit long.
  • both polynomials A (x) and B (x) are 233 bits long. This means that a total of 233 2 one-bit partial multiplications and 232 2 XOR operations are required.
  • both operands must be fragmented into two equal parts.
  • n of the operands When the length n of the operands is odd, they must be "0" to be supplemented with a leading. Denoting with a ⁇ the i-th bit, and as a 1, the i-th segment of operand A (x), so can the operands as follows:
  • US 2004/0109561 A1 describes a method for multiplying numbers over a Galois field GF (2 m ).
  • a recursive algorithm is used to decompose a product into a number of subproducts until the remaining size is sufficient to perform a non-recursive algorithm to complete the multiplication.
  • Disadvantage of the method described in this document is its relatively low area efficiency.
  • the technical problem underlying the invention is to provide a method and a device for polynomial multiplication, which allow an area-efficient realization of elementary mathematical operations.
  • a method for calculating a polynomial multiplication is specified, with the steps: HI
  • selecting step is performed iteratively according to a predefined selection plan, and using fragments in which the respective multiplying step results in the formation of a partial product
  • the inventive iterative application of the selection and multiplication steps enables a hardware implementation with a reduced footprint and power consumption. This applies in particular in comparison with a hardware implementation of a recursive algorithm as described in US2004 / 0109561 A1.
  • the chip area needed to calculate the product of two 233-bit operands is 2.18 mm 2 (2-segment layout).
  • An additional area saving is achieved by the use according to the invention of a predefined accumulation plan, which enables the use of a control signal-based accumulation control in a simple switching system instead of complicated data paths between hard-wired components of the polynomial multiplier.
  • an area requirement of only 1.52 mm 2 (4-segment structure) was achieved on the example of an inventive iterative Karatsuba multiplier for 233 bits, in which case the number of clock cycles is not increased by the use of the accumulation plan.
  • the solution according to the invention also reduces the energy consumption by 30% compared to the known completely recursive solution approaches.
  • the inventive method develops its advantages, in particular in a hardware implementation. However, it can also be implemented in the form of software.
  • a software implementation of the method according to the invention has the advantage of better performance with respect to the calculation of the polynomial product compared to known software solutions for polynomial multiplication.
  • the inventive method also allows over known methods increased flexibility.
  • Fragments of polynomials are sometimes referred to as segments in the following description of like meaning. Instead of fragmentation is also spoken of segmentation.
  • the accumulation step is carried out in parallel with the iterative fragmentation and comprises a partial accumulation step which is carried out after an iteration of a multiplication step.
  • the selection, multiplication and accumulation steps are based on a Karatsuba method for carrying out a polynomial multiplication. An example of the application of the Karatsuba method will be explained in more detail below in connection with the description of FIGS. 1 and 2 with reference to the formulas (3) to (8).
  • the selection schedule and the accumulation schedule are selected from a plurality of stored selection and accumulation schedules corresponding to a respective length of the polynomials and a predetermined word width of a partial multiplier used to perform the partial multiplying step.
  • the length of the partial polynomials corresponds to the length of the data words which can be applied to the input of the polynomial multiplier and which are to be multiplied by one another according to a polynomial multiplication.
  • a method of encrypting data comprising a step of computing a product of two polynomials.
  • the product of the polynomials is calculated according to the method of the first aspect of the invention or according to one of the described embodiments.
  • the encryption of the data is performed by elliptic curve cryptography. That is, the encryption of the data is performed by means of an elliptic curve over a Galois field.
  • One of the following curves is preferably used: the curve B-163 over the Galois field GF (2 163 ) or the curve B-233 over the Galois field GF (2 233 ), or the curve B-283 over the Galois Field GF (2 283 ) or the curve B-409 over the Galois field GF (2 409 ), or the curve B-571 over the Galois field GF (2 571 ), or the curve K-163 over the Galois Field GF (2 163 ) or the curve K-233 over the glocal field GF (2 233 ), or the curve K-283 over the Galois field GF (2 283 ) or the Curve K-409 over the Galois field GF (2 409 ), or the curve K-571 over the Galois field GF (2 571 )
  • a polynomial multiplier comprising
  • selection unit is additionally designed to iteratively select the fragments in successive operating steps according to a predefined selection plan
  • At least one partial multiplier connected to the selection unit and configured to carry out a partial multiplication of the two or more than two operands in an iteration step and to provide the resulting partial product at its output
  • an accumulation unit which is connected to the partial multiplier and which is designed to amplify the complete polynomial product by an iteration step for iteration step completed accumulation of the partial multiplier. calculate the products received from the partial multiplier,
  • an accumulation control unit which is connected to the partial multiplier and the accumulation unit and which is designed to output a control signal depending on the current iteration step, the accumulation unit corresponding to a predetermined accumulation plan for the accumulation of a partial product currently present at the output of the partial multiplier is constructed with one or more terms of an iteration step for iteration step refined result polynomial.
  • the polynomial multiplier according to the second aspect of the invention is characterized by a reduced area requirement and a reduced power consumption with increased flexibility compared to the prior art with regard to the word length of the data words to be multiplied.
  • the latter is effected by the use of a programmable accumulation schedule by the accumulation control unit.
  • the accumulation unit contains a number of XOR gates, each XOR gate being connected at one input to one or more terms of the resulting result polynomial and at another input to the partial multiplier.
  • the accumulation control unit preferably has a number of control logic gates that corresponds to the number of XOR gates of the accumulation unit.
  • Each control logic gate is associated with a respective XOR gate.
  • the accumulation control unit is designed to generate a predetermined set of control signals in a respective iteration step and to apply them to the control logic gates, wherein a respective control signal determines whether or not a respective XOR gate is activated for accumulation in the current iteration step.
  • a current accumulation step is controlled, for example, by a control word that corresponds to the Set of control signals corresponds.
  • Each control bit of the control word corresponds to a control signal, and controls the activation of a particular XOR gate in the respective accumulation step via a respective control logic gate.
  • the control logic gates are preferably AND gates with two inputs, of which a first input is applied to a logical one and a second input is acted upon by a respective control signal.
  • the partial multiplier is designed to perform a partial multiplication calculation step in one clock cycle.
  • the accumulation is controlled by a programmable controller, but also the selection of the fragments.
  • One embodiment has a selection control unit connected to the selection unit and configured to output, according to the current iteration step, control signal instructing the selection unit to select a respective predetermined size fragment of each polynomial in accordance with the predetermined selection plan.
  • the hardware implementation may be similar to the accumulation controller with control logic gates, such that in turn only a corresponding set of control signals must be delivered, which in turn simplifies and shortens data paths, thereby increasing area efficiency.
  • Selection control unit and accumulation control unit are preferably integrated in a single multiplication control unit.
  • the accumulation control unit and the selection control unit are arranged to select, on receipt of polynomials at the input of the selection unit, the selection plan and the accumulation plan corresponding to a respective length of the polynomials and a predetermined word width of the partial multiplier from a plurality of stored selection and accumulation schedules .
  • This embodiment takes advantage of the high flexibility of the polynomial multiplier.
  • a preferred embodiment of the polynomial multiplier is formed in the form of an integrated circuit.
  • a fourth aspect of the invention relates to an encryption unit for encrypting data performing a polynomial multiplication, a data input for unencrypted data, a polynomial multiplier connected to the data input according to the third aspect of the invention or one of its embodiments, and one with the polynomial - Multiplier connected data output to output the encrypted data.
  • a preferred embodiment of the encryption unit is designed to encrypt the data by means of elliptic curve cryptography, that is to say in particular to encrypt the data present at the data input by means of an elliptic curve over a Galois field.
  • elliptic curve cryptography that is to say in particular to encrypt the data present at the data input by means of an elliptic curve over a Galois field.
  • one of the curves already described in connection with the method of the second aspect of the invention may be used.
  • the encryption unit may be implemented in the form of an integrated circuit or in the form of an executable computer program.
  • a further aspect of the invention therefore forms a data carrier with an executable program which implements a method for encrypting data according to the second aspect of the invention or one of its embodiments.
  • FIG. 2 shows a detailed representation of an exemplary embodiment of a method for polynomial multiplication using the example of a 4-word karatsuba
  • FIG. 3 shows a block diagram of an embodiment of a method for data encryption oriented on the data flow
  • FIG. 4 shows a block diagram of an embodiment encryption unit
  • FIG. 5 shows a block diagram of a further exemplary embodiment of a polarity multiplier according to the invention.
  • Figure 6 is a schematic view of the partial multiplier and the accumulation unit of Figure 5 in more detail.
  • FIG. 1 shows the structure of an embodiment of a polynomial multiplier.
  • FIG. 1 shows the structure of an embodiment of a polynomial multiplier.
  • FIG. 1 shows the structure of an embodiment of a polynomial multiplier.
  • FIG. 1 shows the structure of an embodiment of a polynomial multiplier.
  • FIG. 1 shows the structure of an embodiment of a polynomial multiplier.
  • FIG. 1 shows the structure of an embodiment of a polynomial multiplier.
  • ECC Elliptic Curve Cryptography
  • the result of the 'kP' multiplication must be reduced.
  • the reduction is performed using so-called irreducible polynomials and can be a very elaborate operation in the Galois field GF (2 m ).
  • the advantage of the Montgomery method is that a maximum of twice the inverse of the product must be calculated for reduction. This is achieved in the Montgomery method by a larger number of multiplications, which generate less computational effort than computing the inverse. This applies in particular when using the efficient polynomial multiplier proposed here.
  • One approach of the present invention is to iteratively apply the original Karatsuba method. Therefore, we refer to the inventive method as iterative Karatsuba method.
  • the main advantages of this process are:
  • Karatsuba's formula is iteratively applied to calculate the partial products a'b 1 .
  • a total of s log23 ⁇ , y 158 partial multiplications are required, where s is the number of segments.
  • This method can be used to speed up both software and hardware implementations.
  • the Karatsuba method is usually used until both operands are the length of a data word.
  • Karatsuba's formula is used to obtain a formula for a product using only one-segment long operands for partial multiplication.
  • Each operand can be represented and decomposed in the form of a sum of two 2n-bit parts:
  • Each of the operands of the right term of formula (8) is one segment long so that the resulting partial product (2n-1) bit is long.
  • Table 1 Accumulation schedule according to formula (8) All columns in Table 1, listed under the heading "Result Segments”, represent a particular segment c 'that results from partial multiplication of each of the selected fragments mentioned above For each partial product, two rows are provided in Table 1, one row containing the lower portion (a x b x [0]), and the second row represents the upper portion (a x b x [1]) of the product as stated above.
  • the segment c ' can be calculated in Table 1 as the XOR of all the rows in the c the " ⁇ " symbol segment' associated column contained
  • 5 c can be calculated as follows.:
  • c 5 a 1 b 1 [1] ⁇ a 2 b 2 [0] ⁇ a 2 b 2 [1] ⁇ a 3 b 3 [0] ⁇ a 3 b 3 [1] ⁇ ((a 1 ⁇ a 3 ) (b 1 ⁇ b 3 ) [1]) ⁇ ((a 2 ⁇ a 3 ) (b 2 ⁇ b 3 ) [0]) (10)
  • Each segment c ' can be calculated iteratively, ie step by step as in the calculation of the partial products, starting with a ° b ° up to (fl o ®fl 1 ® fl 2 ®fl 3 ) (fo o ® / 7 1 ® / 7 2 ® / 7 3 ). Subsequently, the calculation of the segments of products is started using the already existing results (step 208 in FIG. 2). For example:
  • This iterative calculation of the product C (x) reduces the area requirement of a hardware multiplier. Only a partial multiplier for single-segment long operands is needed. After each new clock signal, this multiplier delivers the next partial product. In this way the segments of product C (x) are collected. Thus, in the example given above, after nine clock cycles, all segments contain the correct product of the polygon multiplication.
  • the solution according to the invention also reduces the energy consumption by 30% compared to the original solution. These advances are paid only with an increased calculation time.
  • a polynomial multiplication requires three clock cycles while in the original Karatsuba method only one clock cycle is needed.
  • the iterative approach of the invention may be applied to the Bailey method, which is referred to in this application as the Bauter iterative method.
  • FIG. 1 The structure and the essential parameters of an embodiment of a hardware implementation of the iterative Karatsuba method will be explained below.
  • the structure of an iterative Karatsuba accelerator consists of three essential parts, cf. FIG. 1:
  • a selection unit 100 makes certain parts of both operands available to a downstream partial multiplier at each new clock signal at its output.
  • a partial multiplier 102 computes the partial product of the operands provided by the selection unit and provides the results of a product accumulation unit.
  • the product accumulation unit 104 calculates the end result of the product from the partial products that it receives from the partial multiplier. The theoretical basis and the exact sequence of steps were explained in detail in sections 4 and 5 above.
  • the performance data, the chip area and the energy requirement of a polynomial multiplier are significantly influenced by the partial multiplier used.
  • this also leads to a relatively large space requirement. Therefore, the hardware design has to make a decision between calculation time and chip area. However, this only applies as long as the partial multiplier alone is taken into account.
  • the area of the selection and product accumulation units is important for the polynomial multiplier.
  • the chip area required by the product accumulation unit depends on the area requirement of the partial multiplier in an inversely proportional manner. That is, the smaller the partial multiplier, the larger the product accumulation unit.
  • the area of the product accumulation unit is 0.649 mm 2 when the partial multiplier accepts 128 bit long operands. In contrast, the area is 1.466 mm 2 if the maximum accepted length of the operands is only 32 bits.
  • partial multipliers In order to obtain a well adapted design for a polynomial multiplier, various partial multipliers have been realized. Three one-clock partial multipliers were used for the Karatsuba method according to the invention as well as for an iterative Bailey method according to the invention. These partial multipliers accept operands with a maximum length of 128, 64 and 32 bits each. They were synthesized using Applicant's circuit library and proprietary 0.25 ⁇ m CMOS technology. Table 3 shows the parameter area, time and energy consumption of each of these six partial multipliers. The values were determined using the design analysis tool from Synopsys.
  • Embodiments with an accumulation control unit and a selection control unit, which are integrated in a multiplication control unit, can further increase the flexibility with regard to the required total duration, the possible clock frequencies and the required chip area.
  • Table 4 below compares parameters of different 233-bit Karatsuba interactive multipliers. It can be seen that a 1-clock multiplier requires the least overall time for a polynomial multiplication, but on the other hand requires by far the largest chip area.
  • the two recursive multipliers use the original Karatsuba or Bailey formula down to one-bit operands. Both multipliers supply the polynomial product after one clock cycle. They differ in the length of the input operands.
  • the Karatsuba multiplier always expects two 256-bit input values, while the Bailey multiplier expects two 243-bit input values.
  • the iterative application of the Karatsuba method for polynomial multiplications thus makes it possible to reduce the required chip area and the energy required to perform elliptic curve cryptography on mobile terminals.
  • Different methods for polynomial multiplication in GF (2 n ) were analyzed and different polynomial multiplication algorithms were implemented.
  • Various partial multipliers were made. They were used to implement a number of iterative polynomial multipliers to determine the best possible variant for use in mobile devices. Our results clearly show that the inventive iterative approach leads to significantly better results in terms of chip area and energy consumption than the original direct applications.
  • FIG. 3 shows a data flow-oriented block diagram of an exemplary embodiment of a device for data encryption, which is referred to below as encryption unit 300.
  • the encryption unit 300 contains a read-only memory 302 in which the coordinates of a base point G of a predetermined elliptic curve are stored.
  • a random number generator 304 generates in each case a random number k per section M for user data to be encrypted.
  • a memory 306 contains a public key S of the recipient of the message.
  • a data segmenter 308 decomposes incoming and to-be-encrypted payload data into payload portions M of a predetermined length.
  • a gated field multiplier 310 which contains an iterative polynomial multiplier according to the invention, the product kG of the base point G with the current random number k is calculated on the one hand. This is symbolized by a block 310.1. Furthermore, in the Galois field multiplier 310, the product kS of the same current random number k and the public key S is determined, which is symbolized by the block 310.2. It should be noted that although it is conceivable to provide two independent Galois field multipliers for the calculation of the products kG and kS. Preferably, however, there is only one Galois field multiplier so as not to unnecessarily increase the area requirement. The associated time delay is tolerable for most encryption applications.
  • the payload data section provided by the data segmenter 308 is checked for correspondence with the X coordinate of a point of the elliptic curve. Unwanted bits of the user data section M are possibly changed, so that a modified user data section M * is created. The undefined bits are freely changeable without the risk of modifying the payload. This modification therefore has no influence on the useful information contained in the payload data M * . After each generation of a modified payload data section M * , it is checked again whether this modified payload data section coincides with the X coordinate of a point on the elliptic curve.
  • a payload section contains the text "zojka” symbolized by the data symbol sequence (Fig. 5A, 6F, 6A, 6B, 61, 00), where the last data symbol "00" is not fixed and can be changed to the sequence of data symbols to match the X coordinate of a point on the elliptic curve.
  • the transformation unit 312 will determine that the resulting sequence of data symbols has no correspondence at any point on the elliptic curve, but if the unspecified data symbol is written as "02 "defines, the transformation unit 312 will determine that the resulting sequence of data symbols corresponds to a point on the elliptic curve having the following Y coordinate: 7D3C7D654AAB7068E1 DA366C49588A27F252D410.
  • the transformation unit 312 derives from the determined point of the elliptic curve X and Y coordinates to an input of an adder 314, to whose other input the product kS of the public key with the current random number k is present.
  • the sum kS + Y is given by the adder 314 to an output unit 316, which is supplied with the product kG at a further input.
  • the output unit 316 assembles the data symbols kG and the sum kS + Y into a data sequence and outputs them.
  • the output can be either serial or parallel.
  • the encryption unit 300 can be implemented both in the form of hardware and in the form of software.
  • FIG. 4 shows a block diagram of a further embodiment of an encryption unit, which is referred to below as encryption unit 400.
  • the representation of FIG. 4 shows a hardware implementation.
  • the individual units of the encryption unit are connected via a central bus 402. Connected to the bus 402 is a control unit 404 which contains control logic for performing the Montgomery method.
  • the control unit 404 controls the cooperation of the units described below.
  • the input / output unit 406 is simultaneously configured to assemble and output an encrypted message generated by the encryption unit 400, as described in connection with the output unit 316 of FIG.
  • a random number generator 408 provides a random number k for each incoming payload section M.
  • a Karatsuba polynomial multiplier 410 is connected to a polynomial reduction unit 412.
  • An inversion unit 414 also connected to the data bus 402 is configured to form the multiplicative inverse of a polynomial.
  • an adder 416 is provided as well as a polyhedron. nom squaring unit 418 connected to another polynomial reducer 420.
  • the mode of operation of the encryption unit 400 corresponds to the mode of operation illustrated with reference to FIG. 3, wherein the control unit 404 performs the function of the transformation unit 312.
  • the encryption unit 400 may be provided that the base point G and / or the public key S are not supplied via the input / output unit 406, but stored permanently in a memory.
  • the memory 422 also used in the polynomial multiplication can be used.
  • adder 416 The addition performed by adder 416 is based on the XOR operation, as previously mentioned.
  • the software variant was used with the Miracle Library Polynomial Multiplier, version 4.7, Shamus Software Ltd. (Ireland), http://indiqo.ie/ ⁇ mscott/), which uses a recursive Karatsuba approach, and with an implementation For the implementation of the software variant Microsoft Visual C ++ 6.0 was used The comparison measurements were made on a PC (Intel Pentium III Processor, 800 MHz, Microsoft Windows XP Professional Version 2002, 256 MB RAM).
  • FIG. 5 shows a block diagram of an embodiment of a polynomial multiplier 500 according to the invention.
  • the structure of the polynomial multiplier 500 is similar in many parts to the structure of the polynomial multiplier described in FIG.
  • the polynomial multiplier 500 also includes a selection unit 502, a partial multiplier 504, and a product accumulation unit 506.
  • the operation of the selection and accumulation unit is predetermined by hard-wired data paths and clock signal for clock signal executes a hardwired selection plan and a hardwired accumulation plan
  • a separate multiplier control unit 508 is provided, which selects Control unit 508.1 and an accumulation control unit 508.2 integrated into it.
  • the multiplier control unit is accordingly connected to the selection unit 502 on the one hand and to the accumulation unit 506 on the other hand.
  • input registers 510 and 512 which are connected upstream of the selector 502 and configured to receive incoming data words A and B whose product is to be calculated by the polynomial multiplier.
  • the calculated product C will be present at the output of an output register 514, shown here as part of the accumulation unit 506.
  • the accumulation unit 506 simultaneously integrates a reduction unit, so that a product C reduced to the word length of the incoming data words can be output.
  • Figure 6 is a schematic view of the partial multiplier and the accumulation unit of Figure 5 in more detail.
  • the representation is schematic in that it represents several structural elements for clarification of the operation of the accumulation in an iteration step several times, as will be explained in more detail below.
  • the structure of the accumulation unit will be described with reference to an example of an iterative Karatsuba multiplier with a 4-segment multiplication of 233-bit long data words, as also exemplified in FIG.
  • 8 product segments c ⁇ to c7 are available at the end of each iteration in the accumulation unit, as was explained in Table 1 in a corresponding example. These segments c ⁇ to c7 are located in respective registers 516 to 530.
  • registers 516 to 530 The structure of registers 516 to 530 is shown three times in FIG. 6 overall in order to illustrate the sequence of an iteration step.
  • the register structure shown on the left side in the figure represents an initial register state
  • the register structure shown in broken line in the middle represents a temporary intermediate state which is not stored
  • the register structure shown on the right represents an end state of each iteration step.
  • all three representations refer to FIG the actual accumulation unit 506 has the same register structure 516 to 530.
  • the data width of the register structure in an nxn-partial multiplier 504 is 8n.
  • the transition from the initial register state to the final register state during an iteration step results from a number of XOR operations performed on a total of seven XOR gates 532 through 544.
  • Each XOR gate combines 2n bits from two adjacent registers with the current result of a partial multiplication, which is available in a register 504.1 at the output of the partial multiplier 504.
  • Each XOR gate is linked on the input side to a control logic gate. Whether an XOR connection of the respective register with the current partial product from the register 504.1 is actually made, decides the state of a respective control logic gate.
  • the control logic gates in the present embodiment are AND gates 546-558, at one input of which is the result of the partial multiplication and at the other input each a control bit cw [0], cw [1], ..., cw [6] of a control word (control word, cw) is present. Depending on the value of the respective control bit in the current iteration cycle, therefore, the partial multiplication result for accumulation at a respective register 516 to 530 is allowed or blocked by the respective AND gate.
  • This form of control of the accumulation with the help of a control word saves complicated data paths and leads to a considerable space saving.
  • Another advantage of this embodiment is that different accumulation schedules can be implemented in this way. These may be available in a memory or may be subsequently stored in the accumulation control unit 508.2.
  • the selection control can be realized in the same way and is not shown here.
  • the area advantage achieved with the present exemplary embodiment is the greater the higher the segmentation of the data words provided for multiplication. While in the embodiment of Figure 1, the data path with increasing segmentation is complicated and therefore increasingly claimed chip area (from 0.30 mm 2 for a 2-segment method over 0.78 mm 2 for a 4-segment method up to 1.18 mm 2 for an 8-segment method), the area requirement of the multiplier control unit 508 including both the selection control unit 508.1 and the accumulation control unit 508.2 remains almost constant and is in the range of 0.30 mm 2 . claims
  • the selection step is carried out iteratively according to a predefined selection plan, and wherein fragments are used in which the respective multiplying step for forming a partial product of respective fragments requires only one calculation step,
  • Accumulating the partial products the accumulation being controlled in accordance with a predefined accumulation plan for the accumulation of a partial product currently present at the output of the partial multiplier with one or more terms of an iteration step further developed by the iteration step.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Computing Systems (AREA)
  • Algebra (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • Complex Calculations (AREA)
  • Error Detection And Correction (AREA)

Abstract

Die Sicherung von Kommunikationskanälen ist insbesondere in drahtlosen Netzwerken erforderlich. Die Anwendung von Verschlüsselungsmechanismen in Form von Software ist durch die benötigten Berechnungs- und Energiekapazitäten mobiler Endgeräte begrenzt. Bei Verwendung von Hardware-Lösungen für kryptographische Operationen sind Kosten von Bedeutung. Die vorliegende Erfindung liefert einen Ansatz der alle diese Punkte zugleich angreift. Sie betrifft einen Hardware-Beschleuniger für die Polynom-Multiplikation in ausgedehnten Galois-Feldern (GF), wobei das an sich bekannte Karatsuba-Verfahren erfindungsgemäss iterativ angewendet wird. Bei Verwendung der Erfindung kann der Flächenbedarf beispielsweise von 6,2 mm<SUP>2</SUP> auf 2,1 mm<SUP>2</SUP> reduziert werden. Die erfindungsgemäße Lösung reduziert auch den Energieverbrauch gegenüber Lösungen nach dem Stand der Technik um 30%.

Description

Berlin, 6. März 2006
Unser Zeichen: IB 1284-03WO LE/jwd
Durchwahl: 030/841 887 16
Anmelder/Inhaber: IHP GMBH Amtsaktenzeichen: Neuanmeldung
IHP GmbH - Innovations for High Performance Microelectronics / Institut für innovative Mikroelektronik
Im Technologiepark 25, D-15236 Frankfurt (Oder)
Verfahren und Vorrichtung zum Berechnen einer Polynom-Multiplikation, insbesondere für die elliptische Kurven-Kryptographie
Die Erfindung betrifft ein Verfahren und eine Vorrichtung zum Berechnen einer Polynom-Multiplikation. Weiterhin betrifft sie ein Verfahren zur Verschlüsselung von Daten sowie eine Verschlüsselungseinheit.
1. Einleitung
Mobile Endgeräte dringen in immer weitere Bereiche des Alltagslebens vor. Immer mehr sensible Informationen werden zwischen mobilen Endgeräten oder zwischen mobilen Endgeräten und ortsfesten Kommunikations-Endpunkten ausgetauscht. Der Datenaustausch ist normaler Weise durch Verschlüsselungsmechanismen geschützt. Wegen der knappen Ressourcen mobiler Endgeräte ist jedoch ein umfassender Gebrauch kryptographischer Verfahren nicht möglich. Dies gilt insbesondere für die Kryptographie mit öffentlichen Schlüsseln (engl. Public Key Cryptography), die in der Regel zur Bereitstellung eines sicheren Kanals zwischen den Kommunikationspartnern sowie für die Erstellung digitaler Signaturen verwendet wird. Bei der Kryptographie mit öffentlichen Schlüsseln werden so genannte asymmetrische Verschlüsselungsverfahren verwendet. Hierbei wird ein öffentlicher Schlüssel zur Verschlüsselung von Daten verwendet, der hierfür seinem Namen entsprechend dritten Personen bekannt gemacht wird. Eine Entschlüsselung der mit dem öffentlichen Schlüssel verschlüsselten Daten kann nur mit einem privaten Schlüssel erfolgen, über den nur der Empfänger der Nachricht verfügt. Eine Entschlüsselung der verschlüsselten Nachricht mit dem öffentlichen Schlüssel ist dagegen praktisch nicht möglich. Diese praktische Unmöglichkeit der Entschlüsselung liegt in der Asymmetrie des Verschlüsselungsverfahrens begründet, das einen nur relativ wenige Rechenschritte erfordernden Verschlüsselungsalgorithmus auf der Basis des öffentlichen Schlüssels verwendet. Die Entschlüsselung, die eine mathematische Inversion des Verschlüsselungsalgorithmus beinhaltet, erfordert jedoch bei alleiniger Kenntnis des öffentlichen Schlüssels so viele Rechenschritte, dass der Zeitaufwand eines solchen Entschlüsselungsversuches selbst unter Verwendung modernster und aufwändigster Rechentechnik praktisch unendlich groß ist.
Bekannte asymmetrische Verschlüsselungsverfahren sind RSA sowie Diffie- Hellmann-Verfahren und der darauf basierende Digitale Signatur Algorithmus DSA.
In jüngerer Zeit ist die Elliptische Kurvenkryptographie (engl. Elliptic Curve Cry- pography, ECC) verstärkt entwickelt worden. Der Vorteil der ECC gegenüber den anderen genannten Verfahren liegt darin, dass kürzere Schlüssel verwendet werden können, ohne die Sicherheit der Verschlüsselung zu reduzieren. Zusätzlich sind ECC-Operationen schneller als solche des RSA-Verfahrens. Eine Ein- führung in die Elliptische Kurvenkryptographie ist im Internet unter der Seite http://www.deviceforge.com/articles/AT4234154468.html veröffentlicht.
Die Verschlüsselung bei der ECC beruht auf der Berechnung eines Produkts zweier Operanden, das als „kP" bezeichnet wird. Dabei ist P ein Punkt auf einer elliptischen Kurve (engl. Elliptic Curve, EC) und k ist eine große Zahl. Die „kP"- Multiplikation basiert auf der Punkt-Verdopplung und der Punkt-Addition. Alle EC- Punkt-Operationen basieren auf Addition, Subtraktion, Quadrierung, Multiplikation und Division in einem ausgewählten Galois-Feld (GF).
Hardwarebeschleuniger für Kryptographie-Operationen mit öffentlichen Schlüsseln sind ideale Mittel, um die Berechnungszeit und den Energieverbrauch zu reduzieren. Eine direkte Umsetzung kryptographischer Operationen führt jedoch zu einem relativ großen Flächenbedarf auf einem Chip. Dies erschwert die Anwendung von Hardwarebeschleunigern unter wirtschaftlichen Gesichtspunkten. Die Randbedingungen des Designs von Hardwarebeschleunigern sind daher die benötige Berechnungszeit, der Energieverbrauch sowie der Flächenbedarf.
2. Stand der Technik
Nachfolgend werden bekannte Verfahren zur Polynom-Multiplikation in einer po- lynomialen Basis beschrieben. Hierzu wird zunächst die Polynom-Multiplikation allgemein beleuchtet und anschließend werden bekannte Verfahren zur Beschleunigung der Polynom-Multiplikation erläutert.
2.1 Polynom-Multiplikation
In einem Galois-Feld GF(2n) sind Addition und Subtraktion XOR-Operationen. Deshalb und zum einfacheren Verständnis der Formeln ist die gewöhnliche Dar-
H-I H-I
Stellung von Polynomen A(x) = £a,x' hier abgeändert in A(x) = @a,x' Im Rah-
I=O (=0 men dieser Anmeldung ist die XOR-Operation als „Θ" gekennzeichnet. Das Sym- bol „+" bezeichnet immer eine gewöhnliche Addition.
Das Produkt zweier Polynome
H-I H-I
A(x) = @ a,x' und B(x) = @b,x' ι=0 ι=0 ist das Polynom C(x) = A(x) ■ B(x) = 0 cfx' (1)
I=O
wobei C, = ■b,,d. h.: k+l=ι
C0 = uo-bo
C1 = uvb0®u0-bx
c„_L =an_ι -bo®an_2 -bγ ®...®a0 -bH_γ
Cin-3 =a„-ι -b„_2 ®a„_2 -bn_γ
C2n-2 =an-l '"n-Y
Eine direkte Implementierung von Formel (1) erfordert n2 partielle Multiplikationen und (n-1)2 XOR-Operationen partieller Produkte, um die Koeffizienten c, zu berechnen. Alle Operanden in Formel (1) sind nur ein Bit lang. Bei Verwendung von EC B-233 sind beide Polynome A(x) und B(x) 233 Bit lang. Das bedeutet, dass insgesamt 2332 Ein-Bit partielle Multiplikationen und 2322 XOR-Operationen erforderlich sind.
2.2 Karatsuba-basierte Verfahren zur Polynom-Multiplikation
Für eine Polynom-Multiplikation mit dem ursprünglichen Karatsuba-Verfahren müssen beide Operanden in zwei gleich lange Teile fragmentiert werden. Wenn die Länge n der Operanden ungerade ist, müssen sie mit einer führenden „0" ergänzt werden. Bezeichnet man mit aι das i-te Bit und als a1 das i-te Segment des Operanden A(x), so können die Operanden wie folgt dargestellt werden:
A(x) = an_x...anan ...aιa0=an_ι...an -x2 ®an ...U1U0 =
~2 T1 ~2 T1 (2) n Das Polynom B(x) kann auf die selbe Weise dargestellt werden. Karatsubas Formel für das Produkt C(x)=A(x)-B(x) ist
n
C(x) = a°b° © [α V © aΨ © (α° © aι)(b° © b1)]- x2 © aΨ ■ x" (3)
In der Veröffentlichung Bailey, D. V.; Paar, C: Efficient Arithmetic in Finite Field Extensions with Application in Elliptic Curve Cryptography. Journal of Cryptology, vol. 14, no. 3, 153-176. 2001 wird ein Verfahren für die Anwendung von Karatsubas Idee vorgeschlagen. Nachfolgend wird dieses Verfahren als Baileys Verfahren bezeichnet. In diesem Verfahren werden die Operanden in drei Teile geteilt.. Baileys Verfahren erfordert sechs partielle Multiplikationen von n/3-Bit lan- gen Operanden. Dieses Verfahren kann mit der ursprünglichen Karatsuba-For- mel für solche Operanden kombiniert werden, deren Länge durch sechs teilbar ist.
Die US 2004/0109561 A1 beschreibt ein Verfahren zur Multiplikation von Zahlen über einem Galois-Feld GF (2m). Bei diesem Verfahren wird ein rekursiver Algo- rithmus zur Zerlegung eines Produktes in eine Anzahl Subprodukte verwendet, bis die verbleibende Größe ausreicht, einen nicht-rekursiven Algorithmus zur Vervollständigung der Multiplikation durchzuführen. Nachteil des in diesem Dokument beschriebenen Verfahrens ist seine relativ geringe Flächeneffizienz.
3. Technisches Problem der Erfindung
Das der Erfindung zugrunde liegende technische Problem ist es, ein Verfahren und eine Vorrichtung zur Polynom-Multiplikation anzugeben, die eine flächeneffiziente Realisierung elementarer mathematischer Operationen ermöglichen.
4. Zusammenfassung der Erfindung
Gemäß einem ersten Aspekt wird ein Verfahren zum Berechnen einer Polynom- Multiplikation angegeben, mit den Schritten: H-I
Bereitstellen von Koeffizienten a„ b, zweier Polynome A(x) = @a,x' und
;=0
H-I
B(x) = @btx' , wobei " 0 " eine Addition oder eine XOR-Operation kenn-
;=0 zeichnet und a„ b, binäre Ein-Bit-Werte sind, d. h . 0 oder 1 , sowie x' = 1 ist,
Auswählen von entweder zwei oder mehr als zwei Fragmenten, eines von jedem Polynom, als Operanden für eine partielle Multiplikation,
partielles Multiplizieren der ausgewählten Fragmente, um ein partielles Produkt zu erhalten,
wobei der Auswählschritt iterativ nach einem vordefinierten Auswahlplan durchgeführt wird, und wobei Fragmente verwendet werden, bei denen der jeweilige Multiplizierschritt zur Bildung eines partiellen Produkts jeweiliger
Fragmente lediglich einen Berechnungsschritt erfordert,
Akkumulieren der partiellen Produkte, wobei das Akkumulieren entsprechend einem vordefinierten Akkumulationsplan zur Akkumulation eines aktuell am Ausgang des partiellen Multiplizierers anliegenden partiellen Pro- duktes mit einem oder mehreren Termen eines Iterationsschritt für Iterationsschritt weiterentwickelten Ergebnispolynoms gesteuert wird.
Die erfindungsgemäße iterative Anwendung der Auswähl- und Multiplizier- Schritte ermöglicht eine Hardware-Implementierung mit einem reduzierten Flächenbedarf und Energieverbrauch. Dies gilt insbesondere im Vergleich mit einer Hardware-Implementierung eines rekursiven Algorithmus wie er in der US2004/0109561 A1 beschrieben ist. Beispielsweise beträgt die Chipfläche, die für die Berechnung des Produkts von zwei 233 Bit langen Operanden benötigt wird, 2,18 mm2 (2-Segment-Aufbau). Diese Fortschritte werden lediglich mit einer geringfügig erhöhten Berechnungszeit bezahlt. Eine zusätzliche Flächeneinsparung wird durch die erfindungsgemäße Verwendung eines vordefinierten Akkumulationsplans erzielt, der die Verwendung einer steuersignal-basierten Akkumulationssteuerung in einem einfachen Schaltsystem anstelle komplizierter Datenpfade zwischen hartverdrahteten Bauteilen des PoIy- nom-Multiplizierers ermöglicht. Hier wurde am Beispiel eines erfindungsgemäßen iterativen Karatsuba-Multiplizierers für 233 Bit ein Flächenbedarf von nur 1 ,52 mm2 (4-Segment-Aufbau) erzielt, wobei in diesem Fall die Anzahl der Taktzyklen durch den Einsatz des Akkumulationsplanes nicht erhöht wird.
Für die Standard-Anwendung der Karatsuba-Methode werden dagegen 6,2 mm2 benötigt. Die erfindungsgemäße Lösung reduziert auch den Energieverbrauch um 30 % gegenüber den bekannten vollständig rekursiven Lösungsansätzen.
Das erfindungsgemäße Verfahren entfaltet seine Vorteile insbesondere bei einer Hardware-Implementierung. Es kann jedoch auch in Form von Software implementiert werden. Eine Software- Implementierung des erfindungsgemäßen Ver- fahrens hat gegenüber bekannten Software-Lösungen zur Polynom-Multiplikation den Vorteil einer besseren Performanz im Hinblick auf die Berechnung des Polynom-Produktes.
Das erfindungsgemäße Verfahren ermöglicht zudem gegenüber bekannten Verfahren eine erhöhte Flexibilität.
Fragmente von Polynomen werden in der nachfolgenden Beschreibung mit gleicher Bedeutung gelegentlich auch als Segmente bezeichnet. Anstelle von Fragmentierung wird auch von Segmentierung gesprochen.
In einem bevorzugten Ausführungsbeispiel des erfindungsgemäßen Verfahrens wird der Akkumulierungsschritt parallel mit der iterativen Fragmentierung durch- geführt und umfasst einen partiellen Akkumulierungsschritt, der nach einer Iteration eines Multiplizierschrittes durchgeführt wird. In einem weiteren bevorzugten Ausführungsbeispiel des erfindungsgemäßen Verfahrens beruhen die Auswähl-, Multiplizier- und Akkumulationsschritte auf einem Karatsuba-Verfahren zur Durchführung einer Polynom-Multiplikation. Ein Beispiel der Anwendung des Karatsuba- Verfahrens wird weiter unten im Zusam- menhang der Beschreibung der Figuren 1 und 2 anhand der Formeln (3) bis (8) näher erläutert.
Bei einem weiteren Ausführungsbeispiel werden vor dem Auswählschritt der Auswählplan und der Akkumulationsplan entsprechend einer jeweiligen Länge der Polynome und einer vorgegebenen Wortbreite eines zur Durchführung des partiellen Multiplizierschrittes verwendeten partiellen Multiplizierers aus einer Vielzahl abgespeicherter Auswahl- und Akkumulationspläne ausgewählt. Die Länge der Teil-Polynome entspricht der Länge der am Eingang des Polynom- Multiplizierers anlegbaren Datenworte, die mit einander entsprechend einer Polynommultiplikation zu multiplizieren sind. Dieses Ausführungsbeispiel profitiert besonders von der erfindungsgemäß vorgegebenen Flexibilität, so dass ein und dieselbe Hardware für unterschiedliche Polynomlängen verwendet werden kann.
Gemäß einem zweiten Aspekt der Erfindung wird ein Verfahren zur Verschlüsselung von Daten angegeben, das einen Schritt der Berechnung eines Produktes zweier Polynome umfasst. Erfindungsgemäß erfolgt die Berechnung des Produk- tes der Polynome gemäß dem Verfahren des ersten Aspektes der Erfindung oder nach einem der beschriebenen Ausführungsbeispiele.
Vorzugsweise wird die Verschlüsselung der Daten mit Hilfe der Elliptischen Kurvenkryptographie durchgeführt. Das heißt: die Verschlüsselung der Daten wird mit Hilfe einer elliptischen Kurve über einem Galois-Feld durchgeführt. Dabei wird bevorzugt eine der folgenden Kurven verwendet: die Kurve B-163 über dem Galois-Feld GF(2163) oder die Kurve B-233 über dem Galois-Feld GF(2233), oder die Kurve B-283 über dem Galois-Feld GF(2283) oder die Kurve B-409 über dem Galois-Feld GF(2409), oder die Kurve B-571 über dem Galois-Feld GF(2571), oder die Kurve K-163 über dem Galois-Feld GF(2163) oder die Kurve K-233 über dem Ga- lois-Feld GF(2233), oder die Kurve K-283 über dem Galois-Feld GF(2283) oder die Kurve K-409 über dem Galois-Feld GF(2409), oder die Kurve K-571 über dem Galois-Feld GF(2571)
Gemäß einem dritten Aspekt der Erfindung wird ein Polynom-Multiplizierer bereitgestellt , mit
einer Auswähleinheit, die ausgebildet ist,
H-I
Koeffizienten a„ b, von zwei Polynomen A(x) = (+) a,x und
;=0
H-I
B(x) = @btx' zu empfangen, wobei " 0 " eine Addition oder eine
;=0
XOR-Operation bezeichnet, a, und b, Ein-Bit-Binär-Werte sind, d. h. 0 oder 1 , und x' = 1 , und
- in einem Arbeitsschritt entweder zwei oder mehr als zwei Fragmente, eines von jedem Polynom, mit einer solchen Länge als Operanden für eine partielle Multiplikation auszuwählen und an ihrem Ausgang bereitzustellen, dass die partielle Multiplikation lediglich einen Berechnungsschritt erfordert,
wobei die Auswähleinheit zusätzlich ausgebildet ist, die Fragmente in aufeinanderfolgenden Arbeitsschritten iterativ nach einem vordefinierten Auswahlplan auszuwählen,
mindestens ein partieller Multiplizierer, der mit der Auswähleinheit verbunden ist und der ausgebildet ist, in einem Iterationsschritt eine partielle Multi- plikation der entweder zwei oder der mehr als zwei Operanden durchzuführen und das erhaltene partielle Produkt an seinem Ausgang bereitzustellen
eine Akkumulationseinheit, die mit dem partiellen Multiplizierer verbunden ist und die ausgebildet ist, das vollständige Polynom-Produkt durch eine Iterationsschritt für Iterationsschritt vervollständigte Akkumulation der partiel- len Produkte zu berechnen, die sie vom partiellen Multiplizierer empfangen hat,
eine Akkumulations-Steuereinheit, die mit dem partiellen Multiplizierer und der Akkumulationseinheit verbunden ist, und die ausgebildet ist, je nach ak- tuellem Iterationsschritt ein Steuersignal auszugeben, das die Akkumulationseinheit entsprechend einem vorbestimmten Akkumulationsplan zur Akkumulation eines aktuell am Ausgang des partiellen Multiplizierers anliegenden partiellen Produktes mit einem oder mehreren Termen eines Iterationsschritt für Iterationsschritt weiterentwickelten Ergebnispolynoms in- struiert.
Der Polynom-Multiplizierer gemäß dem zweiten Aspekt der Erfindung zeichnet sich durch einen verringerten Flächenbedarf und einen verringerten Energieverbrauch bei gegenüber dem Stand der Technik erhöhter Flexibilität im Hinblick auf die Wortlänge der zu multiplizierenden Datenworte aus. Letzteres wird durch die Verwendung eines programmierbaren Akkumulationsplans durch die Akkumulations-Steuereinheit bewirkt.
In einem Ausführungsbeispiel des erfindungsgemäßen Polynom-Multiplizierers enthält die Akkumulationseinheit eine Anzahl XOR-Gatter, wobei jedes XOR- Gatter an einem Eingang mit einem oder mehreren Termen des entstehenden Ergebnispolynoms und an einem anderen Eingang mit dem partiellen Multiplizierer verbunden ist. Bevorzugt hat hierbei die Akkumulations-Steuereinheit eine Anzahl Steuer-Logikgatter, die der Anzahl der XOR-Gater der Akkumulationseinheit entspricht. Jedes Steuer-Logikgatter ist einem jeweiligen XOR-Gatter zugeordnet. Die Akkumulations-Steuereinheit ist ausgebildet, in einem jeweiligen Ite- rationsschritt einen vorbestimmten Satz Steuersignale zu erzeugen und an die Steuer-Logikgatter anzulegen, wobei ein jeweiliges Steuersignal festlegt, ob ein jeweiliges XOR-Gatter im aktuellen Iterationsschritt zur Akkumulation aktiviert ist oder nicht. Dieses Ausführungsbeispiel ermöglicht eine besonders einfache, flächensparende Ausführung der Akkumulations-Steuereinheit. Ein aktueller Akku- mulationsschritt wird beispielsweise durch ein Steuerwort gesteuert, das dem Satz Steuersignale entspricht. Jedes Steuerbit des Steuerwortes entspricht einem Steuersignal, und steuert über ein jeweiliges Steuer-Logikgatter die Aktivierung eines bestimmten XOR-Gatters im jeweiligen Akkumulationsschritt. Dabei sind die Steuer-Logikgatter vorzugsweise UND-Gatter mit zwei Eingängen, von denen ein erster Eingang mit einer logischen Eins beaufschlagt ist und ein zweiter Eingang mit einem jeweiligen Steuersignal beaufschlagt ist.
In einem weiteren bevorzugten Ausführungsbeispiel des erfindungsgemäßen Polynom-Multiplizierers ist der partielle Multiplizierer ausgebildet, in einem Taktzyklus einen Berechnungsschritt einer partiellen Multiplikation durchzuführen.
Vorzugsweise wird nicht nur die Akkumulation durch eine programmierbare Steuereinheit kontrolliert, sondern auch die Auswahl der Fragmente. Ein Ausführungsbeispiel hat eine Auswahl-Steuereinheit, die mit der Auswähleinheit verbunden und ausgebildet ist, je nach aktuellem Iterationsschritt Steuersignal auszugeben, das die Auswähleinheit entsprechend dem vorbestimmten Auswahlplan zur Auswahl eines jeweiliges Fragments vorbestimmter Größe von jedem Polynom instruiert. Die Hardware-Implementierung kann in ähnlicher Weise wie bei der Akkumulations-Steuereinheit mit Steuer-Logikgattern erfolgen, so dass wiederum lediglich ein entsprechender Satz Steuersignale abgegeben werden muss, was wiederum Datenpfade vereinfacht und verkürzt und so die Flächeneffizienz erhöht.
Auswahl-Steuereinheit und Akkumulations-Steuereinheit sind vorzugsweise in einer einzigen Multiplikations-Steuereinheit integriert.
Bevorzugt sind die Akkumulations-Steuereinheit und die Auswahl-Steuereinheit ausgebildet, auf den Empfang von Polynomen am Eingang der Auswähleinheit hin den Auswählplan und den Akkumulationsplan entsprechend einer jeweiligen Länge der Polynome und einer vorgegebenen Wortbreite des partiellen Multiplizierers aus einer Vielzahl abgespeicherter Auswahl- und Akkumulationspläne auszuwählen. Dieses Ausführungsbeispiel nutzt den Vorteil der hohen Flexibilität des Polynom-Multiplizierers. In einem weiteren bevorzugten Ausführungsbeispiel des erfindungsgemäßen Polynom-Multiplizierers ist der partielle Multiplizierer ausgebildet, eine partielle Multiplikation zweier Operanden, die am Ausgang der Auswähleinheit bereitgestellt werden, mit Hilfe einer Karatsuba-Formel für ein partielles Produkt C(x)=A(x)-B(x) durchzuführen, entsprechend dem Typ
n
C(x) = a°b° © [α V © aΨ © (α° © aι)(b° © b1)]- x1 © aιbι ■ x" ,
und das partielle Produkt an seinem Ausgang bereitzustellen.
Ein bevorzugtes Ausführungsbeispiel des Polynom-Multiplizierers ist in Form eines integrierten Schaltkreises ausgebildet.
Ein vierter Aspekt der Erfindung betrifft eine Verschlüsselungseinheit zur Verschlüsselung von Daten unter Durchführung einer Polynom-Multiplikation, mit einem Dateneingang für unverschlüsselte Daten, einem mit dem Dateneingang verbundenen Polynom-Multiplizierer gemäß dem dritten Aspekt der Erfindung oder eines seiner Ausführungsbeispiele, und einem mit dem Polynom- Multiplizierer verbundenen Datenausgang zur Ausgabe der verschlüsselten Daten.
Ein bevorzugtes Ausführungsbeispiel der Verschlüsselungseinheit ist zur Verschlüsselung der Daten mit Hilfe der Elliptischen Kurvenkryptographie ausgebildet, das heißt insbesondere, zur Verschlüsselung der am Dateneingang anlie- genden Daten mit Hilfe einer elliptischen Kurve über einem Galois-Feld. Hierzu kann eine der bereits im Zusammenhang mit dem Verfahren des zweiten Aspektes der Erfindungen beschriebenen Kurven verwendet werden.
Die Verschlüsselungseinheit kann in Form eines integrierten Schaltkreises oder in Form eines ausführbaren Computerprogramms implementiert werden. Einen weiteren Aspekt der Erfindung bildet daher ein Datenträger mit einem ausführbaren Programm, das ein Verfahren zur Verschlüsselung von Daten gemäß dem zweiten Aspekt der Erfindung oder eines seiner Ausführungsbeispiele implementiert.
5. Kurzbeschreibung der Figuren
Im Folgenden werden die Erfindung und weitere bevorzugte Ausführungsbeispiele unter Heranziehung der Figuren im Einzelnen erläutert. Es zeigen:
Figur 1 die Struktur eines Ausführungsbeispiels eines Polynom-Multiplizierers
Figur 2 eine detaillierte Darstellung eines Ausführungsbeispiels eines Verfah- rens zur Polynommultiplikation am Beispiel einer 4-Wort Karatsuba-
Polynom-Multiplikation im GF (2m) und
Figur 3 eine am Datenfluss orientierte Block-Darstellung eines Ausführungsbeispiels eines Verfahrens zur Datenverschlüsselung
Figur 4 ein Blockdiagramm eines Ausführungsbeispiels-Verschlüsselungs- einheit
Figur 5 ein Blockdiagramm eines weiteren Ausführungsbeispiels eines PoIy- nom-Multipliziers gemäß der Erfindung.
Figur 6 eine schematische Ansicht des partiellen Multiplizierers und der Akkumulations-Einheit der Figur 5 mit näheren Details.
6. Detaillierte Beschreibung von Ausführungsbeispielen
Zunächst wird die Erfindung anhand eines konkreten Beispiels erläutert. Dabei wird auf die Figuren 1 und 2 parallel Bezug genommen. Figur 1 zeigt die Struktur eines Ausführungsbeispiels eines Polynom- Multiplizierers. Ein Flussdiagramm eines Ausführungsbeispiels des erfindungsgemäßen Verfahrens, bei dem beispielhaft eine Vier-Wort iterative Karatsuba- Polynom-Multiplikation in GF(2m) verwendet wird, ist in Figur 2 dargestellt.
Die nachfolgende Beschreibung verwendet als Beispiel die Kurve B-233 über einem Galois-Feld GF(2233), welche durch das National Institute of Standards and Technology der Vereinigten Staaten von Amerika (NIST) empfohlen ist und zur Implementierung als Hardware besonders geeignet ist.
Die elliptische Kurven-Kryptographie (engl. Elliptic Curve Cryptography, ECC) garantiert die selbe Sicherheit wie das bekannte Verfahren RSA, ermöglicht jedoch die Verwendung deutlich kürzerer Schlüssel. Zusätzlich sind ECC- Operationen schneller als solche des RSA-Verfahrens. Obwohl ECC weniger rechenintensiv ist als RSA, erfordert es relativ viel Energie und Zeit, um das Produkt von einer 233 Bit langen Zahl k und einem Punkt P mit zwei 233 Bit langen Koordinaten zu berechnen. Diese Operation wird, die als 'kP'"-Multiplikation bezeichnet. Dabei ist P ein Punkt auf einer elliptischen Kurve (engl. Elliptic Curve, EC) und k ist eine große Zahl. Die „kP"-Multiplikation kann mit Hilfe der „Double and Add" Methode (Punkt-Verdopplung und der Punkt-Addition) oder mit der Montgomery Methode berechnet werden.
Unabhängig von der verwendeten Methode muss das Ergebnis der ,kP'-Multiplikation reduziert werden. Die Reduzierung wird unter Verwendung sogenannter irreduzibler Polynome durchgeführt und kann eine sehr aufwändige Operation im Galois-Feld GF(2m) sein. Das irreduzible Polynom für B-233 ist das Trinom: /W = X233 Θ / ΘI .
Im Galois-Feld GF(2m) sind Addition und Subtraktion XOR-Operationen. Deshalb und zum einfacheren Verständnis der Formeln ist die gewöhnliche Darstellung n-l n-1 von Polynomen A(x) = £a,x' hier abgeändert in A(x) = @a,x' Im Rahmen dieser
;=0 /=0
Anmeldung ist die XOR-Operation als „θ" gekennzeichnet. Das Symbol „+" be- zeichnet immer eine gewöhnliche Addition. Die Division von Polynomen wird normaler Weise in zwei Schritten durchgeführt: zunächst wird das Inverse des Divisors mit Hilfe des irreduzieblen Polynoms identifiziert, und anschließend wird das Inverse mit dem Dividenden multipliziert.
Der Vorteil der Montgomery Methode ist, dass maximal zweimal die Inverse des Produktes zur Reduktion berechnet werden muss. Dies wird in der Montgomery Methode durch eine größere Anzahl von Multiplikationen erreicht, die weniger Rechenaufwand erzeugen als das Berechnen der Inversen. Dies gilt insbesondere bei Verwendung des hier vorgeschlagenen effizienten Polynom-Multiplizierers.
Ein Ansatzpunkt der vorliegenden Erfindung ist es, das ursprüngliche Karatsuba- Verfahren iterativ anzuwenden. Daher bezeichnen wir das erfindungsgemäße Verfahren auch als iteratives Karatsuba-Verfahren. Die wesentlichen Vorteile dieses Verfahrens sind:
- ein geringerer Flächenbedarf von Hardwarebeschleunigern aufgrund der Möglichkeit, partielle Multiplikationen seriell durchzuführen
- eine geringere Anzahl von XOR-Operationen im Vergleich mit der rekursiven Variante von Karatsubas Verfahren.
Die Karatsuba-Formel für das Produkt C(x)=A(x)-B(x) ist
n
C(x) = a°b° © [α V © aΨ © (α° © aι)(b° © b1)]- x2 © aΨ ■ x" (3)
Erfindungsgemäß wird Karatsubas Formel iterativ angewendet, um die partiellen Produkte a'b1 zu berechnen. In diesem Falle sind insgesamt slog23 ~ ,y158 partielle Multiplikationen erforderlich, wobei s die Anzahl der Segmente ist. Die Anzahl der Segmente (s), in die die Operanden zerlegt werden müssen, wird durch die Länge der Eingangsworte des Multiplizierers bestimmt und kann vor der Berechnung folgendermaßen bestimmt werden: s = Länge des Operanden / Wortlänge der Multiplizierers.
Dieses Verfahren kann verwendet werden, um sowohl Software- als auch Hardware-Implementationen zu beschleunigen. In Software- Implementationen wird das Karatsuba- Verfahren gewöhnlich angewendet, bis beide Operanden die Länge eines Datenwortes haben.
Nachfolgend wird das Prinzip der erfindungsgemäßen iterativen Anwendung von Karatsubas Formel anhand eines Beispiels erläutert, in dem die Operanden in vier Segmente aufgespalten sind. Zunächst wird Karatsubas Formel verwendet, um eine Formel für ein Produkt zu erhalten, in dem lediglich Ein-Segment lange Operanden für die partielle Multiplikation verwendet werden.
Zu Beginn liegen jedoch zwei Operanden vor, von denen jeder 4n-Bit lang ist. Jeder Operand lässt sich in Form einer Summe zweier 2n-Bit langer Teile darstellen und zerlegen:
Figure imgf000018_0001
Das Ergebnis der Anwendung von Karatsubas Formel ist:
C{x) = aιa° - bιb° ®
® [αV • bΨ ® a3a2 - b3b2 ® a13a02 • b13b02 ]• x2n (5)
® a3a2 - b3b2 - x4n
wobei
al3a02 = a13 - xn ® a02 = (aι ® a3) - xn ® (a° ® a2) =
(6) (α1 • x" ® a°) ® (α3 • x" ® a2) = aιa° ® a3a2 und
bl3b°2=blb°®b3b2 (7)
Jedes Element mit zwei Segmenten lässt sich darstellen als a'aJ =a' -x" ®a] . Für jede partielle Multiplikation aus den Gleichungen (6) und (7) wird das Ergeb- nis der Anwendung von Karatsubas Formel erneut genutzt. Die Berechnung erfolgt durch iterative Anwendung der Schritte 204 und 206 (Fig.2) mit Berücksichtigung der durch den aktuellen Taktzyklus („clk") bestimmten Fallunterscheidung („case"), die einen auf dieses Ausführungsbeispiel bezogenen Auswahlplan repräsentiert.
Das Endergebnis ist in der nachfolgenden Formel (8) wiedergegeben:
C(x) = a3 b3-x6"@(a2 b2 ® a3 b3 ® a23 b23)-x5" ®(aι bι@a2 b2@a3 b3 ® a13 bl3)-x4n ®(a° b°@aι bι@a2 b2@a3 b3
®a01 boι@a02 bO2@a13 bl3@a23 b23 (8)
®α0123 bol23)-x3n
®(a° b°@aι bι@a2 b2@a02 bO2)-x2" ®(α° b°@aι bι@a01 boι)-x"@a° b°
Jeder der Operanden des rechten Terms der Formel (8) ist ein Segment lang, so dass das resultierende partielle Produkt (2n-1)-Bit lang ist. Die Bits von n-1 bis 0 des Produktes a'-b' werden in der Form a'b'[0] notiert und die Bits von 2n-1 bis n in der Form a'b'[1]:
Figure imgf000019_0001
Mit der in Gleichung (9) eingeführten Notation kann die Formel (8) wie in der nachfolgenden Tabelle 1 dargestellt werden:
Figure imgf000020_0001
Tabelle 1 : Akkumulationsplan entsprechend der Formel (8) AIIe Spalten in Tabelle 1 , die unter der Überschrift „Ergebnissegmente" aufgeführt sind, repräsentieren ein bestimmtes Segment c', das durch partielle Multiplikation der jeweils genannten ausgewählten Fragmente entsteht. Für jedes partielle Produkt sind in Tabelle 1 zwei Zeilen vorgesehen, wobei eine Zeile den unteren Abschnitt (axbx[0]), und die zweite Zeile den oberen Abschnitt (axbx[1 ]) des Produkts repräsentiert, wie oben angegeben.
Das Segment c' kann als XOR-Verknüpfung aller Zeilen in Tabelle 1 berechnet werden, die das Symbol „ Θ " in der dem Segment c' zugeordneten Spalte enthalten. Beispielsweise kann c5 wie folgt berechnet werden:
c5=a1b1[1 ]θ a2b2[0]Θ a2b2[1 ]Θ a3b3[0]Θ a3b3[1 ]Θ ((a1 θ a3)(b1 θ b3)[1 ])θ ((a2θ a3)(b2θ b3)[0]) (10)
Jedes Segment c' kann iterativ berechnet werden, d. h. Schritt für Schritt wie bei der Berechnung der partiellen Produkte, beginnend mit a°b° bis zu (flo ®fl1 ®fl2 ®fl3) (foo ®/71 ®/72 ®/73) . Anschließend wird mit der Berechnung der Segmente von Produkten begonnen, wobei die bereits vorliegenden Ergebnisse verwendet werden (Schritt 208 in Fig. 2). Beispielsweise:
Figure imgf000021_0001
Tabelle 2: Beispiel der Berechnung von Produktsegmenten unter Verwendung bereits vorliegender Ergebnisse
Parallel zur Berechnung der Segmente erfolgt in jedem Iterationsschritt auch ein Akkumulationsschritt entsprechend den durch Tabelle 1 repräsentierten Akkumu- lationsplan. Auf diese Weise vervollständigt sich das Ergebnis C(x) mit jedem Iterationsschritt von der ersten bis zur letzten Zeile der zu berechnenden partiellen Produkte.
Diese iterative Berechnung des Produktes C(x) reduziert den Flächenbedarf ei- nes Hardware-Multiplizierers. Es wird nur ein partieller Multiplizierer für EinSegment lange Operanden benötigt. Nach jedem neuen Taktsignal liefert dieser Multiplizierer das nächste partielle Produkt. Auf diese Weise werden die Segmente des Produktes C(x) gesammelt. Bei dem oben gegebenen Beispiel enthalten demnach alle Segmente nach neun Taktzyklen das korrekte Produkt der PoIy- nom-Multiplikation.
Mit der beschriebenen iterativen Hardwarelösung beträgt die Chipfläche, die für die Berechnung des Produkts von zwei 233 Bit langen Operanden benötigt wird,
2.1 mm2. Für die Standard-Anwendung der Karatsuba-Methode werden dagegen
6.2 mm2 benötigt. Die erfindungsgemäße Lösung reduziert auch den Energie- verbrauch um 30% gegenüber dem ursprünglichen Lösungsansatz. Diese Fortschritte werden lediglich mit einer erhöhten Berechnungszeit bezahlt. In einem Ausführungsbeispiel benötigt eine Polynom-Multiplikation drei Taktzyklen während im ursprünglichen Karatsuba-Verfahren nur 1 Taktzyklus benötigt wird.
Auf ähnliche Weise kann der erfindungsgemäße iterative Ansatz auf die Methode von Bailey angewendet werden, was im Rahmen dieser Anmeldung als iterative Bailey-Methode bezeichnet wird.
Nachfolgend werden der Aufbau und die wesentlichen Parameter eines Ausführungsbeispiels einer Hardware-Implementierung des iterativen Karatsuba- Verfahrens erläutert. Die Struktur eines iterativen Karatsuba-Beschleunigers be- steht aus drei wesentlichen Teilen, vgl. Figur 1 :
- Eine Auswähleinheit 100 stellt bei jedem neuen Taktsignal an ihrem Ausgang bestimmte Teile beider Operanden einem nachgeschalteten partiellen Multiplizierer zur Verfügung. - Ein partieller Multiplizierer 102 berechnet das partielle Produkt der von der Auswähleinheit gelieferten Operanden und stellt die Ergebnisse einer Produkt-Akkumulations-Einheit zur verfügen.
- Die Produkt-Akkumulationseinheit 104 berechnet das Endergebnis des Pro- dukts aus den partiellen Produkten, die sie von dem partiellen Multiplizierer erhält. Die theoretische Basis und die genaue Schrittfolge wurden in den obigen Abschnitten 4 und 5 im Einzelnen erläutert.
Die Leistungsdaten, die Chipfläche und der Energiebedarf eines Polynom- Multiplizieres werden wesentlich vom verwendeten partiellen Multiplizierer beein- flusst. Je größer die Eingangssignale des partiellen Multiplizierers sein können, desto schneller ist der partielle Multiplizierer. Andererseits führt dies auch zu einem relativ großen Flächenbedarf. Daher ist beim Hardware-Design eine Entscheidung zwischen Berechnungsdauer und Chipfläche zu treffen. Dies gilt jedoch nur so lange, wie allein der partielle Multiplizierer in Betracht gezogen wird. Für den Polynom-Multiplizierer ist darüber hinaus auch die Fläche der Auswähl- und der Produkt-Akkumulations-Einheiten von Bedeutung. Die Chipfläche, die die Produkt-Akkumulations-Einheit benötigt, hängt von dem Flächenbedarf des partiellen Multiplizierers in einer invers proportionalen Weise ab. Das heißt, je kleiner der partielle Multiplizierer, desto größer ist die Produkt-Akkumulations-Einheit. Dies ergibt sich aus der Tatsache, dass im Falle kleiner partieller Multiplizierer mehr Zwischenergebnisse gespeichert werden müssen, um die abschließende Berechnung des Polynom-Produkts durchzuführen. Beispielsweise ist die Fläche der Produkt-Akkumulations-Einheit 0,649 mm2, wenn der partielle Multiplizierer 128 Bit lange Operanden akzeptiert. Die Fläche beträgt dagegen 1 ,466 mm2, wenn die maximale akzeptierte Länge der Operanden lediglich 32 Bit beträgt.
Um ein möglichst gut angepasstes Design für ein Polynom-Multiplizierer zu erhalten, wurden verschiedene partielle Multiplizierer realisiert. Es wurden drei EinTakt partielle Multiplizierer für das erfindungsgemäße Karatsuba-Verfahren als auch für ein erfindungsgemäßes iteratives Bailey-Verfahren verwendet. Diese partiellen Multiplizierer akzeptieren Operanden mit einer maximalen Länge von jeweils 128, 64 und 32 Bit. Sie wurden mit Hilfe der Schaltungsbibliothek der Anmelderin und der eigenen 0,25 μm-CMOS-Technologie synthetisiert. Tabelle 3 zeigt die Parameterfläche, Zeit und Energieverbrauch jedes dieser sechs partiellen Multiplizierer. Die Werte wurden mit Hilfe des Design-Analyse-Werkzeugs der Firma Synopsys ermittelt.
Figure imgf000024_0001
Tabelle 3: Parameter der hergestellten partiellen Multiplizierer
Ausführungsbeispiele mit einer Akkumulations-Steuereinheit und einer Auswahl- Steuereinheit, die in einer Multiplikations-Steuereinheit integriert sind, können die Flexibilität hinsichtlich der erforderlichen Gesamtdauer, der möglichen Taktfrequenzen und der benötigten Chipfläche weiter erhöhen. In der nachfolgenden Tabelle 4 werden Parameter unterschiedlicher 233-Bit interativer Karatsuba- Multiplizierer verglichen. Dabei ist erkennbar, dass ein 1 -Takt-Multiplizierer die geringste Gesamtzeit für eine Polynommultiplikation benötigt, jedoch anderer- seits bei weitem die größte Chipfläche benötigt.
Es fällt anhand der Daten von Tabelle 4 auf, dass eine 4-Segment-Karatsuba- Implementierung eine geringere Chipfläche benötigt als eine 8-Segment- Implementierung. Hier kommt zum Tragen, dass die Logik für die Auswahl der Fragmente (Segmente) und für die Akkumulation der partiellen Produkte in Ausführungsbeispielen mit einer höheren Fragmentierung einen beträchtlichen Ein- fluss auf den Flächenbedarf hat. Es zeigt sich, dass in der 8-Segment- Implementierung diese Logikteile mehr als 75 % der vom Multiplizierer eingenommenen Chipfläche benötigen. Insgesamt nehmen die Selektions- und Auswahllogiken im 2-Segment-Multiplizierer 0,30 mm2, im 4-Segment-Multiplizierer 0,78 mm2 und im 8-Segment-Multiplizierer 1 ,18 mm2 ein. Die Segmentierung hat aufgrund des sich ergebenden komplizierten Datenpfades einen hohen Einfluss auf die benötigte Chipfläche. Aus diesem Grund werden in einem bevorzugten Ausführungsbeispiel die Akkumulations-Steuereinheit und die Auswahl- Steuereinheit mit einer alternativen Struktur ausgebildet, die weiter unten anhand von Figur 5 näher beschrieben wird.
Figure imgf000025_0001
Tabelle 4: Parameter unterschiedlicher 233-Bit iterativer Karatsuba-Multiplizierer
Für einen Benchmarking-Test wurden Polynom-Multiplizierer mit einer Implementierung der folgenden Verfahren hergestellt:
- iteratives Karatsuba- Verfahren
- iteratives Bailey-Verfahren
- rekursives Karatsuba- Verfahren nach dem Stand der Technik - rekursives Bailey-Verfahren nach dem Stand der Technik Für die ersten beiden Verfahrens-Implementierungen wurden drei Polynom- Multiplizierer mit unterschiedlichen partiellen Multiplizierern verwendet (vgl. Tabelle 4), um den Einfluss des jeweiligen partiellen Multiplizierers auf die Leistungsparameter feststellen zu können. Diese Multiplizierer wurden so benannte, dass der Namen auf das verwendete Verfahren hinweist. Beispielsweise bedeutet der Name iterative_Karatsuba_8segments: iteratives Karatsuba-Verfahren, bei dem eingehende Operanden in acht Segmente fragmentiert werden.
Bei den zwei rekursiven Multiplizierern wird die ursprüngliche Karatsuba- bzw. Bailey-Formel bis hinab zu Ein-Bit-Operanden angewendet. Beide Multiplizierer liefern das Polynom-Produkt nach einem Taktzyklus. Sie unterscheiden sich in der Länge der Eingabe-Operanden. Der Karatsuba-Multiplizierer erwartet stets zwei 256 Bit lange Eingabewerte, während der Bailey-Multiplizierer zwei 243 Bit lange Eingabewerte erwartet.
Wegen der beabsichtigten Verwendung dieser Multiplizierer für EC B-233, sind die zu erwartenden Eingabewerte nur 233 Bit lang. Daher wurden die Operanden mit vorangehenden Nullen aufgefüllt, wo dies erforderlich war. Das Ergebnis der Multiplikation ist stets 465 Bit lang.
Alle Polynom-Multiplizierer wurden unter Verwendung einer Schaltungsbibliothek der 0,25 μm-CMOS-Technologie der Anmelderin synthetisiert. Die Parameter der implementierten Polynom-Multiplizierer sind in Tabelle 4 angegeben. Die darin enthaltenen Daten wurden mit Hilfe unterschiedlicher Arten von Analysen- Reports aus dem „Design Analyzer" von Synopsys erhalten.
Figure imgf000027_0001
Tabelle 5: Parameter der synthetisierten Polynom-Multiplizierer
Die in Tabelle 5 wiedergegebenen Ergebnisse zeigen deutlich, dass eine iterative Anwendung der Verfahren von Karatsuba und Bailey benötigte Chipfläche signifikant verringert. Wird die Anzahl der Iterationen klein gehalten, hilft der erfindungsgemäße Ansatz auch bei einer Reduzierung des Energieverbrauchs. In diesen Designvarianten wird ein geringerer Flächenbedarf und ein geringerer Energieverbrauch auf Kosten einer langsameren Ausführungszeit erzielt. Bei einer Erhöhung der Anzahl von Iterationen wird die benötigte Chipfläche reduziert, jedoch auch die benötigte Leistungsaufnahme und Rechenzeit erhöht. Diese Implementierungen sind nur dann von Nutzen, wenn Kosten den entscheiden- den Parameter bilden.
Die iterative Anwendung des Karatsuba-Verfahrens für Polynom-Multiplikationen ermöglicht also eine Reduzierung der benötigten Chipfläche sowie der für die Durchführung einer elliptischen Kurvenkryptographie auf mobilen Endgeräte erforderlichen Energie. Es wurden verschiedene Verfahren für die Polynom- Multiplikation in GF(2n) analysiert sowie verschiedene Polynom-Multiplikations- Algorithmen implementiert. Verschiedene partielle Multiplizierer wurden hergestellt. Sie wurden zur Implementierung einer Anzahl iterativer Polynom- Multiplizierer verwendet, um die bestmögliche Variante für die Anwendung in mobilen Endgeräten zu ermitteln. Unsere Ergebnisse zeigen deutlich, dass der erfindungsgemäße iterative Ansatz zu signifikant besseren Ergebnissen im Hinblick auf Chipfläche und Energieverbrauch führt als die ursprünglichen direkten Anwendungen.
Figur 3 zeigt eine am Datenfluss orientierte Block-Darstellung eines Ausführungsbeispiels einer Vorrichtung zur Datenverschlüsselung, die nachfolgend als Verschlüsselungseinheit 300 bezeichnet wird. Die Verschlüsselungseinheit 300 enthält einen Festwertspeicher 302, in dem die Koordinaten eines Basispunktes G einer vorbestimmten elliptischen Kurve abgelegt sind. Ein Zufallszahlengenerator 304 erzeugt jeweils eine Zufallszahl k pro Abschnitt M zu verschlüsselnder Nutzdaten. Ein Speicher 306 enthält einen öffentlichen Schlüssel S des Empfän- gers der Nachricht. Ein Datensegmentierer 308 zerlegt eingehende und zu verschlüsselnde Nutzdaten in Nutzdatenabschnitte M einer vorbestimmten Länge.
Im Rahmen der Verschlüsselung eines Nutzdatenabschnitts M wird in einem Ga- lois— Feld-Multiplizierer 310, der einen iterativen Polynom-Multiplizierer gemäß der Erfindung enthält, zum einen das Produkt kG des Basispunkts G mit der ak- tuellen Zufallszahl k berechnet. Dies ist durch einen Block 310.1 symbolisiert. Weiterhin wird im Galois-Feld-Multiplizierer 310 das Produkt kS derselben aktuellen Zufallszahl k und des öffentlichen Schlüssels S bestimmt, was durch den Block 310.2 symbolisiert ist. Es wird darauf hingewiesen, dass es zwar denkbar ist, zwei unabhängige Galois-Feld-Multiplizierer für die Berechnung der Produkte kG und kS vorzusehen. Bevorzugt ist jedoch nur ein Galois-Feld-Multiplizierer vorhanden, um den Flächenbedarf nicht unnötig zu erhöhen. Die damit verbundene Zeitverzögerung ist für die meisten Verschlüsselungsanwendungen tolera- bel.
In einer Transformationseinheit 312 wird der von dem Datensegmentierer 308 gelieferte Nutzdaten abschnitt auf Übereinstimmung mit der X-Koordinate eines Punktes der elliptischen Kurve überprüft. Dabei werden gegebenenfalls nicht festgelegte Bits des Nutzdatenabschnitts M verändert, so dass ein abgewandelter Nutzdatenabschnitt M* entsteht. Die nicht festgelegten Bits sind frei änderbar, ohne die Gefahr einer Modifizierung der Nutzinformation. Diese Abwandlung hat also keinen Einfluss auf die im Nutzdaten abschnitt M* enthaltene Nutzinformation. Nach jeder Erzeugung eines abgewandelten Nutzdatenabschnitts M* wird erneut geprüft, ob dieser veränderte Nutzdatenabschnitt mit der X-Koordinate eines Punktes auf der elliptischen Kurve übereinstimmt.
Die Funktionsweise der Transformationseinheit 312 wird nachfolgend anhand eines Beispiels näher erläutert. Ein Nutzdatenabschnitt enthält beispielsweise den Text „zojka", der durch die Datensymbolsequenz (5A, 6F, 6A, 6B, 61 , 00) symbolisiert ist. Hierbei ist das letzte Datensymbol „00" nicht festgelegt und kann verändert werden, um die Folge der Datensymbole der X-Koordinate eines Punktes auf der elliptischen Kurve anzugleichen. Angenommen, in einem ersten Schritt werde das nicht festgelegte Datensymbol als „01 " definiert, so wird die Transformationseinheit 312 feststellen, dass die dadurch entstehende Folge von Datensymbolen keine Entsprechung in einem Punkt der elliptischen Kurve hat. Wird jedoch das nicht festgelegte Datensymbol als „02" definiert, wird die Transformationseinheit 312 feststellen, dass die dadurch entstehende Folge von Da- tensymbolen einem Punkt auf der elliptischen Kurve entspricht, der folgende Y- Koordinate hat: 7D3C7D654AAB7068E1 DA366C49588A27F252D410. Die Transformationseinheit 312 leitet vom ermittelten Punkt der elliptischen Kurve X- und Y-Koordinate an einen Eingang eines Addierers 314, an dessen anderem Eingang das Produkt kS des öffentlichen Schlüssels mit der aktuellen Zufallszahl k anliegt. Die Summe kS + Y gibt der Addierer 314 an eine Ausgabeeinheit 316, der an einem weiteren Eingang das Produkt kG zugeleitet wird. Die Ausgabeeinheit 316 fügt die Datensymbole kG und der Summe kS + Y zu einer Datensequenz zusammen und gibt diese aus. Die Ausgabe kann entweder seriell oder parallel erfolgen.
Die Verschlüsselungseinheit 300 kann sowohl in Form von Hardware als auch in Form einer Software implementiert werden.
Figur 4 zeigt ein Blockdiagramm eines weiteren Ausführungsbeispiels einer Verschlüsselungseinheit, das nachfolgend als Verschlüsselungseinheit 400 bezeichnet wird. Die Darstellung der Figur 4 zeigt eine Hardware-Implementierung.
Die einzelnen Einheiten der Verschlüsselungseinheit sind über einen zentralen Bus 402 verbunden. An den Bus 402 ist eine Steuereinheit 404 angeschlossen, die eine Kontrolllogik zur Durchführung der Montgomery-Methode enthält. Die Steuereinheit 404 steuert das Zusammenwirken der nachfolgend beschriebenen Einheiten. Über eine Eingabe/Ausgabe-Einheit 406 können der Verschlüsselungseinheit 400 ein Basispunkt G, ein öffentlicher Schlüssel S und ein Nutzda- tenabschnitt M zugeführt werden. Die Eingabe/Ausgabe-Einheit 406 ist gleichzeitig ausgebildet, eine von der Verschlüsselungseinheit 400 erzeugte verschlüsselte Nachricht, wie im Zusammenhang mit der Ausgabeeinheit 316 der Figur 3 beschrieben, zusammenzusetzen und auszugeben.
Ein Zufallszahlengenerator 408 liefert für jeden eingehenden Nutzdatenabschnitt M eine Zufallszahl k. Ein Karatsuba-Polynom-Multiplizierer 410 ist mit einer Polynom-Reduktionseinheit 412 verbunden. Eine ebenfalls mit dem Datenbus 402 verbundene Inversionseinheit 414 ist ausgebildet, die multiplikative Inverse eines Polynoms zu bilden. Weiterhin ist ein Addierer 416 vorgesehen sowie eine PoIy- nom-Quadrierungseinheit 418, die mit einem weiteren Polynom-Reduzierer 420 verbunden ist.
Die Funktionsweise der Verschlüsselungseinheit 400 entspricht der anhand von Figur 3 dargestellten Funktionsweise, wobei die Steuereinheit 404 die Funktion der Transformationseinheit 312 wahrnimmt.
Verschiedene Varianten der Verschlüsselungseinheit 400 sind möglich. Beispielsweise kann vorgesehen sein, den Basispunkt G und/oder den öffentlichen Schlüssel S nicht über die Eingabe/Ausgabe-Einheit 406 zuzuführen, sondern in einem Speicher fest abzulegen. Hierfür kann der auch im Rahmen der Polynom- Multiplikation verwendete Speicher 422 genutzt werden.
Andererseits ist auch denkbar, nicht nur den Basispunkt G, den öffentlichen Schlüssel S und die Nutzdaten M, sondern auch die aktuelle Zufallszahl k von extern zuzuführen und den Zufallsgenerator 408 nicht in die Verschlüsselungseinheit 400 zu integrieren. Auf diese Weise kann der Flächenbedarf der Ver- schlüsselungseinheit 400 bei einer Hardware-Implementierung weiter reduziert werden.
Die vom Addierer 416 durchgeführte Addition basiert, wie bereits vorher erwähnt, auf der XOR-Operation.
Die Software-Variante wurde mit dem Polynommultiplizierer der Miracle- Bibliothek", Version 4.7, Shamus Software Ltd. (Ireland), http://indiqo.ie/~mscott/), der einen rekursiven Karatsuba-Ansatz nutzt, sowie mit einer Implementierung der von Lopez vorgeschlagenen Multiplikations-Alternative verglichen. Für die Implementierung der Software Variante wurde Microsoft Visual C++ 6.0 genutzt. Die Vergleichsmessungen wurden auf einem PC (Intel Penti- um III Processor, 800 MHz, Microsoft Windows XP Professional Version 2002, 256 MB RAM) sowie auf einem PDA (Pocket PC iPAQ Hewlett-Packard Company, 48MB ROM; 128 MB RAM, 400 MHz Intel XScale Processor Modell h5500, OS: Pocket PC 2003 Prem mit Outlook 2002) durchgeführt. Für den Vergleich wurden zunächst eine Anzahl von 1 Million jeweils 233 Bit langen Operanden einem Datenfile gespeichert. Diese Operanden wurden für alle Messungen verwendet, um eine Vergleichbarkeit der Ergebnisse sicherzustellen. Eintrag Nummer n des Datenfiles wurde mit Eintrag Nummer n+1 multipliziert, bis alle Ope- randen verwendet waren. Der Test bestand also in der Durchführung 1 Million Multiplikationen.
Der Vergleich der durchschnittlichen Berechnungszeiten auf dem PC zeigt eine Leistungssteigerung im Vergleich zur rekursiven Anwendung des Karatsuba Ansatzes um:
- bis zu 17% bei Verwendung von Compileroptimierungen und
bis zu 37% ohne Verwendung der Compiler Optimierungen.
Auf dem PDA haben sich folgende Leistungssteigerungen im Vergleich mit der rekursiven Karatsuba Methode ergeben:
bis zu 11 % bei Verwendung von Compileroptimierungen und
- bis zu 17% ohne Verwendung der Compiler Optimierungen.
Diese Werte zeigen, dass das erfindungsgemäße Verfahren nicht nur in einer Hardware-Implementation, sondern auch in einer Software-Implementation Vorteile gegenüber bekannten Verfahren aufweist.
Figur 5 zeigt ein Blockdiagramm eines Ausführungsbeispiels eines erfindungs- gemäßen Polynom-Multiplizierers 500.
Die Struktur des Polynom-Multiplizierers 500 gleicht in weiten Teilen der Struktur des in Figur 1 beschriebenen Polynom-Multiplizierers. So enthält auch der Polynom-Multiplizierer 500 eine Auswähleinheit 502, einen partiellen Multiplizierer 504 und eine Produkt-Akkumulationseinheit 506. Während jedoch im Ausführungsbeispiel der Figur 1 der Betrieb der Auswähl- und der Akkumulationseinheit durch hartverdrahtete Datenpfade vorgegeben ist und Taktsignal für Taktsignal einen hartverdrahteten Auswahlplan sowie einen hartverdrahteten Akkumulationsplan abarbeitet, ist im vorliegenden Ausführungs- beispiel eine separate Multiplizier-Steuereinheit 508 vorgesehen, die eine Auswahl-Steuereinheit 508.1 und eine Akkumulations-Steuereinheit 508.2 in sich integriert. Die Multiplizier-Steuereinheit ist dementsprechend zum einen mit der Auswähleinheit 502 und zum anderen mit der Akkumulationseinheit 506 verbunden.
Ebenfalls dargestellt sind Eingangsregister 510 und 512, die der Auswähleinheit 502 vorgeschaltet sind und zur Aufnahme eingehender Datenworte A und B ausgebildet sind, deren Produkt vom Polynom-Multiplizierer zu berechnen ist. Das berechnete Produkt C wird am Ausgang eines Ausgangsregisters 514 anliegen, das hier als Teil der Akkumulationseinheit 506 dargestellt ist.
In einem bevorzugten Ausführungsbeispiel integriert die Akkumulationseinheit 506 zugleich eine Reduktionseinheit, so dass ein auf die Wortlänge der eingehenden Datenworte reduziertes Produkt C ausgegeben werden kann.
Es ist jedoch alternativ auch denkbar, die Reduktionseinheit dem Polynom- Multiplizierer 500 nachzuschalten. In diesem Fall muss das Ausgangsregister 514 eine entsprechend größere Wortbreite zur Verfügung stellen.
Die gegenüber dem Ausführungsbeispiel der Figur 1 geänderte Betriebsweise des Polynom-Multiplizierers 500 der Figur 5 wird nachfolgend unter Heranziehung der Figur 6 näher erläutert.
Figur 6 zeigt eine schematische Ansicht des partiellen Multiplizierers und der Akkumulations-Einheit der Figur 5 mit näheren Details. Die Darstellung ist insofern schematisch als sie einige Strukturelemente zur Verdeutlichung des Betriebsablaufs der Akkumulation in einem Iterationsschritt mehrfach darstellt, wie nachfolgend näher erläutert wird. Die Struktur der Akkumulationseinheit wird anhand eines Beispiels eines iterativen Karatsuba-Multiplizierers mit einer 4-Segment-Multiplikation 233-Bit langer Datenwörter beschrieben, wie sie auch in Fig. 5 beispielhaft vorgegeben ist. In diesem Fall stehen am Ende jeder Iteration in der Akkumulationseinheit 8 Pro- duktsegmente cθ bis c7 zur Verfügung, wie in Tabelle 1 an einem entsprechenden Beispiel erläutert wurde. Diese Segmente cθ bis c7 befinden sich in entsprechenden Registern 516 bis 530.
Die Struktur der Register 516 bis 530 ist in Figur 6 insgesamt dreimal dargestellt, um den Ablauf eines Iterationsschrittes zu verdeutlichen. Dabei repräsentiert die in der Figur linksseitigdargestellte Registerstruktur einen anfänglichen Registerzustand, die in der Mitte gestrichelt dargestellte Registerstruktur einen temporären Zwischenzustand, der nicht abgespeichert wird, und die rechtsseitig dargestellte Registerstruktur einen Endzustand eines jeweiligen Iterationsschrittes dar. Alle drei Darstellungen betreffen jedoch, wie erwähnt, in der tatsächlichen Akku- mulationseinheit 506 dieselbe Registerstruktur 516 bis 530.
Die Datenbreite der Registerstruktur bei einem nxn-partiellen Multiplizierer 504 beträgt 8n.
Der Übergang vom anfänglichen Registerzustand zum abschließenden Registerzustand während eines Iterationsschrittes ergibt sich durch eine Anzahl XOR- Verknüpfungen, die mit insgesamt 7 XOR-Gattern 532 bis 544 durchgeführt werden. Jedes XOR-Gatter verknüpft 2n Bit aus zwei benachbarten Registern mit dem aktuellen Ergebnis einer partiellen Multiplikation, das in einem Register 504.1 am Ausgang des partiellen Multiplizierers 504 bereitliegt.
Jedes XOR-Gatter ist eingangsseitig mit einem Steuer-Logik-Gatter verknüpft. Ob eine XOR-Verknüpfung des jeweiligen Registers mit dem aktuellen partiellen Produkt aus dem Register 504.1 tatsächlich vorgenommen wird, entscheidet der Zustand eines jeweiligen Steuer-Logik-Gatters. Die Steuer-Logik-Gatter sind im vorliegenden Ausführungsbeispiel UND-Gatter 546 bis 558, an deren einem Eingang das Ergebnis der partiellen Multiplikation und an deren anderem Eingang je ein Steuerbit cw [0], cw[1], ... , cw[6] eines Steuerwortes (control word, cw) anliegt. Je nach Wert des jeweiligen Steuerbits im aktuellen Iterationszyklus wird also das partielle Multiplikationsergebnis zur Akkumulation an einem jeweiligen Register 516 bis 530 vom jeweiligen UND-Gatter zugelassen oder blockiert. Ist das Steuerbit gesetzt, erfolgt eine Addition bzw. XOR-Verknüpfung, ist das Steuerbit nicht gesetzt, erfolgt keine XOR-Verknüpfung am jeweiligen XOR- Gatter. Durch Steuerung der Verknüpfungen in jedem Akkumulations-Zyklus, also in jedem Iterationsschritt, kann auf diese Weise ein Akkumulationsplan entsprechend Tabelle 1 umgesetzt werden.
Diese Form der Kontrolle der Akkumulation mit Hilfe eines Steuerwortes erspart komplizierte Datenpfade und führt zu einer beträchtlichen Flächeneinsparung. Ein weiterer Vorteil dieser Ausführungsform ist, dass auf diese Weise unterschiedliche Akkumulationspläne implementiert werden können. Diese können in einem Speicher bereitliegen oder nachträglich der Akkumulations-Steuereinheit 508.2 eingespeichert werden.
Die Auswählsteuerung kann auf die selbe Weise realisiert werden und ist hier nicht näher dargestellt.
Der mit dem vorliegenden Ausführungsbeispiel erzielte Flächenvorteil ist um so größer, je höher die Segmentierung der zur Multiplikation vorgesehenen Daten- worte ist. Während beim Ausführungsbeispiel der Figur 1 der Datenpfad mit zunehmender Segmentierung komplizierter wird und daher zunehmend Chipfläche beansprucht (von 0,30 mm2 für ein 2-Segment-Verfahren über 0,78 mm2 für ein 4-Segment- Verfahren bis zu 1 ,18 mm2 für ein 8-Segment-Verfahren), bleibt der Flächenbedarf der Multiplizier-Steuereinheit 508, die sowohl die Auswahl- Steuereinheit 508.1 als auch die Akkumulations-Steuereinheit 508.2 enthält, nahezu konstant und bewegt sich im Bereich von 0,30 mm2. Patentansprüche
1 . Verfahren zum Berechnen einer Polynom-Multiplikation, mit den Schritten:
H-I
Bereitstellen von Koeffizienten a„ b, zweier Polynome A(x) = @a,x' und
;=0 n-1
B(x) = @b,x' , wobei " 0 " eine Addition oder eine XOR-Operation kenn-
;=0 zeichnet und a„ b, binäre Ein-Bit-Werte sind, d. h . 0 oder 1 , sowie x' = 1 ist,
- Auswählen von entweder zwei oder mehr als zwei Fragmenten, eines von jedem Polynom, als Operanden für eine partielle Multiplikation,
- partielles Multiplizieren der ausgewählten Fragmente, um ein partielles Produkt zu erhalten,
wobei der Auswählschritt iterativ nach einem vordefinierten Auswahlplan durchgeführt wird, und wobei Fragmente verwendet werden, bei denen der jeweilige Multiplizierschritt zur Bildung eines partiellen Produkts jeweiliger Fragmente lediglich einen Berechnungsschritt erfor- dert,
- Akkumulieren der partiellen Produkte, wobei das Akkumulieren entsprechend einem vordefinierten Akkumulationsplan zur Akkumulation eines aktuell am Ausgang des partiellen Multiplizierers anliegenden partiellen Produktes mit einem oder mehreren Termen eines Iterationsschritt für Iterationsschritt weiterentwickelten Ergebnispolynoms gesteuert wird.
2. Verfahren nach Anspruch 1 , bei dem das Akkumulieren parallel mit dem Fragmentieren durchgeführt wird und einen partiellen Akkumulierungsschritt gemäß dem Akkumulationsplan umfasst, der nach einer jeweiligen Iteration eines Multiplizierschrittes durchgeführt wird.

Claims

3. Verfahren nach Anspruch 1 oder 2, bei dem in einem Taktzyklus eines Berechnungsgeräts zur Durchführung des Verfahrens ein Berechnungsschritt durchgeführt wird.
4. Verfahren nach einem der vorstehenden Ansprüche, bei dem die Auswähl-, Multiplizier- und Akkumulationsschritte auf einem Karatsuba-Verfahren zur
Durchführung einer Polynom-Multiplikation beruhen.
5. Verfahren nach einem der vorstehenden Ansprüche, bei dem vor dem Auswählschritt der Auswählplan und der Akkumulationsplan entsprechend einer jeweiligen Länge der Polynome und einer vorgegebenen Wortbreite eines zur Durchführung des partiellen Multiplizierschrittes verwendeten partiellen Multiplizierers aus einer Vielzahl abgespeicherter Auswahl- und Akkumulationspläne ausgewählt werden.
6. Verfahren zur Verschlüsselung von Daten, mit einem Schritt der Berechnung eines Produktes zweier Polynome gemäß einem Verfahren nach ei- nem der Ansprüche 1 bis 5.
7. Verfahren nach Anspruch 6, bei dem die Verschlüsselung der Daten mit Hilfe einer elliptischen Kurve über einem Galois-Feld durchgeführt wird.
8. Verfahren nach Anspruch 7, bei dem die elliptische Kurve die Kurve B-163 über dem Galois-Feld GF(2163) oder die Kurve B-233 über dem Galois-Feld GF(2233), oder die Kurve B-283 über dem Galois-Feld GF(2283) oder die
Kurve B-409 über dem Galois-Feld GF(2409), oder die Kurve B-571 über dem Galois-Feld GF(2571), oder die Kurve K-163 über dem Galois-Feld GF(2163) oder die Kurve K-233 über dem Galois-Feld GF(2233), oder die Kurve K-283 über dem Galois-Feld GF(2283) oder die Kurve K-409 über dem Galois-Feld GF(2409), oder die Kurve K-571 über dem Galois-Feld
GF(2571) ist.
9. Polynom-Multiplizierer, mit einer Auswähleinheit, die ausgebildet ist,
- Koeffizienten a„ b, von zwei Polynomen Λ(x) = 0α,x' und
;=0
B(x) = @b,x' zu empfangen, wobei " 0 " eine Addition oder eine
;=0
XOR-Operation bezeichnet, a, und b, Ein-Bit-Binär-Werte sind, d. h. 0 oder 1 , und x' = 1 , und
- in einem Arbeitsschritt entweder zwei oder mehr als zwei Fragmente, eines von jedem Polynom, mit einer solchen Länge als Operanden für eine partielle Multiplikation auszuwählen und an ihrem Ausgang bereitzustellen, dass die partielle Multiplikation lediglich einen Berech- nungsschritt erfordert,
wobei die Auswähleinheit zusätzlich ausgebildet ist, die Fragmente in aufeinanderfolgenden Arbeitsschritten iterativ nach einem vordefinierten Auswahlplan auszuwählen,
- mindestens ein partieller Multiplizierer, der mit der Auswähleinheit ver- bunden ist und der ausgebildet ist, in einem Iterationsschritt eine partielle Multiplikation der entweder zwei oder der mehr als zwei Operanden durchzuführen und das erhaltene partielle Produkt an seinem Ausgang bereitzustellen
- eine Akkumulationseinheit, die mit dem partiellen Multiplizierer verbun- den ist und die ausgebildet ist, das vollständige Polynom-Produkt durch eine Iterationsschritt für Iterationsschritt vervollständigte Akkumulation der partiellen Produkte zu berechnen, die sie vom partiellen Multiplizierer empfangen hat,
- eine Akkumulations-Steuereinheit, die mit dem partiellen Multiplizierer und der Akkumulationseinheit verbunden ist, und die ausgebildet ist, je nach aktuellem Iterationsschritt ein Steuersignal auszugeben, das die Akkumulationseinheit entsprechend einem vorbestimmten Akkumulationsplan zur Akkumulation eines aktuell am Ausgang des partiellen Multiplizierers anliegenden partiellen Produktes mit einem oder mehreren Termen eines Iterationsschritt für Iterationsschritt weiterentwickelten Ergebnispolynoms instruiert.
10. Polynom-Multiplizierer nach Anspruch 9, bei dem die Akkumulationseinheit eine Anzahl XOR-Gatter enthält, wobei jedes XOR-Gatter an einem Eingang mit einem oder mehreren Termen des entstehenden Ergebnispoly- noms und an einem anderen Eingang mit dem partiellen Multiplizierer verbunden ist.
11. Polynom-Multiplizierer nach Anspruch 10, bei dem die Akkumulations- Steuereinheit eine Anzahl Steuer-Logikgatter aufweist, die der Anzahl der XOR-Gater der Akkumulationseinheit entspricht, wobei jedes Steuer- Logikgatter einem jeweiligen XOR-Gatter zugeordnet ist, und bei der die
Akkumulations-Steuereinheit ausgebildet ist, in einem jeweiligen Iterationsschritt einen vorbestimmten Satz Steuersignale zu erzeugen und an die Steuer-Logikgatter anzulegen, wobei ein jeweiliges Steuersignal festlegt, ob ein jeweiliges XOR-Gatter im aktuellen Iterationsschritt zur Akkumulation aktiviert ist oder nicht.
12. Polynom-Multiplizierer nach Anspruch 11 , bei dem die Steuer-Logikgatter UND-Gatter mit zwei Eingängen sind, von denen ein erster Eingang mit einer logischen Eins beaufschlagt ist und ein zweiter Eingang mit einem Steuersignal beaufschlagt ist.
13. Polynom-Multiplizierer nach einem der Ansprüche 9 bis 12, mit einer Auswahl-Steuereinheit, die mit der Auswähleinheit verbunden und ausgebildet ist, je nach aktuellem Iterationsschritt Steuersignal auszugeben, das die Auswähleinheit entsprechend dem vorbestimmten Auswahlplan zur Aus- wahl eines jeweiliges Fragments vorbestimmter Größe von jedem Polynom instruiert.
14. Polynom-Multiplizierer nach einem der Ansprüche 9 bis 13, der ausgebildet ist, eine partielle Multiplikation zweier Operanden, die am Ausgang der Auswähleinheit bereitgestellt werden, mit Hilfe einer Karatsuba-Formel für ein partielles Produkt C(x)=A(x)-B(x) durchzuführen, entsprechend dem Typ
n
C(jc) = a°b° ® [α V ® aΨ ® (α° ® aι)(b° ® b1)]- x1 ® aΨ ■ x"
und das partielle Produkt an seinem Ausgang bereitzustellen.
15. Polynom-Multiplizierer nach einem der Ansprüche 9 bis 14, bei dem die Akkumulations-Steuereinheit und die Auswahl-Steuereinheit ausgebildet sind, auf den Empfang von Polynomen am Eingang der Auswähleinheit hin den Auswählplan und den Akkumulationsplan entsprechend einer jeweiligen Länge der Polynome und einer vorgegebenen Wortbreite des partiellen Multiplizierers aus einer Vielzahl abgespeicherter Auswahl- und Akkumula- tionspläne auszuwählen.
16. Polynom-Multiplizierer nach einem der Ansprüche 9 bis 15, bei dem die Akkumulations-Steuereinheit und die Auswahl-Steuereinheit eine integrierte Multiplizier-Steuereinheit bilden.
17. Polynom-Multiplizierer nach einem der Ansprüche 9 bis 16, der in Form eines integrierten Schaltkreises ausgebildet ist.
18. Verschlüsselungseinheit zur Verschlüsselung von Daten unter Durchführung einer Polynom-Multiplikation, mit einem Dateneingang für unverschlüsselte Daten, einem mit dem Dateneingang verbundenen Polynom- Multiplizierer gemäß einem der Ansprüche 9 bis 17, und einem mit dem Po- lynom-Multiplizierer verbundenen Datenausgang zur Ausgabe der verschlüsselten Daten.
19. Verschlüsselungseinheit nach Anspruch 18, die zur Verschlüsselung der Daten mit Hilfe der Elliptischen Kurvenkryptographie ausgebildet ist.
20. Verschlüsselungseinheit nach einem der Ansprüche 18 oder 19, die in Form eines integrierten Schaltkreises oder in Form eines ausführbaren Computerprogramms implementiert ist.
21. Datenträger mit einem ausführbaren Programm, das ein Verfahren zur Verschlüsselung von Daten gemäß Anspruch 6 implementiert.
PCT/EP2006/060494 2005-03-04 2006-03-06 Verfahren und vorrichtung zum berechnen einer polynom-multiplikation, insbesondere für die elliptische kurven-kryptographie Ceased WO2006092448A2 (de)

Priority Applications (2)

Application Number Priority Date Filing Date Title
US11/885,827 US8477935B2 (en) 2005-03-04 2006-03-06 Method and apparatus for calculating a polynomial multiplication, in particular for elliptic curve cryptography
EP06708654A EP1859344A2 (de) 2005-03-04 2006-03-06 Verfahren und vorrichtung zum berechnen einer polynom-multiplikation, insbesondere für die elliptische kurven-kryptographie

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
EP05090052 2005-03-04
EP05090052.1 2005-03-04
DE102005028662.3 2005-06-15
DE102005028662.3A DE102005028662B4 (de) 2005-03-04 2005-06-15 Verfahren und Vorrichtung zum Berechnen einer Polynom-Multiplikation, insbesondere für die elliptische Kurven-Kryptographie

Publications (2)

Publication Number Publication Date
WO2006092448A2 true WO2006092448A2 (de) 2006-09-08
WO2006092448A3 WO2006092448A3 (de) 2007-03-29

Family

ID=36848239

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2006/060494 Ceased WO2006092448A2 (de) 2005-03-04 2006-03-06 Verfahren und vorrichtung zum berechnen einer polynom-multiplikation, insbesondere für die elliptische kurven-kryptographie

Country Status (4)

Country Link
US (1) US8477935B2 (de)
EP (1) EP1859344A2 (de)
DE (1) DE102005028662B4 (de)
WO (1) WO2006092448A2 (de)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7991162B2 (en) 2007-09-14 2011-08-02 University Of Ottawa Accelerating scalar multiplication on elliptic curve cryptosystems over prime fields

Families Citing this family (25)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2899702A1 (fr) * 2006-04-10 2007-10-12 France Telecom Procede et dispositif pour engendrer une suite pseudo-aleatoire
US8478809B2 (en) * 2007-12-15 2013-07-02 Intel Corporation Method and apparatus for multiplying polynomials with a prime number of terms
US8244909B1 (en) * 2009-06-18 2012-08-14 Google Inc. Method, apparatus and networking equipment for performing flow hashing using quasi cryptographic hash functions
US8385541B2 (en) * 2010-02-18 2013-02-26 King Fahd University Of Petroleum And Minerals Method of performing elliptic polynomial cryptography with elliptic polynomial hopping
US8351601B2 (en) * 2010-02-18 2013-01-08 King Fahd University Of Petroleum And Minerals Elliptic polynomial cryptography with secret key embedding
US8332651B2 (en) 2010-02-18 2012-12-11 King Fahd University Of Petroleum And Minerals Method of generating a password protocol using elliptic polynomial cryptography
US8331558B2 (en) * 2010-02-18 2012-12-11 King Fahd University Of Petroleum And Minerals Method of cipher block chaining using elliptic curve cryptography
US8189775B2 (en) * 2010-02-18 2012-05-29 King Fahd University Of Petroleum & Minerals Method of performing cipher block chaining using elliptic polynomial cryptography
IT1401937B1 (it) * 2010-09-16 2013-08-28 St Microelectronics Srl Metodo di generazione di una firma digitale
US8699701B2 (en) 2010-12-01 2014-04-15 King Fahd University Method of performing XZ-elliptic curve cryptography for use with network security protocols
US8509426B1 (en) 2010-12-01 2013-08-13 King Fahd University Of Petroleum And Minerals XZ-elliptic curve cryptography system and method
US8903882B2 (en) 2010-12-13 2014-12-02 International Business Machines Corporation Method and data processing unit for calculating at least one multiply-sum of two carry-less multiplications of two input operands, data processing program and computer program product
US9645794B2 (en) 2014-09-23 2017-05-09 Texas Instruments Incorporated Homogeneous atomic pattern for double, add, and subtract operations for digital authentication using elliptic curve cryptography
CN105068784B (zh) * 2015-07-16 2018-02-16 清华大学 实现基于蒙哥马利模乘的Tate对算法的电路
US10498532B2 (en) * 2016-10-01 2019-12-03 Intel Corporation Parallel computation techniques for accelerated cryptographic capabilities
US11206136B1 (en) * 2020-05-27 2021-12-21 Nxp B.V. Method for multiplying polynomials for a cryptographic operation
KR20220078155A (ko) * 2020-12-03 2022-06-10 삼성전자주식회사 암호 프로세서, 암호 프로세서의 동작 방법 및 이를 포함한 전자 장치
US11444767B1 (en) 2021-03-03 2022-09-13 Nxp B.V. Method for multiplying polynomials for a cryptographic operation
CN113485751B (zh) * 2021-06-30 2023-07-04 海光信息技术股份有限公司 执行伽罗瓦域乘法的方法、运算单元和电子装置
CN113504895B (zh) * 2021-07-13 2024-02-20 深圳市智芯华玺信息技术有限公司 椭圆曲线多标量点乘计算优化方法及优化装置
US11847938B2 (en) 2021-08-03 2023-12-19 Nxp B.V. Combining regular and symbolic NTTs using co-processors
WO2023055377A1 (en) * 2021-09-30 2023-04-06 Pqsecure Technologies, Llc An area efficient architecture for lattice based key encapsulation and digital signature generation
CN115062565B (zh) * 2022-06-22 2024-01-05 北京理工大学 一种低时延椭圆曲线点乘电路设计方法
CN115587274B (zh) * 2022-10-12 2025-08-05 南京大学 一种多项式乘法的加速方法及装置
CN117834113B (zh) * 2023-12-30 2024-09-17 北京海泰方圆科技股份有限公司 一种伪随机序列的确定方法及装置

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20040109561A1 (en) 2002-08-06 2004-06-10 The State Of Oregon Acting By And Through The State Board Of Higher Education On Behalf Of Lean multiplication of multi-precision numbers over GF(2m)

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB9707861D0 (en) * 1997-04-18 1997-06-04 Certicom Corp Arithmetic processor
US6490352B1 (en) * 1999-03-05 2002-12-03 Richard Schroeppel Cryptographic elliptic curve apparatus and method
US6721771B1 (en) * 2000-08-28 2004-04-13 Sun Microsystems, Inc. Method for efficient modular polynomial division in finite fields f(2{circumflex over ( )}m)
US6772184B2 (en) * 2000-08-28 2004-08-03 Sun Microsystems, Inc. Method for efficient modular division over prime integer fields
US7069287B2 (en) * 2000-09-19 2006-06-27 Worcester Polytechnic Institute Method for efficient computation of odd characteristic extension fields
US6766345B2 (en) * 2001-11-30 2004-07-20 Analog Devices, Inc. Galois field multiplier system
US7346159B2 (en) 2002-05-01 2008-03-18 Sun Microsystems, Inc. Generic modular multiplier using partial reduction
US7401109B2 (en) 2002-08-06 2008-07-15 The State Of Oregon Acting By And Through The State Board Of Higher Education On Behalf Of Oregon State University Multiplication of multi-precision numbers having a size of a power of two
US7724898B2 (en) * 2002-10-17 2010-05-25 Telefonaktiebolaget L M Ericsson (Publ) Cryptography using finite fields of odd characteristic on binary hardware
US7197527B2 (en) * 2002-10-17 2007-03-27 Telefonaktiebolaget Lm Ericsson (Publ) Efficient arithmetic in finite fields of odd characteristic on binary hardware
FR2853424B1 (fr) * 2003-04-04 2005-10-21 Atmel Corp Architecture de multiplicateurs polynomial et naturel combines
US8194855B2 (en) * 2003-06-30 2012-06-05 Oracle America, Inc. Method and apparatus for implementing processor instructions for accelerating public-key cryptography

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20040109561A1 (en) 2002-08-06 2004-06-10 The State Of Oregon Acting By And Through The State Board Of Higher Education On Behalf Of Lean multiplication of multi-precision numbers over GF(2m)

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
BAILEY, D. V.; PAAR, C.: "Efficient Arithmetic in Finite Field Extensions with Application in Elliptic Curve Cryptography", JOURNAL OF CRYPTOLOGY, vol. 14, no. 3, 2001, pages 153 - 176
See also references of EP1859344A2

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7991162B2 (en) 2007-09-14 2011-08-02 University Of Ottawa Accelerating scalar multiplication on elliptic curve cryptosystems over prime fields

Also Published As

Publication number Publication date
DE102005028662B4 (de) 2022-06-02
DE102005028662A1 (de) 2006-09-07
WO2006092448A3 (de) 2007-03-29
US8477935B2 (en) 2013-07-02
EP1859344A2 (de) 2007-11-28
US20090136022A1 (en) 2009-05-28

Similar Documents

Publication Publication Date Title
EP1859344A2 (de) Verfahren und vorrichtung zum berechnen einer polynom-multiplikation, insbesondere für die elliptische kurven-kryptographie
DE69828150T2 (de) Vom Rechenaufwand her effizientes modulares Multiplikationsverfahren und Gerät
EP1342154B1 (de) Kryptographieprozessor
DE60105788T2 (de) AES Verschlüsselungsschaltung
DE69329929T2 (de) Mikroelektronische Kompaktanlage zum Ausführen modulärer Multiplizierung und Potenzierung mit grossen Operanden
EP1342148B9 (de) Kryptographieprozessor
DE102020102453A1 (de) Integrierte Schaltung zum modularen Multiplizieren von zwei ganzen Zahlen für ein kryptographisches Verfahren und Verfahren zur kryptographischen Verarbeitung von Daten basierend auf modularer Multiplikation
DE112007001319T5 (de) Multiplizieren zweier Zahlen
WO2013060467A1 (de) Effiziente primzahlprüfung
DE10260655B3 (de) Vorrichtung und Verfahren zum Berechnen einer Multiplikation mit einer Verschiebung des Multiplikanden, insbesondere bei der kryptographischen Berechnung
DE60109805T2 (de) Verfahren und system zur benützung eines ungesicherten krypto-beschleunigers
DE10304451B3 (de) Modulare Exponentiation mit randomisiertem Exponenten
DE102015104421A1 (de) Verfahren zum Verwenden eines Tokens in der Kryptographie
EP1891512B1 (de) Bestimmung einer modularen inversen
EP1999571B1 (de) Verfahren und vorrichtung zur reduktion eines polynoms in einem binären finiten feld, insbesondere im rahmen einer kryptographischen anwendung
WO2003093969A2 (de) Berechnen eines ergebnisses einer modularen multiplikation
EP3215931B1 (de) Vorrichtung und verfahren zur multiplikation zur erschwerung von seitenkanalangriffen
EP1922837B1 (de) Verfahren zum sicheren ver- oder entschlüsseln einer nachricht
DE602004012096T2 (de) Verfahren und vorrichtung für eine hadwareimplementierung der schlüsselexpansionsfunktion mit wenig speicher
DE10219164B4 (de) Vorrichtung und Verfahren zum Berechnen eines ganzzahligen Quotienten
EP3504616B1 (de) Modul und verfahren zur abgesicherten berechnung von mathematischen operationen
EP1446711B1 (de) Schiebevorrichtung und verfahren zum verschieben
DE602004006126T2 (de) Verbesserte inversionsberechnungen
DE10303723B4 (de) Vorrichtung und Verfahren zum Berechnen von verschlüsselten Daten aus unverschlüsselten Daten oder von unverschlüsselten Daten aus verschlüsselten Daten
DE10201450B4 (de) Carry-Skip-Addierer für verschlüsselte Daten

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application
NENP Non-entry into the national phase

Ref country code: DE

NENP Non-entry into the national phase

Ref country code: RU

REEP Request for entry into the european phase

Ref document number: 2006708654

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2006708654

Country of ref document: EP

WWW Wipo information: withdrawn in national office

Ref document number: RU

WWP Wipo information: published in national office

Ref document number: 2006708654

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 11885827

Country of ref document: US