RSA：使用扩展的欧几里得算法的私钥计算 [英] RSA: Private key calculation with Extended Euclidean Algorithm

问题描述

我是一名高中生，在RSA上写论文，我正在用一个很小的素数做一个例子。我了解系统的工作原理，但我终生无法使用扩展的欧几里得算法来计算私钥。

I'm a high school student writing a paper on RSA, and I'm doing an example with some very small prime numbers. I understand how the system works, but I can't for the life of me calculate the private key using the extended euclidean algorithm.

这是我到目前为止所做的：

Here's what I have done so far:

• 我选择了质数p = 37
  和q = 89并计算出N = 3293


• 我计算出（p-1）（q-1）= 3168


• 我选择了一个数字e，使得e和3168相对质数。我正在使用标准的欧几里得算法进行检查，效果很好。我的e = 25

现在我只需要计算私钥d，该私钥应满足ed = 1（mod 3168）

Now I just have to calculate the private key d, which should satisfy ed=1 (mod 3168)

使用扩展的欧几里得算法找到d，使得de + tN = 1我得到-887•25 + 7•3168 = 1。我丢掉7，得到d = -887。

Using the Extended Euclidean Algorithm to find d such that de+tN=1 I get -887•25+7•3168=1. I throw the 7 away and get d=-887. Trying to decrypt a message, however, this doesn't work.

我从我的书中知道d应该是2281，它可以工作，但我不知道该怎么做。

I know from my book that d should be 2281, and it works, but I can't figure out how they arrive at that number.

有人可以帮忙吗？在过去的4个小时中，我一直尝试解决此问题，并且一直在寻找答案。我正在手动执行扩展欧几里得算法，但是由于结果可行，所以我的计算应该是正确的。

Can anyone help? I've tried solving this problem for the last 4 hours, and have looked for an answer everywhere. I'm doing the Extended Euclidean Algorithm by hand, but since the result works my calculations should be right.

在此先感谢

疯子

推荐答案

你是如此亲密，自己会踢自己。

You're so close you're going to kick yourself.

3168-887 = 2281。

3168-887=2281.

具体来说，如果您有mod x，则A必须满足 0< = a< x 。如果不是，请根据需要加减x直到您在此范围内。这就是所谓的模块化算术。

Specifically, If you have a mod x, then A must satisfy 0<=a<x. If it doesn't, add or subtract x as many times as necessary until you are in this range. This is called modular arithmetic.

您可能想读一下线性同余和数论。这些主题是英国的学位水平数学（我想您将其称为大学），所以不要担心它看起来有些奇怪。线性一致性只是说 -887 mod 3168 和 2281 mod 3168 实际上是同一回事，因为它们是在同一类别中，该类别在所需范围内显示为 2281 mod 3168 。 2281 + 3168 mod 3168 也将在该课程中。

You might want to read up on linear congruences and number theory. These topics are degree level mathematics in the UK (what you'd call college I guess) so don't worry if it seems a bit odd. A linear congruence simply says that -887 mod 3168 and 2281 mod 3168 are actually the same thing because they are part of the same class, the class that turns out as 2281 mod 3168 in the required range. 2281+3168 mod 3168 would also be in that class.

玩得开心！

PS PARI / GP是理论家用于计算的实用程序编号。可能值得一看。

P.S. PARI/GP is a utility number theorists use for calculations. Might be worth a look.

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