So, I’ve been implementing the Secure Remote Password protocol (SRP) for a game project I’m working on. As you can see on the protocol design page, the protocol needs two values, N and g, in order to function. N (the modulus) must be a large, safe prime number and g (the generator) must be a primitive root of N (and thus also a coprime of it) also called a generator modulo N. In typical SRP speak, there is a key size KS which is the byte length of N. This key size is used in other computations in the protocol (such as when generating random numbers of a certain size) so we want it to be relatively large.
In my case, I’m configuring SRP with a hash function H of SHA-512. I want a prime number with a byte length of 256 (i.e. 2048 bits). I’ll set the generator to 7 (the size of the generator really doesn’t matter in practice, but its value does matter in some regard as we’ll see).
I wanted to learn the OpenSSL API and so I figured I might as well generate my prime using OpenSSL. To that end, I wrote a tool that generates a prime with a specified bit length and verifies that a given generator is indeed a primitive root of it.
For example:
$ pgen 7 2048 N = 30817315993488094950063876611235224995197015486777838966039582184466989601737137785061150319729619861304023701874943954720410365155449212378509728297079378161875051028799177659132903881263214197958240731547326531423454481362477841674050050915185206506619708099215010108502376591014173871205694210918500927079807342355799375661000520374063019571782387361197808323622083769298736910284318017757455603510572185239046633686272701011272606841336216587476945751457343136023480297100196085405628980635988198354477091187313063439790470202359125187362725727097509333399354569332837280881731107660517239937731269477580686853163 g = 7 gcd(g, N) = 1
OpenSSL verifies that the final value of N is probably (i.e. very likely; see the documentation for BN_generate_prime) a prime (that is, it is not composite). The last line showing the result of applying the GCD operation on N and g verifies that g is indeed a generator modulo N (see here for why).
With N and g defined, all random numbers are generated with a byte length of KS such that they are as long as N. It is worth noting that both ends should agree on how the return value of the hash function H is interpreted (consider that the hash function most likely returns a raw byte array). The typical way is to interpret it as an unsigned, little-endian integer with the same byte length as the digest. Everything else in the protocol follows mathematical convention and is trivially implemented.
