Scott Fluhrer edited untitled.tex  over 8 years ago

Commit id: d480ee4c33d80d1961eb694d6c5b3315a8f21fb9

deletions | additions      

       

If our Elliptic Curve representation makes addition as cheap as doubling (which some do), and we ignore the negations (which are comparatively cheap), then the base-32 method turns out to be 7.3\% faster than the base-48 method. If we instead assume that a doubling is 80\% of the cost of an addition (another common assumption), then the base-32 method turns out to be 10.4\% faster than the base-48 method. In other words, from this perspective, we can implement the blinding on a special format prime, and be within 7-10\% of the performance of a random prime. These results are fairly stable if we tweak our assumptions (e.g. change the size of the group order or the size of $t$)  When we multiply by a fixed point (for example, the curve generator $G$), one common optimization is to precompute various multiples $k_i G$ for various values $k_i$, and use those to accelerate the point multiplication process. While this works even better with bases that aren't powers of 2 (as we no longer need to perform multiplications by the fixed value $b$), $b$, and not restricting ourselves to power of 2 bases often allows us to fine-tune the base better),  this technique  does require us to store some precomputed tables, and hence is less likely to be considered useful for a hardware implementation. Hence, other than this quick note, we will ignore the possibility. \section{Working with exponents in nonpower-of-2 bases}  The other advantage that we discard if we work in an odd base is the fact that have to do something to convert our multiplier (which is in binary) into the base. The obvious approach would be to compute $k + tn$ in binary, and then do a base conversion into our desired format. The problem with that is that the digits of $k + tn$ will be expressed as a temporary, and thus will be subject to the same side channel attacks that we are trying to avoid.