python - 使用扩展欧几里德算法创建 RSA 私钥

Question

这是我在学校做的作业。我在生成私钥时遇到问题。我的主要问题是理解我的方程式之间的关系。为了设置一切，我们有:

p = 61
q = 53
n = p * q (which equals 3233)

从这里我们得到 n (phi(n)) 等于 3120 的总和，现在我们可以选择素数 e；其中 1 < e < 3120

e = 17

好吧，很简单。

对于我的作业，我们已经知道 d = 2753，但是我仍然需要能够任意生成这个值。

现在这是我遇到麻烦的地方。我一直在仔细阅读维基百科以了解某些地方没有连接。我知道我需要找到 modular multiplicative inverse e (mod phi(n)) 的 d，我们的私有(private)指数。

虽然维基百科告诉我们要找到我们需要使用 Extended Euclidian Algorithm 的 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)

这就是我迷路的地方。据我现在的理解，方程 ax + bx = gcd(a, b) = 1 是相同的 e*x + phi(n)*y = gcd(e, phi(n )) = 1。 所以我们调用 egcd(e, phi(n))，现在我的 x 和 y 得到了 [-367, 2]。

老实说，从这里我不知道该去哪里。我读过 this similar question我看到发生了一些替换，但我不明白这些数字与我得到的答案或我开始时的值(value)观有何关系。有人可以务实地向我解释我需要从这里做什么吗？ (当我实用地说时，我的意思是没有实际代码。伪代码很好，但如果我得到实际代码，我将无法在没有抄袭的情况下学习我的作业，这是一个很大的禁忌)。

一如既往，我们真诚地感谢您的帮助。谢谢大家!

(是的，我看过这些:RSA: Private key calculation with Extended Euclidean Algorithm 和 In RSA encryption, how do I find d, given p, q, e and c?)

Answer 1

您拥有的扩展欧几里得算法的实现并不完整，因为它为私钥生成负数。请改用此代码:

https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

对于您的示例，私钥 d 是 2753。

p=61
q=53
n = 3233
phi(n)=3120
e=17
d=modinv(17,3120)=2753

尝试一下:

message m m=65


encryption: m^e mod n = c    (65**17) % 3120 =  65
decryption: c^d mod n = m      (65**2753) % 3120 =   65

一切都在这里解释:

http://southernpacificreview.com/2014/01/06/rsa-key-generation-example/