javascript encryption cryptography modular-arithmetic elgamal

Unidirectional ElGamal Proxy Re-Encryption implementation

I've implemented an ElGamal scheme in JavaScript (the code is awful, just wanted to test it quick) based on this explanation.

var forge = require('node-forge');
var bigInt = require("big-integer");

var bits = 160;
forge.prime.generateProbablePrime(bits, function(err, num) {
  // Create prime factor and convert to bigInt
  var factor = bigInt(num.toString(10));
  // Find a larger prime of which factor is prime factor
  // Determine a large even number as a co-factor
  var coFactor = bigInt.randBetween("2e260", "3e260"); // should be bitLength(prime) - bitLength(factor)
  var prime = 4;
  while(!coFactor.isEven() || !prime.isPrime()) {
    coFactor = bigInt.randBetween("2e260", "3e260"); // should be bitLength(prime) - bitLength(factor)
    prime = coFactor.multiply(factor);
    prime = prime.add(1);
  }
  // Get a generator g for the multiplicative group mod factor
  var j = prime.minus(1).divide(factor);
  var h = bigInt.randBetween(2, prime.minus(1));
  var g = h.modPow(j, factor);
  // Alice's keys
  // Secret key
  var a = bigInt.randBetween(2, factor.minus(2));
  // Public key
  var A = g.modPow(a, prime);
  // Bob's keys
  // Secret key
  var b = bigInt.randBetween(2, factor.minus(2));
  // Public key
  var B = g.modPow(b, prime);
  // Shared secret
  // Calculated by Alice
  var Sa = B.modPow(a, prime);
  // Calculated by Bob
  var Sb = A.modPow(b, prime);
  // Check
  // Encryption by Alice
  var k = bigInt.randBetween(1, factor.minus(1));
  var c1 = g.modPow(k, prime);
  // Using Bob's public key
  var m = bigInt(2234266) // our message
  var c2 = m.multiply(B.modPow(k, prime));
  // Decryption by Bob
  var decrypt = c1.modPow((prime.minus(b).minus(bigInt(1))), prime).multiply(c2).mod(prime);
  console.log(decrypt); // should be 2234266

This seems to be working, the decryption step in the end returns the original number. I now wanted to convert this into a unidirectional proxy re-encryption scheme based on the following idea, taken from this paper (page 6, left column).

So you don't have to read the paper, the logic behind it is that we can split a private key x in two parts x1 and x2 such that x = x1 + x2. A proxy would get x1 and decrypt with x1, passing the result to the end user, which would decrypt with x2. The following picture describes the math in more detail for the first by the proxy, using x1.

where:

m = plaintext message
g = generator of the group
r = integer chosen at random from Zq
x = secret key

The next step would be for the proxy to pass that to the end user which would use x2 to get the plaintext m (the functioning is analogous to the one above).

Now, I've tried implementing this by adding to the code

  // Proxy re-encryption test
  // x is secret key
  var x = bigInt.randBetween(1, factor.minus(1));
  var x1 = bigInt.randBetween(1, x);
  var x2 = x.minus(x1);
  // y is public key
  var y = g.modPow(x, prime);
  var r = bigInt.randBetween(1, factor.minus(1));
  var c3 = g.modPow(r, prime);
  // mg^xr
  var c4 = bigInt(2234266).multiply(y.modPow(r, prime));

  var _decryptP = c4.divide(g.modPow(x1.multiply(r), prime));
  var _decryptF = _decryptP.divide(g.modPow(x2.multiply(r), prime));
});

by following the same logic as in the equation above. However, _decryptF does not return 2234266 as it should. Strangely, it always returns 0.

My question is: can anyone see where this is going wrong?

Solution

You have at least two problems:

divide divides two numbers. Since both numbers are large, it is unlikely that the divident is a multiple of the divisor so you will always get 0 as a result. Modular division is actually a multiplication with the modular inverse. So, a / b is actually meant as a * (b^-1 (mod p)) (mod p) .
multiply multiplies two numbers. It is possible and likely that you jump out of the group using this function (I mean you can get a number larger or equal to prime). You have to apply the mod operation on the result. Technically, you only need to do this for the last multiply, but doing it for the intermediate steps considerably improves performance, because the numbers are smaller.

Here is the resulting code that works:

  // Proxy re-encryption test
  // x is secret key
  var x = bigInt.randBetween(1, factor.minus(1));
  var x1 = bigInt.randBetween(1, x);
  var x2 = x.minus(x1);
  // y is public key
  var y = g.modPow(x, prime);
  var r = bigInt.randBetween(1, factor.minus(1));
  var c3 = g.modPow(r, prime);
  // mg^xr
  var c4 = m.multiply(y.modPow(r, prime)).mod(prime);

  var _decryptP = c4.multiply(c3.modPow(x1, prime).modInv(prime)).mod(prime);
  var _decryptF = _decryptP.multiply(c3.modPow(x2, prime).modInv(prime)).mod(prime);
  console.log(_decryptF); // should be 2234266
});

Full code