Related to this question: Is there any memory trade-off that helps such attack?
Obviously if the field size is very small (say 40 bits) it´s possible, but what if the field size is 160 bits long? or 256 bits?
Tell me more
×
Cryptography Stack Exchange is a question and answer site for
software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
|
|
Well, Big-Step/Little-Step can be written as a precompute-table and then lookup type algorithm, however, it doesn't become close to practical with a 160 bit field. Here's how Big-Step/Little-Step works; we first select two integers $a$ and $b$ with $ab \ge size(group)$ (I consistently talk about group rather than the curve; that's because Big-Step/Little-Step will apply to any finite group. In terms of Elliptic Curves, for practical purposes we can make the assumption that $size(group) \approx size(field)$. In the precompute phase, we construct a table with the pair of values $(ib, (ib)G)$ for $(0 \le i < a)$. This table will contain $a$ rows, and takes $O(a)$ time to construct. Note that this table does not depend on the point $Q$ that we'll end up computing the discrete log on. In the lookup phase, we compute the points $Q - jG$ for $0 \le j < b$, and look up each of these points in the table. If we find one of the points in the table, we have $(ib)G = Q - jG$ (where $i$ is the value in the table, and $j$ is the value we used to compute the point), we then know that $Q = (ib + j)G$, and hence we have the discrete log. This phase takes $O(b)$ expected time (assuming each lookup can be done in constant time using appropriate data structures). Now, the total time taken is $O(max(a,b))$; to minimize this value, we generally assume that $a=b\approx\sqrt{size(group)}$, thus giving us a squareroot time algorithm. However, there is no such hard requirement, and if we're going to reuse the table multiple times, it makes sense to increase the value of $a$ (the one time cost) so we can decrease $b$ (the per-discrete-log cost). However, once we start talking about a group with circa $2^{160}$ members, well, this doesn't work out. For one, even in the balanced case, we're talking about a table with $2^{80}$ entries; that in itself is impractically large. If we consider increasing $a$, the table size becomes even more impractically large. Now, one obvious idea to reduce the table size is to create a Rainbow table. It turns out that Rainbow tables will work in the way we want (allowing us to build a table that we can use to lookup $i$ given $(ib)G$ values); however, it turns out not to buy us anything. Rainbow tables allow us to compress the table by a factor of $k$ by increasing the lookup time by that same factor $k$. That turns out to be the killer; because the lookup phase involved $O(b)$ table lookups. We can make the table $O(a/k)$ entries long; however the lookup phase will now take $O(kb)$ work; we haven't gained anything that we wouldn't have gotten by making $a$ smaller by a factor of $k$ and $b$ larger by a factor of $k$. |
|||||||||||
|
