# How does the DH algorithm deal with enormous powers?

I am studing DH Key Exchange and trying to implement it.

I am using the algorithm as follows:

In order to generate the public Key:

(Generator ^ Random_Number) mod Prime_Number

Generator = 2

Prime number = 5809605995369958062791915965639201402176612226902900533702900882779736177890990861472094774477339581147373410185646378328043729800750470098210924487866935059164371588168047540943981644516632755067501626434556398193186628990071248660819361205119793693985433297036118232914410171876807536457391277857011849897410207519105333355801121109356897459426271845471397952675959440793493071628394122780510124618488232602464649876850458861245784240929258426287699705312584509625419513463605155428017165714465363094021609290561084025893662561222573202082865797821865270991145082200656978177192827024538990239969175546190770645685893438011714430426409338676314743571154537142031573004276428701433036381801705308659830751190352946025482059931306571004727362479688415574702596946457770284148435989129632853918392117997472632693078113129886487399347796982772784615865232621289656944284216824611318709764535152507354116344703769998514148343807

(this is a standard from here in 3072-bit MODP Group)

The random number is in between 0 and 999.

After the public keys are exchanged, the algorithm evaluates:

(Public_Key_Received ^ MyPrivateKey) mod Prime number

The problem is that the Public Key Received is extremely large. How would the computer evaluate (Public_Key_Received ^ MyPrivateKey)?

• – user991 Oct 26 '16 at 0:06
• If "The random number is in between 0 and 999" then it is guessable and at most 10 bits; in DH with the 3072-bit MODP group, for security, we wan random numbers in the order of 256 bits. – fgrieu Oct 26 '16 at 6:54
• "I am studing DH Key Exchange and trying to implement it." as fgrieu pointed out: Using a 10 bit random number is not enough. And a DH key exchange requires a much larger number. How large also depends on the "order of the subgroup", usually noted as $n$, and then you choose a uniform random value between $0$ and $n$. Disregarding the specified assumption means, you don't have a DH key exchange. – tylo Oct 26 '16 at 11:51

Here's an example using decimals instead of binary; you know that $323 \times 323$ ends with a $9$ even without doing the full computation. This is a $\bmod 10$ operation. In the same way, you know that $323^3$ ends with a $7$ because $323 \times 323 \times 323$ ends with a $7$.