隨機數(shù)發(fā)生器應用類型

這是一個由美國國家標準協(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后門如何工作進行了簡化解釋。