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.


1 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.

  • $\begingroup$ 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$? $\endgroup$
    – Joe
    Commented Aug 9, 2014 at 15:04
  • $\begingroup$ You also introduce $n$, what is that? $\endgroup$
    – Joe
    Commented Aug 9, 2014 at 15:10
  • $\begingroup$ @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$. $\endgroup$ Commented Aug 9, 2014 at 15:53
  • $\begingroup$ The parameter $n$ in my answer is an arbitrary attack parameter that might be any value between $0$ and $128$. $\endgroup$ Commented Aug 9, 2014 at 15:56
  • $\begingroup$ 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. $\endgroup$
    – Joe
    Commented Aug 9, 2014 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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