有人可以解释这个 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))

否则(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 如果我在两边 mod 3220 我得到 1019*79 = 1 mod 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

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

然后一步步进行：

   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 重新组合并继续前进。

有人可以解释这个 RSA 示例的最后部分发生了什么吗？

Can someone explain what is happening with the final part of this RSA example?

encryption

algorithm

rsa

linear-algebra

python-3.x