Abstracts

 
 
 
 
 
 
 
 
 
 
 
 
  
 

  Redundant Number Systems for Reconfigurable Arithmetic Units

  Arnaud Tisserand
 
Representation of numbers plays a key role in arithmetic units. They widely impact the speed, silicon area and power consumption of computation units. Choosing a specific representation is not a simple task. There is a complex trade-off between:
  • the number system(s) used to represent the data (width, number coding...);
  • the algorithm used to compute the mathematical operations (evaluation methods, speed/area trade-offs, fused operations...);
  • the characteristics of data (signal activity, space/time correlations...);
  • and some circuit constraints (specific cells in the standard library, logic style...).
Redundant number systems have been introduced to speed-up some computations. In a redundant number system, some numbers have several distinct representations. This property is used in some number systems to allow constant time addition (the addition time does not depend on the number of digits). Constant time addition is useful for the addition of multiple values (n*n-bit multiplication is equivalent to n additions of n-bit numbers). The conversion into a non-redundant number system is done using a standard adder. One drawback of a redundant number system is the fact that comparisons are expensive (this may be a problem for modular arithmetic).

Redundant number systems are used in cryptography for a long time. Recodings of some values into a redundant number system are frequent. For instance, Non-Adjacent Forms (NAF and w-NAF) are used in modular exponentiation in RSA and in scalar multiplication in ECC. Redundancy is used to lower the number of some operations.

After an introduction to redundant number systems, we will present some current investigations on links between redundant number systems and reconfigurable arithmetic units with countermeasures against some side channel attacks. The use of redundant number system allows to change the way some computations are performed (and then their effects on side channels). The frequency (internal iteration level, field operation level, curve operation level...) and the location (digit level, number level, curve point level...) of the reconfigurations widely impact units characteristics. We will show some very first results on a long term project dedicated to reconfigurable arithmetic units for cryptography.