Diffie-Hellman implementation doesn't work for bigger numbers

Question

Context

I was looking at this video DHE explained

It talks about how two people can exchange a key without eyedroppers to know much.

The implementation according to the video

// INITIALIZERS (video's values)-------------------------

var prefx = 3
var modulo = 17

// SECRET NUMBERS ---------------------------------------

var alice_secret_number = 19 // replaced 54 since there is a precision loss with it.
var bob_secret_number = 24

// PUBLIC KEYS ------------------------------------------

var public_alice = Math.pow(prefx , alice_secret_number) 
var public_bob = Math.pow(prefx , bob_secret_number)

// Check potential overflow -----------------------------
console.log(public_alice , public_bob)

// Apply the modulo -------------------------------------
public_alice %= modulo
public_bob %= modulo

// Check the value again --------------------------------
console.log( public_alice , public_bob )

// Calculate the good number ------------------------------------------
var final_alice = Math.pow( public_bob , alice_secret_number ) % modulo
var final_bob = Math.pow( public_alice , bob_secret_number ) % modulo

console.log( final_alice , final_bob )

Problem

That doesn't always work. First, javascript, for example, loses precision. So you can try with small numbers only. The speaker talks about big modulos. Even small one won't make it. I gave you the code, which is not tailored toward performance but readability.

Could someone give me his/her opinion on what I am doing wrong?

Answer 1

All numbers in JavaScript are floats (actually doubles). The corresponding specification is IEEE 754. To represent an integer without loss of precision it must fit into the mantissa which is 53 bit big for 64 bit floats. You can check the maximum integer with Number.MAX_SAFE_INTEGER which is 9007199254740991. Everything beyond that loses precision.

Why is this a problem? (Most of) cryptography must be exact otherwise the secret cannot be learned. What you try to do is exponentiate and then apply the modulus, but since you do this separately, you get a very big number after exponentiation before it can be reduced through the modulus operation.

The solution is to use some kind of BigNumber library (like BigInteger) which handles all those big numbers for you. Note that there is specifically a modPow(exp, mod) function which combines those two steps and calculates the result efficiently.

Note that user secrets should be smaller than the modulus.