Scott Fluhrer edited untitled.tex  almost 9 years ago

Commit id: afb45c4dd15d9e72296c0aa0814991c31b5bd423

deletions | additions      

       

\section{Abstract}  This paper shows how scalar blinding can be implemented to protect against side channel attacks when performing elliptic curve operations, operations with relatively small cost,  even if the characteristic of the field has a sparse representation. This may indicate that random primes might not be as advantageous for hardware elliptic curve implementations as previously  thought. \section{Background}  Elliptic curves are a useful tool within cryptography. An Elliptic Curve is an abstract group, and some Elliptic Curves have this useful property: given a group member (point) $G$ and an integer $k$, the point $H = kG$ can be computed in $\log k$ time; however given two points $G, H$, computing the integer $k$ such that $H = kG$ takes $\sqrt{k}$ time. By selecting $k$ (and the Elliptic Curve) to be the right size, we can make finding $H$ given $k$ and $G$ (known as point multiplication) relatively quick, while making finding $k$ given $H$ and $G$ (known as the discrete logarithm problem) infeasible. 

Of course, once we consider nonpower-of-2 bases, we lose the two advantages that we formally had; let us examine how bad that makes the situation.  \section{Costs of point multiplying using a non-power-of-2 base}  The first thing we want to look at is how much more expensive it is to use a base which is not a power of 2. After all, a base which is a power of 2 allows us to implement that fixed multiplication by a handful of doublings, which is the most efficient possible. However, it turns out that other bases are almost as cheap.  \begin{itemize}  \item Implementing radix of non-power-of-2  \item Generating exponents into non-power-of-2 base  \item ECDH/ECIES  \item ECDSA