[發明專利]高效可證安全的偽隨機生成器

無效

• 申請號: 200810046105.5
• 申請日: 2008-09-19
• 公開（公告）號: CN101677268A
• 公開（公告）日: 2010-03-24
• 發明（設計）人: 石泓松;李發根;鄧蔚;鐘婷;陳偉
• 申請（專利權）人: 電子科技大學
• 主分類號: H04L9/18
• 分類號: H04L9/18
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及密碼學，尤其涉及可證明安全的高效偽隨機生成器。此外，由于隨機算法和現代通信技術都需要頻繁使用隨機序列，因此本發明也涉及到這些領域。

背景技術

本發明是基于可證安全密碼理論的，以下在此意義上描述了偽隨機生成器的研究背景。

很多密碼算法都需要使用足夠長的隨機序列(包括數序列和位序列，下面統稱為隨機序列)來實現安全性，如將隨機位序列和明文消息逐位異或可立刻得到一個一次一密的流密碼系統。由于產生長的隨機序列的代價往往很高，實際應用中常常代之以算法產生的偽隨機序列。本發明設計了一個擴展隨機序列的算法，通常稱為偽隨機生成器。直觀地說，偽隨機生成器是一個確定性的算法，它接受一個較短的隨機種子，通過計算產生出一個更長的和隨機序列在計算上不可區分的偽隨機序列。偽隨機生成器的效率通常是在忽略具體的計算模型下，以每個模乘運算輸出的比特數(或輸出每比特需要的模乘數)來衡量的，它是衡量其應用價值的重要指標。在實際應用中，由于很難找到有足夠大擴張率的函數，一般的構造方法是迭代一些擴張率較小的函數，將每次迭代的輸出串聯起來以得到足夠長的偽隨機序列。這主要體現在迭代函數(Iterator)和偽隨機序列提取函數(Extractor)上。圖1表示現有偽隨機生成器的功能方框圖，其中模塊101表示輸入的隨機種子S₀，模塊102表示迭代函數I，模塊103表示偽隨機序列提取函數E，{S_i}為狀態序列，它隨著函數I的每一次作用更新到一個新的狀態。最后r_i表示第i輪輸出的偽隨機值，根據算法的計算能力，最終可以輸出多項式p(n)長的偽隨機序列。

現代密碼學是建立在計算復雜性基礎上的，基于各種困難性假設，已出現了很多可證安全的偽隨機生成器的構造方法。如基于離散對數問題、整數分解問題、RSA問題、DDH問題以及多變量二次方程組的難解性等問題的生成器。由這些方法產生的偽隨機序列滿足可證安全性，并有足夠大的擴展能力。不過這些算法的效率都很低，在允許預運算的條件下，目前最快的生成器(Gennaro生成器)能在一個模乘運算下漸進地輸出o(n)個偽隨機位。但是漸進效率并不能反映實際應用的情況，其具體安全性情況下的效率可能很低。如由于基于的困難性假設太強，為了生成1個隨機位Gennaro生成器至少需消耗1500個基本運算(只含加減乘和比特邏輯運算)以保證安全性，因此不適于實際應用。

目前關于偽隨機序列生成器的專利主要集中在電路設計或設備制造上，也有一些專利和算法相關，這些算法大多數是基于放射源和物理噪聲提取或移位寄存器理論的。這些專利產生的序列能通過很多針對隨機性的統計檢驗，但是都不具有可證安全性。因此，其輸出序列雖能用于實現隨機算法和現代通信技術，但用于實現密碼算法卻不夠安全，目前很多基于這些生成器的密碼算法都找到了有效的攻擊方法。另外，基于放射源或物理噪聲的生成器生成長隨機序列的代價往往太高，且這樣產生的隨機序列往往帶有相關性或偏向性，并可能無法重現，因此其實際應用價值非常有限。國內專利CN?1240318A和本發明有類似之處，都是設計可證安全的偽隨機生成器。不過前者是基于小指數離散對數問題的，這個困難性假設目前還未經過廣泛的檢驗，缺乏有力的安全性證明；相比之下，本發明是基于有限域上多項式的重構問題的，這是問題已有幾十年的研究背景，已被接受為一個標準的困難性假設。同時，專利CN?1240318A聽述算法在一個模乘運算下只能漸進地輸出1個隨機位，效率大約只及本發明的1/11。

本發明的困難性基礎是有限域上多項式的重構問題，它等價于Reed-Solomon解碼問題。該問題可簡單地描述為從含噪聲的多項式點值對中恢復出多項式。該問題具有很長的研究歷史，在敘述其研究現狀前，先給出一個簡單定義。