单向 ElGamal 代理重新加密实现
Unidirectional ElGamal Proxy Re-Encryption implementation
我根据 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。
我的问题是:谁能看出哪里出了问题?
你至少有两个问题:
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
});
我根据 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。
我的问题是:谁能看出哪里出了问题?
你至少有两个问题:
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
});