有人能解释一下这个RSA示例的最后部分发生了什么吗

Question

标题可能不正确，我不确定如何表达我的问题

我正试图用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))

否则CCD_ 2不存在。

现在发布！：)

在数字不太容易处理的情况下计算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(793220)必须等于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(793220)=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修改3220

(包含3220的术语消失了，因为3220＝0 mod 3220)。

因此d=1019。

Answer 1

因此，问题在于展开以下序列：

3220 = 40*79 + 60
79 = 1*60 + 19
60 = 3*19 + 3
19 = 6*3 + 1
3 = 3*1 + 0

首先，忘记最后一行，从具有最后一个非null余数的行开始。

然后逐步进行：

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

请注意，这个想法是在每个步骤中扩展前面的余数。例如，当用：79 - 1*60展开余数19时，可以将19*19 - 6*60转换为19*(79 - 1*60) - 6*60。这使您可以围绕79和60重新组合并继续前进。