雙橢圓曲線確定性隨機數(shù)發(fā)生器

在算法成為ANSI，ISO以及之前由美國國家標準與技術(shù)研究院（NIST）認可的正式標準的一部分之前，算法的加密安全性的弱點是眾所周知的并且公開批評。公開發(fā)現(xiàn)的弱點之一是該算法有可能為那些知道盜版后門 - 美國政府的國家安全局（NSA） - 而不是其他人 - 提供有利的盜版后門。 2013年，“紐約時報”報道，他們擁有但從未向公眾發(fā)布的文件“似乎證實”后門是真實的，并且作為其Bullrun解密計劃的一部分被NSA故意插入。在2013年12月，路透社一篇文章稱，在2004年，NIST標準化Dual_EC_DRBG之前，NSA支付RSA安全千萬$的秘密協(xié)議使用Dual_EC_DRBG作為RSA BSAFE加密庫默認，導致RSA信息安全成為最重要的不安全算法的分銷商。RSA回答說，他們“斷然否認”他們曾經(jīng)故意與國家安全局勾結(jié)，采用一種眾所周知的有缺陷的算法，并說“我們從來沒有[與NSA]的關(guān)系保持秘密”。

某時在2004年的第一個已知的出版之前，可能kleptographic后門是與Dual_EC_DRBG的設計發(fā)現(xiàn)，與具有不同尋常的特性，這是任何人理論上是不可能Dual_EC_DRBG的設計，但Dual_EC_DRBG的設計師（NSA）確認后門的存在。 Bruce Schneier在標準化后不久就得出結(jié)論，“相當明顯的”后門（以及其他缺陷）意味著沒有人會使用Dual_EC_DRBG。后門將允許NSA解密，例如使用Dual_EC_DRBG作為CSPRNG的SSL/TLS加密。

最初提交Dual_EC_DRBG的ANSI標準組的成員了解潛在后門的確切機制以及如何禁用它，但沒有采取足夠的步驟無條件地禁用后門或廣泛宣傳它。在Dan Shumow和Niels Ferguson的出版物，或Certicom的Daniel R. L. Brown和Scott Vanstone的2005專利申請描述后門機制之前，一般的加密社區(qū)最初并未意識到潛在的后門。

在2013年9月，紐約時報報道，由愛德華·斯諾登泄露的內(nèi)部NSA備忘錄指出，美國國家安全局在標準化進程已經(jīng)努力最終成為Dual_EC_DRBG標準的獨立的一個編輯，并得出結(jié)論認為，Dual_EC_DRBG標準確實包含國家安全局的后門。作為回應，NIST表示“NIST不會刻意削弱加密標準?！备鶕?jù)紐約時報的報道，NSA每年花費2.5億美元在軟件和硬件中插入后門作為Bullrun計劃的一部分?？偨y(tǒng)顧問委員會隨后成立，負責審查美國國家安全局的行為，其中包括美國政府“全力支持而不是破壞制定加密標準的努力”。

2014年4月21日，NIST從其關(guān)于隨機數(shù)發(fā)生器的指南草案中撤回了Dual_EC_DRBG，該指南建議“盡快將當前用戶的Dual_EC_DRBG轉(zhuǎn)換為其余三種已批準的算法之一?！?/p>

使用Dual_EC_DRBG的實現(xiàn)通常是通過庫獲得的。 至少RSA Security（BSAFE庫），OpenSSL，Microsoft和Cisco都有包含Dual_EC_DRBG的庫，但只有BSAFE默認使用它。 據(jù)路透社的文章透露，RSA Security和NSA之間達成了1000萬美元的秘密協(xié)議，RSA Security的BSAFE是該算法中最重要的分銷商。OpenSSL的Dual_EC_DRBG實現(xiàn)存在一個缺陷，使其無法在測試模式之外工作，OpenSSL的Steve Marquess從中得出結(jié)論，沒有人使用OpenSSL的Dual_EC_DRBG實現(xiàn)。

NIST提供了經(jīng)過CSPRNG實施FIPS 140-2驗證的產(chǎn)品清單。已驗證的CSPRNG列在Description/Notes字段中。 請注意，即使Dual_EC_DRBG列為已驗證，默認情況下也可能未啟用。 許多實現(xiàn)來自庫實現(xiàn)的重命名副本。

BlackBerry軟件是非默認使用的示例。它包括對Dual_EC_DRBG的支持，但不支持默認值。但黑莓有限公司并沒有向可能使用它的任何客戶發(fā)出咨詢，因為他們認為可能的后門不是漏洞。杰弗里卡爾引用黑莓的一封信：

Dual EC DRBG算法僅適用于第三方開發(fā)人員通過[Blackberry]平臺上的Cryptographic API。對于Cryptographic API，如果第三方開發(fā)人員希望使用該功能并明確設計和開發(fā)了一個請求使用API的系統(tǒng)，則可以使用它。

Bruce Schneier指出，即使未默認啟用，將后備CSPRNG作為選項實施也可以使NSA更容易監(jiān)視具有軟件控制命令行開關(guān)以選擇加密算法的目標，或者“注冊表“系統(tǒng)，像大多數(shù)Microsoft產(chǎn)品，如Windows Vista：

特洛伊木馬非常非常大。不能說這是一個錯誤，這是收集按鍵的大量代碼。但是，將[bit-one]更改為[在注冊表中更改機器上的默認隨機數(shù)生成器]的第二位可能不會被檢測到。獲得后門是一種低陰謀，高度否定的方式。因此，將它放入庫和產(chǎn)品中是有好處的。- Bruce Schneier

2013年12月發(fā)布了一個概念驗證后門，它使用泄漏的內(nèi)部狀態(tài)來預測隨后的隨機數(shù)，這種攻擊在下次重新開始之前是可行的。

2015年12月，瞻博網(wǎng)絡宣布他們的ScreenOS固件的一些修訂使用了Dual_EC_DRBG和可疑的P和Q點，在他們的防火墻中創(chuàng)建了一個后門。最初它應該使用Juniper選擇的Q點，它可能或者可能沒有以可證明的安全方式生成。然后使用Dual_EC_DRBG為ANSI X9.17 PRNG播種。這會使Dual_EC_DRBG輸出混淆，從而殺死后門。但是，代碼中的“錯誤”暴露了Dual_EC_DRBG的原始輸出，從而危及系統(tǒng)的安全性。然后這個后門被一個改變了Q點和一些測試向量的未知方所取代。有關(guān)NSA通過Juniper防火墻進行持久后門訪問的指控已于2013年由Der Spiegel發(fā)布。

盜版后門是NSA的NOBUS政策的一個例子，它具有只有他們可以利用的安全漏洞。2100433B

這是一個由美國國家標準協(xié)會（NIST）制定并被美國國家安全局（NSA）大力提倡的隨機數(shù)發(fā)生器。Dual_EC_DRBG利用橢圓曲線算法的機制生成隨機數(shù)。這個算法涉及到在曲線上取點并反復在橢圓曲線上進行“打點”操作。該算法公布之后，據(jù)報道可能存在一個后門程序，可以根據(jù)一個密碼完全預測其返回的數(shù)字順序。最近，RSA公司由于其安全產(chǎn)品生產(chǎn)線上的隨機數(shù)發(fā)生器被設置為默認的偽隨機數(shù)發(fā)生器而召回了它的部分產(chǎn)品。無論這種隨機數(shù)發(fā)生器是否被寫了后門程序都不會改變橢圓曲線技術(shù)本身的力量，但這確實引起了關(guān)于對橢圓曲線標準化過程的一些問題。這也是我們應該將注意力用在確保系統(tǒng)充分使用隨機數(shù)的部分原因。

在NIST SP 800-90A中包含Dual_EC_DRBG的既定目的是其安全性基于數(shù)論的計算硬度假設。數(shù)學安全性降低證明可以證明，只要理論問題的數(shù)量很難，隨機數(shù)發(fā)生器本身就是安全的。但是，Dual_EC_DRBG的制造商沒有公布Dual_EC_DRBG的安全性降低，并且在NIST草案發(fā)布后不久就發(fā)現(xiàn)了Dual_EC_DRBG確實不安全，因為它每輪輸出太多比特。太多位的輸出（以及精心選擇的橢圓曲線點P和Q）是使NSA后門成為可能的原因，因為它使攻擊者能夠通過強力猜測來恢復截斷。在最終發(fā)布的標準中沒有更正過多位的輸出，使得Dual_EC_DRBG既不安全又無后顧之憂。

在許多其他標準中，意味著任意的常數(shù)是通過我的套數(shù)原則選擇的，其中常數(shù)是從例如pi中得出的，其方式幾乎沒有調(diào)整的余地。但是，Dual_EC_DRBG沒有指定如何選擇默認的P和Q常量，可能是因為它們是由NSA構(gòu)造為后門的。由于標準委員會意識到了后門的可能性，因此包括了實施者選擇自己的安全P和Q的方法。但是標準中的確切表述是這樣的，即FIPS 140-2驗證需要使用所謂的后向P和Q，因此OpenSSL項目選擇實施后門P和Q，即使他們意識到潛在的后門并且更愿意生成他們自己的安全P和Q. 紐約時報后來寫道，國家安全局在標準化過程中起作用，最終成為該標準的獨立的一個編輯。

后來由Daniel RL Brown和KristianGj?steen為Dual_EC_DRBG發(fā)布了安全證明，表明生成的橢圓曲線點與均勻隨機橢圓曲線點無法區(qū)分，并且如果在最終輸出截斷中輸出的位數(shù)較少，如果兩個橢圓曲線點P和Q是獨立的，如果顯示三個問題很難（通常只接受其中一個是硬的），那么Dual_EC_DRBG是安全的。證據(jù)依賴于三個問題很難的假設：決策性的Diffie-Hellman假設（通常被認為很難），以及兩個通常不被認為難以解決的新問題：截斷點問題和x-對數(shù)問題。與許多替代CSPRNG（沒有安全性降低）相比，Dual_EC_DRBG相當慢，但Daniel R.L.Brown認為安全性降低使得慢速Dual_EC_DRBG成為一種有效的替代方案（假設實現(xiàn)者禁用明顯的后門）。請注意，Daniel R.L. Brown為橢圓曲線加密專利的主要所有者Certicom工作，因此在推廣EC CSPRNG時可能存在利益沖突。

所謂的NSA后門將允許攻擊者通過查看單輪（32字節(jié)）的輸出來確定隨機數(shù)生成器的內(nèi)部狀態(tài);然后可以容易地計算隨機數(shù)發(fā)生器的所有未來輸出，直到用外部隨機源重新接種CSPRNG。這使得例如SSL / TLS易受攻擊，因為TLS連接的設置包括以明文形式發(fā)送隨機生成的加密隨機數(shù)。NSA所謂的后門將取決于NSA知道e * Q = P的單個e - 這是一個難題，給定Q和P，但如果你可以選擇P和Q則容易生成。因此，e是一個秘密密鑰，據(jù)推測只有NSA才知道，所謂的后門是一個盜版非對稱隱藏后門。Matthew Green的博客文章“Dual_EC_DRBG的多重缺陷”通過使用Crypto 1997中引入的離散日志kleptogram，對所謂的NSA后門如何工作進行了簡化解釋。

概念：具有某種共同屬性的橢圓或雙曲線的集合，稱為橢圓系或雙曲線系。

幾種常見的橢圓系或雙曲線系方程：

（1）x^2/(c^2 t) y^2/t=1（半焦距為c且c≠0），當t>0時，表示共焦點(±c,0)的橢圓系；當-c^2

（3）與橢圓x^2/a^2 y^2/b^2=1(a^2>b^2)共焦點的曲線系方程可設為x^2/(a^2-λ) y^2/(b^2-λ)，當λ（4）漸近線方程為x/a±y/b=1或y=±(b/a)x的雙曲線系可設為x^2/a^2-y^2/b^2=λ（λ≠0）。2100433B

橢圓曲面就是以橢圓曲線 (虧格的Riemann面) 為一般纖維，具有這種纖維結(jié)構(gòu)的復曲面 (2維緊復流形)。

這一概念正如后面所述對于向高維發(fā)展以及對纖維微分拓撲都作出了重要的貢獻。而且小平先生已經(jīng)指出了這一發(fā)展方向。正如橢圓函數(shù)論是19世 紀整個數(shù)學的源泉，說橢圓曲面為本世紀后半葉整個代數(shù)幾何的源泉 (之 一) 也不過分。由此產(chǎn)生的源流通過 “弦模型理論” 等等而在理論物理學中保持著。

橢圓曲面是小平(在數(shù)學的論述部分遵循慣例，直呼其名而不加敬稱) 在關(guān)于復曲面的一系列基礎研究的論文集 “On compact analytic surfaces”中收錄的第23部分中處理的。該論文的出版是1963年。

ECC(橢圓曲線密碼系統(tǒng))是已寫入我國無線局域網(wǎng)標準WAPI和我國正在制定其算法標準的一種公鑰密碼，在信息安全領域具有重要應用。本項目研究ECC算法的有效實現(xiàn)，重點是ECC算法VLSI實現(xiàn)時的算法結(jié)構(gòu)和電路結(jié)構(gòu)，具體包括兩方面內(nèi)容。一是為了更好地滿足ECC軟件實現(xiàn)或VLSI實現(xiàn)對各種具體實現(xiàn)算法的需求，要尋找ECC實現(xiàn)中的新算法、新方法，或者要優(yōu)化各種已存在的ECC實現(xiàn)算法。二是如何依據(jù)這些新算法、新方法或優(yōu)化算法，再結(jié)合VLSI實現(xiàn)的不同設計目標，要提出各種VLSI實現(xiàn)的算法結(jié)構(gòu)、電路結(jié)構(gòu)，并要獲取各種VLSI實現(xiàn)的實驗數(shù)據(jù)與結(jié)果。研究內(nèi)容與擬解決的關(guān)鍵問題凝練于申請者近年來從事高速ECC密碼芯片研制時所遇到的科學問題。研究成果對于豐富ECC算法VLSI實現(xiàn)的理論、方法和實驗數(shù)據(jù)，支撐基于我國ECC標準的芯片研發(fā)具有重要意義。 2100433B