0
$\begingroup$

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)?

$\endgroup$
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Exponentiation_by_squaring ​ ​ $\endgroup$ – user991 Oct 26 '16 at 0:06
  • 1
    $\begingroup$ 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. $\endgroup$ – fgrieu Oct 26 '16 at 6:54
  • $\begingroup$ "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. $\endgroup$ – tylo Oct 26 '16 at 11:51
4
$\begingroup$

It doesn't. The mod operation does not have to be performed after exponentiation. Modular exponentiation can be implemented using modular multiplication (and modular addition). Modular multiplication in turn can be implemented relatively efficiently, for instance using a Montgomery multiplier.

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$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.