使用扩展欧几里德算法创建RSA私钥 [英] Using Extended Euclidean Algorithm to create RSA private key

问题描述

这是一个任务我做上学。我无法生成私钥。我的主要问题是理解我的方程彼此的关系。要设置好一切，我们有：

This is for an assignment I'm doing through school. I am having trouble generating a private key. My main problem is understanding the relation of my equations to each other. To set everything up, we have:

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

从这里，我们有N个的totient（岛（N）），这等于3120，现在我们可以选择推动电子;其中1＆LT; E＆LT; 3120

From here we have the totient of n (phi(n)) which equals 3120, now we can choose prime e; where 1 < e < 3120

e = 17

好易就够了。

Okay easy enough.

有关我的任务，我们已经意识到了 D = 2753 ，但是我仍然需要能够任意生成此值。

For my assignment we've been made aware that d = 2753, however I still need to be able to arbitrarily generate this value.

现在这里是我有麻烦。我已经仔细阅读维基百科了解和地方一些不连接。我知道，我需要找到模反元素电子商务（MOD岛（N））将在 D ，我们的私人指数。

Now here is where I am having trouble. I've been perusing wikipedia to understand and somewhere something isn't connecting. I know that I need to find the modular multiplicative inverse of e (mod phi(n)) which will be d, our private exponent.

阅读虽然维基百科告诉我们，找到MMI，我们需要使用扩展欧几里德算法。我已经实现了算法蟒蛇如下：

Reading though wikipedia tells us to find the mmi we need to use the Extended Euclidian Algorithm. I've implemented the algorithm in python as follows:

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 +岛（N）* Y = GCD（E，披（N））= 1 。 所以我们称之为 egcd（即岛（N）），现在我得到 [ - 367，2] 的我x和y。

This is where I am lost. To my understanding now, the equation ax + bx = gcd(a, b) = 1 is the same e*x + phi(n)*y = gcd(e, phi(n)) = 1. So we call egcd(e, phi(n)), and now I get [-367, 2] for my x and y.

在这里，我真的不知道哪里去了。我读过<一个href="http://math.stackexchange.com/questions/67171/calculating-the-modular-multiplicative-inverse-without-all-those-strange-looking">this类似的问题，我看到有一些替换的发生，但我不明白如何将这些数字涉及到，我得到了答案或者我已经开始了的值。可有人向我解释务实什么，我需要在这里做什么？ （当我说实事求是，我的意思是没有实际code。伪code是好的，但如果我得到实际的code我就不能学而不抄袭我的任务是一大禁忌否）。

From here I honestly don't know where to go. I've read this similar question and I see that there are some substitutions that happen, but I don't understand how those number relate to the answer that I got or the values I have started out with. Can someone explain to me pragmatically what I need to do from here? (When I say pragmatically, I mean without actual code. Pseudo code is fine, but if I get actual code I won't be able to learn without plagiarism on my assignment which is a big no-no).

一如往常，任何帮助是真正的AP preciated。谢谢大家！

As always, any help is genuinely appreciated. Thanks everyone!

（是的，我已经看到了这些：<一href="http://stackoverflow.com/questions/4422633/rsa-private-key-calculation-with-extended-euclidean-algorithm?rq=1">RSA:私钥计算与扩展欧几里得算法和<一href="http://stackoverflow.com/questions/16310871/in-rsa-encryption-how-do-i-find-d-given-p-q-e-and-c">In RSA加密，我怎么求d，由于P，Q，E和C？）

(And yes, I have seen these:RSA: Private key calculation with Extended Euclidean Algorithm and In RSA encryption, how do I find d, given p, q, e and c?)

推荐答案

扩展欧几里德算法你的实现是不完整的，因为它产生负数私钥。使用此code来代替：

The implementation of the Extended Euclidean algorithm you have is not complete, since it is generating a negative number for the private key. Use this code instead:

<一个href="https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm" rel="nofollow">https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

有关您的例子公钥，D，是2753。

For your example the public key, d, is 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

它的一切都在这里解释的：

Its all explained here:

http://southernpacificreview.com/2014/01/06 / RSA密钥产生，例如/

这篇关于使用扩展欧几里德算法创建RSA私钥的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！