1

I am currently beginning to studying the different security protocols and came across the SRP secure remote password protocol. I manage to understand the mathematic formulas behind it and the calculation but i do not understand the reason/purpose of using the "g" -> a generator of the multiplicative group.

Why is "g" a static value

why it should be predefined, why not dynamically assigned

why is "g" has the value of 2 in the most implementations i.e. why not 3,4,5,6,7,8,..

what is so important about this parameter that it needs to be included into the calculation,

what is the purpouse of the generator of the multiplicative group is there any special relation that i must be aware in the matematics

what happens when g is 1

I have read the wikipedia definition of the Generators but i still do not understand what is the reason, WHY do we need to use them i.e. what happens when the group Z is cyclic, why is this an advantage or not.

Tito
  • 113
  • 2
  • 1
    http://security.stackexchange.com/questions/54359/what-is-the-difference-between-diffie-hellman-generator-2-and-5/54366#54366 – Tito Aug 14 '14 at 13:25

1 Answers1

1

SRP is one of the large collection of algorithms which operate in a cyclic group. A cyclic group consists in elements 1, g, g2, g3,... up to some value gr-1 where r is the group order (the smallest non-zero integer such that gr = 1). So g is "static" because it actually is part of the definition of the playground: SRP operates in the cyclic group generated by a given value g, using multiplication modulo a given prime N as group law. Note that both client and server must agree on g and N, and the same g and N must be used for a given user. It is easier for the server if the same g and N, i.e. the same cyclic group, are used for all users; and sharing the same group is not a problem for security.

For cryptographic purposes, we need a group such that discrete logarithm is hard, but computations are easy (these two conditions imply that we need a cyclic group, but just not any cyclic group). This requires that N is big enough, and also that r (the order of g) is such that it is a multiple of a big enough prime (at least 160 bits). SRP recommends that N be chosen as a "safe prime", i.e. N = 2_q_+1 where q is also a prime integer. If N is a safe prime, then the order of any g in the 2..N-2 range is necessarily q or 2_q_, hence appropriate.

If you choose g = 1, then you get a cyclic group of order 1 and all your values will be 1; any password will be accepted and there is no security at all. Similarly, if you choose g = N-1, then you get a cyclic group of order 2, which is not substantially better.

However, any value between 2 and N-2 will be good for g (if N is a safe prime). Then, we may as well use g = 2, which is optimal for performance (though the gain is slight when compared with a random g).

Community
  • 1
Tom Leek
  • 168,808
  • 28
  • 337
  • 475
  • Tom thank you for your answer. It made the reason of "g" clear. Your last sentence states "use g = 2, which is optimal for performance" could you please elaborate on that. Is this related to the logic how processors (matrix) calculate numbers? – Tito Aug 15 '14 at 08:10
  • Tom you wrote "SRP is one of the large collection of algorithms which operate in a cyclic group" what would be the opposite i.e. algorithm/protocol that do not operate on a cyclic group as a example. – Tito Aug 15 '14 at 08:27
  • RSA is a cryptographic algorithm which does not operate in a cyclic group (at least, not as such). – Tom Leek Aug 15 '14 at 13:30
  • Performance boots from a small "g" is related to the usual "square-and-multiply" algorithm for modular exponentiation. The "multiply" steps are "multiply by _g_", which will be more efficient if _g_ is a small integer. Note, though, that with common window-based optimizations of that algorithm, more than 80% of the work is spent in the squarings, so the gain obtained by using _g_=2 (instead of any random integer) are slight. Still, if it can be done with no extra cost, there is no reason to refrain. – Tom Leek Aug 15 '14 at 13:33