解密RSA下小整數
讓 $ (n,e) $ 是RSA公鑰。認為 $ c = m^e \pmod n $ ， 在哪裡 $ c>1 $ 是一個非常小的整數。為了具體，說 $ c=2 $ 然後 $ e = 65537 $ .
是很難找到 $ m $ 根據RSA假設（或任何變體）？
由於RSA問題假設辛苦，我們不知道，找不到的因式分解 $ n $ .
我們知道，（從標準RSA），其 $ m=c^{\left(e^{-1}\bmod\varphi(n)\right)}\bmod n $ 滿足需求 $ c\equiv m^e\pmod n $ ，但我們不知道如何計算 $ m $ 如果沒有一些額外的資訊或Oracle。
是很難找到 $ m $ 根據RSA假設（或任何變體）？
是的，但我沒有更好的理由比：整數之中 $ c>1 $ 獨立於 $ n $ , 只有精確 $ e^\text{th} $ 眾所周知，權力可以很容易地解決任意的 RSA 問題 $ n $ 太大而無法考慮和奇怪 $ e>1 $ 製造 $ (n,e) $ 有效的 RSA 公鑰。此外，沒有這樣的 $ c $ 在區間 $ [2,2^e) $ , 其中與 $ e=65537 $ 正如OP 的評論一樣，包括所有常用的值 $ n $ ，因此 $ c $ .
求解 $ c\equiv m^e\pmod n $ 對於小 $ c $ 其他人不一定難 $ c $ 並且無論何時 $ n $ 很難考慮。反例證明： $ c=2 $ , $ e=65537 $ , $ n=(3^{65537}-2)/29 $ . 我不能考慮這一點 $ n $ ，但很容易找到解決方案 $ m=3 $ .
更正式地說：我對小固定奇數的 RSA 問題的難度有信心 $ e>1 $ [即：求解 $ m $ 方程 $ c=m^e\bmod n $ 對於隨機 $ c $ 什麼時候 $ n $ 被構造為大素數的乘積 $ p_i $ 在這些中隨機選擇，使得 $ \gcd(p_i-1,e)=1 $ ] 因為我的問題僅限於小 $ c>1 $ . 然而，如果我們能證明前一個問題的硬度意味著後一個問題的硬度，我會感到非常驚訝。
首先你不能擁有 $ e = 2 $ 或者 $ e = 4 $ 因為為了生成私有指數 $ d $ 你需要 $ e $ 與 $ \phi(n) $ 自從 $ d = e^{-1} $ 裡面 $ \mathbb{Z}/n\mathbb{Z} $
而且因為 $ n = pq $ 在哪裡 $ p $ 和 $ q $ 是素數（因此是奇數），
$ \phi(n) = (p-1)(q-1) $ ， 所以 $ \phi(n) $ 甚至。
這就是為什麼 $ e $ 必須是奇數（與偶數互質）。
有了這個說，讓我們假設一個小 $ e > 1 $ 奇怪的，像 $ 3 $ .
讓 $ m $ 成為資訊， $ c = m^e \mod n $ 密文和 $ d $ 私人指數。
模數的典型長度（以字節為單位） $ n $ 是 $ 1024 $ , $ 2048 $ 甚至更大，所以你可以想像這個數字有多大。
如果加密是在沒有任何填充的情況下進行的，那麼您有機會 $ m $ 不是很大，例如如果消息只是將字元串轉換為整數。
在這些條件下，您可以擁有 $ c = m^e < n $ ， 所以 $ m = \sqrt[e]{c} $
如果不是這種情況，您可以嘗試一些小的值 $ k $ 這樣：
$ m = \sqrt[e]{c + kn} $
請注意，這也是可能的，以防萬一 $ e $ 是“正常”值，但 $ n $ 是誇張的大。
另請注意，這在正常情況下是不可能的，因為消息被填充，因此小消息也會產生非常大的數字。（而且當然 $ e $ 和 $ n $ 選擇準確）