单向 ElGamal 代理重新加密实现

Question

我根据 this 的解释在 JavaScript 中实现了一个 ElGamal 方案（代码很糟糕，只是想快速测试一下）。

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

这似乎是可行的，最后的解密步骤 return 是原始数字。我现在想根据以下想法将其转换为单向代理重加密方案，取自 this 论文（第 6 页，左栏）。

所以你不必阅读论文，其背后的逻辑是我们可以将私钥 x 分为两部分 x1 和 x2 这样 x = x1 + x2。代理将获得 x1 并使用 x1 解密，将结果传递给最终用户，最终用户将使用 x2 解密。下图更详细地描述了代理第一次使用 x1 的数学运算。

其中：

m = 明文消息
g = 组的生成器
r = 从 Zq
x = 密钥

下一步是代理将其传递给最终用户，最终用户将使用 x2 获取明文 m（功能类似于上面的功能）。

现在，我尝试通过添加到代码中来实现它

  // 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));
});

遵循与上述等式相同的逻辑。但是，_decryptF 并不像它应该的那样 return 2234266。奇怪的是，它总是 returns 0。

我的问题是：谁能看出哪里出了问题？

Answer 1

你至少有两个问题：

divide 将两个数相除。由于两个数字都很大，被除数不太可能是除数的倍数，因此结果总是 0。模除法实际上是与 mod 逆元的乘法。所以，a / b 实际上意味着 a * (b<sup>-1</sup> (mod p)) (mod p) .
multiply 将两个数相乘。您有可能并且很可能使用此功能跳出该组（我的意思是您可以获得大于或等于 prime 的数字）。您必须对结果应用 mod 操作。从技术上讲，您只需对最后一个 multiply 执行此操作，但对中间步骤执行此操作可显着提高性能，因为数字较小。

这是有效的结果代码：

  // 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

单向 ElGamal 代理重新加密实现

Unidirectional ElGamal Proxy Re-Encryption implementation

javascript

encryption

cryptography

modular-arithmetic

elgamal