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

Question

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

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

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

e = 17

好的很容易.

对于我的任务,我们已经意识到d = 2753,但是我仍然需要能够任意生成这个值.

现在这里是我遇到麻烦的地方.我一直在仔细阅读维基百科以及某些东西没有连接.我知道,我需要找到模反元素的e (mod phi(n)),这将是d我们的私人指数.

通过维基百科阅读告诉我们找到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)),现在我得到[-367, 2]我的x和y.

从这里我老实说不知道去哪里.我已经阅读了这个类似的问题,我发现有一些替代发生,但我不明白这些数字与我得到的答案或我开始的价值观有何关联.有人可以从我这里务实地向我解释我需要做什么吗？(当我说实用时,我的意思是没有实际的代码.伪代码很好,但如果我得到实际的代码,我将无法学习没有抄袭我的任务,这是一个很大的禁忌).

一如既往,任何帮助都是真正的赞赏.感谢大家!

(是的,我已经看到了这些:RSA:使用扩展欧几里得算法和在RSA加密中的私钥计算,我如何找到d,给定p,q,e和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/