标题可能不正确，我不确定如何表达我的问题。
我正在尝试使用 Python3.6 编程一种非对称密码，我相信它与 RSA 加密通信使用的密码相似
我对此的逻辑理解如下:
Person1 (p1) picks two prime numbers say 17 and 19
let p = 17 and q = 19
the product of these two numbers will be called n (n = p * q)
n = 323
p1 will then make public n
P1 will then make public another prime called e, e = 7
Person2(p2) wants to send p1 the letter H (72 in Ascii)
To do this p2 does the following ((72 ^ e) % n) and calls this value M
M = 13
p2 sends M to p1
p1 receives M and now needs to decrypt it
p1 can do this by calculating D where (e^D) % ((p-1)*(q-1)) = 1
In this example i know D = 247
With D p1 can calculate p2 message using M^D % n
which successfully gives 72 ('H' in ASCII)
话虽如此，必须适用以下规则:
GCD(e,m) = 1
哪里
m = ((p-1)*(q-1))否则
(e^D) % ((p-1)*(q-1)) = 1 不存在。现在问题来了! :)
在数字不太容易处理的地方计算 D。
现在请告诉我是否有更简单的方法来计算 D，但这就是我开始使用在线帮助的地方。
(我在网上查看的示例使用了不同的值，因此它们如下:
p=47
q=71
n = p*q = 3337
(p-1)*(q-1) = 3220
e = 79
现在我们必须找到 D。我们知道 (e^D) % ((p-1)*(q-1)) = 1
因此 D = 79^-1 % 3220
方程改写为 79*d = 1 mod 3220
这就是我感到困惑的地方
使用常规的欧几里得算法 gcd(79,3220) 必须等于 1 否则实际上可能没有解决方案(我的描述在这里正确吗？)
3220 = 40*79 + 60 (79 goes into 3220 40 times with remainder 60)
79 = 1*60 + 19 (The last remainder 60 goes into 79 once with r 19)
60 = 3*19 + 3 (The last remainder 19 goes into 60 three times with r 3)
19 = 6*3 + 1 (The last remainder 3 goes into 19 6 times with r 1)
3 = 3*1 + 0 (The last remainder 1 goes into 3 three times with r 0)
最后一个非零余数是 gcd。因此 gcd(79,3220) = 1 (应该是)
这里的最后一步我不知道到底发生了什么
有人告诉我通过备份树将 gcd(one) 写为 19 和 3220 的线性组合......
1 = 19-6*3
= 19-6*(60-3*19)
= 19*19 - 6*60
= 19*(79-60) - 6*60
= 19*79 - 25*60
= 19*79 - 25*(3220-40*79)
= 1019*79 - 25*3220
在此之后，我只剩下
1019*79 - 25*3220 = 1，如果我在两边修改 3220，我会得到 1019*79 = 1 mod 3220(包含 3220 的术语会消失，因为 3220 = 0 mod 3220)。
因此 d = 1019。
最佳答案
因此，问题是展开以下序列:
3220 = 40*79 + 60
79 = 1*60 + 19
60 = 3*19 + 3
19 = 6*3 + 1
3 = 3*1 + 0
首先，忘记最后一行并从具有最后一个非空余数的那一行开始。
然后一步步进行:
1 = 19 - 6*3 ; now expand 3
= 19 - 6*(60 - 3*19) = 19 - 6*60 + 18*19
= 19*19 - 6*60 ; now expand 19
= 19*(79 - 1*60) - 6*60 = 19*79 - 19*60 - 6*60
= 19*79 - 25*60 ; now expand 60
= 19*79 - 25*(3220 - 40*79) = 19*79 - 25*3220 + 1000*79
= 1019*79 - 25*3220 ; done
请注意，这个想法是在每一步扩展之前的剩余部分。例如，当用
19 扩展余数 79 - 1*60 时，您将 19*19 - 6*60 转换为 19*(79 - 1*60) - 6*60 。这让您可以围绕 79 和 60 重新组合并继续前进。关于algorithm - 有人可以解释这个 RSA 示例的最后部分发生了什么吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46913806/