Calculation of Diffie–Hellman public key slow

hi i’m trying to implement a Diffie–Hellman key exchange

public static Integer secret = 100000;
public static BigInteger g = new BigInteger("5");
public static BigInteger p = new BigInteger("315791951375393537137595555337555955191395351995195751755791151795317131135377351919777977373317997317733397199751739199735799971153399111973979977771537137371797357935195531355957399953977139577337393111951779135151171355371173379337573915193973715113971779315731713793579595533511197399993313719939759551175175337795317333957313779755351991151933337157555517575773115995775199513553337335137111");
public static BigInteger public = g.pow(secret).mod(p);

but the calculation for 100000 already takes several seconds. I won’t know hoch much time it would take for a 256bit number.

Is it so slow because of the implementation of BigInteger or am i off the track?

Answer

the problem is that g.pow(secret) is a really, really, REALLY big number. It is much bigger than p, and has around secret digits. If you increase secret to be in the range of a normal Diffie-Hellman secret exponent (about the same number of digits as p), your computer won’t have enough memory to hold it. All the computers on earth combined wouldn’t have enough memory to hold it. It’s a really big number.

But g.pow(secret).mod(p) — the final answer you want — only has about as many digits as p, so it’s a tractable number for computer to keep track of. It’s just the intermediate value that is too big to deal with.

So you need to take advantage of the distributive rule for mod with integers like this —
(a * b).mod(p) == (a.mod(p) * b.mod(p)).mod(p). With that rule, you can break down the g.pow(secret) computation into lots and lots of multiplies (O(log₂secret) multiplies are all that is needed), and apply a .mod(p) at each step to keep the numbers involved from getting too big.