為什麼 RSA 的橢圓曲線變體“主要是學術興趣”？
昨天我在考慮流行協議/算法（ECDH，ECES）的橢圓曲線變體
$$ 1 $$等），然後我想到我從未見過 RSA 的橢圓曲線變體。我對 RSA 和橢圓曲線的理解告訴我這應該是可能的。 經過一番搜尋，我找到了以下解釋（類似引用）：
正如我們所提到的，存在與 RSA 類似的橢圓曲線，但事實證明，這些主要是出於學術興趣，因為它們與 RSA 相比基本上沒有任何實際優勢。這主要是因為RSA 的橢圓曲線變體的安全性實際上依賴於與 RSA 相同的潛在問題，即整數分解問題。
這讓我開始思考。我曾認為我之前提到的基於離散對數的系統也是基於相同的潛在問題，即離散對數。但文章有這樣的說法：
這種情況與離散對數密碼系統的變體不同。離散對數密碼系統的橢圓曲線變體的安全性取決於對橢圓曲線的傳統離散對數問題的重述。這種重述使得在所謂的次指數時間內解決傳統離散對數問題的目前算法在解決類似的橢圓曲線問題方面幾乎沒有價值。相反，解決這些橢圓曲線問題的唯一可用算法是在所謂的指數時間內執行的更通用的技術。
所以現在，我的問題是：為什麼我們能夠重述離散對數問題以使其在橢圓曲線上更實用，而不是 RSA 問題？
- ECES是ElGamal的橢圓曲線變體
通用離散對數問題是這樣的：
給定一組 $ (G, ·) $ 帶發電機 $ g $ 和 $ y \in G $ ， 尋找 $ x \in \mathbb N $ 這樣 $ y = g^x $ .
“經典”離散對數問題（“經典”DSA 和 ECDSA 中使用的問題）與素數域的（乘法）組的某個子組有關，即 $ (\mathbb Z/p \mathbb Z)^* $ :
給定一個素數 $ p $ , 一個生成器 $ g $ （一些大的子群）和 $ y \in \left<g\right> $ ， 尋找 $ x \in \mathbb N $ 這樣 $ y = g^x \bmod p $ .
橢圓曲線離散對數問題是橢圓曲線群的子群：
給定一條橢圓曲線 $ (E, +) $ , 一個生成器 $ G $ 一些大的子群，和 $ y \in \left<G\right> $ ， 尋找 $ x \in \mathbb N $ 這樣 $ y = x · G $ .
有通用算法（例如嬰兒步巨步算法）用於求解任何組中的離散對數（假設一個可計算的組律，或者甚至只是預言機訪問組律），這些對橢圓曲線工作得很好組，以及經典的素數場。這些算法的平均執行時間通常取決於組的大小，例如 $ O(\sqrt{|G|}) $ 為嬰兒步巨步。這仍然是輸入大小的指數（因為輸入大小在 $ O(\log|G|) $ ，如果沒有選擇非常愚蠢的編碼）。
但是對於某些特殊組，離散對數更容易，因為它們具有更多（和已知）的結構。作為一個極端情況，考慮加法組 $ (\mathbb Z/n \mathbb Z, +) $ （對於任何正整數 $ n $ )，與任何發電機。即使對於相當大的問題，也很容易解決這個問題 $ n $ – 我們只需要一個模除法，即擴展歐幾里得算法的一次執行。（如果生成器是固定的，我們甚至可以計算一次它的乘法逆元並在以後重用它，然後每個問題都可以乘法一次。）
素數域的乘法群更難。沒有已知的多項式時間算法，但仍有一些算法比通用算法更快，使用次指數時間。（是的，指數和多項式之間存在一些差距。）用於分解整數的數字域篩實際上也可以用於計算素數組中的離散對數（並且對於兩個問題的相似輸入大小需要相似的執行時間）。
因此，對於相同的“安全級別”，我們需要比通用組更大的素數欄位組。
對於某些橢圓曲線，看起來離散對數幾乎與相同大小的通用組一樣難，這意味著沒有比通用算法快得多的專門算法。（當有時，稱相應的組為“壞”。）
效果是，對於類似的安全級別，我們可以使用比素數組更小的橢圓曲線組（事實證明，對於這些更小的組，計算速度也更快）。
另一方面，看看RSA 問題。這是關於這個的：
給定 $ n $ （兩個大的未知素數的乘積）， $ e $ （和 $ \operatorname{gcd}(m,e) = 1) $ 和 $ x < n $ , 我們尋找 $ m $ 這樣 $ x = m^e \bmod n $ .
解決這個問題的最有效的已知方法（除了可能對 $ m $ 當它來自一個小的子空間時）是通過分解模數，然後計算私鑰 $ d $ 並解密。所以這裡的難題是模數分解。
目前尚不清楚如何將其推廣到任何組（或其他類型的結構）。我發現了具有小擴展因子的語義安全橢圓曲線 RSA 方案（2002 年），它引用（並包括描述）早期工作（N. Demytko。基於 RSA 的新橢圓曲線類似物。EUROCRYPT ‘93，LNCS 765 40–49（1993 年）。）
Demytko 的方案適用於環上的橢圓曲線（及其扭曲） $ \mathbb Z/n\mathbb Z $ （在哪裡 $ n $ 仍然是兩個大素數的乘積），並使用加密 $ c = e \star m $ ， 哪一個是 $ x $ - 座標 $ e·(m,y) $ 對於一些 $ y $ 這樣它就在曲線上，並解密密文 $ c $ 作為 $ m = d \star c $ ， 在哪裡 $ d $ 是四個倒數之一 $ e $ ，這取決於 $ c $ 使用哪一個。
第二個甚至在曲線上工作 $ \mathbb Z/n^2 \mathbb Z $ （但聲稱在語義上是安全的，因為它包含了一個隨機組件）。
在這兩種情況下，打破這種情況的最簡單方法似乎是考慮因素 $ n $ （在自然數中），而不是基於橢圓曲線的結構中的一些類似問題。
這表示 $ n $ 必須和 RSA 一樣大，因此我們有相應的大曲線——在這裡使用橢圓曲線並不是真正的優勢。