Patent Publication Number: US-6903663-B2

Title: Method for converting the binary representation of a number in a signed binary representation

Description:
This disclosure is based upon French Application No. 00/08547, filed on Jun. 30, 2000 and International Application No. PCT/FR01/01944, filed Jun. 20, 2001, the contents of which are incorporated herein by reference. 

   BACKGROUND OF THE INVENTION 
   The present invention concerns a method of obtaining a signed binary representation of a number from its binary representation. 
   Fast arithmetic calculation techniques have for a long time been using the signed binary representation, since it makes it possible to calculate additions, multiplications or divisions very effectively. 
   Many integrated circuits comprise a device for converting a number into signed binary code from its binary representation and arithmetic calculation devices for performing operations with this operand in signed binary representation. In general, a reverse conversion device is provided, for supplying the result in the binary form. 
   In signed binary representation, a number is expressed in m digits of values “0”, “1” or “−1”. Several signed binary representations of the same number exist. For example, the number 5 can be written as (1 1 −1), that is to say 1×2 2 +1×2 1 −1×2 0 . However, it can also be written (1 0 1). 
   Amongst the possible signed binary representations, there exists a remarkable one, known as the Reitwiesner representation. This representation has the particularly interesting characteristics of being unique and hollow and having the smallest Hamming weight. 
   If the binary representation of the number r is denoted r=(r m−1 , . . . , r 0 ), the Reitwiesner signed binary representation, which is denoted r=(r′ m , r m−1 , . . . , r′ 2 , r′ 1 , r′ 0 ), comprises one additional digit. 
   To state that this representation is hollow means that it satisfies the fact that the multiplication of two adjacent digits is zero, which is written:
 
 r′   i·   r′   i−1 =0 , ∀iε{ 0 , . . . m}.  
 
   The Hamming weight for its part expresses the number of non-zero digits in the representation in question. Having a minimum Hamming weight therefore means an optimum maximum number of digits at “0”. However, the fewer “1” or “−1” digits in the representation, the fewer calculations there are actually to carry out, and hence an improvement in terms of calculation speed. This is therefore a particularly interesting property of the Reitwiesner representation in terms of fast arithmetic calculation. 
   The algorithm which makes it possible to obtain this remarkable signed binary representation from the binary representation (r m−1 , . . . , r 0 ) of a number r, can be described as follows:
         A calculation variable c is used, in binary.   The bit c 0  of rank 0 of this variable c is initialised to “0”.   There are added, to the binary representation (r m−1 , . . . , r 0 ) of the number r, a bit of rank m+1 and a bit of rank m, both initialised to “0”: r m−1 =0; r m =0   Then, for i equal to 0 up to i equal to m, the following are calculated:
 
 c   i+1 =└( c   i   +r   i   +r   i−1 )/2┘
 
 r′   i   =c   i   +r   i −2 c   i−1  
   where └t┘ means the default value, that is to say the integer value immediately lower than the number t. In practice, as the arithmetic sum of the bits c i +r i +r i+1  is coded in a maximum of two bits in binary, the bit c i+1  is obtained by shifting this sum by one position to the right.       

   It can be seen that, in this Reitwiesner algorithm, the bits r i  of the binary representation of the number r are processed from right to left, in order to obtain each of the digits r′ i  of the signed binary representation, from i equals 0 up to i equals m. 
   Various works were able to show that there was no algorithm in which the bits would be processed from left to right and by means of which the Reitwiesner signed binary representation would be obtained. 
   However, in many applications, the fast arithmetic calculation algorithms applied to an operand r process the digits r′ i  in the signed binary representation of this operand from left to right. These algorithms prove in fact, in some cases, to be more effective both with regard to calculation time and on the hardware level (fewer registers necessary). 
   If the example is taken of calculating the exponentiation, an algorithm for modular exponentiation of a number α by an exponent r based on the right to left processing (ARL) can be as follows:
         There are applied, as inputs of the algorithm, a number α, and the signed binary representation (r′ m , r′ m−1 , . . . , r′ 2 , r′ 1 , r′ 0 ).   The accumulator which contains the result M is initialised to 1, that is to say M=1.   A temporary register is initialised, which contains a calculation variable S with the number α to which the exponentiation is applied.   The following loop is implemented for i equals 0 up to i equals m−1:
           if r′ i =1, the content M of the accumulator is multiplied by the variable S, and the result is loaded into the accumulator, which is written: M=M.S   if r′ i =−1, the content M of the accumulator is multiplied by the inverse of the variable S, and the result is loaded into the accumulator, which is written M=M.S −1 .   
               

   An algorithm for the modular exponentiation of the number a by the exponent r based on a left to right processing (ALR) of the exponent is as follows:
         There are applied as inputs the number α, and the signed binary representation (r′ m , r′ m−1 , . . . , r′ 2 , r′ 1 , r′ 0 ) of the exponent r.   The content M of the accumulator is initialised to 1: M=1.   For i equals m to i equals 0:
           the multiplication of the content of the accumulator by itself is performed and the accumulator is loaded with the result, which is written: M=M 2 , and then   if r′ i =1, the content of the accumulator is multiplied by α and the result is loaded into the accumulator: M=M.α, or   if r′ i =−1, the content of the accumulator is multiplied by the inverse of α and the result is loaded into the accumulator: M=M.α −1 .   
               

   The right to left algorithm ARL therefore requires at least one additional register, for the variable S, than the left to right algorithm ALR. In addition, S being variable, it is necessary to calculate S −1  each time the associated condition is achieved 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 method of converting an operand and in the arithmetic processing using this operand. 
   Thus, in the invention, a signed binary representation equivalent to the Reitwiesner representation has been sought, that is to say a representation which has the same Hamming weight for the same length m (number of digits in the representation). 
   SUMMARY OF THE INVENTION 
   The object 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 a maximum number, of zeros (minimum Hamming weight), and in which the bits are processed from left to right. 
   Another object of the invention is a conversion device for obtaining a corresponding signed binary representation. 
   As characterised, the invention therefore concerns a method of obtaining a signed binary representation in m+1 digits (r′ m , . . . , r′ 0 ) of a number from its binary representation in m bits (r m−1 , . . . , r 0 ). According to this invention, this method consists of:
         Adding in the binary representation of the number r to be converted a bit of rank m, a bit of rank −1 and a bit of rank −2 and initialising the said bits to the value 0,   Taking at least one calculation variable and initialising to 0 a bit of rank m of this variable, and   Performing m+1 iterations of a conversion loop, for i equals m up to i equals 0, the conversion loop comprising the following operations:   Applying 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, the said first means supplying as an output the bit of rank i−1 of the calculation variable, performing an arithmetic operation equivalent to the default value of the arithmetic sum divided by two of the bits applied as inputs,   Applying as inputs of second calculation means the bits of rank i and i−1 of the calculation variable b, and the bit of rank i of the binary representation of the number to be converted r, the said 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 preceding result with the other two bits applied as an input, in order to supply as an output the digit of rank i of the signed binary representation.       

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Other characteristics arid advantages of the invention are detailed in the following description, given by way of indication and so as not to limit the invention and with reference to the accompanying drawings, in which: 
       FIG. 1  depicts an integrated circuit comprising such a conversion device and a device for arithmetic calculation of a modular exponentiation; 
       FIG. 2  depicts a block diagram of a conversion device according to the invention; 
       FIG. 3  depicts a look-up table which can be used for carrying out a conversion according to the method of the invention; 
       FIG. 4  depicts an example embodiment of a conversion device using such a table; and 
       FIG. 5  depicts another example embodiment of a conversion device according to the invention, using Boolean operators. 
   

   DETAILED DESCRIPTION 
     FIG. 1  depicts an integrated circuit of the microprocessor μP type comprising a memory MEM and a random number generator GEN. 
   This integrated circuit also comprises a device  1  for the exponentiation calculation of a number α by an exponent r. In the example, the number α is a fixed number contained in memory MEM and the exponent r is a number supplied in binary (r m−1 , . . . , r 0 ) by the random number generator. 
   A device  2  for conversion into signed binary is provided in the integrated circuit, for converting the number r applied as an exponent in the calculation device  1 . 
   There is obtained as an output from this conversion device the signed binary representation (r′ m , . . . , r′ 0 ) according to the invention, applied as an input to the calculation device  1 . This signed binary representation is such that it has an optimum Hamming weight, like the so-called Reitwiesner representation. 
   The calculation device  1  depicted in  FIG. 1  makes it possible to apply the left to right modular exponentiation algorithm ALR previously described. In this example, 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 . In reality, the register  11  for the exponent is a double register: since each digit “0”, “1”, “−1” in signed binary is normally coded in at least two bits. 
   In one example, this code comprises two bits: one bit for the sign and one bit for the absolute value of the digit. In this example, this then gives: “0”=(X, 0); “1”=(0, 1); “−1”=(1, 1) where X means that the bit can be equal to either to 0 or 1. In the example in the FIGURE, X is equal to 0. 
   The calculation device  1  also comprises two multiplexers  20  and  21 , and a multiplier  22 . A control circuit  23  and a switch  24  supply the signals controlling the multiplexers. 
   The control circuit  23  receives the bit of absolute value r′ iL  of the digit r′i of rank i of the exponent r (and a sequencing signal Ck). If this bit is equal to “1”, it activates (com 1 ) the switch  24 , in order to apply the sign bit r′ iH  of the digit r′ i  of the exponent as a control input for the multiplexer  20 . Depending on whether the bit r′ iH  is equal to “0” or “1”, the multiplexer  20  then transmits α or α −1  as an input for the second multiplexer  21 . 
   This second multiplexer  21  receives at another input the content M of the accumulator  10 . It is controlled by an output Com 2  of the control circuit  23 , in order to apply, to an input of the multiplier  22 , either the output of the first multiplexer  20 , that is to say α or α −1 , or the content M of the accumulator. 
   The result of the output of the multiplexer is loaded into the accumulator. 
   The control circuit  23  is such that, in each iteration of the calculation loop for a result bit of the modular exponentiation, it first of all demands the switching of the input M output from the multiplexer  21 , in order to calculate M.M in the multiplexer, and then, if the absolute value r′ iL  of the digit r′ i  of the exponent is equal to 1, in order to demand the switching of the output of the first multiplexer  20  (α or α −1 ) output from the multiplexer  21 . 
   The calculation device thus allows the calculation of the exponentiation of α by r, by means of a left to right processing. 
   The association of a left to right conversion device and an arithmetic processing device processing the result of the conversion from left to right, makes it possible to perform all these processing steps in real time. This is because, as soon as the digit r′i is calculated and available at the output of the conversion device  2 , it is immediately used in the arithmetic processing device  1 . 
   With a conversion device processing the bits from right to left (Reitwiesner), it is possible to use the signed binary representation only once it is fully calculated, since the last digit converted r′ m  is the first used in the arithmetic processing device processing the digits from left to right. 
   The homogeneity of the left to right processings of the bits in the conversion device according to the invention and of the digits in the calculation devise therefore makes it possible to simplify the hardware implementation of these devices, by saving in particular on registers and improving the performance in terms of calculation speed. 
   The conversion device is not applied only to a device for calculating an exponentiation. It applies equally well to the calculation of the multiplication of a number α by a number r in signed binary representation, or to the scalar multiplication of a point by the number r in signed binary representation. In the latter case, a particularly interesting application of the-invention concerns the case where the point is taken on an elliptic curve. 
     FIG. 2  depicts a block diagram of a conversion device  2  illustrating a conversion method according to the invention. 
   The method of obtaining a signed binary representation according to the invention, using left to right processing, is as follows:
         There are added, in a register R 1  containing the binary representation of the number r, a bit r m  of rank m, a bit r −1  of rank −1 and a bit r −2  of rank −2, and these three bits are initialised to the value 0.   A calculation variable b is taken from a register R 2 , and the bit b m  of rank m of this variable is initialised to 0.   m+1 iterations of a conversion loop are performed, from i equals m up to i equals 0, the conversion loop comprising the following operations:
           Application as inputs e 1 , e 2 , e 3  of first calculation means  30  of the bit b i  and the bits r i−1 , r i−2 , in order to calculate the arithmetic sum divided by two of these bits and to supply as an output bit b i−1  the bit corresponding to the default value of the result, which is written:
 
 b   i−1 =└( b   i+   r   i−1+   r   i−2 )/2┘. 
   Application as inputs e 1 ′, e 2 ′, e 3 ′ of second calculation means  31 , of the bits b i , b i−1 , of the calculation variable b, and of the bit r i  of rank i of the binary representation of the number r, in order to calculate the arithmetic sum of minus twice the bit b i  with the other two bits applied as inputs, and to supply as an output the digit r′ i  of the signed binary representation, which is written: r′ i =−2.b i +b i−1 +r i .   
               

   The first and second calculation means can perform the arithmetic operation indicated, or an equivalent arithmetic operation. 
   These calculations are performed by means of a variable b. However, it is possible to implement the invention by using several variables. 
   As depicted in  FIG. 2 , a conversion device for implementing this method comprises the register R 1  for containing the signed binary representation of the number r, including the bits r m , r −1 , r −2  added to this representation. This register is of the shift to the left type, corresponding to the direction of processing of the bits from left (i=m) to right (i=0). The outputs of rank m, m−1 and m−2 of the register R 1  are thus respectively applied to the input e′3 of the second calculation means  31 , and to the inputs e 2  and e 3  of the first calculation means  30 . At the end of each iteration, the register R 1  is shifted by one position to the left, so that the outputs of rank m, m−1 and m−2 supply at each iteration the corresponding bits of rank i, i−1 and i−2. 
   The conversion device comprises another register R 2  for the calculation variable b, also of the shift to the left type. In the example, this register comprises for each iteration the bit b i  and the bit b i−1 . As the bit b i−1  is established from the bit b i , the first calculation means are activated first, in order to load into the register R 2  the new value b i−1 , to be used in the current iteration, in the second calculation means. 
   At the end of the iteration, the register R 2  is shifted by one position to the left, for the following iteration. 
   In the invention, it has been possible to establish a look-up table corresponding to the conversion method which has just been disclosed. This look-up table depicted in  FIG. 3  simplifies the conversion according to the invention. This is because it directly gives the result as an output, according to the inputs. In addition the register R 2  in  FIG. 2  can then be produced in the form of a simple latch, in order to contain, for the current iteration i, the bit b i . 
   In order to obtain this table, the value of the bit b i−1  was determined for each possible triplet (e 1 , e 2 , e 3 )=(b i , r i−1 , r i−2 ), and the value of the digit r′ i  for each possible triplet as inputs (e 1 ′, e 2 ′, e 3 ′)=(b i , r i , b i−1 ) from the conversion algorithm according to the invention disclosed previously in relation to FIG.  2 . 
   It has thus been possible to show that it was possible to determine the value of the bit bi, and of the digit r i , from the quadruplet (b i , r i , r i−1  and r i−2 ), for each of the possible values of the latter. 
   With this conversion table, only the bit b i  of the variable b is used as an input for the current iteration. The bit b i−1  supplied as an output serves for the following iteration. Thus, with such a look-up table, the register R 2  can be reduced to a simple latch, the new value of which is loaded at the end of each iteration, by the bit b i−1  supplied as an output by the table. This new value becomes that of the bit b i  in the following iteration. 
   An example of a practical embodiment of a conversion device according to the invention using such a conversion table is depicted in FIG.  4 . It comprises a content addressable memory, denoted CAM. The look-up table in  FIG. 3  is programmed in this memory so that, by applying the bits b i. , r i , r i−1  and r i−2  to the address bits A 0 , A 1 , A 2 , A 3  of this memory, it supplies as an output the corresponding bit b i−1  and digit r′ i . 
   At the end of each iteration, the bit b i−1  is loaded into the register R 2 . This bit becomes the bit b i  for the following iteration of the loop. 
   The digit r′ i  is loaded into a register R 3 , which comprises in practice a first register R 3 H, for containing the signed bit r′ iH  of each digit of the signed binary representation and a second register R 3 L for containing its absolute value r′ iL . 
   Another example embodiment of a conversion device according to the invention is shown in FIG.  5 . In this example, the conversion device is based on Boolean operators. Here also, the register R 2  can be a simple latch reloaded by the bit bi, determined in the current iterations. 
   The definition of the Boolean operators results from work consisting of logic manipulation and minimalisation of the algorithm corresponding to the conversion method and to the look-up table according to the invention. 
   In the invention, it has been possible to define these operators from the bits b i. , r i , r i−1  and r i−2 , in order to obtain directly as an output the bit b i−1  and the digit r′ i . 
   By using the coding in two bits representing the sign and the absolute value, it has been possible to define the following Boolean operations:
 
 b   i−1   =/b   i·   r   i−1·   r   i−2+   b   i·   r   i−1+   b   i·   r   i−2 ; 
 
r′ iH =b i ; 
 
 r′   IL   =/b   i·   r   r−1·   r   i−2+   /b   i·   r   i   +.b   i−   /r   i+   b   i·   /r   i−1·   r   i−2 . 
 
   It should be noted that, when the digit r′ i  is zero, that is to say if r′ iL =0, the signed bit r′ iH  can be taken to be equal to either 0 or 1. Making r′ iH =b i  thus covers all cases, if any value 0 or 1 is accepted for the signed bit in the case where the digit is equal to 0. However, provision can be made for this signed bit to be fixed, for example fixed at 0, when the digit equals 0, as in the example given in FIG.  1 . 
   An example of a corresponding embodiment of a conversion device comprising Boolean operators is depicted in FIG.  5 . In this example, the conversion device comprises, in addition to the registers R 1  and R 2 :
         A first gate P 1  of the AND type, comprising an inverting input for receiving the bit r i , and a non-inverting input for receiving the bit b i ;   A second gate P 2  of the AND type with the opposite inputs to the first;   A third gate P 3  of the AND type, comprising an inverting input for receiving the bit r i−1 , another inverting input for receiving the bit r i−2  and a non-inverting input for receiving the bit b i ;   A fourth gate P 4  of the AND type, receiving the opposite inputs to the third gate;   A fifth gate P 5  of the AND type comprising a non-inverting input for receiving the bit r i−1 , and another non-inverting input for receiving the bit b i ;   A sixth gate P 6  of the AND type, comprising a non-inverting input for receiving the bit r i−2 , and another non-inverting input for receiving the bit b i ;   A seventh gate P 7  of the OR type, receiving as inputs the outputs of the first, second, third and fourth gates, and supplying as an output the absolute value r′ iL  (0 or 1) of the digit r′ i  of rank i of the signed binary representation, the signed bit r′ iH  being supplied by the bit b i ; and   An eighth gate P 8  of the OR type, receiving as inputs the outputs of the fourth, fifth and sixth gates, in order to supply the bit b i−1  as an output.       

   The registers R 1 , R 2  and R 3 , which contain respectively 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 for supplying the signed binary representation of an operand used in any arithmetic processing, preferably processing the bits from left to right in order to extract therefrom the greatest benefit in terms of simplicity of design and processing speed. It should be noted that an example of application of the invention to the exponentiation of a fixed number by a variable number r (random) has been given, which uses the techniques of calculation by squares and multiplications (square and multiply). The invention applies equally well to the exponentiation of a random number by a fixed number r, which uses the techniques of additive chains. More generally, the invention applies to arithmetic calculation devices for the multiplication of a number a by the number r in signed binary representation, or to the scalar multiplication of a point by the number r. In the latter case, a particularly interesting application of the invention concerns the case where the point is taken on an elliptic curve. The list of possible applications is not exhaustive. 
   In all these applications the number of operations is reduced, as with the Reitwiesner representation, because of the minimum Hamming weight, with the additional advantages related to the left to right processing (hardware simplicity, reduction in the number of registers, processing in real time).