从RSA中的n，e，p，q计算d？ [英] Calculate d from n, e, p, q in RSA?

问题描述

不知道这是否是询问密码学问题的正确位置，但是在这里。

Not sure if this is the correct place to ask a cryptography question, but here goes.

我正在尝试在RSA中计算 d，我有算出p，q，e，n和ø（n）;

I am trying to work out "d" in RSA, I have worked out p, q, e, n and ø(n);

p = 79, q = 113, e = 2621

n = pq                   ø(n) = (p-1)(q-1)
n = 79 x 113 = 8927      ø(n) = 78 x 112 = 8736

e = 2621
d = ???

我似乎找不到d，我知道d的意思是.. ed modø（n）=1。将不胜感激

I cant seem to find d, I know that d is meant to be a value that.. ed mod ø(n) = 1. Any help will be appreciated

例如，e = 17，d = 2753，ø（n）= 3120

As an example would be e = 17, d = 2753, ø(n) = 3120

17 * 2753 mod 3120 = 1

推荐答案

您正在寻找 e （mod n ）的模逆，可以使用扩展的欧几里得算法：

You are looking for the modular inverse of e (mod n), which can be computed using the extended Euclidean algorithm:

function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q := b // x # integer division
        x, a, b, u := b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

因此，在您的示例中， inverse（17，3120） = 2753和 inverse（2621，8736） =4373。如果您不想实现算法，您可以向 Wolfram | Alpha 寻求答案。

Thus, in your examples, inverse(17, 3120) = 2753 and inverse(2621, 8736) = 4373. If you don't want to implement the algorithm, you can ask Wolfram|Alpha for the answer.

这篇关于从RSA中的n，e，p，q计算d？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！