6

这是我在学校做的作业。我无法生成私钥。我的主要问题是理解我的方程之间的关系。要设置所有内容，我们有：

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: Private key calculation with Extended Euclidean Algorithm and In RSA encryption, how do I find d, given p, q, e and c?）

4

2 回答 2

7

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

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/

于 2014-01-06T01:03:40.333 回答
2 
def egcd(a,b):   
    s1, s2 = 1, 0   
    t1, t2 = 0, 1   
    while b!=0:   
        q = a//b    
        r = a%b   
        a, b = b, r     
        s = s1-q*s2    
        s1, s2 = s2, s      
        t = t1-q*t2    
        t1, t2 = t2, t    
    return (s1, t1)

尝试在上面进行比较。

我会告诉你你的错误在哪里：

a, b = b, a % b

a 现在具有 b 的值 (b=a%b)==(b=b%b)
以及进行两行的类似原因

于 2018-03-08T16:29:12.693 回答