Diffie-Hellman 公钥的计算速度很慢

Question

嗨，我正在尝试实现 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 的实现而这么慢还是我偏离了轨道？

Answer 1

问题是g.pow(secret)是一个非常非常非常大的数字。 它比p大得多，大约有secret个数字。 如果将secret增加到正常的迪菲-赫尔曼秘密指数范围内（与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₂秘密）乘法），并在每一步应用.mod(p)以防止所涉及的数字变得太大。

Answer 2

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

祝你好运。

Answer 3

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