this is for holding javascript data
Scott Fluhrer edited untitled.tex
almost 9 years ago
Commit id: c7fd8e6c84e767fdab7d4cbad44c03e08344cf38
deletions | additions
diff --git a/untitled.tex b/untitled.tex
index f89bee6..b47c8fd 100644
--- a/untitled.tex
+++ b/untitled.tex
...
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.
This allows us to compute the modular multiplication of two numbers in not much more time than it takes to perform a bignum multiplication of those two numbers. Examples of Elliptic Curves that allow this speed up include the so-called NIST curves\cite{NIST_1999}, Curve25519\cite{Bern_2005}, and the Microsoft NUMS curves\cite{Black_2014}.
If we instead select an aribtrary prime without such a simple representation, there are still some optimizations we can do beyond the obvious 'perform a multiply, and then perform a generic modulo reduction'. We can implement Montgomery Multiplication, which replaces the modulo operation with some multiplies and shifts; the net result is that a modular reduction can be done in the time of approximately two bignum multiplications.
- Side channel attacks
- Scalar randomizatoin