Discovering private exponent from public key

Question

I'm going to assume this isn't possible, but I have to ask because I'm trying to fundamentally understand what I've thus far been trying to implement by following an RFC.

SRP-6a starts off with declaring that I should choose $N$, a sufficiently large prime, and $g$, a generator. Let's say $N$ is 1024-bits and $g$ is 2. A sufficiently random number $a$ is generated. For arguments sake I chose the length of $a$ to be 128 bits. My public key $A$ is then given as $g^a \bmod N$.

Now, assume that I'm the server (or in this case I'm just trying to debug an SRP-6a protocol), and I receive $A$. Since I know both $g$ and $N$, can I determine $a$ (in a reasonable amount of time). I'm guessing absolutely not, but it would be nice to know precisely why.

Answer 1

When using a Discrete Logarithm based scheme, such as SRP, the rule of thumb is to always use private exponents with a bit length twice the desired security strength. Hence, a 128 bit exponent $a$ will at most give you 64 bits of security. If you want 128 bit security, you need (at least) a 256 bit exponent. This is because the algebraic structure of the groups used for such schemes, make it possible to calculate discrete algorithms using a meet-in-the-middle approach that effectively halves the necessary effort, compared to a naive brute force approach.

In this case, for instance, let $q$ be the order of $g$ in $\mathbb Z_N$. Calculate $y = A(g^{q-x2^n}) \bmod N$ for all $0 \le x \lt 2^{128-n}$ and put the pairs $y,x$ in a table for fast access, indexed by the $y$ component. Next calculate $y' = g^z \bmod N$ for all $0 \le z \lt 2^n$. If you find a $y$ in the table such that $y = y'$, then you know that $z = a - x2^n \bmod q$, and hence that $a = z + x2^n$.

The latter calculations might be carried out in parallel and might be more effectively optimized than the former, so the optimal trade-off might e.g. be to set $n = 80$, meaning you put $2^{48}$ pairs $y,x$ in your table and perform a total of $2^{80}$ parallel calculations $y' = g^z \mod N$. This is feasible using modern hardware.