Calculating the Modular Inverse in JavaScript

Question

I am trying to take ed = 1 mod((p-1)(q-1)) and solve for d, just like the RSA algorithm.

e = 5, (p-1)*(q-1) = 249996

I've tried a lot of code in javascript such as:

function modInverse(){
var e = 5;
var p = 499;
var q = 503;
var d = e.modInverse((p-1) * (q-1));
DisplayResult(d, "privateKeyResultLabel")
}

or

function modInverse(){ 
System.out.println(BigInteger.valueOf(5).modInverse(BigInteger.valueOf(249996)));
}

I just can't figure out the correct way to solve for d, the modular inverse, in javascript.

Answer 1

I was just going through the definition of modular multiplicative inverse and from what I understand:

ax = 1 (mod m)
=> m is a divisor of ax -1 and x is the inverse we are looking for
=> ax - 1 = q*m (where q is some integer)
And the most important thing is gcd(a, m) = 1
i.e. a and m are co-primes

In your case:

ed = 1 mod((p-1)(q-1)) //p, q and e are given 
=> ed - 1 = z*((p-1)(q-1)) //where z is some integer and we need to find d

Again from the wikipedia entry, one can compute the modular inverse using the extended Euclidean GCD Algorithm which does the following:

ax + by = g //where g = gcd(a,b) i.e. a and b are co-primes
//The extended gcd algorithm gives us the value of x and y as well.

In your case the equation would be something like this:

ed - z*((p-1)(q-1)) = 1; //Compare it with the structure given above

a -> e
x -> d
b -> (p-1)(q-1)
y -> z

So if we just apply that algorithm to this case, we will get the values of d and z.

For ax + by = gcd(a,b), the extended gcd algorithm could look something like (source):

function xgcd(a, b) { 

  if (b == 0) {
    return [1, 0, a];
  }

  temp = xgcd(b, a % b);
  x = temp[0];
  y = temp[1];
  d = temp[2];
  return [y, x-y*Math.floor(a/b), d];
}

This algorithm runs in time O(log(m)^2), assuming |a| < m, and is generally more efficient than exponentiation.

I don't know if there is an inbuilt function for this in javascript. I doubt if there is, and I am a fan of algorithms, so I thought you might want to give this approach a try. You can fiddle with it and change it to handle your range of values and I hope it gets you started in the right direction.