摘要：

本文主要考慮了基于計算復雜性定義的偽隨機數生成器.介紹了單向函數與偽隨機數生成器之間的關系以及幾種常見的基于離散對數問題,DDH問題的偽隨機數生成器.在分析了它們的安全性和效率的同時也提出了改進方法. 針對基于離散對數問題的IRG生成器,本文指出它在每次迭代中產生的前O(logn)個比特和其后的n-c-O(logn)比特具有不同的安全性,而前O(logn)個比特相對不安全,也是導致IRG的參數比較大的主要因素.所以本文提出了改進辦法,每次迭代僅僅輸出后n-c-O(logn)個比特.雖然每次輸出的比特數減少了,但是卻增強了安全性,使得比較小的參數就能... 展開 本文主要考慮了基于計算復雜性定義的偽隨機數生成器.介紹了單向函數與偽隨機數生成器之間的關系以及幾種常見的基于離散對數問題,DDH問題的偽隨機數生成器.在分析了它們的安全性和效率的同時也提出了改進方法. 針對基于離散對數問題的IRG生成器,本文指出它在每次迭代中產生的前O(logn)個比特和其后的n-c-O(logn)比特具有不同的安全性,而前O(logn)個比特相對不安全,也是導致IRG的參數比較大的主要因素.所以本文提出了改進辦法,每次迭代僅僅輸出后n-c-O(logn)個比特.雖然每次輸出的比特數減少了,但是卻增強了安全性,使得比較小的參數就能滿足IRG的安全需求.無論理論分析還是實際測試都顯示改進后的效率大約是原IRG生成器的3倍. 針對基于橢圓曲線上DDH問題的Dual_EC_DRBC生成器,橢圓曲線的倍乘是影響生成器效率的關鍵.本文提出了針對j不變量等于1728的一類GLS橢圓曲線上4維GLV方法,它大大的加速了橢圓曲線的倍乘.實際測試表明,相對Galbraith等人提出的2維GLV方法,它能提升30-35%的效率. 最后,本文給出了一種基于一般有限群的子覆蓋的偽隨機數生成器構造方法.前文中介紹的IRG生成器,Dual_EC_DRBC生成器,FSS生成器和NG生成器都可以看做是它的特殊例子.本文還給出了基于對稱群Sn的具體構造.這是第一個基于非交換群的可證明安全性的偽隨機數發生器.本文還指出這種構造方法能通過NIST Statistical Test Suite. 收起

展開