生成偽隨機字符串的方法和設備的製作方法

2023-12-08 16:27:51 3

專利名稱：生成偽隨機字符串的方法和設備的製作方法
技術領域：
本發明涉及產生屬於給定符號系統(alphabet)的符號(symbol)的偽 隨機字符串(pseudorandom string )。這樣的字符串具體使用在一些密碼術 (cryptography)過程中。
背景技術：
儘管偽隨機字符串是確定性地產生的，但是(至少在合理時間內)該偽 隨機字符串不可能與其中從符號系統中完全隨機(random)地選擇每個符號
源有聯繫)。實際上，偽隨機字符串通常通過使用秘密參數(被稱為種子或 密鑰，這取決於上下文)啟動合適的算法來產生，並且在啟用附加參數時， 不管所述參數是否秘密，都稱為初始化向量。
上面所指的符號系統可以是二進位集合{0， 1}、從0到9的數字集合、 或者包括那些數字和大寫小寫字母的字母數字集合。在本發明的上下文中， 符號系統的符號屬於基數(cardinal)《22的有限體(finite body ) K或伽羅瓦 體GF(《)。
偽隨機字符串的重要應用是流加蜜。這個技術用於利用符號系統中的值 的字符串(z,)對同 一符號系統中具有值的另 一明文(in clear)數據字符串{jc,.} (用H故索引)進行加密(在密碼術意義上)，其中，(z,)是偽隨機字符串發 生器產生的字符串，用以產生加密的字符串[yj,其也具有符號系統中的值。 換言之，選擇符號系統內的內部合成規律乂.-x,5^;例如，如果符號系統是 二進位符號系統(O, 1},則這個內部規律可以是異或(exclusive OR)運算。 流加密還已知為空中(onthefly)加密，因為數據字被逐一地加密，這與對 數據塊進行操作的加密方法相對。與塊加密相比，流加密具有減少傳送延遲 的優點和數據存儲問題，但是明顯地需要至少與明文數據的數據速率一樣高 的偽隨機符號數據速率；因此，對流加密的應用被保留給相對快速的偽隨機 字符串發生器。流加密被使用在TLS(傳輸層安全)網際網路交換保護協議(參見"The TLS Protocol", T. Dierks and C. Allen, version 1.0, RFC 2246, January 1999 )，它的最 廣泛使用的流加密算法之一是RC4算法(參見"Linear Statistical Weakness of Alleged RC4 Keystream Generator", J.D. Golic， proceedings of "Advances in Cryptology - EUROCRYPT '97"， pages 226 to 238, editor W. Fumy, Lecture Notes in Computer Science vol. 1233, Springer-Verlag);和GSM系統中的無線 電信道業務和信令加密，它的最廣泛使用的算法是A5/1算法(參見"Real Time Cryptanalysis of A5/1 on a PC", A. Biryukov， A. Shamir, and D. Wagner, Proceedings of FSE 2000, pages 1 to 18, editor B. Schneier, Springer-Verlag 2000 )。
偽隨機字符串還有其它的重要應用，例如隨機計算和公鑰鑑別密碼術協議。
例如上面提到的A5/1算法的許多當前流算法使用由線性反饋寄存器產 生的、可能使用非線性函數組合的周期性發生的線性字符串(參見"Le chiffrement & la vol6e" ["On the fly encryption"], A. Canteaut， special issue of the review "Pour la Science", pages 86 and 87， Paris, July-October 2002 )。這些算法 可實現在快速偽隨機字符串發生器中，但是有必要警惕注意它們的安全性， 因為它們缺乏可以安放強列信心的強有力安全論據(argument),涉及實踐中 不可能與從全部的隨意字符串產生的偽隨機字符串區分開。
法國專利申請05 06041公開了 一種意欲在密碼術過程中使用的、屬於基 數《之2的有限體K的項的偽隨機字符串發生器。這個發生器包括用於根據 元素K的初始化n元數組Z(。) =(%(%,義(。)2,...,%(。) )迭代計算元素K的n元數
組^)=(義('、,;^)2,...，1(') )(其中i = l、 2.......)的裝置，每個n元數組X〃)
以預定的方式從元素K的m元數組yw =^(')1,:^')2,...，") 1)產生，並且所述偽 隨機字符串的項是以預定方式從n元數組J^和/或m元數組yw提取的。這 個發生器的引人注意之處在於它還包括用於通過將具有K中的係數的預定 二次齊式(quadratic form)應用到n元數組W-"的分量來為一個或多個值i 獲得m元數組yw的一個或多個分量"、(其中k-l、 2.......m)的裝置。
給定了求解有P艮體上的二次方程系統的問題難度，這個偽隨機發生器使 用提供高級別安全性的算法。經受了複雜性理-淪的一般接受的推測P ^ NP 的驗證，可以看出，無論考慮什麼有限體K,解決這個問題都需要多於多項式時間，即使在多項式時間中可以實現驗證給定的候選者是或不是這個系統
方程的解(這類問題也稱為NP硬(NP-hard)問題)。此外，即使對於相對 適中大小的m和n(例如，對於K-GF(2)，並且m和n大於或等於100 ), 如果m和n的值足夠接近，則目前也已知沒有解決這個問題的隨意實例的有 效方法。
鑑於此，出現確定根據法國專利申請05 06041的偽隨機發生器是否可以 充分有效的疑問，即，為了在將要展望的工業規模上使用這類發生器，對於 所產生的充分小的字符串的每個符號(至少對於適中參數值，但是對於剛才 提及的問題十分高仍被認為是困難的)，都需要計算資源(時間、存儲器等)。
這個需要計算資源的問題具體涉及將該類型的偽隨機發生器集成在諸 如硬連線邏輯晶片的低成本電子系統中的可能性。硬連線電子邏輯電路由從 電晶體產生的邏輯門構成(可能使用"與非"門和"或非"門這兩種類型的 邏輯門來構思程序的所有邏輯函數)。因此，實現邏輯電路所需要的邏輯門 數目具體反映了電路的尺寸、它的電流消耗和它的成本。
因此，更詳細地考慮在法國專利申請05 06041的偽隨機發生器中進行的 計算。
所述發生器迭代地調用在迭代i上將至少一個變量Y(i)k (其中，k= 1、
2.......m)與n變量W- (其中j-l、 2.......n)相關聯的一個或多個二
次齊式。因此，這個關聯包括特定的函數"G"，它將輸入值的n元數組
I"x,，x，,jO與輸出值的111元數組7 = 0;1,力,...,;0相關聯。這個函數G因此 對應於有限體K上的m元二次多項式的系統(G)(即，具有n個變量x!到 xn，其中11>1)。這些多項式因此是接下來的形式，其中係數屬於K,並且參 量yk也屬於K:
Z "，巧+ Z A0) + h = A (B "附)。
1。X/" l力^
在用以實現這類發生器的傳統方式中，這些係數的值將被存儲在存儲器 中，並將對每次迭代計算m個多項式的值。因此，需要存儲的係數總數等於 m-N,其中N是每個多項式的項數。驗證這一點是簡單的問題，對於具有n
個變量的二次多項式，這個項數等於^ = 1 + ^^。
2
此外，對於認為難以求解K上n個未知數的m個二次方程的系統，希 望m和n的值足夠大，並且它們的數量級(order of magnitude)充分接近。 這樣，對於高值n，並且對於與值n處於相同數量級的值m,將要存儲的系
6數數量是113級別。例如，如果n近似等於100,則必須存儲大約一百萬係數。 結果，根據法國專利申請05 06041的傳統偽隨機發生器實現需要極奇多 的電子門，因為它有可能展望將它合併到硬連線邏輯晶片中。勿庸置疑的是， 即使較小可行地展望插入到硬連線邏輯晶片，偽隨機發生器也使用其中部分 多元多項式具有高於2的整體度(global degree)的多元多項式系統，儘管 更高度的多項式將以適中增加計算資源為代價而具有使發生器更安全的優 點。

發明內容
因此，本發明涉及一種意欲使用在密碼術過程中的、屬於基數q^2的 有限體K的項的偽隨機字符串的發生器，所述發生器包括用於迭代地計算具 有屬於有限體K的n個變量的m個多項式的系統(r)的裝置。這個偽隨機 字符串發生器引人注意之處在於在每個迭代重新生成所述m個多項式的係數。
因此，本發明基於少量的參數在每個迭代生成(例如重新計算)多項式 的係數，從而本發明的發生器起作用所需要的存儲器尺寸非常適中。
本發明者已經認識到，與可能不成熟地期望的相比，本發明承擔的附加 計算負擔對總計算時間具有非常小的影響。由於相對高度的多項式的計算時 間相對短，所以即使它們有很多並且它們是眾多變量的函數，如所公知的， 本發明也產生了快(並因此例如可用於流加密)且非常適合於低成本計算設 備的偽隨機發生器，這些優點附加在上面所提及的增加安全性上。
如果高速度是首要的，則形成系統的所述多項式的每一個有利地最多為 二度多項式(second degree )。
根據特定特徵，所述偽隨機字符串發生器包括線性移位寄存器形式的系 數發生器模塊。
替換地，所述偽隨機字符串發生器可採取非線性移位寄存器形式或有限 狀態才幾形式。
利用這些特徵，可以使用小的電子存儲器生成大量的係數。 才艮據特定特徵，為了計算系統(r)的m個多項式為給定的n元數組變 量(;c,，;c2，…,;0所採取的m元數組值(y,，少2，…,;0，其中所述多項式都是小於或 等於D的整體度(global degree )，所述發生器包括進行以下處理的裝置 為D度的具有n個變量的一般多項式的項的給定集合選"t奪處理順序 (order )5
對於所處理的項，以相同的順序計算所述變量的單項式，並然後連續 地對於m個多項式，生成該項的係數並相乘該係數和所述單項式以獲得所述 項的值。
利用這些特徵，變量的每個因數僅計算一次而不是m次。 以相關的方式，本發明涉及一種意欲在密碼術過程中使用的、用於生成 屬於基數q 2 2的有限體K的項的偽隨機字符串的方法，所述方法迭代地計 算具有屬於有限體K的n個變量的m個多項式的系統(r)。這個生成偽隨 機字符串的方法的引人注意之處在於在每個迭代重新生成所述m個多項式 的係數。
根據特定特徵，所述多項式的每一個最多為二度多項式。 根據特定特徵，為了計算系統(r)的m個多項式為給定的n元數組變
量(x"^…,x")所採取的111元數組值0;1,少2,...,30，其中所述多項式都是小於或
等於D的整體度，所述方法包括以下步驟
為D度的具有n個變量的一般多項式的項的給定集合選擇處理順序； 對於所處理的項，以相同的順序計算所述變量的單項式，並然後連續
地對於m個多項式，生成該項的係數並相乘該係數和所述單項式以獲得所述
項的值。
這些方法的優點實質上與上面簡要描述的相關偽隨機序列發生器的優 點相同。
本發明還旨在
電子電路，具體地為硬接線的邏輯晶片，包括上面簡要描述的偽隨機 字符串發生器中的任一個；
包括電腦程式代碼指令的不可移除數據存儲裝置，所述電腦程式 代碼指令用於運行上面簡要描述的用於生成偽隨機字符串的方法中的任一 個的步驟；
包括電腦程式代碼指令的部分或全部可移除數據存儲裝置，所述計 算機程序代碼指令用於運行上面筒要描述的用於生成偽隨機字符串的方法 中的任一個的步驟；以及。
包含代碼指令的電腦程式，使得當所述程序控制可編程數據處理設
8備時，所述指令促使所述數據處理設備運行上面簡要描述的用於生成偽隨才幾 字符串的方法中的任一個。
這個電子電路、這些數據存儲裝置和這個電腦程式的優點實質上與所 述方法的優點相同。


發明的其它方面和優點將變明顯。所述描述針對附圖，其中
圖1是示出本發明的一個實施例的用於生成偽隨機字符串的方法的框 圖；以及
圖2是示出本發明的一個實施例的偽隨機發生器的框圖。
具體實施例方式
如上面說明的，本發明的偽隨機字符串發生器的安全性(即，"黑客" 根據前面的i項計算輸出處的第(i+l)項字符串的不可能性)是基於求解 有限體K上n個未知數的m個方程式的問題難度。
在一個實施例中，這些方程可以都是二次方程，如在法國專利申請 05 06041中(為了筒化描述，即使當一些方程，對應地一些多項式為線性時， 也使用表述"二次方程"和"二次多項式"一一要理解，系統的至少一個方 程式，對應地至少一個多項式實際上是二度方程)。這個問題可以精確地用 7>式表達如下
給定屬於有限體K的n個未知數Xi到x。中的m個二次方程的系統(r ), 其形式為
Z <化+ Z A(力^ + m (""附)
其中係數W力、""和h屬於K,並且其中參量yk也屬於K;
找到解Z"^，jc2，…,jO， 'T"是方程式系統(r )描述的函數，具有與輸出值的m元數組y -O^a,...,:^) 相關聯的輸入值的n元數組X-(x,，x2，…,;0。
偽隨機發生器迭代地調用用於將至少一個變量"'、(其中k= 1、 2.......
m)與n個變量X('-",(其中j-l、 2.......n)相關聯的一個或多個二次齊式。
9如上面解釋的，優選地選擇參數q、 m和n，使得
求解K上n個未知數的m個二次方程的系統可以被認為是困難的， 這要求m和n的值足夠高，並且它們的數量級足夠接近(例如，qn和qm二 者都在2犯與2柳之間)，並且
所述計算可以有效地實現，這要求q、 m和n的值足夠小(例如，q 小於100, m和n小於幾百)。
此外，根據本發明，在每次迭代上再生(例如重新計算)這些二次齊式 的係數。
清楚的是，零係數的數目越大，則計算越快；然而，必須注意，為了求 解方程系統，實際上不可能有足夠的二次項係數(下面表示為"〗'力)數量不 為零；如果為了增加運行速度而一些方程(但是明顯地不是所有方程)相對 於所有變量為線性，則推薦用於生成係數的方法保持為秘密，以便補償較容 易求解方程系統的事實(理論上)。
這個實施例中，對於每個值i,通過將具有K中的係數的二次齊式應用到n 元數組X^"的分量來計算m元數組￥ 的所有分量。
首先，在初始化步驟期間，構建n元數組X⑨。取決於意欲使用的發生 器，X仰可取決於公共種子、密鑰、初始化向量或者這些元素的組合；初始 化向量是通常不秘密的附加參數，使能夠將相同的密鑰使用多於一次從而生 成多個不同的偽隨機字符串。
然後運行迭代步驟以根據初始狀態X仰並利用下面描述的方法來產生組
成K的元素的t元數組的偽隨機字符串(其中，i=l、 2.......)，其中t是
位於1到m之間的常數。總的迭代次數可以在例如1和25之間。
在第i迭代中，將組成K的元素的n元數組的當前狀態^W當作輸入值 來運行接下來的子步驟
1) 使用上面定義的函數r來從X(i_"推導出K的值的m元數組Y(i)(即， = r(x'-"));
2) 通過將選擇的輸出函數S應用到對(pair) (y乂yw)來獲得輸出值 Z(i)，即Z(')-S(I('乂"'))；以及
3 )通過將選擇的反饋函數F應用到對(W-",yW)來獲得組成K值的n元 數組的新當前狀態XG)，即= F(W-。以連續方式將這個方法表達在圖1中(覆蓋了兩個連續迭代)，但是它 可以等同地適當表達為環的形式。這裡要注意的重點在於所述方法的連續步 驟可通過一個電子電if各來實現。
對於上面提及的反饋函數f和輸出函數s的可能選擇，例如參見法國專 利申請05 06041。此外，要注意，例如至少基於字符串zw而在輸出處組成 符號的各種偽隨機字符串(例如，二進位符號)的手段的應用。
圖2是示出本發明的偽隨機字符串發生器的一個實施例的圖。這個發生 器包括下列模塊
存儲器(100)，用於包含將要計算的多項式系統的輸入變量值；
存儲器(500)，用於包含在計算結束時、將要計算的一個或多個多項 式所採用的值，並且意欲同時用作中間值存儲單元；
模塊(200),用於(按照預定的順序)生成在將要計算的多項式系統 中涉及的各個單項式的值，該單項式發生器模塊(200)可選地具有它自己 的存儲器；
模塊(300),用於生成用於定義將要計算的多項式系統的係數序列， 該模塊(300)具有它自己的存儲器；以及
*組合模塊(400),用於相乘係數和單項式的值，以更新包含多項式值 的存儲器(500 )。
下面描述上面的係數發生器模塊(300)的一個具體有利實施例。
中應用相同的函數r;換言之，如果證明m個多項式的每個係數值從一個迭 代到另一迭代變化是方便的話，則沒有什麼來阻止這種變化。本實施例嫻熟 地使用這一點。
係數發生器模塊(300 )的第一實施例採取線性反饋移位寄存器(lfsr) 的形式。
lfsr包括通過在每個時鐘脈衝用包含在存儲器&i中的值替換除了包 含在存儲器",中的值之外的、包含在每個存儲器a中的值而刷新的/存儲器 ^^，...,a,集合，該存儲器a,中的值用在前一時鐘脈沖中包含在各個存儲器中 的值的給定線性組合來代替。
通常將來自線性移位寄存器的輸出比特用作偽隨機比特字符串。根據本 發明，有利地使用lfsr輸出數據，不是為了直接生成輸出值z(i)，而是為了生成m個多項式的係數。LFSR僅根據存儲器中的r比特並使用僅包括r 個邏輯門量級的電子電路來產生長度為(2'-l)的偽隨機字符串。
例如，在二進位體GF ( 2 )上具有n = 80個變量、包括m = 80個多變 量多項式的方程系統(r )中，可以從r-18比特的線性移位寄存器，而不 是259200比特的不成熟實現中，生成系統的m ■ N 259200個係數。
在第二實施例中，係數發生器模塊(300)採用非線性反饋移位寄存器 (NLFSR)的形式。與線性反饋移位寄存器相比，這在電子門的數量方面涉 及了非常少的附加成本，但是顯著地改善了在發生器的輸出處產生的項的字 符串的隨機特性。
在第三實施例中，係數發生器模塊(300)釆取有限狀態機的形式，包括
在每個時鐘脈衝更新的存儲器；
用於更新存儲器的電路；以及
用於擴展在存儲器中存儲的數據的擴展電路。
表述"擴展電路"指的是適於根據存儲器中的g比特生成f比特的電路， 其中f〉g。例如，如果f是h的倍數，則f比特的集合可劃分為每h比特的 子集，此後這些h比特子集的每一個穿過一串混合器，並且最終級聯該結果 生成的比特字符串。
在有限狀態機中，所有存儲器值(在擴展之前)在每個時鐘脈沖被刷新， 而在移位寄存器中，在每個時鐘脈衝僅刷新存儲器中的一個值。因此，有限 狀態機比移位寄存器執行更快的計算，但是以電子門數量的一定增加為代 價。
無論如何，上面的實施例迅速地並使用少量的電子門而在每次迭代生成 了方程系統(r)的係數。
還可以展望單項式值發生器模塊(200)的不同實施例。為了簡化描述， 這裡僅考慮(x,、類型的，其中i和j從l到n變化)二次項的計算。
所述"不成熟，，實現一個接一個地考慮所有變量對；因此所述計算需要 112個時鐘脈沖。
然而，單項式可以替換地計算如下在存儲器中放置變量(^,X2,…,;0值 的當前字符串的兩個複製。計算"正面對(facing)"的項首先產生n平方;c,2。 然後，將循環排列一個位置應用到變量^,12,...,;0的值的字符串之一；計算 "正面對"的項再次產生n個乘積 繼續這個逐n個地計算單項式的處理，直到獲得了 ！12個乘積。最後，乘法被交換，僅需要n/2
個時鐘脈衝，但是這個設備需要兩倍於"不成熟"實現的存儲器。
最後，通過組合模塊(300)中的係數生成和模塊(200)中的單項式生成可以增加速度並節約存儲器容量，以便在繼續下一項之前對所有多項式"並行，，計算相同類型的每一項。例如，在二次多項式系統中，計算對應變量的對應單項式(分別為;c,、、、或1類型)，此後，對於隨後的m個多項式中，生成這個項的係數(分別為類型a，、""或h)，並然後乘以所述單項式以獲得所述項的值。
權利要求
1. 一種意欲在密碼術過程中使用的、屬於基數q≥2的有限體K的項的偽隨機字符串發生器，所述發生器包括用於迭代地計算具有屬於有限體K的n個變量的m個多項式的系統(Γ)的裝置，其特徵在於在每次迭代重新生成所述m個多項式的係數。
2. 根據權利要求1的偽隨機字符串發生器，其特徵在於形成所述系 統(r)的所述多項式的每一個最多為二度多項式。
3. 根據權利要求1或權利要求2的偽隨機字符串發生器，其特徵在於 它包括線性移位寄存器形式的係數發生器模塊(300 )。
4. 根據權利要求1或權利要求2的偽隨機字符串發生器，其特徵在於 它包括非線性移位寄存器形式的係數發生器模塊(300 )。
5. 根據權利要求1或權利要求2的偽隨機字符串發生器，其特徵在於 它包括有限狀態機形式的係數發生器模塊(300 )。
6. 根據權利要求1到5中任一項的偽隨機字符串發生器，其特徵在於 為了計算系統(r)的m個多項式為給定的11元數組變量(^^2,...,^)所採取 的m元數組值(力，h,...其中所述多項式都是小於或等於D的整體度， 所述發生器包括進行以下處理的裝置 為D度的具有n個變量的一般多項式的項的給定集合選擇處理順序； 對於所處理的項，以相同的順序計算所述變量的單項式，並然後連續地對於m個多項式，生成該項的係數並相乘該係數和所述單項式以獲得所述項的值。
7. —種電子電路，其特徵在於該電子電路包括根據權利要求1到6 中任一項的偽隨機字符串發生器。
8. 根據權利要求7的電子電路，其特徵在於所述電子電路包括硬接 線的邏輯晶片。
9. 一種意欲在密碼術過程中使用的、用於生成屬於基數q22的有限體 K的項的偽隨機字符串的方法，所述方法迭代地計算具有屬於有限體K的n 個變量的m個多項式的系統(r)，其特徵在於在每次迭代重新生成所述m 個多項式的係數。
10. 根據權利要求9的方法，其特徵在於形成所述系統(r)的所述多項式的每一個最多為二度多項式。
11.根據權利要求9或權利要求IO的方法，其特徵在於為了計算系 統(r)的111個多項式為給定的11元數組變量(11^2,...，、)所採取的111元數組 值Ovh，...,;O,其中所述多項式都是小於或等於D的整體度，所述方法包括 以下步驟 為D度的具有n個變量的一般多項式的項的給定集合選擇處理順序； 對於所處理的項，以相同的順序計算所述變量的單項式，並然後連續地對於m個多項式，生成該項的係數並相乘該係數和所述單項式以獲得所述項的值。
12. —種包括電腦程式代碼指令的不可移除數據存儲裝置，所述計算 機程序代碼指令用於運行根據權利要求9到11中任一項的方法的步驟。
13. —種包括電腦程式代碼指令的部分或全部可移除數據存儲裝置， 所述電腦程式代碼指令用於運行根據權利要求9到11中任一項的方法的 步驟。
14. 一種包含代碼的電腦程式，使得當所述程序控制可編程數據處理 設備時，所述指令促使所述數據處理設備運行根據權利要求9到11中任一 項的方法。
全文摘要
本發明涉及一種意欲在密碼術過程中使用的、用於生成屬於基數q≥2的有限域K的項的偽隨機字符串的方法，所述方法包括迭代地計算具有屬於有限體K的n個變量的m個多項式的系統(Γ)。根據本發明，在每個迭代重新生成這些m個多項式的係數。本發明還涉及一種意欲實現這個方法的偽隨機字符串發生器。
文檔編號G06F7/58GK101467127SQ200780021591
公開日2009年6月24日 申請日期2007年4月2日 優先權日2006年4月10日
發明者亨利·吉爾伯特, 奧利維爾·比利特, 科姆·伯貝恩 申請人:法國電信公司