在java中运行一个具有巨大基数和指数的计算

Question

我需要在盲签名方案中进行非常大的计算得到一个盲标记。我在java中使用BigInteger类尝试过这个。我相信我当前的代码是正确的，因为它运行，但最终抛出一个异常，因为数字将超出支持的范围。

我最初尝试的计算如下所示:

BigInteger blindedToken = hashedToken.multiply(randomElementDecimal.pow(formattedValue.multiply(BigInteger.valueOf(3))));

这不能工作因为BigInteger pow()必须取int的值。因此，我使用我自己的Helpers类来做这个.

class Helpers { 
public static BigInteger pow(BigInteger base, BigInteger exponent) {
BigInteger result = BigInteger.ONE;
while (exponent.signum() > 0) {
if (exponent.testBit(0)) result = result.multiply(base);
base = base.multiply(base);
exponent = exponent.shiftRight(1);
}
return result;
}
}

更新后的计算结果如下:

BigInteger blindedToken = Helpers.pow(randomElementDecimal, formattedValue.multiply(BigInteger.valueOf(3)));
blindedToken = blindedToken.multiply(hashedToken);
System.out.println(blindedToken);

结果为

Z = 941180828215645688530913292077221835722091184537123007963440625299702649269*1631434789^(222347888349073615524064151195238689903425040008399562092481278391150317944919*3)

Z = h(Tid)*R^(公共指数*格式值)

我已经通过将散列值从SHA-256的结果更改为SHA-1来缩短数字，但我仍然面临问题。

It似乎永远运行我认为它会溢出，因为计算量太大.

我只是想知道是否有的另一种方法来计算这个并存储值。或者其他语言(如Python)是否支持此功能?

Answer 1

是的，这个数字的幂在任何硬件上都需要几十亿年的时间。

通常，对于加密，所有这些都需要对某些东西取模，这就是问题所在。x^y % z，其中y是一个可怕的数字，但z是一个合理的大小，可以快速完成，但不能用Math.pow。

Answer 2

由于这是关于密码学的，所以您缺少的一点是您需要一个模数。在密码学中，我们主要研究有限模。似乎你在尝试像盲签名一样进行RSA，因此你需要对模进行幂。

它们，使用BigInteger类的modPow，并且从JDK1.1开始可用。这使用了平方乘技术的模块化版本，它具有O(log n)复杂度，其中n是指数。每一步的中间值最多为m^2。

modPow(BigInteger exponent, BigInteger m)

返回值为(this^exponentmod m)的BigInteger(与pow不同，此方法允许取负指数)