我知道我需要使用扩展欧几里得算法，但我不确定我需要做哪些计算。我有大量的数字。谢谢
user1816690
问问题
86000 次
6 回答
22
鉴于此，p=11，q=7，e=17，n=77，φ(n)=60，d=?
公式中的第一个替换值：-
ed mod φ (n) =1
17 天 mod 60 = 1
下一步： – 取 n 的总和，即 60 在您的左侧， [e] 在您的右侧。
60 = 17
第三步：——问多少次 17 到 60。那是 3.5…….. 忽略余数，取 3。
60 = 3(17)
第 4 步： - 现在您需要平衡这个方程 60 = 3(17)，使左侧等于右侧。如何？
60 = 3(17) + 9 <== 如果将 3 乘以 17，则得到 51，然后再加上 9，即 60。这意味着双方现在相等。
第 5 步： - 现在将 17 移至您的左侧，将 9 移至您的右侧。
17 = 9
第6步：-问9到17的次数。那是1.8……。
17 = 1(9)
第 7 步：- 第 4 步： – 现在您需要平衡这 17 = 1(9)
17 = 1(9) + 8 <== 如果将 1 乘以 9，则得到 9，然后再加上 8，即 17。这意味着双方现在相等。
第 8 步：- 再次将 9 移至您的左侧，将 8 移至您的右侧。
9 = 1(8)
9 = 1(8) + 1 <== 一旦你达到 +1 以平衡你的方程，你可以停止并开始做反向替换。
步骤 A：- 步骤 8 中的最后一个方程 9 = 1(8) + 1 可以写成如下： 1.= 9 – 1(8)
步骤 B：-我们通过简单地说步骤 7 中的 8 = 17 – 1(9) 来知道 (8) 是什么。现在我们可以将步骤 A 重写为：-
1=9 -1(17 – 1(9)) <== 这里因为 9=1(9) 我们可以重写为：-
1=1(9)-1(17) +1(9) <== 对相似词组进行分组。在这种情况下，您将 1(9) 与 1(9) 相加——即 2(9)。
1=2(9)-1(17)
步骤 C： - 我们通过简单地说步骤 4 中的 9 = 60 - 3(17) 来知道 (9) 是什么。现在我们可以将步骤 B 重写为：-
1=2(60-3(17) -1(17)
1=2(60)-6(17) -1(17) <== 对相似词组进行分组。在这种情况下，您将 6(17) 与 1(17) 相加——即 7(17)。
1=2(60)-7(17) <== 在这个阶段我们可以停下来，没有什么可以替代的，因此取下一个17的值。即7。用totient减去它。
60-7=d
因此，d = 53 的值。
于 2015-10-30T00:16:18.937 回答
20
好吧，d选择这样d * e == 1 modulo (p-1)(q-1)，所以你可以使用欧几里得算法（找到模乘逆）。
如果您对了解算法不感兴趣，您可以直接调用BigInteger#modInverse。
d = e.modInverse(p_1.multiply(q_1))
于 2013-05-01T00:14:39.973 回答
2
我只是想补充Sidudozo 的答案并澄清一些要点。
首先，我们应该将什么传递给扩展欧几里得算法来计算d？
请记住ed mod φ(n) = 1和cgd(e, φ(n)) = 1。
知道扩展欧几里得算法是基于公式的cgd(a,b) = as + bt，因此cgd(e, φ(n)) = es + φ(n)t = 1，d为了s + φ(n)满足
ed mod φ(n) = 1健康）状况。
因此，给定e=17and φ(n)=60（从Sidudozo 的答案中借用），我们替换上述公式中的相应值：
cgd(e, φ(n)) = es + φ(n)t = 1⇔ 17s + 60t = 1。
在Sidudozo 的回答结束时，我们得到s = -7。因此d = s + φ(n)⇔ d = -7 + 60⇒ d = 53。
让我们验证结果。条件是ed mod φ(n) = 1。
看 17 * 53 mod 60 = 1。正确的！
于 2017-10-28T11:35:19.987 回答
1
Thilo批准的答案是不正确的，因为它使用Euler 的 totient 函数而不是Carmichael 的 totient 函数来查找d。虽然 RSA 密钥生成的原始方法使用 Euler 函数，但d通常使用 Carmichael 函数派生，原因我不会深入探讨。找到d给定p q的私有指数所需的数学运算e如下：
d = e^-1*mod(((p-1)/GCD(p-1,q-1))(q-1))
为什么是这样？因为d在关系中定义
de = 1*mod(λ(n))
λ(n)Carmichael 的函数在哪里
λ(n)=lcm(p-1,q-1)
可以扩展到哪个
λ(n)=((p-1)/GCD(p-1,q-1))(q-1)
所以将它插入到定义d我们得到的原始表达式中
de = 1*mod(((p-1)/GCD(p-1,q-1))(q-1))
然后将其重新排列为最终公式
d = e^-1*mod(((p-1)/GCD(p-1,q-1))(q-1))
更多相关信息可以在这里找到。
于 2020-04-17T23:25:51.553 回答
0
取值p=7, q=11和e=17。那么 和 的n=p*q=77值f(n)=(p-1)(q-1)=60。因此，我们的公钥对是，(e,n)=(7,77)
现在为了计算d我们有约束的值，
e*d == 1 mod (f(n)), [here "==" represents the **congruent symbol**].
17*d == 1 mod 60
(17*53)*d == 53 mod 60, [7*53=901, which gives modulus value 1]
1*d == 53 mod 60
因此，这给出了 的值d=53。因此，我们的私钥对将是，(d,n)=(53,77)。
希望这有帮助。谢谢！
于 2021-05-21T04:15:20.750 回答
0
Simply use this formula,
d = (1+K(phi))/e. (Very useful when e and phi are small numbers)
Lets say, e = 3 and phi = 40 we assume K = 0, 1, 2... until your d value is not a decimal
assume K = 0, then d = (1+0(40))/3 = 0. (if it is a decimal increase the K value, don't bother finding the exact value of the decimal)
assume K = 2, then d = (1+2(40)/3) = 81/3 = 27
d = 27.
Assuming K will become exponentially easy with practice.
于 2020-05-12T19:58:10.300 回答