我們應該相信 NIST 推薦的 ECC 參數嗎？
根據斯諾登文件，媒體最近發表的文章表明，美國國家安全域積極嘗試通過將弱點嵌入商業部署技術（包括至少一項 NIST 標準）來實現監視。
NIST FIPS 186-3 標準為可用於橢圓曲線加密的曲線提供推薦參數。這些推薦的參數被廣泛使用；人們普遍認為它們是一個合理的選擇。
**我的問題。**我們可以相信這些參數嗎？有什麼方法可以驗證它們是否以誠實的方式生成，以使其不太可能包含後門？
擔心的原因。 Bruce Schneier 寫道，他看到了一堆秘密的斯諾登文件，在看到它們之後，他推薦經典的基於整數離散對數的密碼系統，而不是橢圓曲線密碼學。當被要求詳細說明為什麼他認為我們應該避免使用橢圓曲線密碼學時，他寫道：
我不再相信常數。我相信美國國家安全域通過他們與工業界的關係操縱了他們。
這表明如果我們使用 ECC，我們應該仔細研究如何選擇“常數”（曲線參數）。這是事情看起來令人擔憂的地方。我最近在 tor-talk 郵件列表上閱讀了一條消息，該消息似乎表明 NIST 曲線參數不是以可驗證的方式生成的。該消息檢查參數是如何生成的：
我查看了 P-xxxr 曲線的隨機種子值。例如，P-256r 的種子是 c49d360886e704936a6678e1139d26b7819f7e90。沒有為該值提供任何理由。
並最終得出結論：
我現在個人認為這是參數被煮熟的吸煙證據。
根據我對 FIPS 186-3 的閱讀，這似乎是對生成 P-xxxr 曲線的過程的準確描述。那麼，人們應該關注這個嗎？或者這只是基於對國家安全域失去信任的偏執狂？
另請參閱Dan Bernstein 和 Tanja Lange 的這些幻燈片，特別是第 6-7、8-10、14-17 頁，以進一步討論 NIST 參數選擇。
**編輯：**我做了一些測試，我發現了一些奇怪的東西。見最後。
初步答案：
至少Koblitz 曲線（NIST 術語中的 K-163、K-233 ……）不能被特別“煮熟”，因為整個過程非常透明：
- 從二進製欄位開始 $ GF(2^m) $ . 對於每個m只有一個這樣的欄位（您可以有多種表示形式，但它們都是同構的）。
- 將自己限制在m的質數範圍內，以避免通過進入子欄位來避免可能的弱點。
- 考慮曲線 $ Y^2+XY=X^3+aX^2+b $ 在哪裡 $ b \ne 0 $ ; 這是二元場中非超奇異曲線的正常形式。
- 你只想要曲線 $ a = a^2 $ 和 $ b = b^2 $ ，這樣您就可以使用Frobenius 內同態加快計算速度（基本上，您可以用簡單地對兩個座標進行平方來替換點倍增，這非常快）。
- 什麼時候 $ a = 0 $ ，曲線階數必然是4的倍數；什麼時候 $ a = 1 $ ，必須是 2 的倍數。
然後你想要一個“盡可能素數”的曲線順序，即等於 $ 2p $ 或者 $ 4p $ 為了一個素數 $ p $ （取決於是否 $ a = 1 $ 或者 $ 0 $ ）。為了 $ m $ 在“有趣的範圍”（比如 160 到 768）範圍內，您不會找到很多合適的曲線（我不記得確切的計數，但大概是 6 或 7 條曲線）。NIST 簡單地取了其中的 5 個對應於 $ m $ 最接近（但不低於）其“安全級別”（80、112、128、192 和 256 位“等效強度”）的值。這裡沒有“做飯”的空間。
所以我想說，至少 Koblitz 曲線顯然沒有所有這些“烹飪”謠言。當然，其他一些人認為 Koblitz 曲線有一些特殊的結構，可以用來進行更快的攻擊。這在兩個方面是正確的：
- 更快的計算意味著更快的攻擊，機械地；
- 可以求解離散對數“模 Frobenius 內同態”，這意味著 K-233 與 225 位曲線一樣強（因為 233 是一個 8 位數字）。
我仍然認為這樣的曲線是嚴肅的密碼學工作的合理候選者。他們已經“在野外”至少 15 年了，仍然毫髮無損，這還不錯，因為這些事情發生了。
編輯：我做了一些測試，列舉了所有 Koblitz 曲線 $ GF(2^m) $ 為了 $ m $ 範圍從 3 到 1200。對於每個 $ m $ ，有兩條曲線要測試，對於 $ a = 0 $ 和 $ a = 1 $ . 如果它的階數等於，我們認為曲線是“合適的” $ 4p $ （為了 $ a = 0 $ ） 或者 $ 2p $ （為了 $ a = 1 $ ） 和 $ p $ 素數（這是“最好的”，因為曲線始終是同一曲線的延伸 $ GF(2) $ , 所以曲線階數必然是曲線的倍數 $ GF(2) $ , 那是 4 或 2, 取決於 $ a $ ）。對於“有趣的範圍” $ m $ 在 160 和 768 之間，有14 條合適的曲線：
- $ m = 163 $ , $ a = 1 $
- $ m = 233 $ , $ a = 0 $
- $ m = 239 $ , $ a = 0 $
- $ m = 277 $ , $ a = 0 $
- $ m = 283 $ , $ a = 0 $
- $ m = 283 $ , $ a = 1 $
- $ m = 311 $ , $ a = 1 $
- $ m = 331 $ , $ a = 1 $
- $ m = 347 $ , $ a = 1 $
- $ m = 349 $ , $ a = 0 $
- $ m = 359 $ , $ a = 1 $
- $ m = 409 $ , $ a = 0 $
- $ m = 571 $ , $ a = 0 $
- $ m = 701 $ , $ a = 1 $
NIST 的目標是它們的 80、112、128、192 和 256 位這五個“安全級別”，並且只有當其大小至少是該級別的兩倍時，曲線才會匹配該級別。所以每個級別的標準曲線應該是對該級別足夠大的最小曲線。這應該分別產生大小為 163、233、277、409 和 571 位的欄位中的 Koblitz 曲線。
奇怪的是，這符合 NIST 的選擇，除了他們選擇的“128 位”級別 $ m = 283 $ 代替 $ m = 277 $ . 我不知道這是什麼原因。對於這兩種欄位大小，最小可能的歸約多項式是五項式 ( $ X^{277}+X^{12}+X^{6}+X^{3}+1 $ 為了 $ m = 277 $ , $ X^{283}+X^{12}+X^{7}+X^{5}+1 $ 為了 $ m = 283 $ )，因此在使用多項式基時，兩個欄位都沒有計算優勢（嗯，277 位欄位要短一些，所以要快一些）。對於普通基，277 位欄位實際上更有效，因為它接受“類型 4”高斯普通基，而 283 位欄位是“類型 6”（較小的類型對性能更好）。所有合適的 Koblitz 曲線的列表很容易重建，事實上，NIST / NSA 做到了（例如，參見NSA 僱用的 JA Solinas 的這篇文章——搜尋“277”）。
為什麼他們選擇 283 位欄位對我來說很神秘。我仍然認為這不太可能構成“烹飪”；僅當 NIST（或 NSA）知道如何在 283 位欄位而不是 277 位欄位中破壞 Koblitz 曲線時，這才是一個後門，這不僅需要“未發表的大密碼分析進展”的假設，而且還需要據說新穎的破解技術很奇怪。
FIPS 186-3本身至少部分回答了您的問題……
附錄 A描述瞭如何從種子開始並使用涉及 SHA-1 的迭代過程，直到找到有效的橢圓曲線。
附錄 D包含 NIST 推薦的曲線，並包括用於根據附錄 A中的程序生成每條曲線的種子。
因此，要相信 NSA 熟化了常數，您必須相信以下兩件事之一：要麼他們可以反轉 SHA-1，要麼有足夠的曲線必須滿足他們的隱藏條件，以便他們可以通過蠻力找到合適的 SEED 值強制搜尋。
通常，“無所不能”的結構從簡單的東西開始，比如 $ sin $ （對於 MD5）或 $ sqrt $ （對於 SHA-1）小整數。據我所知（我錯了嗎？），NIST 曲線的 SEED 值並沒有那麼容易描述，這本身可以說是可疑的。
另一方面，這些是商業軟體必須支持的曲線才能獲得 FIPS 認證，允許它被美國政府機構購買並用於保護機密數據。
因此，如果 NSA 確實做了這些常量，他們在隱藏它方面做得還算不錯，而且他們有信心其他人不會很快發現這些漏洞。
Bernstein/Lange 的批評基於其他屬性，例如使用 NIST 曲線搞砸實現是多麼容易。
那就是說…
最新披露的大量證據表明，NSA 知道一些與 SSL/TLS 密碼相關的內容。也許這意味著 ECDHE，也許不是。（哎呀，也許它只是意味著某些常見的實現。）
但鑑於我們有來自 Dan Bernstein (Curve25519) 之類的替代品，我認為沒有令人信服的理由使用 NIST 的曲線，即使您想忽略 Schneier 的直覺以完全避免 ECC。
$$ Update $$ Bernstein/Lange 的展示文稿說 NIST 橢圓曲線是由“美國國家安全域的傑里·索利納斯”創建的。我在第一次閱讀時錯過了這一點。
我已將此問題發送到 Perry Metzger 的密碼學列表：
http://www.metzdowd.com/pipermail/cryptography/2013-September/017446.html
也許有人可以與 Solinas 先生取得聯繫，詢問他是如何選擇種子值的，以及為什麼。從源頭聽到答案會很有趣，即使沒有人可能相信它。
$$ Update 2 $$ 另見http://safecurves.cr.yp.to/rigid.html