# Discovering private exponent from public key

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.

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.
• You lost me with $q$. To simplify things I have chosen $N=251$, $g=2$ (though I am confused as to what a generator is anyway), and $a=43$. That gives me $A=2^{43} \bmod N = 151$. Where would $q$ fit in? In this example is $\mathbb Z_{251}$ known as the group $G$? – Joe Aug 9 '14 at 15:04
• You also introduce $n$, what is that? – Joe Aug 9 '14 at 15:10
• @Joe In SRP, $g$ is supposed to be a generator of the multiplicative group, meaning that the order of $g$ should be $q = N-1$. Since $N$ is supposed to be a safe prime, the only other possible values are $q = (N-1)/2$, $q = 2$ and $q = 1$. Checking the order of $g$ is done by finding the least $q$ such that $g = g^q \bmod N$. – Henrick Hellström Aug 9 '14 at 15:53
• The parameter $n$ in my answer is an arbitrary attack parameter that might be any value between $0$ and $128$. – Henrick Hellström Aug 9 '14 at 15:56
• Thanks @Henrick, I'm clearly still learning, a trip to the bookstore is in order. In my above comment about $g = 2$, I've just figured that it cannot be if $N = 251$, but $6$ can. If I'm now understanding generators correctly. – Joe Aug 9 '14 at 16:00