用於產生隨機的輸出比特序列的方法
2023-05-20 14:00:16 2
用於產生隨機的輸出比特序列的方法
【專利摘要】本發明涉及用於產生隨機的輸出比特序列的方法。提出用於生成隨機輸出比特序列的方法和設備。在該方法中將輸入輸入到狀態自動機的裝置中。該裝置基於輸入確定輸出，其中該輸入與單向函數邏輯關聯地被輸入到所述裝置中。
【專利說明】用於產生隨機的輸出比特序列的方法
【技術領域】
[0001] 本發明涉及一種用於產生隨機的輸出比特序列的方法以及一種用於執行該方法 的設備。
【背景技術】
[0002] 稱為隨機元件的結果的隨機數對很多應用所需要。為了產生隨機數採用所謂的隨 機生成器。隨機生成器是提供隨機數序列的方法。隨機數的決定性準則是生成的結果是否 能被看作與先前的結果無關。
[0003] 為了產生隨機的比特序列採用在輸入輸入比特序列的情況下提供隨機輸出比特 序列的隨機比特生成器（Random Bit Generator)。
[0004] 例如對於密碼方法來說隨機數被需要。這些隨機數被用於生成用於加密方法的密 鑰。對這樣的密鑰提出涉及隨機特性的高要求。
[0005] 尤其是隨機的量或程度、也就是每比特的熵應當是足夠的。此外對於來自{0，1} 的值的比特概率應當是同概率的。要注意的是，為此由已知的隨機源生成的隨機值大多 不滿足這些要求。因此需要附加的方法，其中這些方法被概括在概念"後處理"（"post processing"）下。對於這樣的後處理典型地米用 DRBG (Deterministischer Random Bit Generator，確定性隨機比特生成器)，如這例如通過在2001年9月25日的BSI AIS 31中 的 das Bundesamt fiir Sicherheit in der Informationstechnik(BSI,聯邦局信息技術安 全性）中描述的那樣。這樣的生成器產生確定性的比特序列，但是該比特序列看起來是隨 機的。也將這樣的生成器稱為偽隨機生成器。如果未知的種子（Seed)被用作偽隨機序列 的起始點，則該序列不允許是可預測的，即使人們知道該偽隨機序列的已經輸出的比特，但 不知道種子。
[0006] 在此情況下，DRBG的特性被更準確地檢查並且由國家標準技術局（NIST)在2007 年3月的Special Paper NIST SP 800-90中給出針對DRBG的建議。
[0007] 根據現有技術的後處理典型地通過彈性函數（Resilient Function)、線性反饋移 位寄存器（LFSR)和多輸入 LFSR 或 MISR (Multiple Input Signature Register，多輸入籤 名寄存器）加以實現。
[0008] 根據現有技術的方法要麼非常費事，例如彈性函數，要麼所述方法不精確地滿足 50%比特概率，例如LFSR。上述兩種方法此外不具有識別裝置中例如由於誤攻擊而導致的 錯誤。
【發明內容】
[0009] 以此為背景提出一種具有權利要求1的特徵的方法和一種根據權利要求9的設 備。其它實施由從屬權利要求和說明書得出。
[0010] 首先提出一種用於生成偽隨機輸出比特序列的方法，其中使用2"個分別相同構建 的狀態自動機的裝置，其中這些狀態自動機分別包括η個狀態比特，其中每個狀態自動機 總是採取與該裝置的其它狀態自動機不同的狀態，其中在輸入側向這些狀態自動機分別輸 送相同的輸入信號，並且這些狀態自動機分別依據其狀態而產生η個籤名比特，這些籤名 比特一起形成籤名比特序列，其中通過從該裝置的所有狀態自動機的籤名比特序列中選擇 各個比特來產生隨機輸出比特序列。
[0011] 該方法例如利用用於用未知種子（Seed)生成隨機輸出比特序列的偽隨機比特生 成器來執行，該偽隨機比特生成器包括2"個分別相同構建的狀態自動機的裝置，其中這些 狀態自動機分別包括η個狀態比特，其中每一個總是採取與該裝置的其它狀態自動機不同 的狀態，其中在輸入側能夠向這些狀態自動機輸送輸入信號，並且這些狀態自動機分別依 據其狀態而產生η個籤名比特，這些籤名比特一起形成籤名比特序列，其中通過從該裝置 的所有狀態自動機的籤名比特序列中選擇各個比特來產生隨機輸出比特序列。
[0012] 該方法與已知方法相比具有識別誤攻擊的可能性。此外提供了比LFSR更好的比 特概率。但是該方法具有以下缺點：可能出現衝突，也就是可能出現不同輸入比特序列的相 同輸出序列。通過這樣的衝突可能有利於攻擊者或襲擊者的攻擊。此外在該方法情況下對 所輸出的輸出信號的回溯可能比這裡在下面提出的方法情況下更為簡單。
[0013] 上述方法現在通過以下方式加以擴展，即輸入被處理兩次，而且這些輸入一次直 接進入狀態機的裝置（也稱為C0SSMA裝置（Complete Set of State Machines,完整的狀 態機組)），並且附加地與單向函數邏輯關聯地進入。
[0014] 單向函數在此是能被"輕易"計算但是"難以"逆轉的數學函數。
[0015] 直接輸入保證，在處理時不丟失熵並且第二次邏輯關聯的輸入有助於避免衝突， 使得難以回溯（Backtracking),也就是說難以計算出前任輸出值，並且在種子（Seed)未 知的情況下使得難以預告或預測未來的輸出值。如果可以證明在與單向函數邏輯關聯 (Verkniipfung)的情況下不丟失熵並且衝突也不由此加強地出現，貝U也可以放棄直接輸入。
[0016] 附加地，如果在處理最後的輸入比特之後也還計算出奇偶性並且該奇偶性進入輸 出值中，則所有輸入比特對輸出值的影響可以被同等化。
[0017] 本發明的其它優點和構型從說明書和附圖中得到。
[0018] 不言而喻，上面提到以及下面還要闡述的特徵不僅能以分別說明的組合，而且還 能以其它組合或者單獨地加以使用，而不脫離本發明的範圍。
【專利附圖】
【附圖說明】
[0019] 圖1示出所提出的方法的實施布置。
[0020] 圖2示出所描述的用於執行所述方法的設備的實施方式。
[0021] 圖3示出狀態自動機的裝置。
[0022] 圖4示出4比特狀態自動機。
[0023] 圖5示出狀態過渡。
[0024] 圖6示出單向函數。
[0025] 圖7示出DRBG輸出級。
【具體實施方式】
[0026] 本發明藉助實施方式在附圖中被示意性示出並在下面參照附圖加以詳盡的描述。
[0027] 如圖1中所示，在第一步驟10中基於64個輸入比特分別產生4個輸出比特s0， sl，s2, s3,這64個輸入比特稱為種子。該種子被預先給定並且例如可以是TRNG源的輸出。 在計算出4個輸出比特之後，通過內建的增量器將該種子提高1，並且該被遞增的種子被用 於產生後面的4個輸出比特。該行動一直繼續，直到預先給定新的種子為止。從這64比特 的輸入中首先在第一步驟中選擇第一 4個比特，並且直接應用於具有16個狀態自動機14 的狀態自動機裝置12。
[0028] 狀態自動機裝置的功能在圖2,3和4中加以闡述。
[0029] 圖2示出用於執行該方法的設備的結構，該設備總地用附圖標記50表示。該圖示 示出被分成4比特的塊的輸入向量52、第一初始狀態54,該第一初始狀態將所述裝置的內 部計數器復位，所述內部計數器與輸入向量52的值相關地起作用用於選擇輸出比特58。此 夕卜，該圖示示出單向函數60、狀態自動機的裝置62 (C0SSMA)，第二初始狀態64作用於該裝 置，該第二初始狀態或者在每次新處理輸入向量52之前有效或者也在預先給定數目的輸 入向量52之後才確定在該裝置62中存在的狀態自動機的初始狀態。由此在兩次輸入處理 之後在裝置62的輸出端66處得到值。
[0030] 圖3闡明狀態自動機的裝置，該裝置總地用附圖標記100表示並且也稱為完整的 狀態自動機組（C0SSMA :C0mplete Set of State MAchines)。由此圖3示出與圖1中的裝 置12對應的完整的狀態自動機組。
[0031] 裝置100具有4比特輸入s0'，si'，s2'，S3'和64比特輸出102。輸出102的比 特通過狀態自動機104的觸發器驅動。
[0032] 圖4示出用附圖標記150表示並且被實施為4比特NLMISR(non linear multiple input signature register,非線性多輸入籤名寄存器）的4比特狀態自動機。
[0033] 如果對於任意預先給定的輸入序列分別明確地確定後續狀態（Folgezustand)和 前任狀態，則代替圖4的NLMISR還可以使用任意的狀態自動機。
【權利要求】
1. 用於生成隨機輸出比特序列的方法，其中將輸入輸入到狀態自動機（14, 104)的裝 置（12, 62, 100)中並且該裝置（12, 62, 100)基於該輸入來確定輸出，其中該輸入與單向函 數（60)邏輯關聯地被輸入到所述裝置（12, 62, 100)中。
2. 根據權利要求1所述的方法，其中附加地將所述輸入直接輸入到所述裝置 (12, 62, 100)中。
3. 根據權利要求1或2所述的方法，其中使用2"個分別相同構建的狀態自動機 (14, 104)的裝置（12, 62, 100)，其中狀態自動機（14, 104)分別包括η個狀態比特，其中每個 狀態自動機（14, 104)總是採取與該裝置（12, 62, 100)的其它狀態自動機（14, 104)不同的 狀態，其中在輸入側向狀態自動機（14, 104)分別輸送相同的輸入信號，並且這些狀態自動 機分別依據其狀態而產生η個籤名比特，這些籤名比特一起形成籤名比特序列，其中通過 從該裝置（12, 62, 100)的所有狀態自動機（14, 104)的籤名比特序列中選擇各個比特來產 生隨機輸出比特序列。
4. 根據權利要求1至3之一所述的方法，其中在多個步驟中分別將輸入輸入到所述裝 置（12, 62, 100)中並且與單向函數（60)邏輯關聯地輸入。
5. 根據權利要求4所述的方法，其中分別在特定數目的輸入步驟之後在所述輸入中插 入奇偶性。
6. 根據權利要求1至5之一所述的方法，其中作為單向函數（60)使用乘法。
7. 根據權利要求6所述的方法，其中將第一操作數與第二操作數相乘，其中作為第一 操作數使用所述輸入，並且作為第二操作數使用來自之前的運算的中間結果。
8. 根據權利要求1至7之一所述的方法，其中作為輸入使用TRNG源的輸出。
9. 用於利用狀態自動機（14, 104)的裝置（12, 62, 100)生成隨機輸出比特序列的設備， 尤其是用於執行根據權利要求1至8之一所述的方法，其中能夠向狀態自動機（14, 104)的 裝置（12, 62, 100)分配單向函數（60)，該單向函數的輸出能夠作為輸入被分配給所述裝置 (12, 62, 100)。
10. 根據權利要求9所述的設備，其中狀態自動機（14, 104)的裝置（12, 62, 100)包括 2"個分別相同構建的狀態自動機（14, 104)的裝置（12, 62, 100)。
11. 根據權利要求9或10所述的設備，其包括用於提供輸入的TRNG源。
【文檔編號】G06F7/58GK104063203SQ201410107271
【公開日】2014年9月24日 申請日期:2014年3月21日 優先權日:2013年3月22日
【發明者】M.劉易斯, E.貝爾, K.達姆 申請人:羅伯特·博世有限公司