Classifications

• • H—ELECTRICITY
  • H03—ELECTRONIC CIRCUITRY
  • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
  • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
  • H03M7/02—Conversion to or from weighted codes, i.e. the weight given to a digit depending on the position of the digit within the block or code word
  • H03M7/12—Conversion to or from weighted codes, i.e. the weight given to a digit depending on the position of the digit within the block or code word having two radices, e.g. binary-coded-decimal code
• • 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/533—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even
  • G06F7/5332—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by skipping over strings of zeroes or ones, e.g. using the Booth Algorithm

Definitions

• the present invention relates to a method for obtaining a 'signed binary representation of a number from its binary representation.
• This representation has as particularly interesting characteristics, to be unique, hollow, and to present the smallest weight of ' Hamming.
• the Hamming weight expresses the number of non-zero digits in the representation considered.
• a modular exponentiation algorithm of the number ⁇ by the 'exponent ' r based on a left-to-right processing (ALR) of the exponent is as follows: -We apply as inputs the number ⁇ , and the signed binary representation (r ' m , r ' m - ⁇ , ..., r' 2 , r'i, r ' 0 ) of the exponent r.
• M l. -For i equal m a i equal 0:
• the right to left algorithm ARL therefore requires at least one additional register, for the variable S, than the left to right algorithm ALR. Furthermore, since S is variable, S "1 must be calculated each time the associated condition is fulfilled in the right to left algorithm. In the left to right algorithm, ⁇ being determined (fixed), its inverse ⁇ " 1 can be calculated only once and stored. In the invention, it has been sought to combine the advantages of left-to-right processing both in the process of converting an operand and in the arithmetic processing using this operand. Thus, in the invention, we looked for a signed binary representation equivalent to the Reitwiesner representation, that is to say a representation which has the same Hamming weight for the same length m (number of digits in the representation).
• the subject of the invention is therefore a method of converting a binary representation of a number into a signed binary representation comprising an optimum number, that is to say maximum, of zero (minimum Hamming weight), ' and in which bits are processed from left to right.
• the invention also relates to a conversion device allowing the obtaining of a corresponding signed binary representation.
• the invention therefore relates to a process for obtaining a signed binary representation on m + 1 digits (r ' m , ..., r' 0 ) of a number from its binary representation on m bits (r m _ ⁇ , ..., r 0 ).
• this method consists: in adding in the binary representation of the number r to convert a bit of rank m, a bit of rank -1 and a bit of rank -2 and to initialize said bits to the value 0,
• the conversion loop comprising the following operations: -Apply as inputs of first calculation means the bit of rank i of the calculation variable b, and the bits of ranks i-1 and i-2 of the binary representation of the number r to be converted, said first means providing output the bit of rank i-1 of the calculation variable, by performing an arithmetic operation.
• calculation means performing an arithmetic operation equivalent to the multiplication by minus two of the bit of rank i of the calculation variable b, and the arithmetic sum of the previous result with, the other two bits applied as input, to output the digit of rank i of the signed binary representation.
• FIG. 1 represents an integrated circuit comprising such a device conversion and a device for arithmetic calculation of a modular exponentiation
• FIG. 2 represents a block diagram of a conversion device according to the invention, -la.
• FIG. 3 represents a correspondence table usable for carrying out a conversion according to the method of the invention
• FIG. 4 represents an exemplary embodiment of a conversion device using such a table
• FIG. 5 represents another exemplary embodiment of a conversion device according to the invention, using Boolean operators.
• FIG. 1 there is shown an integrated circuit of the microprocessor type ⁇ P and comprising a memory MEM and a generator of random number GEN.
• This integrated circuit further comprises a device 1 for calculating the exponentiation of a number ⁇ by an exponent r.
• the number ⁇ is a fixed number contained in memory MEM and the exponent r is a number supplied in binary (r m - ⁇ , ... ', r 0 ) by the random number generator.
• a device 2 for converting to signed binary is provided in the integrated circuit, for converting the number r applied as an exponent in the device 1 for calculation.
• the signed binary representation (r ' m , ..., r' 0 ) according to the invention, applied at the input of the calculation device 1, is obtained at the output of this conversion device.
• This signed binary representation is such that it has an optimum Hamming weight, like the so-called Reitwiesner representation.
• the computing device 1 shown in FIG. 1 makes it possible to apply the modular modular exponentiation algorithm left to right ALR previously described.
• the calculation device comprises an accumulator 10 for the intermediate results and the final result of the exponentiation and three registers: a register 11 for the exponent, a register 12 for the number ⁇ , and a register 13 for its inverse ⁇ "1.
• register 11 for the exponent is a double register: because each digit" 0 ",” 1 "" -1 "in signed binary is usually coded on at least two bits.
• this code includes two bits: one bit. for the sign and one bit for the absolute value of the digit.
• -X is 0.
• the computing device 1 still includes two multiplexers 20 and 21 , a multiplier 22.
• a control circuit 23 and a switch 24 supply the control signals of the multiplexers.
• the control circuit 23 receives the absolute value bit r'i L of the digit r'i of rank i from the exponent r (and a sequencing signal Ck). If this bit is equal to "l”, it activates (coml) the switch 24, in order to apply the bit r 'i H of sign of the digit r'i of the exponent at the command input of the multiplexer 20. Depending on whether the bit r' i H is "0" or "1", the multiplexer 20 transmits
• This second multiplexer 21 receives on another input, the content M of the accumulator 10. It is controlled by an output Com2 of the control circuit 23, to apply to an input of the multiplier 22, ie the output of the first multiplexer 20, c 'is to say ⁇ or ⁇ "1 , ie the content M of the accumulator. The result at the output of the multiplier is loaded into the accumulator.
• the control circuit 23 is such that in each iteration of the loop for calculating a result bit of the modular exponentiation, it first controls the switching of the input M at the output of the multiplexer 21, to calculate MM in the multiplier, then, if the absolute value r 'i L of the digit r'i of the exponent is 1, to control the switching of the output of the first multiplexer 20 ( ⁇ or ⁇ ⁇ l) to the output of the multiplexer 21.
• the calculation device thus allows the calculation of the exponentiation of ⁇ by r, by a left-to-right processing.
• the homogeneity of the processing from left to right of the bits in the conversion device according to the invention and of the figures in the calculation device therefore makes it possible to simplify the hardware production of these devices, in particular by saving registers and improving the performance in terms of calculation speed.
• FIG. 2 represents a block diagram of a conversion device 2 illustrating a conversion method according to the invention.
• the first and second computing means can perform the indicated arithmetic operation, or an equivalent arithmetic operation.
• the outputs of rank m, m-1 and m-2 of the register RI are thus respectively applied to the input e'3 of the second computing means 31, and to the inputs e2 and e3 of the first computing means 30.
• the register RI is shifted by one position to the left, so that the outputs of rank m, m-1 and m-2 provide at each iteration the bits of rank i, i-1 and i-2 correspondents.
• the conversion device includes another register R2 for the calculation variable b, also of the left shift type.
• this register comprises for each iteration, the bit bi and the bit bi_ ⁇ .
• the first calculation means are activated first, to load into the register R2 the new value bi-i, to be used in the current iteration, in the second calculation means.
• the register R2 is shifted by one position to the left, for the next iteration.
• This correspondence table represented in FIG. 3 makes it possible to simplify the conversion according to the invention. Indeed, it gives directly the result in output, in. function of inputs.
• the register R2 in FIG. 2 can then be produced in the form of a simple latch,. To contain, for iteration i in progress, the bit bi.
• the correspondence table in Figure 3 is programmed in this memory so that by applying to the address bits A0, Al, A2, A3 of this memory, the bits bi_, ri, ri_ ! and ri_ 2 / it provides as output ' the bit bi- ! and the corresponding number r'i.
• the bit bi_ is loaded into the register R2. This bit becomes the bi bit for the next iteration of the loop.
• the digit r'i is loaded into a register R3, which in practice comprises a first register R3H, to contain the sign bit r'i H of each digit of the signed binary representation and a second register R3L, to contain its absolute value r'i L.
• a register R3H Another embodiment of a conversion device according to the invention is shown in FIG. 5.
• the conversion device is based on Boolean operators.
• the register R2 can be a simple latch reloaded by the bit bi_ ⁇ determined in the current iteration.
• Boolean operators are the result of logical manipulation and minimization of the algorithm corresponding to the conversion process and the correspondence table according to the invention.
• the conversion device comprises, in addition to the registers RI and R2:
• a first gate ' PI of type ET comprising an inverting input to receive the bit ri, and a non-inverting input to receive the bit bi, - - A second gate P2 • of type ET with the inverse inputs of the first;
• -A third ET type P3 gate including an inverting input to receive the bit ri-i, another - inverting input to receive the bit ri- 2 and a non-inverting input to receive the bit bi, - -A fourth gate P4 AND type, receiving the reverse inputs from the third door;
• -A fifth gate P5 type ET comprising a non-inverting input to receive the bit - r ⁇ - ⁇ , and another non-inverting input to receive the bit bi
• a sixth door P6 of type ET comprising a non-inverting input for receiving the bit ri- 2 , and another non-inverting input for receiving the bit bi
• -A seventh OR type P7 gate receiving the inputs of the first, second, third and fourth doors as inputs.
• the registers RI, R2 and R3 which respectively contain the binary representation of r, the calculation variable and the result of the conversion into signed binary are controlled as in FIG. 4.
• the invention which has just been described can be used in many applications, and in particular those using cryptographic methods. It is applicable 'to provide the signed binary representation of an operand used for any arithmetic operation, processing preferably

Landscapes

• Engineering & Computer Science (AREA)
• Theoretical Computer Science (AREA)
• Complex Calculations (AREA)
• Executing Machine-Instructions (AREA)

Applications Claiming Priority (3)

Publications (1)

Family

ID=8851988

Family Applications (1)

Country Status (6)

Families Citing this family (4)

Family Cites Families (3)

• 2000
  • 2000-06-30 FR FR0008547A patent/FR2811168B1/fr not_active Expired - Fee Related
• 2001
  • 2001-06-20 WO PCT/FR2001/001944 patent/WO2002001727A1/fr not_active Ceased
  • 2001-06-20 US US10/312,530 patent/US6903663B2/en not_active Expired - Fee Related
  • 2001-06-20 AU AU2001269217A patent/AU2001269217A1/en not_active Abandoned
  • 2001-06-20 EP EP01947558A patent/EP1299953A1/de not_active Withdrawn
  • 2001-06-20 CN CN01812126.8A patent/CN1258883C/zh not_active Expired - Fee Related

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events