给定p、q和e的值，但gcd(e,phi)不为1，那么如何在RSA中找到n和d？甚至有可能吗？

Question

值为：p = 19、q = 23 和 e = 3. 按照算法计算：n = 437 & phi = 396。但我认为 RSA 在这里无效，因为 GCD(e, phi) 在这种情况下不是 1，因为 GCD(3, 396) = 3。所以，这意味着 RSA 算法不满足，不能进一步计算 d，对吗？

我想问我假设由于 GCD(e,phi) 给定的 p、q 和 e 值没有解是否正确= 1 不满意。

还是我做错了什么？这是我正在解决的以前试卷中出现的原始问题：（逐字）

In RSA, given p=19, q=23 and e=3, find n and d.

我愿意假设这是一个棘手的问题，它检查一个人是否知道算法（及其步骤）。请让我知道我的假设是否正确，在此先感谢！ :)

Answer 1

你是对的。运行 Extended Euclidean Algorithm 计算 ModInv(3, 396) 我们得到

ModInverse(3, 396)
  r=396, newR=3, t=0, newT=   1
  r=  3, newR=0, t=1, newT=-132

  newR == 0 && r > 0: Not Invertible.

因此 d 没有价值。（根据 lambda(n) 而不是 phi(n) 计算它也会产生 "Not invertible"，因为 lambda 只是 phi/2 而 3 是破坏事物的主要因素。）

给定p、q和e的值，但gcd(e,phi)不为1，那么如何在RSA中找到n和d？甚至有可能吗？

Given values for p, q and e, but gcd(e,phi) is not 1, then how to find n & d in RSA? Or is it even possible?

cryptography

rsa