# What's the algorithm to generate a modulus and a base for a Diffie-Hellman key exchange app?

I have a school project in which I have to write a java console application that can be used for key exchange between two people. All is fine and well, but finding good base and modulus seems to be a difficult task, especially for someone with not much mathematical background, such as myself.

I know that the two numbers have to be prime but I don't seem to be able to find any algorithm for automatically generating them. Apparently, Java has a class for it (DHParameterSpec), but I'm supposed to implement this on my own. I've read other threads on the topic, but I've found none that I can understand well.

The easiest method to generate the DH modulus and base (collectively called the "DH parameters") is to use values which have already been generated. This does not imply security issues -- several people can share the same DH parameters without trusting each other.

Technically, you need three values: the modulus p, the base g, and the sub-group order q. Ideally, q should be a prime integer, and gq = 1 mod p.

There are nice pre-generated values in RFC 3526 and RFC 5114.

If you want to make your own, then the basic algorithm is "try random values until you hit a prime", but there are details. You have basically two choices:

1. Generate random q values and compute p = 2​q+1; do that until both q and p are prime. When you have found a q and p with these characteristics, then you can use g = 4 as base; it is guaranteed that g will have order exactly q.

2. Generate random q values of the "right size" for a sub-group order (say, 256 bits) until you find a prime q. Then generate random values r and compute p = qr+1 for each r; do that until you find a prime p. At that point, generate a random value h and compute g = hr mod p. That value g will have order q (it is theoretically possible but in practice highly improbable that you get g = 1; in that case, generate a new random h).

The first method allows the use of a very small g, which gives a slight performance advantage when using Diffie-Hellman (not a big advantage in practice, something like a +15% speed at most when proper optimizations have been applied). However, generating the modulus p with that method is quite expensive, because you have to try about a few millions of q values until you find one such that both p and q are prime.

With the second method, parameter generation is a lot faster, since it goes in two stages: first finding a prime q (a few hundred tries), then a prime p (a few thousand tries). It also gives you a relatively small sub-group order, which can be nice too. However, you end up with a "huge" base g. This method is really what is done in DSS, as specified in FIPS 186-4, so if you want a formal specification with all the details laid out, go read appendix A of that standard ("Generation and Validation of FFC Domain Parameters").

In any case, you will need computations on big integers, including modular exponentiations and primality tests. Java provides both in `java.math.BigInteger`.

• Thank you for your answer, I understand what has to be done now. – Vlad Adrian Moglan Oct 28 '15 at 13:58
• I have an issue. I think 256 bits might be too much for the prime number q since whenever I try to calculate p, I get a negative value. – Vlad Adrian Moglan Oct 28 '15 at 16:50
• All of this is about integers which are "big", i.e. quite bigger than what can fit in an `int` or a `long`. You should have `BigInteger` everywhere in your code. – Thomas Pornin Oct 28 '15 at 16:52
• I understand that and I do, but for some reason I still get a negative modulus such as: Large prime num: 62922831596778141152094421595998779930080421720286658690885601325815534595093 Modulus: -100967936633159750480197855067683103173782345578795306989399796028054527178237418468437 The modulus is the result of (_randLargePrime,multiply(BigInteger.valueOf(_rand.nextInt())).add(valueOf(1)) as in p = qr + 1 . I hope that makes sense. – Vlad Adrian Moglan Oct 28 '15 at 17:11
• By the way, for finding the large prime number (q) I use some code I found on wikipedia (I think it can be freely used). The name of the algorithm is Miller-Rabin. I tested my resulted q on a website that checks for prime numbers and the code seems to do its job. – Vlad Adrian Moglan Oct 28 '15 at 17:14