Scott Fluhrer edited untitled.tex  almost 9 years ago

Commit id: e36a8f59cab14575e428f941d2e5ff1bc184b5e5

deletions | additions      

       

This paper shows how scalar blinding can be implemented to protect against side channel attacks when performing elliptic curve 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 an appropriate  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. The most common Elliptic Curves used in practice are defined over a prime field $GF(p)$; in practice, this implies that a majority of the time taken computing the point multiplication $kG$ is done computing the modular multiplication $a \times b \pmod p$, for a large (perhaps 256 bit) prime $p$ that we have picked.