[發明專利]隨機數生成器

有效

• 申請號: 201780091668.3
• 申請日: 2017-11-07
• 公開（公告）號: CN111279307B
• 公開（公告）日: 2023-05-12
• 發明（設計）人: 揚·瓦森貝格;羅伯特·歐伯克;于爾基·阿拉庫夾拉;伊曼紐爾·莫格納特
• 申請（專利權）人: 谷歌有限責任公司
• 主分類號: G06F7/58
• 分類號: G06F7/58;H04L9/06
• 代理公司: 上海華誠知識產權代理有限公司 31300
• 代理人: 肖華

一種用于生成隨機數(202)的方法(300)包括初始化偽隨機數生成器(PRNG)(200)，該偽隨機數生成器(PRNG)(200)具有包括內部位和外部位的2048位的狀態，內部位包括2048位的前128位，外部位包括2048位的剩余位。該方法還包括：從密鑰源(192)檢索AES輪密鑰(192)，并且針對閾值次數，使用AES輪密鑰(192)，通過將具有16個128位的分支的Feistel網絡中的奇數分支(220)與Feistel網絡中的對應的偶數相鄰分支的函數進行異或運算來執行輪函數；該方法還包括執行置換后狀態的所述內部位與先前狀態的所述內部位的異或運算。

技術領域

本公開涉及生成隨機數。

背景技術

在對大數據流進行分類，洗牌和/或采樣以保持屬于客戶端的數據安全時，隨機化算法通常依賴于偽隨機數生成器(PRNG)。PRNG使用確定性算法從被稱為種子的隨機輸入以非常快的速度生成偽隨機數。當對手可以預測PRNG的行為時，依賴于PRNG的算法可能失去其性能保證。在提供對對手的抗攻擊的同時，強PRNG通常遭受緩慢的應變方法時間。另一方面，快速PRNG通常容易預測，使得PRNG容易受到攻擊者/對手的意外關聯或利用的攻擊。因此，當為隨機化應用選擇PRNG時，開發者常常不得不確定適當的安全/速度折衷。通常，開發者不知道隨機化應用可能易受對手攻擊，因此不愿犧牲安全的速度。審計成千上萬的隨機生成器使用來識別安全/速度折衷的任務是因為它昂貴而令人怯步。

發明內容

本公開的一個方面提供了一種用于生成偽隨機數的方法。該方法包括通過數據處理硬件初始化具有包括內部位和外部位的2048位的狀態的偽隨機數生成器(PRNG)。內部位包括2048位的前128位，外部位包括2048位的剩余位。該方法還包括由數據處理硬件通過從密鑰源檢索高級加密標準(AES)輪密鑰來置換PRNG的狀態。該方法還包括通過使用AES輪密鑰執行輪函數，來將PRNG的狀態置換閾值次數。輪函數包括將具有16個128位的分支的Feistel網絡中的奇數分支與Feistel網絡中的對應的偶數相鄰分支的函數進行異或運算。對于閾值次數，該方法還包括通過將每個128位的分支洗牌成規定的順序來置換PRNG的狀態。該方法還包括由數據處理硬件執行置換后狀態的內部位與先前狀態的內部位的異或運算。

然后，一些或所有狀態，特別是一些或所有外部位，可以用作或提供偽隨機數，用于進一步使用根據需要進行操作。

Feistel網絡可以是一般化的Feistel網絡，或者更具體地是一般化的type-2Feistel網絡。

本公開的實施方式可以包括以下可選特征中的一個或多個。在一些實施方式中，初始化PRNG包括將PRNG的狀態設置為零，并將外部位設置為任意種子值。可選地，初始化PRNG還可以包括將PRNG的狀態設置為先前狀態。閾值次數可以包括至少17次。在一些示例中，輪函數包括至少兩輪AES。在這些示例中，至少兩輪AES中的每一輪可以使用與其它輪AES的AES輪密鑰不同的對應AES輪密鑰。

在一些示例中，將Feistel網絡的奇數分支與Feistel網絡的對應的偶數相鄰分支的函數進行異或運算，得到隨機位。在這些示例中，外部位包括所得到的隨機位。在執行所述輪函數并將每個分支洗牌八次之后，將每個128位的分支洗牌成規定的順序實現了完全子分支擴散。在一些實施方式中，規定的順序包括{7、2、13、4、11、8、3、6、15、0、9、10、1、14、5、12}。可選地，該方法可以包括防止訪問內部位和允許訪問外部位。

本公開還提供了一個或多個計算機可讀介質，其包括計算機程序代碼，所述計算機程序代碼被安排成當在適當的計算機設備上實施時執行所述方法。