2

嗨，我正在尝试实现 Diffie-Hellman 密钥交换

public static Integer secret = 100000;
public static BigInteger g = new BigInteger("5");
public static BigInteger p = new BigInteger("315791951375393537137595555337555955191395351995195751755791151795317131135377351919777977373317997317733397199751739199735799971153399111973979977771537137371797357935195531355957399953977139577337393111951779135151171355371173379337573915193973715113971779315731713793579595533511197399993313719939759551175175337795317333957313779755351991151933337157555517575773115995775199513553337335137111");
public static BigInteger public = g.pow(secret).mod(p);

但是计算 100000 已经需要几秒钟。我不知道 256 位数字需要多少时间。

是因为 BigInteger 的实施而如此缓慢还是我偏离了轨道？

4

3 回答 3

4

问题是这g.pow(secret)是一个非常非常非常大的数字。它比 大得多p，并且有大约secret位数。如果您增加到secret正常 Diffie-Hellman 秘密指数的范围内（大约与 的位数相同p），您的计算机将没有足够的内存来保存它。地球上所有的计算机加起来都没有足够的内存来容纳它。这是一个非常大的数字。

但是g.pow(secret).mod(p)——你想要的最终答案——只有大约和 一样多的数字p，所以它是一个易于计算机跟踪的数字。只是中间值太大而无法处理。

因此，您需要利用带有这样的整数的 mod 的分配规则 --
(a * b).mod(p) == (a.mod(p) * b.mod(p)).mod(p)。使用该规则，您可以将g.pow(secret)计算分解为大量的乘法（只需要 O(log 2 secret) 乘法），并.mod(p)在每个步骤中应用 a 以防止所涉及的数字变得太大。

于 2013-09-09T21:08:16.647 回答
3

使用此处描述的方法（以及许多其他位置）： https ://math.stackexchange.com/questions/36318/modulo-arithmetic-with-big-numbers

祝你好运。

于 2013-09-08T18:24:22.577 回答
1

在 Java 中使用modPow 的 BigInteger，它可以有效地计算

于 2021-05-01T00:22:28.703 回答