单向ElGamal代理重新加密实现 [英] Unidirectional ElGamal Proxy Re-Encryption implementation

问题描述

我已经在JavaScript中实现了一个ElGamal方案（代码很糟糕，只是想快速测试它）基于

其中：

• m =明文消息


• g =小组的发电机


• r =从Zq随机选择的整数


• x =密钥

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

现在，我试过了通过添加代码来实现这一点

  //代理重新加密测试
 // x是密钥
 var x = bigInt.randBetween（1，factor.minus（1））; 
 var x1 = bigInt.randBetween（1，x）; 
 var x2 = x.minus（x1）; 
 // y是公钥
 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 不会返回 2234266 。奇怪的是，它总是返回0.

我的问题是：谁能看到出错的地方？

解决方案

您至少有两个问题：

• 除以除以两个数字。由于两个数都很大，因此divide不太可能是除数的倍数，所以你总是得到0。模块化除法实际上是模乘逆的乘法。所以， a / b 实际上是指 a *（b -1 （mod p））（mod p） 。




• 乘以乘以两个数字。您可能并且可能使用此功能跳出组（我的意思是您可以获得大于或等于 prime 的数字）。您必须对结果应用 mod 操作。从技术上讲，你只需要为最后的乘法执行此操作，但是为中间步骤执行此操作可以显着提高性能，因为数字较小。

以下是生成的代码：

  //代理重新加密测试
 // x是密钥
 var x = bigInt.randBetween（1，factor.minus（1））; 
 var x1 = bigInt.randBetween（1，x）; 
 var x2 = x.minus（x1）; 
 // y是公钥
 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）; //应为2234266 
}）; 
  

完整代码

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?

解决方案

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

这篇关于单向ElGamal代理重新加密实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！