EP1859344A2 - Procede et dispositif de calcul d'une multiplication polynome, en particulier pour cryptographie curviligne elliptique - Google Patents

Procede et dispositif de calcul d'une multiplication polynome, en particulier pour cryptographie curviligne elliptique

Info

Publication number
EP1859344A2
EP1859344A2 EP06708654A EP06708654A EP1859344A2 EP 1859344 A2 EP1859344 A2 EP 1859344A2 EP 06708654 A EP06708654 A EP 06708654A EP 06708654 A EP06708654 A EP 06708654A EP 1859344 A2 EP1859344 A2 EP 1859344A2
Authority
EP
European Patent Office
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.)
Withdrawn
Application number
EP06708654A
Other languages
German (de)
English (en)
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 EP06708654A priority Critical patent/EP1859344A2/fr
Publication of EP1859344A2 publication Critical patent/EP1859344A2/fr
Withdrawn 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

La sécurité des canaux de communication est requise en particulier dans des réseaux sans fil. L'utilisation de mécanismes de cryptage sous forme de logiciel est limitée par les capacités de calcul et d'énergie requises des terminaux mobiles. Lors de l'utilisation de solutions matériel pour des opérations cryptographiques, des frais importants entrent en ligne de compte. L'invention fournit des moyens solutionnant en même temps tous ces points. Elle concerne un accélérateur matériel pour la multiplication polynôme dans des champs de Galois étendus (GF), le procédé Karatsuba connu en soi étant, conformément à l'invention, utilisé de manière itérative. Lors de l'utilisation de l'invention, l'encombrement peut être réduit, par exemple de 6,2 mm<SUP>2</SUP> à 2,1 mm<SUP>2</SUP>. La solution selon l'invention permet en outre de réduire la consommation d'énergie, par rapport aux solutions connues de la technique, de l'ordre de 30 %.
EP06708654A 2005-03-04 2006-03-06 Procede et dispositif de calcul d'une multiplication polynome, en particulier pour cryptographie curviligne elliptique Withdrawn EP1859344A2 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
EP06708654A EP1859344A2 (fr) 2005-03-04 2006-03-06 Procede et dispositif de calcul d'une multiplication polynome, en particulier pour cryptographie curviligne elliptique

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
EP05090052 2005-03-04
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
PCT/EP2006/060494 WO2006092448A2 (fr) 2005-03-04 2006-03-06 Procede et dispositif de calcul d'une multiplication polynome, en particulier pour cryptographie curviligne elliptique
EP06708654A EP1859344A2 (fr) 2005-03-04 2006-03-06 Procede et dispositif de calcul d'une multiplication polynome, en particulier pour cryptographie curviligne elliptique

Publications (1)

Publication Number Publication Date
EP1859344A2 true EP1859344A2 (fr) 2007-11-28

Family

ID=36848239

Family Applications (1)

Application Number Title Priority Date Filing Date
EP06708654A Withdrawn EP1859344A2 (fr) 2005-03-04 2006-03-06 Procede et dispositif de calcul d'une multiplication polynome, en particulier pour cryptographie curviligne elliptique

Country Status (4)

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

Families Citing this family (26)

* 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
US7991162B2 (en) 2007-09-14 2011-08-02 University Of Ottawa Accelerating scalar multiplication on elliptic curve cryptosystems over prime fields
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 (fr) * 2021-09-30 2023-04-06 Pqsecure Technologies, Llc Architecture à efficacité surfacique pour une encapsulation de clé basée sur un réseau et une génération de signature numérique
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
WO2003048918A1 (fr) * 2001-11-30 2003-06-12 Analog Devices Inc. Systeme multiplicateur de champs de galois

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
US7346159B2 (en) 2002-05-01 2008-03-18 Sun Microsystems, Inc. Generic modular multiplier using partial reduction
US7447310B2 (en) 2002-08-06 2008-11-04 The State Of Oregon Acting By And Through The State Board Of Higher Education On Behalf Of Oregon State University Lean multiplication of multi-precision numbers over GF(2m)
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
WO2003048918A1 (fr) * 2001-11-30 2003-06-12 Analog Devices Inc. Systeme multiplicateur de champs de galois

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
ROLF KRAEMER ET AL: "EFFICIENT IMPLEMENTATIONS OF CRYPTOGRAPHIC ROUTINES: A REVIEW AND PERFORMANCE ANALYSIS OF VARIOUS APPROAHCES", COMPUTER SCIENCE REPORTS, BRANDENBURGISCHE UNIVERSITY OF TECHNOLOGY COTTBUS, COTTBUS, DE, 1 January 2004 (2004-01-01), pages 1 - 2, XP001248873 *
See also references of WO2006092448A2 *

Also Published As

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

Similar Documents

Publication Publication Date Title
EP1859344A2 (fr) Procede et dispositif de calcul d&#39;une multiplication polynome, en particulier pour cryptographie curviligne elliptique
DE69828150T2 (de) Vom Rechenaufwand her effizientes modulares Multiplikationsverfahren und Gerät
EP1342154B1 (fr) Processeur cryptographique
DE60105788T2 (de) AES Verschlüsselungsschaltung
DE69329929T2 (de) Mikroelektronische Kompaktanlage zum Ausführen modulärer Multiplizierung und Potenzierung mit grossen Operanden
EP1342148B9 (fr) Processeur cryptographique
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 (fr) Vérification efficace de nombre premier
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 (fr) Determination d&#39;une inverse modulaire
EP1999571B1 (fr) Procédé et dispositif de réduction d&#39;un polynôme dans un champ fini binaire, en particulier dans le cadre d&#39;une application cryptographique
WO2003093969A2 (fr) Dispositif et procede de calcul d&#39;un resultat d&#39;une multiplication modulaire
EP3215931B1 (fr) Dispositif et procédé de multiplication pour rendre les attaques de canaux latéraux plus difficiles
EP1922837B1 (fr) Procede de codage ou decodage securise d&#39;un message
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 (fr) Module et procédé de calcul sécurisé d&#39;opérations mathématiques
EP1446711B1 (fr) Dispositif de decalage et procede de decalage
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
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20071004

AK Designated contracting states

Kind code of ref document: A2

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IS IT LI LT LU LV MC NL PL PT RO SE SI SK TR

RIN1 Information on inventor provided before grant (corrected)

Inventor name: PETER, STEFFEN

Inventor name: LANGENDOERFER, PETER

Inventor name: DYKA, ZOYA

DAX Request for extension of the european patent (deleted)
17Q First examination report despatched

Effective date: 20090622

RAP1 Party data changed (applicant data changed or rights of an application transferred)

Owner name: IHP GMBH-INNOVATIONS FOR HIGH PERFORMANCE M

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 20160301