產生偽隨機數的方法

2023-04-28 13:23:41

專利名稱：產生偽隨機數的方法
技術領域：
本發明涉及通過單向函數的迭代應用產生偽隨機數的方法，其 中單向函數根據起始值和密鑰產生偽隨機數，並且其中迭代從隨機起 始值和隨機密鑰開始，並且本發明還涉及包括相應的程序代碼的數據 載體。
背景技術：
用於產生偽隨機數的一種已知思想包括利用可靠的單向函數
f(k,s)的偽隨機數發生器，其中k是加密密鑰，s是隨機選擇的起始
值。根據預定分配來選擇這種密鑰k，並且在偽隨機數發生器產生偽
隨機數期間使用該密鑰k。密鑰k在整個產生過程中都保持相同。一
旦選擇了起始值S，則根據以下規則迭代地產生偽隨機數Xi:
x, = f (k， s)
Xi = f (k，Xw)其中i〉1
典型地，按照這種方式產生的偽隨機數的長度是有限的。 一旦 達到預定極限，偽隨機數發生器就會重新初始化，而起始值s被重新 選擇。密鑰k繼續保持相同。
這種實現方式的一個缺點就是，知道加密密鑰k的攻擊者將可 能計算出從最近的初始化到下一次初始化之間的所有的偽隨機數。因 此，這一特性極大地限制了該類偽隨機數發生器。
從W0 2005/029315 Al可以進一步得知， 一旦偽隨機數發生器 初始化，除了新的起始值s之外，還使用了新的加密密鑰k。此外， 在計算各個偽隨機數時，該加密密鑰k每次是由起始值s重新計算出 的。該方法的缺點是每種情況下的下一起始值s+l在隨機數的計算期 間均被存儲在非易失存儲器中。因此，例如，如果攻擊者能從非易失 存儲器中讀取各個下一起始值s+l甚至操縱它，那麼攻擊者會危及偽隨機數發生器的內部狀態。

發明內容
本發明的目的是提供一種產生偽隨機數的方法，其至少部分地
避免了上述缺點。通過權利要求1中的方法和權利要求9中的數據載 體實現了該目的。從屬權利要求中定義了其它有利的進展。
本發明提供了一種通過迭代方式產生偽隨機數的方法，其至少 包括應用於單向函數的兩個迭代步驟，其中，所述單向函數根據起始 值和密鑰產生偽隨機數的一部分，並且其中，迭代採用隨機起始值和 隨機密鑰進行初始化，並且其中，在每個迭代步驟中，用於迭代步驟 的起始值和密鑰都是由利用了所述單向函數的先前迭代步驟中所確 定的偽隨機數的所述部分確定的。
用於迭代步驟的起始值和密鑰由先前迭代步驟的偽隨機數的一 部分直接產生。起始值和密鑰並沒有被立即存儲起來。因此，攻擊者 不可能讀取或者改變這些值。
在進一步的實施例中，在利用了所述單向函數的各個先前迭代 步驟中確定的偽隨機數的所述部分被分成兩個部分，其中一個部分被 用於確定用於迭代步驟的起始值和密鑰，並且另一部分是先前迭代步 驟的偽隨機數的一部分。
一種產生偽隨機數的方法包括以下步驟 -第一步驟，定義隨機起始值和隨機密鑰；
-第二步驟，利用所述單向函數，根據起始值和密鑰，確定偽 隨機數的一部分，其中，在第一迭代步驟中，起始值對應於來自第一 步驟的隨機起始值，而密鑰對應於來自第一步驟的隨機密鑰；
-第三步驟，將在第二步驟中確定的偽隨機數的所述部分分成 兩個部分；
_第四步驟，由在第三步驟中確定的兩個部分中的一個部分確 定新的起始值和新的密鑰，其中在第三步驟中確定的兩個部分中的另 一個部分是偽隨機數的一部分；
-第二步驟至第四步驟的重複，直到達到預定次數的重複。在第四步驟中，在第三步驟中確定的兩個部分中的一個部分被 分成兩個子部分，其中新的起始值由第一子部分組成，新的密鑰由第 二子部分組成。新的起始值還可以由第二子部分組成，而新的密鑰還 可以由第一子部分組成。
在進一步的實施例中，在每種情況下，僅僅利用所確定的子部 分的隨機選擇部分來確定起始值和密鑰。
所確定的子部分的所選部分隨著每個迭代步驟而改變，這具有 特別的優勢。.不再可能由密鑰和起始值進行隨機選擇部分的反算。
在第四步驟中，僅僅在第三步驟中確定的兩個部分中的另一部 分的隨機選擇部分被用作偽隨機數的一部分。同樣，在這種情況下， 不再可能由偽隨機數的部分進行隨機選擇部分的反算。
本發明還提供一種在多個步驟中產生組合的偽隨機數的方法， 其中， 一個步驟執行產生偽隨機數的方法，並且其中每個步驟都採用 新的隨機起始值和新的隨機密鑰進行初始化。
一旦到達預定極限，就通過產生偽隨機數的方法的重複應用來 擴展將要產生的偽隨機數。
本發明還提供一種數據載體，其包括程序代碼，該程序代碼用 於產生與根據本發明的方法一致的偽隨機數。
因此，本發明提供了產生偽隨機數的迭代方法，其中，在每個 確定的隨機數之後，單向函數的起始值和密鑰都為下一個迭代步驟進 行重新初始化，其中起始值和密鑰由各個先前確定的隨機數直接確 定。由於任何時候起始值和密鑰均不被立即存儲起來，並且由於隨機 數的確定是由各個先前確定的隨機數的隨機成分確定的，所以，攻擊 者不可能讀取或者操縱起始值和密鑰，也不可能通過兩個連續的隨機 數對來分析單向函數以便由此確定密鑰。
因此，本發明提供了通過偽隨機數發生器的方式產生偽隨機數 的方法，這就使攻擊者更難危及偽隨機數發生器的安全並因此獲取已 經產生或將要產生的隨機數。
通過參考附圖中的實施例示例，將進一步描述本發明，但是， 本發明並不限於這些示例。


圖1示出了根據本發明的方法的概要。
圖2示出了根據本發明的方法，其利用了兩個迭代步驟。 圖3示出了根據本發明的方法的流程圖。 圖4示出了組合的偽隨機數的結構。
具體實施例方式
偽隨機數發生器產生預定數量的偽隨機數。偽隨機數發生器以 起始值s。和密鑰k。初始化。下文中，密鑰k被假定是加密密鑰。
偽隨機數發生器具有這樣的特性，在幾輪之後，它們的輸出變 為周期性的輸出。這就意味著，在到達周期末端後，就會再次產生與 之前相同的隨機數。為了避免這樣的情況，根據本發明的偽隨機數發 生器在初始化時採用新的密鑰k和新的起始值s。在這種情況下，密 鑰k和起始值s是隨機選擇的。
圖1示出了根據本發明的方法的概要。偽隨機數發生器通過單 向函數f的迭代應用產生了一組隨機數。所用的單向函數f可以是諸 如3DES (三層數據加密標準)或AES (高級加密標準)之類的對稱單 向函數，或者是諸如RSA函數(根據Rivest、 Shamir和Adleman) 或經由有限組的離散對數之類的非對稱單向函數。單向函數還適用於 起始值s和密鑰k。
迭代包括若干迭代步驟。在圖1中，步驟10、 20和30形成了 第一迭代步驟，而步驟40、 50和60形成了第二迭代步驟。在必要時， 偽隨機數發生器在每種情況下執行由若干迭代步驟組成的若干次迭 代。在一次迭代中，每個迭代步驟都以起始值s和密鑰k進行類似地 初始化。在各次迭代的第一迭代步驟中，迭代步驟的起始值s對應於 偽隨機數發生器的起始值s。，迭代步驟的密鑰k對應於偽隨機數發生 器的密鑰k。。下文中，迭代的第一起始值和第一密鑰被表示為s。和 k0。
在第一迭代步驟10中，偽隨機數發生器接收起始值s。。密鑰k。從中計算出來。在進一步的實施例中，偽隨機數發生器還在第一迭代 步驟10中接收密鑰k。。在下一迭代步驟20中，將單向函數f應用至
起始值s。和密鑰k。。隨後，在迭代步驟30中可獲得函數f (k。， s。) 的結果。此處，步驟30中的三元組(s，匕，rj表示第一次產生的 隨機數。該隨機數被分成兩個部分t,和r,。仁確定了用於第二次迭 代步驟40至60的起始值Si和密鑰k1Q元素r,是迭代的隨機數的第 一部分。
按照以下方式確定用於各個下一個迭代步驟的起始值Si和密鑰ki。
各個當前迭代步驟i的隨機數的部分ti確定了各個下一個迭代 步驟所要求的值Si和k"部分仁被分成兩個子部分，其中起始值Si
是ti的第一部分，密鑰ki是ti的第二部分。S,還可以是ti的第二部
分，而密鑰ki還可以是仁的第一部分。隨機數的剩餘部分rj乍為迭 代的偽隨機數的一部分。
在一個特定的優選實施例中，部分ti被分成兩個子部分，其中 在每種情況下，僅僅隨機選擇部分被用作下一迭代步驟的起始值Sl 和密鑰h。優選地，隨後，只有ri部分被用作迭代的全部偽隨機數 的一部分。該實施例的優點在於，偽隨機數發生器並不產生任何使攻 擊者可以分析單向函數f並由此確定密鑰k的隨機數對(rw，:n)。
圖1中的第二迭代步驟使用起始值Sl (在步驟40中)和密鑰k, (在步驟50中)從而由此計算出第二隨機數(s2， k2， r2)。如上所 述，這個隨機數被再次分成兩個部分，其中，從一部分確定用於下一 迭代步驟(未示出)的密鑰和起始值，從另一部分確定迭代的隨機數 的另一部分。
一旦迭代達到預定極限，迭代再次從步驟10開始，其中使用了 新的隨機起始值s。和新的隨機密鑰k。。因此產生了組合的偽隨機數。
圖2示出了根據本發明方法，其基於兩個迭代步驟。第一迭代 步驟從步驟101開始，其中偽隨機數發生器採用起始值s。和密鑰k。 進行初始化。根據單向函數f，在步驟102確定隨機數(k,， Sl， rO 。 元素n (例如3256)作為第一迭代步驟的輸出104。元素(k，Sl)作為用於第二迭代步驟的輸入103。類似於第一迭代步驟，第二迭代
步驟以初始化105開始。然而，在這種情況下，值k,和s,是由第一 迭代步驟的結果102確定的。隨後，根據單向函數f，在步驟106中 確定隨機數(k2， s2， r2)。元素n (例如7158)作為第二迭代步驟 的輸出108。元素(k2, s2)作為用於進一步的迭代步驟的輸入107。 在兩次迭代步驟之後，所產生的偽隨機數(由元素r,和i"2組成)為 32567158。
圖3示出了根據本發明的方法的流程圖。在第一步驟201中， 確定用於對偽隨機數發生器進行初始化的隨機起始值和隨機密鑰。利 用這兩個數值，在下一個步驟202中確定隨機數的一部分。隨機數的 該部分在步驟203中被分成兩個部分。一部分在下一個步驟204中被 用於確定新的起始值和新的密鑰。另一部分就是全部偽隨機數的一部 分。
在步驟205中，進行檢查以確定是否已經到達預定極限。如果 答案是否定的，則重複步驟202至204，其中在步驟204中確定的新 數值被用於確定步驟202中的隨機數的一部分。 一旦到達周期末端， 該方法從步驟206繼續進行，其中，進行檢查以確定組合的偽隨機數 是否完全產生。如果組合的偽隨機數並未完全產生，那麼該方法再次 從步驟201開始，其中確定了新隨機起始值和新隨機密鑰。如果組合 的偽隨機數已經完全產生，那麼該方法結束。
那麼，步驟204中所確定的元素組成的偽隨機數就是該方法的 結果。
圖4示出了組合的偽隨機數。這個組合的偽隨機數由六個部分 305組成，其中，第一次迭代303的三個迭代步驟產生了前三個部分， 第二次迭代304的三個迭代步驟產生了後三個部分。
第一次迭代303採用隨機數值(sZl，kZl) 301進行初始化，並且 第二次迭代採用隨機數值(sz2，kz2) 302進行初始化。此處，szi是 第i次迭代的隨機起始值，k&是第i次迭代的隨機密鑰。
每種情況下，迭代步驟Ii, j305都採用由先前迭代步驟Ii, ^確 定的值(sw，kw) 306進行初始化，其中Ii.」是第i次迭代的第j迭代步驟，並且j〉0。第i次迭代的各個第一迭代步驟II 。都採用數值 (SZi，kZi)進行初始化。
標號列表
10、 20、 30 第一次迭代的步驟 40、 50、 60 第二次迭代的步驟
101 初始化(第一迭代步驟)
102 結果(第一迭代步驟)
103 用於第二迭代步驟的輸入(第一迭代步驟)
104 輸出(第一迭代步驟)
105 初始化(第二迭代步驟)
106 結果(第二迭代步驟)
107 用於進一步的迭代步驟的輸入(第二迭代步驟)
108 輸出(第二迭代步驟)
201 隨機起始值和隨機密鑰的定義(第一步驟)
202 確定偽隨機數(第二步驟)
203 劃分偽隨機數(第三步驟)
204 新的起始值和新的密鑰的確定(第四步驟) 205、 206 詢問步驟
301、 302 迭代的隨機起始值和隨機密鑰
303、 304 迭代
305 迭代的迭代步驟
306 迭代步驟的起始值和密鑰
權利要求
1.一種通過迭代方式產生偽隨機數的方法，其至少包括應用於單向函數的兩個迭代步驟，其中，所述單向函數根據起始值和密鑰產生所述偽隨機數的一部分，並且其中，所述迭代採用隨機起始值和隨機密鑰進行初始化(201)，所述方法的特徵在於，在每個迭代步驟中，用於迭代步驟的所述起始值和所述密鑰都是由利用了所述單向函數的先前迭代步驟中確定的所述偽隨機數的所述部分確定(204)的。
2. 如權利要求l所述的方法，其特徵在於，在利用所述單向函 數的各個先前迭代步驟中確定的所述偽隨機數的所述部分被分成(203)兩個部分，其中一個部分被用於確定(204)用於一個迭代步 驟的起始值和密鑰，並且另一部分是所述先前迭代步驟的偽隨機數的 一部分。
3. 如權利要求2所述的方法，其特徵在於，偽隨機數的產生包 括以下步驟:-第一步驟(201)，定義隨機起始值和隨機密鑰；-第二步驟(202)，利用所述單向函數，根據起始值和密鑰， 確定所述偽隨機數的一部分，其中，在所述第一迭代步驟中，所述起 始值對應於來自所述第一步驟的所述隨機起始值，而所述密鑰對應於 來自所述第一步驟的所述隨機密鑰；-第三步驟(203)，將在所述第二步驟中確定的偽隨機數的所 述部分分成兩個部分；-第四步驟(204)，由在所述第三步驟(203)中確定的兩個部 分中的一個部分確定新的起始值和新的密鑰，其中在所述第三步驟 (203)中確定的兩個部分中的另一個部分是所述偽隨機數的一部分；-重複所述第二步驟(202)至所述第四步驟(204)，直到達 到預定次數的重複。
4. 如權利要求3所述的方法，其特徵在於，在所述第四步驟(204)中，在所述第三步驟(203)中確定的兩個部分中的一個部分 被分成兩個子部分，其中所述新的起始值由第一子部分組成，所述新 的密鑰由第二子部分組成。
5. 如權利要求4所述的方法，其特徵在於，所述新的起始值由 所述第二子部分組成，所述新的密鑰由所述第一子部分組成。
6. 如權利要求5所述的方法，其特徵在於，在每種情況下，僅 僅利用所述確定的子部分的隨機選擇部分來確定所述密鑰和所述起 始值。
7. 如權利要求6所述的方法，其特徵在於，在所述第四步驟 (204)中，僅僅在所述第三步驟(203)中確定的所述兩個部分中的另一個部分中的隨機選擇的部分是所述偽隨機數的一部分。
8. —種在多個步驟中產生組合的偽隨機數的方法，其中，首先， 一個步驟執行如上述權利要求中任一權利要求所述的方法，並且其中 每個步驟(303)都採用新的隨機起始值(301)和新的隨機密鑰(301) 進行初始化。
9. 一種數據載體，其包括程序代碼，在將所述程序代碼載入計 算機時，所述程序代碼執行如權利要求1至8中任一權利要求所述的 方法。
全文摘要
一種通過迭代方式產生偽隨機數的方法，其至少包括應用於單向函數的兩個迭代步驟，其中，所述單向函數根據起始值和密鑰產生偽隨機數的一部分，並且其中，迭代採用隨機起始值和隨機密鑰進行初始化，並且其中，在每個迭代步驟中，用於迭代步驟的起始值和密鑰都是由利用了所述單向函數的先前迭代步驟中確定的偽隨機數的所述部分確定的。
文檔編號G06F7/58GK101292223SQ200680038731
公開日2008年10月22日 申請日期2006年10月10日 優先權日2005年10月19日
發明者斯特芬·塑爾策, 海克·諾伊曼, 馬蒂亞斯·弗格爾 申請人:Nxp股份有限公司