this is for holding javascript data
Scott Fluhrer edited untitled.tex
almost 9 years ago
Commit id: 9d494b561b05d918bf83c8bc05e5860ed9739b54
deletions | additions
diff --git a/untitled.tex b/untitled.tex
index b0dec28..83a3310 100644
--- a/untitled.tex
+++ b/untitled.tex
...
If we instead select an aribtrary prime without such a special structure, 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; in other words, modular reduction of a special form prime can be done approximately twice as fast as an arbitrary prime.
If this were the only consideration, the choice on whether we should use a prime with special structure would be an obvious one. However, there is another issue. Sometimes, Elliptic Curves are implemented by hardware that needs to
do go into hostile environments, and can be expected to be subject to side channel attacks, such as Differential Power
Analysis; with this, Analysis, In this attack, the attacker runs the system, performing the same operation repeatedly, and takes careful measurements of power consumed (or EM radiation emitted) on a cycle-by-cycle basis; by statistically combining these measurements, the attacker hopes to recover the internal states
(and thus (which includes the private key).
To combat these sorts of attacks, one of the strategies that need to be employed is
blinding; masking; we include random data in our computations, and while the end results is independent of the random value, the intermediate values are strongly dependent, and thus the correlations between the internal states and anything that the attacker wants (such as the private key) is much weaker.
One such method of blinding Elliptic Curve calculations (first published by Coron\cite{Coron_1999}) took advantage of a property of Elliptic Curve groups; we know an integer $n$ such that $nG = 0$ (this value $n$ is known as the order of the point $G$). Coron's method to compute $kG$ would be to select a random value $r$ and computing first $nr+k$, and then $(nr + k)G$. Everytime we would perform a point multiplication, we would select a random $r$, and hence the bits of the integer we're giving to the point multiplication logic are independent of the integer $k$ we're actually multiplying by.