Elliptic-Curves

是否有一種可行的方法可以故意操縱素數場上的 NIST ECC 曲線?

  • January 14, 2014

FIPS 186-4附錄 D.1.2中規定的 NIST 橢圓曲線 P-192、P-224、P-256、P-384 和 P-521根據明確定義的過程生成,但使用任意隨機- 160 位的種子值。出於這個原因,DJB 網站的一個頁面稱他們為

可操作性:曲線生成過程有大量無法解釋的輸入,給曲線生成器很大的曲線空間可供選擇。例如,考慮一個曲線生成過程,該過程需要 $ y^2=x^3-3x+H(s) $ 滿足各種安全標準,其中 $ s $ 是一個大的隨機“種子”並且 $ H $ 是一個雜湊函式。不管多強 $ H $ 也就是說,惡意曲線生成器可以搜尋多種選擇 $ s $ ,檢查每個 $ y^2=x^3-3x+H(s) $ 易受秘密攻擊;如果秘密攻擊適用於(例如)十億分之一的曲線,則此方法有效。

這可行嗎?更準確地說,是否有一種公開已知的方法使其可行?如果不是(正如我所懷疑的那樣),是否有關於這種故意操縱的可行性或不可行性以及相關努力的額外理性論據(甚至是知情意見)?或者,關於如何選擇種子的更多資訊?

注意:我還沒有在這些相關 問題的答案中找到對那個精確點的深入研究。

我想說,整個論點都圍繞著美國國家安全域可能知道的“秘密攻擊”,使他們能夠打破世界其他地方認為安全的橢圓曲線的一些實例,因為秘密攻擊是,嗯,秘密。

這產生了對您問題的唯一可能答案:由於秘密攻擊是秘密的,因此不知情的人不知道它們(duh),因此根據定義,沒有“公開已知的方法使其可行”。由於我們不知道,在數學上,“安全橢圓曲線”這樣的東西是否存在,“未知攻擊”是你將得到的最好的安全假設。


現在,如果我們仔細觀察,我們可能會注意到 NIST 曲線是使用強 PRNG 生成的:給定種子值 $ s $ , 曲線是 $ y^2 = x^3 + ax + H(s) $ 和 $ a = -3 $ (此參數的經典值;它為雅可比座標中的點加倍提供了輕微的性能改進)和 $ H $ 確定性 PRNG。在這裡,PRNG 是 ANSI X9.62(第 A.3.3.1 節)中描述的內容,並且基於基礎散列函式,在 NIST 曲線的情況下為 SHA-1。出於實際目的,我們可以將此 PRNG 視為隨機預言機。這意味著即使NSA 知道一些打破橢圓曲線的秘密方法,他們仍然需要做很多工作才能找到產生“看起來不錯”的曲線的種子(特別是曲線具有素數順序),但仍屬於“易斷曲線”的集合。例如,如果只有一條曲線 $ 2^{100} $ 對這種未知的攻擊很弱,那麼 NSA 將面臨平均 $ 2^{100} $ SHA-1 呼叫(至少),一個高得離譜的數字。

因此,除非我們在猜測中添加另一個“未知攻擊”,這次針對 SHA-1(特別是 X9.62 A.3.3.1 的 PRNG,以 SHA-1 作為雜湊函式),否則我們必須假設如果NSA知道一些橢圓曲線的秘密破壞方法用它來裝配 NIST 曲線,那麼該方法必須能夠破壞可能曲線的重要比例。所以我們不是在談論少數特殊格式的弱曲線,而是真正具有破壞性的東西。

我們沒有證據證明橢圓曲線天生就很強大,但是我們有一些“直覺”,即曲線對離散對數的表觀強度與規範高度的概念有關(另請參見此展示文稿)。如果這種直覺是正確的,那麼“弱曲線”(例如曲線 $ y^2 = x^3 + ax $ 如果基欄位是 256 位欄位,則為弱);隨機生成的曲線達到一周曲線的機會 $ b $ 參數將非常遙遠。從這個意義上說,假設 NSA 的“未知攻擊”,為了可用於操縱 NIST 曲線的生成,也必須證明許多專門研究橢圓曲線的數學家的直覺是錯誤的。

我認為上面的段落是最接近關於為什麼 NIST 曲線沒有被操縱的數學理性論證的。


不過,我確實有第二個論點,我認為它是合理的,儘管它來自經濟學,而不是數學:我們無法衡量秘密攻擊的秘密程度。請記住,美國政府指定的密碼參數的主要使用者是美國公司;NSA 的主要目標是保護這些公司免受外敵(競爭對手)的侵害。故意推動操縱曲線的使用,其中操縱使用一些尚未發表的攻擊的知識,這是非常冒險的:只要來自西伯利亞最深處的一些半瘋狂的數學家沒有發現相同的攻擊,這種情況就會成立。正如萊布尼茨所解釋的,科學發現似乎同時發生在整個世界;每個人同時思考同樣的事情。這是學術界眾所周知的概念:發布或滅。

因此,如果美國國家安全域正確地履行其官方職責,那麼它就不能促進美國企業使用已知易損壞並因此可能被任何人利用的工具。NSA 無法確保它壟斷了數學……

這與 DualEC_DRBG 後門形成對比,後者有一種已知的方法來操縱它(通過仔細選擇兩個相關的曲線點),但至關重要的是,同樣明顯的是,沒有選擇曲線點的人無法利用後門。是 NSA 可以安全推廣的那種後門,因為他們知道他們可以將其置於自己的獨家控制之下。

這也與 56 位 DES 密鑰形成對比,後者的後門很明顯(密鑰可以進行窮舉搜尋),但只能通過積累純粹的處理能力來利用;在 1970 年代,美國在該領域比蘇聯擁有眾所周知的巨大優勢,他們知道這一點。當計算能力變得太普遍時,他們改變了策略並決定推廣強加密方法(3DES,然後是 AES):當他們的敵人無法破解加密時,他們更喜歡它,即使這意味著他們也無法破解它。

引用自:https://crypto.stackexchange.com/questions/12898