3
$\begingroup$

Can someone explain, how $a^x \mod N$ can be speeded up, when $a$ and $N$ are known constants? How big is the gain and what resources are needed?

https://www.imperialviolet.org/2013/05/10/fastercurve25519.html


Just to mention: it can speed up SRP hashes bruteforce, which is calculated as $v = g^x \mod N$ where $x = hash(username, salt, password)$

$\endgroup$
2
  • $\begingroup$ Rereading my answer, I have to say that Adam's blog you've linked to provides a better explanation. Perhaps it would be easier to try and help you understand that: What did you have trouble understanding? $\endgroup$ Nov 26, 2013 at 18:13
  • $\begingroup$ I want to know this "How big is the gain and what resources are needed?" The explanation in the blog is too big for fast understanding. $\endgroup$ Nov 26, 2013 at 18:59

2 Answers 2

4
$\begingroup$

One obvious way is to precompute values $a^{k_1} \bmod N$, $a^{k_2} \bmod N$, ...,$a^{k_i} \bmod N$, and (depending on the value of $x$) multiply together the appropriate elements.

To take a simple example, if we precompute $a^1 \bmod N, a^2 \bmod N, a^4 \bmod N, ... a^{2^k} \bmod N$, and (based on the value of $x$ in binary, multiply the appropriate elements together); this gives a method which takes an average of $1/2 log_2 N$ multiplies, which is an obvious improvement over what you can do without any precomputation.

The paper gives a slightly more aggressive example (treating $x$ as a base 16 rather than a base 2 number).

However, you can do even better: see this paper for a survey of the various possibilities.

One note: if you are performing operations on an Elliptic Curve (that is, doing a point addition rather than a modular multiplication), then the operation of computing the inverse of an element is cheap; even though the cited paper doesn't cover that case, that can be used to reduce the number of operations even further.

$\endgroup$
7
  • $\begingroup$ AFAIU it's not $1/2 log_2 N$ but $\mathrm{pop}(x)$ where $\mathrm{pop}(x)$ is the number of $1$ bits (Hamming weight). Am I right? $\endgroup$ Nov 26, 2013 at 19:06
  • $\begingroup$ I meant dependence between x and calculation time. $\endgroup$ Nov 26, 2013 at 19:09
  • $\begingroup$ @SmitJohnth: yes, it is $pop(x)$; that's why I said "average" (because the average of $pop(x)$ is $1/2\log_2(x)$ $\endgroup$
    – poncho
    Nov 26, 2013 at 19:09
  • $\begingroup$ Ah ok. But normally it's $1,5 log2(x)$. NOt a big gain. $\endgroup$ Nov 26, 2013 at 19:11
  • $\begingroup$ @poncho: Sorry, didn't realise you'd replied when i deleted my comment. rest of world: I was unsure as to which was 'more' aggressive. $\endgroup$ Nov 26, 2013 at 19:13
2
$\begingroup$

In brief: If you know $(a,N)$, you can speed the computation up by precomputing some of the powers of $a$.


Let $x=x_n\dots x_1x_0=\sum_{i=0}^n x_i 2^i$ be the binary expansion of $x$, and let $a_j=a^{2^j}\pmod N$.

Very naively: $$ a^x \pmod N = \overbrace{a*(a*(a*\dots*(a))\dots))}^{\text{x terms}} $$ This requires $\theta(x)$ multiplications.

Traditional Square and Multiply: $$ a^x \pmod N = a^{x_n \dots x_0} = a^{2^n x_n+ \dots+ x_0} =(a^{2^n})^{x_n} (a^{2^{n-1}})^{x_{n-1}} \dots a^{2^0})^{x_n} =\prod_{i=0}^n a_i^{x_i} $$ So, to use this for efficient multiplication, we maintain a product value $y$, and exponentiation variable $e$ - initialised with $(y,e)=(1,a)$. Then, we simply continue to square $e$, multiplying $y$ by $e$ each time we reach some power $a^{2^j}$ for which $x_j= 1$. How much work does this require? Well, we must calculate $n=\log_2(x)$ multiplications to calculate the $a_j$, and then on average $n/2$ multiplications to calculate $a^x$ (where we assume that an "average" value of $x$ has half it's bits set), and at most $n$ multiplications. Total? $2n$ worst case, $\frac{3}{2}n$ on average.

Precomputational Optimisations of Square and Multiply

Calculating each $a_j=a^{2^j}\pmod N$ in advance, when we calculate $a^x$ we only need to do the (at most) $n$ multiplications. That is, we do not need to do any exponentiations at all. However, if $x$ may be very large, this will involve storing a large amount of data, but by storing some subset of these $j$ we can reduce the number of exponentiations required to reach the remaining values. Moreover, if one so wished this could store values such as $b=a_4*a_2$, which would reduce the online cost of calculating $a^{1010b}$ to the cost of looking up $b=a^{1010b}$.

Deciding a balance for this trade-off provides an interesting question, since at some point storing too many powers becomes unreasonable. For example, it would be possible to precompute and store $a^x\pmod N$ for all $x\in\{0,\dots,2^t\}$. This would reduce calculating $a^x$ to the look-up cost, but such a table would have size $\theta(2^t)$, which may well be impractically large.

$\endgroup$
6
  • $\begingroup$ Sorry, what is θ(x)? $\endgroup$ Nov 26, 2013 at 19:07
  • $\begingroup$ Maybe I've used bad notation, but when I was taught asymptotics $\theta(\cdot)$ was the version for 'grows like' (contrasting to $O(\cdot)$ for 'upper bounded by' which need not be anywhere near tight). $\endgroup$ Nov 26, 2013 at 19:08
  • $\begingroup$ The simpliest lookup method (table for every $2^n$) give 3x speedup, compared to this, every $x$ speed gain results in $2^x$ table growth (e.g. 8x speed gain needs 256 times bigger table), right? $\endgroup$ Nov 27, 2013 at 14:06
  • $\begingroup$ For 3x speedup (precomputing $a^{2^n}$, online calculation of $a^x$), the table will grow as $\log(x)$, since we need to store a value of $a_j$ for each bit in the length of $x$. I'm not sure I understand the second half of your question [sorry :( ] $\endgroup$ Nov 27, 2013 at 14:29
  • $\begingroup$ I meant speedup compared to the table for $a^{2^n}$ $\endgroup$ Nov 27, 2013 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.