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

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

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

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

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

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

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

在NIST SP 800-90A中包含Dual_EC_DRBG的既定目的是其安全性基于數(shù)論的計(jì)算硬度假設(shè)。數(shù)學(xué)安全性降低證明可以證明，只要理論問題的數(shù)量很難，隨機(jī)數(shù)發(fā)生器本身就是安全的。但是，Dual_EC_DRBG的制造商沒有公布Dual_EC_DRBG的安全性降低，并且在NIST草案發(fā)布后不久就發(fā)現(xiàn)了Dual_EC_DRBG確實(shí)不安全，因?yàn)樗枯嗇敵鎏啾忍?。太多位的輸出（以及精心選擇的橢圓曲線點(diǎn)P和Q）是使NSA后門成為可能的原因，因?yàn)樗构粽吣軌蛲ㄟ^強(qiáng)力猜測(cè)來恢復(fù)截?cái)?。在最終發(fā)布的標(biāo)準(zhǔn)中沒有更正過多位的輸出，使得Dual_EC_DRBG既不安全又無后顧之憂。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這一概念正如后面所述對(duì)于向高維發(fā)展以及對(duì)纖維微分拓?fù)涠甲鞒隽酥匾呢暙I(xiàn)。而且小平先生已經(jīng)指出了這一發(fā)展方向。正如橢圓函數(shù)論是19世 紀(jì)整個(gè)數(shù)學(xué)的源泉，說橢圓曲面為本世紀(jì)后半葉整個(gè)代數(shù)幾何的源泉 (之 一) 也不過分。由此產(chǎn)生的源流通過 “弦模型理論” 等等而在理論物理學(xué)中保持著。

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

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