Python 使用扩展欧几里德算法创建 RSA 私钥
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18940194/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Using Extended Euclidean Algorithm to create RSA private key
提问by Paul Nelson Baker
This is for an assignment I'm doing through school. I am having trouble generating a private key. My main problem is understanding the relation of my equations to each other. To set everything up, we have:
这是我在学校做的作业。我在生成私钥时遇到问题。我的主要问题是理解我的方程之间的关系。为了设置一切，我们有：
p = 61
q = 53
n = p * q (which equals 3233)
From here we have the totient of n (phi(n)) which equals 3120, now we can choose prime e; where 1 < e < 3120
从这里我们有 n ( phi(n))的整数等于 3120，现在我们可以选择素数 e；其中 1 < e < 3120
e = 17
Okay easy enough.
好吧，很简单。
For my assignment we've been made aware that d = 2753, however I still need to be able to arbitrarily generate this value.
对于我的任务，我们已经意识到d = 2753，但是我仍然需要能够任意生成这个值。
Now here is where I am having trouble. I've been perusing wikipedia to understand and somewhere something isn't connecting. I know that I need to find the modular multiplicative inverseof e (mod phi(n))which will be d, our private exponent.
现在这是我遇到麻烦的地方。我一直在仔细阅读维基百科来理解和某处没有连接的东西。我知道，我需要找到模反元素的e (mod phi(n))，这将是d我们的私人指数。
Reading though wikipedia tells us to find the mmi we need to use the Extended Euclidian Algorithm. I've implemented the algorithm in python as follows:
阅读维基百科告诉我们找到我们需要使用扩展欧几里得算法的 mmi 。我在python中实现了算法如下：
def egcd(a, b):
x, lastX = 0, 1
y, lastY = 1, 0
while (b != 0):
q = a // b
a, b = b, a % b
x, lastX = lastX - q * x, x
y, lastY = lastY - q * y, y
return (lastX, lastY)
This is where I am lost. To my understanding now, the equation ax + bx = gcd(a, b) = 1is the same e*x + phi(n)*y = gcd(e, phi(n)) = 1.
So we call egcd(e, phi(n)), and now I get [-367, 2]for my x and y.
这就是我迷失的地方。以我现在的理解，等式ax + bx = gcd(a, b) = 1是一样的e*x + phi(n)*y = gcd(e, phi(n)) = 1。所以我们调用egcd(e, phi(n))，现在我得到[-367, 2]了我的 x 和 y。
From here I honestly don't know where to go. I've read this similar questionand I see that there are some substitutions that happen, but I don't understand how those number relate to the answer that I got or the values I have started out with. Can someone explain to me pragmatically what I need to do from here? (When I say pragmatically, I mean without actual code. Pseudo code is fine, but if I get actual code I won't be able to learn without plagiarism on my assignment which is a big no-no).
从这里我真的不知道该去哪里。我读过这个类似的问题，我看到发生了一些替换，但我不明白这些数字与我得到的答案或我开始的价值观有何关系。有人可以务实地向我解释我需要从这里做什么吗？（当我说务实时，我的意思是没有实际代码。伪代码很好，但如果我得到实际代码，我将无法在没有抄袭我的作业的情况下学习，这是一个很大的禁忌）。
As always, any help is genuinely appreciated. Thanks everyone!
与往常一样，我们真诚地感谢任何帮助。谢谢大家！
(And yes, I have seen these:RSA: Private key calculation with Extended Euclidean Algorithmand In RSA encryption, how do I find d, given p, q, e and c?)
（是的，我看过这些：RSA：使用扩展欧几里得算法的私钥计算和在 RSA 加密中，我如何找到 d，给定 p、q、e 和 c？）
回答by Walker Rowe
The implementation of the Extended Euclidean algorithm you have is not complete, since it is generating a negative number for the private key. Use this code instead:
您所拥有的扩展欧几里得算法的实现并不完整，因为它正在为私钥生成一个负数。请改用此代码：
https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
For your example the private key, d, is 2753.
对于您的示例，私钥 d 是 2753。
p=61
q=53
n = 3233
phi(n)=3120
e=17
d=modinv(17,3120)=2753
Try it out:
试试看：
message m m=65
encryption: m^e mod n = c (65**17) % 3120 = 65
decryption: c^d mod n = m (65**2753) % 3120 = 65
Its all explained here:
一切都在这里解释：
http://southernpacificreview.com/2014/01/06/rsa-key-generation-example/
http://southernpacificreview.com/2014/01/06/rsa-key-generation-example/
回答by Faiyaz Ansari
def egcd(a,b):
s1, s2 = 1, 0
t1, t2 = 0, 1
while b!=0:
q = a//b
r = a%b
a, b = b, r
s = s1-q*s2
s1, s2 = s2, s
t = t1-q*t2
t1, t2 = t2, t
return (s1, t1)
try comparing above.
i will tell you where was your mistake:
a, b = b, a % b
a has the value of b now (b=a%b)==(b=b%b)
and similar reason for proceeding two lines
尝试比较上面。
我会告诉你你的错误在哪里：
a, b = b, a % b
a 现在具有 b 的值 (b=a%b)==(b=b%b)
以及进行两行的类似原因
