CODEWITHSUNDEEP
javascripthex
thedethfox
thedethfox

Reputation: 1739

Operation of big HEX number

I am trying to implement the Diffie–Hellman key exchange. I am working with big numbers that JavaScript cannot handle in their decimal form because of memory limitation.

I want to perform the operation g^a mod p = A where the length of the variables is between 512 and 1536 bits.

I have no idea how to solve such equation because of the memory limitation. I cannot convert the variables into decimals and then solve it.

I tried to find JavaScript libraries used to perform math operations on Hex numbers but I did not manage to find any

Note: I will be using SSL, so don't worry about JavaScript code injection.

Upvotes: 2

Views: 409

Answers (2)

thedethfox
thedethfox

Reputation: 1739

I have managed to do it.

1) Download the bigInt library. I have used this one: http://www.leemon.com/crypto/BigInt.html

2) Use it to generate the big numbers or convert an existing number to a bigInt object.

We need to calculate: g^a mod p = A

Which can be translated into the following JavaScript code:

var a = randBigInt(1536);                            // Generate (a)
var p = str2bigInt(my_prime_as_string, 16);          // convert p into a bigInt
var g = str2bigInt(my_primitive_root_as_string, 16); // convert q into a bigInt

var y   = powMod(g,Y, p);    // Calculate the common secret key.

Upvotes: 1

user9876
user9876

Reputation: 11102

First of all, when calculating g^a mod p, you don't calculate the exponent first then do the mod, since that way the numbers get insanely big. Instead, you take the modulo at each step, so you never have to deal with a number bigger than p^2.

To calculate the exponent, you probably need to use the exponentiation by squaring algorithm, remembering to take the modulo after every squaring and after every multiplication.

See: http://en.wikipedia.org/wiki/Exponentiation_by_squaring (look at the basic menthod there).

But really, any good JavaScript bignum library should do this for you.

And if you have to ask, you're not competent to implement cryptographic functions yourself. Cryptography is hard. (E.g. the method I describe above has timing side channel attacks, so it's not suitable for more than a toy). Find a library where someone else has already done the hard work, and learn how to use it correctly.

Upvotes: 1

Related Questions