Roy*_*mir 3 c# cryptography diffie-hellman
简要 ：
Alice 和 Bob 试图进行交流，但不想让 Eve（正在倾听）知道他们要谈论什么。
所以
Bad Eve
|
|
Alice ------------+--------------- Bob
爱丽丝和鲍勃公开同意质数模数和生成器。
说
所以公式将是（例如）：
3^x % 17
好的。
Alice 选择一个私人号码（比如15）并且3^15 %17 => 6
Bob 选择一个私人号码（比如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
鲍勃正在做：6^13 % 17 => 10
所以现在它们有相同的对称数。
现在：
这是一个例子，很容易被破解。
Eve 所要做的就是尝试找出或中x的哪一个。3^x % 171513
但显然我们在这里谈论的是大数字。
如果是这样 - 我写了这个演示：
Console.WriteLine(BigInteger.Pow( new BigInteger(3213213213212123332), 6549875) % 17);
这是：
3213213213212123332 ^ 6549875 % 17
我有 I7 和 16GB 内存，运行时间超过 5 分钟
问题 ：
如果双方（爱丽丝和鲍勃）都使用大数字，那么他们需要非常非常长的时间才能获得第一步的结果（稍后他们应该交换该值）
我可能在这里遗漏了一些东西，但似乎通过使用大量数字使 Eve 的生活变得困难，也使 Alice 和 Bob 的生活变得困难。
我缺少什么？
您缺少的东西称为模幂。这是计算以某个值为模的巨大指数的快速方法。
\n例如，假设您要计算 (123^456) mod 777。
\n如果先执行幂运算，您将得到大约 1000 位的结果。对于 DH 密钥交换中通常使用的值类型，您最终可能会使用更多的数字，甚至可能是数百万个数字。这显然根本没有效率。
\n模幂将问题分解为更简单的步骤。有两个数学恒等式使这成为可能：
\n\n\n\n
\n- (x^a) \xc3\x97 (x^b) = x^(a+b)，并且
\n- (x^y) mod n = ((x mod n)^y) mod n
\n
第一个应该是不言而喻的。第二个可以证明如下：
\n如果 x mod n == z，则对于 c 的某个整数值，x 等于 (c\xc3\x97n + z)。(c\xc3\x97n + z)^y 的二项展开式有 (y+1) 项
\n\n\nc^y\xc3\x97n^y + k1\xc3\x97c^(y-1)\xc3\x97n^(y-1).z + k2\xc3\x97c^(y-2)\xc3\x97n^ (y-2)\xc3\x97z^2 + ... + k(y-1)c\xc3\x97n\xc3\x97z^(y-1) + z^y
\n
（其中 k1 ... k(y-1) 是二项式系数）
\n除最后一项 (z^y) 外，所有这些项都是 n 的倍数，因此等于零 (mod n)。因此 (x^y) mod n == (z^y) mod n == ((x mod n)^y) mod n。
\n要计算 (x^y) mod n，请重复将 x 与其自身相乘以获得以下序列：
\n\n\nX0 = x mod n
\n
\nX1 = X0\xc3\x97X0 mod n = x^2 mod n
\nX2 = X1\xc3\x97X1 mod n = x^4 mod n
\nX3 = X2\xc3\x97X2 mod n = x^ 8 mod n
\nX4 = X3\xc3\x97X3 mod n = x^16 mod n
现在将这一系列中对应于 y 的二进制表示中的设置位的项相乘。例如，假设 y=21：
\n\n\n(x^21) mod n = ((x^16) \xc3\x97 (x^4) \xc3\x97 x) mod n = (X4 * X2 * X0) mod n
\n
以这种方式进行计算有两个优点。首先，您需要计算的最大数字的位数最多是模数 n 的两倍。其次，您必须执行的计算次数与指数的（以 2 为底）对数成正比，这意味着对于像 6549875 这样的指数，计算运行速度将快数百万倍。
\n