gpt4 book ai didi

algorithm - RSA:使用扩展欧几里德算法计算私钥

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:17:55 26 4
gpt4 key购买 nike

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

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

  • 我选择了质数 p=37q=89,计算出N=3293
  • 我已经计算出 (p-1)(q-1)=3168
  • 我选择了一个数 e,使 e 和 3168 互质。我正在使用标准欧几里得算法对此进行检查,并且效果很好。我的 e=25

现在我只需要计算私钥d,它应该满足ed=1 (mod 3168)

使用扩展欧几里得算法求 d 使得 de+tN=1 我得到 -887•25+7•3168=1。我把 7 扔掉,得到 d=-887。然而,尝试解密一条消息是行不通的。

我从我的书中知道 d 应该是 2281,而且它有效,但我不知道他们是如何得出这个数字的。

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

提前致谢

疯狂

最佳答案

你离得太近了,你会踢自己。

3168-887=2281.

具体来说,如果你有一个 mod x,那么 A 必须满足 0<=a<x .如果不是,则根据需要多次加减 x,直到您位于该范围内。这称为模运算。

您可能想阅读有关线性同余和数论的内容。这些主题是英国的学位水平数学(我猜你称之为大学)所以如果看起来有点奇怪,请不要担心。线性同余简单地说 -887 mod 31682281 mod 3168实际上是同一件事,因为它们属于同一类,结果为 2281 mod 3168 的类在要求的范围内。 2281+3168 mod 3168也会在那个类(class)。

玩得开心!

附言PARI/GP 是效用数理论家用于计算的。可能值得一看。

关于algorithm - RSA:使用扩展欧几里德算法计算私钥,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4422633/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com