證明具有非平方自由模的 RSA 加密函式不是置換
這是手頭問題的背景。在學習 RSA 時，我想出了一個問題，如果 $ p $ 和 $ q $ 參與模數計算實際上不是素數？已經有一個相關的主題（為什麼 RSA 需要 p 和 q 是素數？）。雖然大多數答案歸結為效率和安全性考慮，但有一個答案指出，具有由素數冪組成的模數的 RSA 加密函式失去了它的雙射特性，即它不再是排列。但是，此行為僅在範例中顯示，沒有任何證據。
鑑於此，我已經開始搜尋 RSA 置換屬性的證明，並且在這裡找到了這樣的證明。但同樣，它指出該證明僅在以下情況下才有效 $ p \ne q $ , 雖然目前還不清楚為什麼它不適合 $ p = q $ .
然後我就開始自己挖了。實際上，這似乎很清楚 $ p = q $ 情況如果 $ p $ 是素數。那麼對於 $ N = p^2 $ ，我們得到了一組明文 $ {m_i} $ 這樣 $ 0 \leq m_i < N $ 和 $ m_i \equiv 0\pmod{p} $ ，並且有指數 $ e > 2 $ 我們也得到了 $ m_i^e \equiv 0\pmod{p^2} $ .
但我不確定如何概括案例 $ N = p^s, s > 2 $ ; $ N=p^sq, s > 1 $ ; $ N=p^sq^r, s > 2, r > 2 $ . 讓我們以第二種情況為例。讓 $ N=5^23= 75 $ ， 然後 $ \phi(N) = (5^2 - 5)(3 - 1) = 40 $ ， 和 $ e=3 $ 是可接受的指數。接下來如果我計算所有 $ c_i=m_i^3\pmod{75} $ 對所有人 $ 0 < m_i < 75 $ ，我看到有3組disinct $ m_i $ 給出相同的值 $ c_i $ 加密後：
- $ c_i = 0, m_i={0, 15, 30, 45, 60} $
- $ c_i = 50, m_i={5, 20, 35, 50, 65} $
- $ c_i = 25, m_i={10, 25, 40, 55, 70} $
想到這個 $ c_i $ 值我發現了以下模式 $ 5^3 \equiv 50\pmod{75} $ , $ 5^32\equiv 25\pmod{75} $ , $ 5^33 \equiv 0\pmod{75} $ , $ 5^34 \equiv 50\pmod{75} $ 等等。鑑於很明顯：
- 為了 $ m_i = 5(3k_j + 0)\pmod{75}, k_j \geq 0 $ 我們有 $ c_i = 0 $
- 為了 $ m_i = 5(3k_j + 1)\pmod{75}, k_j \geq 0 $ 我們有 $ c_i = 50 $
- 為了 $ m_i = 5(3k_j + 2)\pmod{75}, k_j \geq 0 $ 我們有 $ c_i = 25 $
這就是我堅持的地方。我試圖探索的例子 $ N = p^s $ 和 $ N=p^sq^r $ 並發現了類似的模式，如上圖所示。但是我仍然需要一些線索來概括這種行為並證明具有非平方自由模的 RSA 加密不是排列。我相信我應該缺少一些簡單的概念，但由於我不太喜歡數論，所以我需要社區幫助。
只是為了澄清。我對以下方面的效率和安全考慮完全滿意 $ p $ 和 $ q $ 是兩個截然不同的素數。我唯一擔心的是 RSA 加密函式雙射屬性（或者它是不存在的，就是這種情況）。
提前致謝。
UPD
@poncho 對多個原像的存在給出了明確的解釋 $ c = 0 $ . 但是，概括其他可以具有多個原像的密文的存在也是很好的。
雖然大多數答案歸結為效率和安全性考慮，但有一個答案指出，具有由素數冪組成的模數的 RSA 加密函式失去了它的雙射特性，即它不再是排列。但是，此行為僅在範例中顯示，沒有任何證據。
展示起來相當簡單（假設 $ e>1 $ ; 和 $ e=1 $ ，這是一種排列，但不是很有趣）。
一個值 $ N $ 如果有值，則為非平方自由 $ p>1, q $ 這樣 $ N = p^2q $ （注意 $ q $ 可能有 $ p $ 作為一個因素）。如果是，那麼考慮對這兩個值進行加密 $ 0 $ 和 $ pq $ . 在這兩種情況下，我們有：
$$ 0^e \equiv 0 \pmod N $$
$$ (pq)^e \equiv p^eq^e \equiv p^{2+x}q^{1+y} \pmod N $$
為了 $ x = e-2 $ 和 $ y = e-1 $ . 現在，兩者 $ x, y \ge 0 $ ， 所以 $ p^{2+x}q^{1+y} $ 是的倍數 $ p^2q $ , 所以後者等價於 $ 0 \bmod N $
由於這兩個不同的明文映射到相同的密文0，所以映射不能是雙射的。