我正在尝试采用 ed = 1 mod((p-1)(q-1)) 并求解 d,就像 RSA 算法一样。
e = 5, (p-1)*(q-1) = 249996
我在 javascript 中尝试了很多代码,例如:
function modInverse(){
var e = 5;
var p = 499;
var q = 503;
var d = e.modInverse((p-1) * (q-1));
DisplayResult(d, "privateKeyResultLabel")
}
或
function modInverse(){
System.out.println(BigInteger.valueOf(5).modInverse(BigInteger.valueOf(249996)));
}
我只是想不出在 javascript 中求解 d(模逆)的正确方法。
最佳答案
我只是在查看 modular multiplicative inverse 的定义据我了解:
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
在你的情况下:
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
再次来自wikipedia entry ,可以使用 extended Euclidean GCD Algorithm 计算模逆它执行以下操作:
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.
在你的情况下,等式是这样的:
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
因此,如果我们只是将该算法应用于这种情况,我们将获得 d
和 z
的值。
对于 ax + by = gcd(a,b)
,扩展的 gcd 算法可能类似于 ( 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.
我不知道 javascript 中是否有内置函数。我怀疑是否存在,而且我是算法的粉丝,所以我认为您可能想尝试一下这种方法。您可以摆弄它并更改它以处理您的值范围,我希望它能让您朝着正确的方向开始。
关于javascript - 在 JavaScript 中计算模逆,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26985808/