Scott Fluhrer edited untitled.tex  almost 9 years ago

Commit id: e9324b3dd9730baa788dbe8a40a7c9cc75b45f89

deletions | additions      

       

To speed this operation, one approach is to select a prime $p$ with a representation $2^e - c$, where $c$ has a simple representation in binary. What this allows us to do is accelerate the computation of the modular reduction by taking advantage of the identity:  $$a \cdot 2^e + b \equiv a \cdot c + b \pmod{2^e-c}$$  If the binary representation of $c$ is simple enough, we can compute $a \cdot c$ without doing a full multiply, and hence we can compute this modular reduction significantly faster than we could for an arbitrary prime. Examples of Elliptic Curves that allow this speed up include the so-called NIST curves\cite{NIST_1999}, Curve25519, Curve25519\cite{Bern_2005},  and the Microsoft NUMS curves. curves\cite{Black_2014}.  - Side channel attacks  - Scalar randomizatoin