为什么在RSA或Euler定理中使用乘法群而不是加性？

Question

我快要理解RSA了，但突然想到了一个问题。当我们计算U(N)，即U(PQ)时，我们取的是与N同质化的可逆元素。例如，U(5\times2)变成了\{1,3,7,9\}。我们最终不会在密钥生成或加密中使用U(N)中的逆。但我们需要的只是U(N)的顺序。我们按照U(N)的顺序使用可逆元素作为密钥生成的一部分，这部分我理解为什么，但是永远不会在U(N)内部使用可逆元素。所以问题是，为什么我们不使用相加群？这是安全问题吗？PS，我对加性群不太了解，只是乘法群，因为它是RSA的一部分，我正在研究RSA。谢谢:)

Answer 1

为什么我们不使用加法群？这是安全问题吗？

是的，这是出于安全考虑。如果我们使用加性组(\Bbb Z_N,+)而不是(\Bbb Z_N^*,*)来实现RSA，那么公开加密就会变成M\mapsto C=e\,M\bmod N而不是M\mapsto C=M^e\bmod N。问题是，解密很简单，因为任何拥有公钥(N,e)的人都可以计算d=e^{-1}\bmod N (例如使用扩展的欧几里得算法)，然后解密为S\mapsto M=d\,S\bmod N，而不知道N的因式分解。

这与(\Bbb Z_N,+)是公钥(N,e)的N部分的顺序有关，而(\Bbb Z_N^*,*)的顺序是\Phi(N)，这很难从公钥中获得。

Answer 2

你的问题还不清楚。你想使用哪一类添加剂？因为组{\mathbb Z}_N^*有未知的顺序(假设N的因式分解是未知的)，所以RSA很难实现。哪个相加群具有这种性质？