为什么 RSA 的安全性取决于模数 n 的不可分解性？
Why does the security of RSA depend on the non-factorability of the modulus n?
只是想知道为什么 RSA 的安全性取决于模数 n 的不可分解性？
干杯！
RSA 中的 public 数据是 n - public modulus 和 e - public 指数。秘密是 d - 私有指数。
创建参数时，您首先生成两个随机素数 p 和 q，然后计算 public modulus n = p*q。所以 p 和 q 是 n 的因式分解。实际上你可以使用更多的素数，但大多数只使用两个。
然后选择 public 指数 e，它通常是一个小质数，例如 65537 或 17 甚至 3。
你的秘密指数 d 将是 d = 1/e mod (p-1)(q-1).
很明显，如果知道 p 和 q，任何人都可以计算 d，这就是因式分解。
嗯……modulus n 的不可分解性并不是全部……
正如 vlad 已经指出的，如果您知道 n 的因数，您可以轻松计算私有指数...
(p-1)(q-1) ... 或更多一般... 如果您知道数字 n 的质因数 P[i]，那么您可以计算所有 (P [i] - 1)... 即欧拉 PHI 函数 ... 知道可逆乘法元素的个数 mod n
如果你可以对 n 进行因式分解，那么计算就会变得微不足道...如果 n 仅由 2 个大素数组成，并且该因式分解很困难，那并不是很简单...
但是......如果你想出另一种计算 PHI(n) 的想法......元素的数量 modn 具有乘法逆......因式分解可能不再是你的问题...
目前没有其他 public 已知的计算 phi 的方法，除了欧拉方法 ... prod(P[i] - 1)
因此，无论是找到因式分解的方法，还是以不同的方式计算 PHI(n)，都可能会导致破坏 RSA
只是想知道为什么 RSA 的安全性取决于模数 n 的不可分解性？
干杯！
RSA 中的 public 数据是 n - public modulus 和 e - public 指数。秘密是 d - 私有指数。 创建参数时，您首先生成两个随机素数 p 和 q，然后计算 public modulus n = p*q。所以 p 和 q 是 n 的因式分解。实际上你可以使用更多的素数，但大多数只使用两个。 然后选择 public 指数 e，它通常是一个小质数，例如 65537 或 17 甚至 3。 你的秘密指数 d 将是 d = 1/e mod (p-1)(q-1).
很明显，如果知道 p 和 q，任何人都可以计算 d，这就是因式分解。
嗯……modulus n 的不可分解性并不是全部……
正如 vlad 已经指出的，如果您知道 n 的因数，您可以轻松计算私有指数...
(p-1)(q-1) ... 或更多一般... 如果您知道数字 n 的质因数 P[i]，那么您可以计算所有 (P [i] - 1)... 即欧拉 PHI 函数 ... 知道可逆乘法元素的个数 mod n
如果你可以对 n 进行因式分解，那么计算就会变得微不足道...如果 n 仅由 2 个大素数组成，并且该因式分解很困难，那并不是很简单...
但是......如果你想出另一种计算 PHI(n) 的想法......元素的数量 modn 具有乘法逆......因式分解可能不再是你的问题...
目前没有其他 public 已知的计算 phi 的方法，除了欧拉方法 ... prod(P[i] - 1)
因此，无论是找到因式分解的方法，还是以不同的方式计算 PHI(n)，都可能会导致破坏 RSA