Diffie-Hellman 密钥交换 - 澄清？

Question

简介：

Alice 和 Bob 试图在不希望 Eve（正在倾听）知道他们要谈什么的情况下进行交流。

所以

               Bad Eve
                  |
                  |
Alice ------------+--------------- Bob

Alice 和 Bob 公开同意质数模数和生成器。

说

发电机 = 3
总理 = 17

所以公式将是（例如）：

3^x % 17

好的。

爱丽丝正在选择一个私人号码（比如 15）并执行 3^15 %17 => 6
Bob 正在选择一个 private 号码（比如 13）并执行 3^13 %17 => 12

现在爱丽丝和鲍勃互相告诉对方他们的结果（而不是他们的私钥）而夏娃正在听。

所以现在图片是：

                Bad Eve ( knows : 3^x %17 , 12,6)
                   |
                   |
 Alice ------------+--------------- Bob  
 (15)private                       (13)private 
  12(Bob's)                        6(Eve's)

现在爱丽丝拿到鲍勃的 12 和她的私钥并做：

((other's public num) ^ secret number) % 17

爱丽丝正在做：12^15 % 17 => 10

Bob 在做什么：6^13 % 17 => 10

所以现在他们有相同的对称数。

现在：

这是一个示例，很容易破解。

Eve 所要做的就是尝试找出 3^x % 17 中的 x 是 15 还是 13。

但显然我们在这里谈论的是大数字。

如果是这样 - 我写了这个演示：

Console.WriteLine(BigInteger.Pow( new BigInteger(3213213213212123332), 6549875) % 17);

即：

3213213213212123332 ^ 6549875 % 17

我有 I7 和 16gb 内存，这个运行超过 5 分钟

问题：

如果双方（爱丽丝和鲍勃）都使用大数字，那么他们需要很长时间才能得到第一步的结果（稍后他们应该交换该值）

我可能在这里遗漏了一些东西，但似乎使用大量数字让 Eve 的生活变得艰难，也会让 Alice 和 Bob 的生活变得艰难。

我错过了什么？

Answer 1

您缺少的东西叫做 modular exponentiation。这是计算巨大指数的快速方法 modulo 一些值。

例如，假设您要计算 (123^456) mod 777.

如果先求幂，将得到约 1000 位的结果。对于 DH 密钥交换中通常使用的那种值，您最终可能会使用更多的数字，甚至可能数百万。这显然根本没有效率。

模幂将问题分解为更简单的步骤。有两个数学恒等式使这成为可能：

(x^a) × (x^b) = x^(a+b), and

(x^y) mod n = ((x mod n)^y) mod n

证明：

第一个应该是不言而喻的。第二个可以证明如下：

如果 x mod n == z，则对于 c 的某个整数值，x 等于 (c×n + z)。 (c×n + z)^y 的二项式展开有 (y+1) 项

c^y×n^y + k1×c^(y-1)×n^(y-1).z + k2×c^(y-2)×n^(y-2)×z^2 + ... + k(y-1)c×n×z^(y-1) + z^y

（其中 k1 ... k(y-1) 是 binomial coefficients）

除最后一项 (z^y) 外，所有这些项 都是 n 的倍数，因此等于零 (mod n)。因此 (x^y) mod n == (z^y) mod n == ((x mod n)^y) mod n.

模幂算法：

计算(x^y)modn，重复x自乘得到如下数列：

X0 = x mod n
X1 = X0×X0 mod n = x^2 mod n
X2 = X1×X1 mod n = x^4 mod n
X3 = X2×X2 mod n = x^8 mod n
X4 = X3×X3 mod n = x^16 mod n

现在将这个系列中与 y 的二进制表示中的设置位相对应的项相乘。例如，假设 y=21:

(x^21) mod n = ((x^16) × (x^4) × x) mod n = (X4 * X2 * X0) mod n

这样计算有两个好处。首先，您必须计算的最大数字的位数最多是 modulus n 的两倍。其次，您必须执行的计算次数与指数的（以 2 为底的）对数成正比，这意味着对于像 6549875 这样的指数，计算速度将运行提高数百万倍。

Diffie-Hellman 密钥交换 - 澄清？

Diffie-Hellman Key Exchange - Clarification?

c#

cryptography

diffie-hellman

证明：

模幂算法：