生成加密數據流密碼的方法和裝置的製作方法

2023-09-18 21:03:10 2

專利名稱：生成加密數據流密碼的方法和裝置的製作方法
背景技術：
I.發明領域本發明涉及加密。本發明尤其涉及一種生成加密數據流密碼的方法和裝置。
II.相關技術領域的描述加密是一種處理過程，通過該過程，採用隨機處理對數據進行運算，從而使除特定用戶外的所有的用戶都不能理解這些數據。對數位化的數據進行加密的一種方法是通過採用數據流密碼來完成的。數據流密碼是採用要加密的數據以及由加密規則所產生的偽隨機位數據流(或加密位數據流)並且通常採用異或(XOR)運算將它們合併來進行工作的。解密是這樣一種簡單的處理過程，它生成同樣的加密位數據流，並採用相應的運算操作從加密的數據中去除加密位數據流。如果XOR運算是在加密一側進行的，那麼在解密側也進行相同的XOR運算。對於保密的加密處理過程，加密位數據流必須是在計算上較難預測的。
用於生成偽隨機數數據流的許多技術是基於階數為2的伽羅瓦有限域上線性反饋移位寄存器(LFSR)的。這是2n階伽羅瓦有限域在n是正整數時的特殊情況。當n＝1時，伽羅瓦域元素包含0和1的數據位值。寄存器是通過使數據位移位一個數據位位置，並計算新的輸出數據位來更新的。將新的數據位移位到寄存器內。對於斐波那契寄存器，輸出數據位是寄存器中的數據位的線性函數。而對於伽羅瓦寄存器，許多數據位是按照剛剛從寄存器中移位出來的輸出數據位來更新的。從數學上說，斐波那契寄存器和伽羅瓦寄存器的結構是等效的。
生成偽隨機數數據流即移位和數據位獲取的運算操作在硬體上沒問題，但在軟體或採用通用處理器或微處理器進行的其他實施方式上卻存在一些難度。存在的難度在移位寄存器的長度超過用於生成數據流的處理器中寄存器的長度時而增加。另外，當n＝0時，每一組運算操作僅生成一個輸出數據位，從而處理器的利用率很低。
採用數據流密碼的典型的應用場合是無線電話。典型的無線電話通信系統是碼分多址(CDMA)系統。CDMA系統操作運行可參見已轉讓給本發明受讓人的美國專利4,901,307，該專利的標題是「SPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATIONSYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS」。已轉讓給本發明的受讓人的美國專利5,103,459中進一步揭示了一種CDMA系統，該專利的標題是「SYSTEMAND METHOD FOR GENERATING SIGNAL WAVEFORMS IN A CDMA CELLULAR TELEPHONESYSTEM」。另一種CDMA系統包括GLOBALSTAR通信系統，用於採用低地軌道衛星進行的全球通信。其他的無線電話系統包括時分多址(TDMA)系統和頻分多址(FDMA)系統。可以將CDMA系統設計成滿足「雙模式寬帶擴譜蜂窩系統的TIA/EIA/IS-95移動站-基站兼容性標準」，該標準在本文中簡稱為IS-95標準。同樣，可以將TDMA系統設計成滿足TIA/EIA/IS-54(TDMA)標準，或者對於歐洲全球系統來說滿足移動通信(GSM)標準。
由於遠端站中缺乏計算能力，而使無線電話中數位化話音數據加密受到了影響。這使得諸如TDMA標準中所使用的話音專用屏蔽加密處理能力較弱，並使生成如GSM標準中所使用的A5密碼的數據流密碼的硬體受到影響。硬體數據流密碼的缺點是附加的硬體成本，以及當加密過程需要改變時，所花的時間及費用具大。由於無線電話系統和數字電話中許多的遠端站都包含有微處理器和存儲器，速度快並且採用很少存儲器的數據流密碼很適合於這些應用場合。
發明概述本發明是一種生成加密數據流密碼的新的、改進的方法和裝置。按照本發明，設計循環關係(或稱之為遞歸關係)，使之在比GF(2)更大的有限域上進行運算操作。可以採用循環緩存器或使用滑動窗口來實現形成循環關係的線性反饋移位寄存器。在典型的實施例中，有限域元素的運算是用查詢表來進行的。採用一個或組合的非線性處理過程，可以得到一個非線性輸出。可以將數據流密碼設計成支持多層密鑰控，以滿足數據流密碼的使用要求。
本發明要解決的問題是，採用在處理器中實現起來較簡單的結構來生成加密數據流密碼。特別是，可以通過選擇更適合於處理器的有限域，來實現更為有效的結構。可以選擇循環關係的元素和係數，來配合處理器的字節或字的長度。這就使得可以由處理器對元素進行有效的運算。在典型的實施例中，所選擇的有限域是具有256個元素(GF(28))的伽羅瓦域。這使得循環關係的元素和係數佔用存儲器的一個字節，而使得可以進行有效的變換。另外，使用大的有限域減少了循環關係的階數。對於有限域GF(2n)，對相同狀態數進行編碼的循環關係的階數k減少了n倍(對於典型的GF(28)，是8倍)。
本發明要解決的另一個問題是採用查詢表來進行域的乘法。在該典型的實施例中，可以通過對兩個運算對象中的每一個運算對象取對數、將對數值相加並對混合的對數值取指數，而在域中(對非零元素)進行乘法。可以用一種不可約多項式，來生成對數表和指數表。在本典型實施例中，表格是預先計算並存儲在存儲器中的。同樣，可以用一種簡單的查詢表來進行常數係數的域計算。另外，可以用不可約多項式來預先計算表格，並將表格存儲在的存儲器內。
本發明再要解決的問題是，採用一個或混合的下述處理過程，去除線性反饋移位寄存器輸出中的線性關係不規則擾動(有時也稱為抽取)、非線性函數、多個移位寄存器以及混合寄存器的輸出、一個寄存器上的變量反饋多項式以及其他的非線性過程。在本典型實施例中，可以採用非線性輸出來隨機控制移位寄存器的擾動(stuttering)。另外，通過對移位寄存器內被選擇的元素上進行非線性運算，可以得到非線性輸出。此外，可以將非線性函數的結果與一組常數進行異或，而使非線性輸出位出現不可預計的轉化。
本發明的要解決的再一個問題是，用循環緩存器或滑動窗口來構成線性反饋移位寄存器。採用這種循環緩存器或滑動窗口結構，緩存器中的元素是不移位的。相反，採用指針或指示符來給出最近計算的元素的位置。指針隨著進行新元素的計算而移動，並移位到循環緩存器或滑動窗口內。當指針到達邊緣時，指針繞回。
本發明再要解決的問題是提供一種具有多層密鑰控能力的數據流密碼。在該典型實施例中用一個密鑰首先使移位寄存器的狀態初始化。對於某些以幀的方式進行數據傳送的通信系統，可以為每一幀生成一個數據流密碼，從而擦除的或溢出的序列幀不會打斷加密過程。用幀密鑰初始化過程，可以為每一幀，使第二層密鑰控過程初始化。
本發明再要解決的問題是，使用最大長度的循環關係，而使得序列復蓋了重複前最大數量的狀態。
本發明還要解決的問題是，採用清晰配對差異的循環關係或輸出等式。清晰配對差異是，當用來實現循環關係的移位寄存器出現移位時，無論是在循環關係或非線性輸出等式中，移位寄存器中不會出現特定元素對使用過兩次的情況。這種特性就從輸出等式的結果中去掉了線性關係。
本發明還要解決的問題是，在具有清晰配對差異的同時，按照應用的要求，有選擇地使密碼保密性以及計算效率為最佳。
再有，本發明要解決的問題是，提供一種方法，使加密過程的延遲不會超過預定的界限。為此，對加密延遲進行測量，如果估計的延遲超過了預定的閾值，則採用第二種加密方法，來限制加密操作的累計延遲。
附圖簡述在參照附圖閱讀了本發明的詳細描述以後，讀者將會更清楚地了解本發明的特徵、目的和優點。圖中，相同的標號所表示的意義相同。


圖1是本發明典型實施例循環關係的方框圖；圖2是採用處理器的數據流密碼發生器的典型方框圖；圖3A和3B分別表示時刻n和時刻n+1時循環緩存器內容的圖；圖3C表示滑動窗口內容的圖；圖4是本發明典型數據流密碼發生器的方框圖；圖5是本發明典型密鑰初始化過程的流程圖；圖6A是本發明典型每一幀初始化過程的流程圖；圖6B是本發明第二種典型每一幀初始化過程的流程圖；圖7是本發明第二種典型數據流密碼發生器的方框圖；圖8是本發明第三種典型數據流密碼發生器的方框圖；圖9是本發明用於限制加密延遲通常實施結構的方框圖；圖10是本發明用於限制採用隨機抽取或擾動的加密密碼中的加密延遲的一種通用結構的方框圖；圖11是本發明用於限制採用圖7所示修改形式的隨機抽取或擾動的加密密碼中的加密延遲一種通用結構的方框圖。
較佳實施例的詳細描述線性反饋移位寄存器(LFSR)是基於伽羅瓦域上的循環關係的，這裡的輸出序列由下面的循環關係定義Sn+k＝Ck-1Sn+k-1+Ck-2Sn+k-2+…+C1Sn+1+C0Sn(1)式中，Sn+k是輸出元素，Cj是常係數，k是遞歸關係的階數，而n是時間指數。狀態變量S和係數C是基礎有限域的元素。等式(1)有時也用本說明書中忽略的常數項來表示。
圖1中示出了等式(1)中遞歸關係的典型實施方式的方框圖。對於階數為k的遞歸關係，寄存器12含有k個元素Sn至Sn+k-1。將這些元素提供給伽羅瓦域乘法器14，將這些元素與常數Cj相乘。從乘法器14得到的乘積提供給伽羅瓦域加法器16，將乘積加和，給出輸出元素。
對於n＝1，GF(2)的元素包含一個數據位(0值或1值)，而等式(1)的執行需要許多次按數據位進行的運算。這時，由於是採用設計用來對字節或字大小的對象進行計算的處理器來對一個數據位進行許多次運算的，所以採用通用處理器來構成遞歸關係是低效率的。
本發明中，線性反饋移位寄存器是設計用於對大於GF(2)的有限域進行計算的。特別是，通過選擇更適合於處理器的有限域，可以構成更有效的結構。本實施例中，選擇的有限域是具有256個元素(GF(28))的伽羅瓦域，或具有2n個元素的伽羅瓦域，這裡，n是處理器的字長。
在本較佳實施例中，採用的是具有256個元素(GF(28))的伽羅瓦域。這就使得遞歸關係中的每一個元素和係數佔據存儲器的一個字節。可以由處理器更有效地進行字節運算。此外，對相同數量的狀態進行編碼的遞歸關係的階數k減少了n倍，對於GF(28)來說是8倍。
本發明中，採用最大長度的遞歸關係可以得到最佳的結果。最大長度指的是在重複前輸出序列的長度(寄存器的狀態數)。對於階數為k的遞歸關係，最大長度是Nk-1，這裡，N是基礎有限域中的元素數，並且在本較佳實施例中，N＝256。狀態全部為0是不允許的。
圖2中示出的是採用處理器的數據流密碼發生器的典型方框圖。控制器20連接到處理器22，並且包含一組指示處理器22進行操作的指令。所以，控制器20可以包含一個軟體程序或一組微碼。處理器22是一個執行發生器所需的運算的硬體。處理器22可以是一個微控制器、微處理器，或者是設計用於執行本文中的功能的數位訊號處理器。存儲器元件24連接到處理器22，並用來構成線性反饋移位寄存器，並儲存將在下文中描述的預計算表和指令。存儲器元件24可以是用隨機存取存儲器或其他設計用於執行這裡所描述的功能的存儲器件構成的。指令和表格可以存儲在只讀存儲器內，只有用於寄存器本身的存儲器才需要在算法的執行期間進行修改。
I.生成非線性輸出數據流採用線性反饋移位寄存器用於數據流密碼是很難恰當執行的。這是因為可以利用輸出數據流中剩餘的線性關係得到某一時刻的寄存器狀態。接著，按照需要，可以使寄存器向前或者向後，使輸出數據流恢復。可以採用幾種技術，用線性反饋移位寄存器來生成非線性數據流密碼。在本典型實施例中，這些非線性技術包含寄存器的擾動(無法預計的抽取)，對寄存器的狀態採用非線性功能，採用多個寄存器和寄存器輸出的非線性組合，在一個寄存器上使用變量反饋多項式，以及其他的非線性過程。這些技術中的每一種技術描述如下。某些技術是通過舉例來說明的。也可以採用其他的技術來生成非線性數據流，這些技術也包括在本發明的範圍內。
擾動是這樣一種處理過程，即，以可變的和不可預計的方式對寄存器實行時鐘控制。擾動實施簡單，並且能給出良好的結果。擾動時，在數據流密碼處是不提供與寄存器的某些狀態相關的輸出的，因此，就更難從數據流密碼來重新構築寄存器的狀態。
對移位寄存器的狀態採用非線性函數也可以給出良好的結果。如等式(1)所定義的那樣，對於某一遞歸關係，從寄存器狀態的線性函數和係數，產生輸出元素。為了提供非線性關係，可以從寄存器狀態的非線性函數中生成輸出元素。特別是，可以採用對通用處理器上的字節或字的長度數據進行運算的非線性函數。
採用多個移位寄存器並以非線性方式將寄存器的輸出組合起來，可以給出良好的結果。可以以硬體的方式容易地構成多個移位寄存器，這時所添加的費用是最少的，並且可以並行地操作移位寄存器，以保持相同的操作速度。為了能在通用處理器上實施，由於可以以固定的時間來對更大的移位寄存器進行更新，可以採用執行與多個移位寄存器的功能相似的功能的單個更大的移位寄存器(不降低整體速度)。
採用變量反饋多項式在一個寄存器上以不可預計的方式進行變更可以給出良好的結果。不同的多項式可以以隨機的順序互換，也可以以隨機的方式來改變多項式。如果設計得當，這種技術的實現可能會很簡單。
II.更大階數有限域元素的運算操作伽羅瓦域GF(28)含有256個元素。伽羅瓦域GF(28)的元素可以以幾種不同方式中的一種方式來表述。一種共同的並且是標準的表述是從具有階數小於8的所有多項式的係數模2中形成所述數據域。即，數據域的元素可以用具有數據位(a7，a6，…a0)的字節來表述，代表下面的多項式a7x7+a6x6+…+a1x+a0(2)數據位也稱為是多項式的係數。可以通過相應係數(a7，a6，…a0)中每一個係數加法模2來執行由等式(2)所代表的兩個多項式的加法運算。換句話說，通過對兩個字節進行異或計算，可以實現對兩個字節的加法運算。加法恆等式是多項式具有全0的係數(0，0，…，0)。
通過將普通的多項式與模2係數相乘，可以在數據域中進行乘法運算。然而，階數為n的兩個多項式相乘給出一個階數為(2n-1)的多項式，該多項式需要減小為階數為n的多項式。在典型的實施例中，通過將合成多項式除以一個不可約多項式，去掉商，並且保留餘數作為約減的多項式，可以來實現多項式的約減。不可約多項式的選擇改變了將編組內元素變換為存儲器中的被編碼的字節，但不會影響實際編組的運算操作。在典型的實施例中，選擇的階數為8的不可約多項式是x8+x6+x3+x2+1(3)也可以採用其他階數為8的不可約首一多項式，這也在本發明的範圍內。乘法單位元是(a7，a6，…a0)＝(0，0，…，1)。
在通用處理器上進行多項式乘法和後續的約減運算是較複雜的運算。然而，對於具有中等數量元素的伽羅瓦域，這些運算操作可以通過查詢表以及更簡單的操作來完成。在本典型實施例中，數據域中(非0運算)的相乘可以通過對兩個運算對象中的每一個運算對象取對數、加入對數值模255並對混合的對數值取指數來完成。可以將約減組合在查詢表內。
可以象下面所描述的那樣來生成指數表和對數表。首先，確定乘法子編組GF(28)的生成符g。這時，字節值g＝2(代表多項式x)是一個生成符。表1中的指數表是i＝0，1，…，28-1時，值gi的256個字節的表。當gi(看作是整數)小於256時，指數值如表1中第一行開頭的8個表值所示的那樣。因為g＝2，所以表中的每一個表值是相鄰左邊的表值的2倍(考慮到表1中繞回到下一行)。但是，當每一gi大於255時，指數由等式(3)中所給出的不可約多項式約減。例如指數x8(第一行，第九列)由不可約多項式x8+x6+x3+x2+1約減，而產生餘數-x6-x3-x2-1。該餘數等效於模2運算的x6+x3+x2，在表1中表示為77(26+23+22+1)。重複該過程，直到當所有的指數i＝0至255都計算了gi為止。
在定義了指數表以後，可以計算對數表，作為指數表的逆。在表1中，對於採用不可約多項式得到的每一個指數i，有一個唯一的指數值gi的對應關係。對於表1，映射是i_2i，所以第i個位置上儲存的值是2i。對兩邊取log2對數，得到下面的結果log2(i)_i。這兩種變換表示，如果指數表中第i個位置上是用作對數表的指數的，那麼該指數的對數是指數表的索引。例如，對於i＝254，如表1中最後一行、第5列所示的那樣，指數值2i＝2254＝166。兩邊取log2對數，得到254＝log2(166)。所以，對數表中索引i＝166中的值設置為254。重複該過程，一直到變換了對數表中所有的值為止。0的對數是一個未定義數。在本典型實施例中，0用作佔位符。
在定義了指數表以及對數表以後，數據域中(非零元素)的乘法可以通過查詢對數表中的兩個運算對象的對數、用模255將對數值相加以及通過查詢指數表對混合的對數值取指數冪來進行。因此，數據域中的相乘可以通過三次查詢操作和一次舍位相加來進行。在典型的伽羅瓦域GF(28)中，每一表格是255個字節長，並且可以預先計算和存儲在存儲器內。在本典型實施例中，對數表的0位置是不使用的，從而無需從索引中減去1。注意，當無論哪一個運算對象是0時，對數表中相應的值並不代表實際值。為了給出正確的結果，在按照所述的方法進行乘法之前，必須對每一運算對象進行測試看看是不是0，如果是0，則結果就是0。
為了用遞歸關係從線性反饋移位寄存器中產生輸出元素，由於係數Cj在等式(1)中是常數，那麼情況就更簡單了。為了進行有效的實施，只要有可能，就應當將係數選擇為0或1。當Cj是除0或1以外的一些值時，對於乘法ti＝Cj·i，可以預先計算一個表格，這時，i＝0，1，2，…，28-1。這時，乘法運算可以用一次表格查詢來進行，而無需進行測試。這樣的表格是固定的，並且可以存儲在只讀存儲器內。
表1-指數表
表2-對數表
III.存儲器結構在採用硬體來實施的時候，使數據位移位是一個簡單而有效的操作過程。採用處理器和比起處理器的寄存器更大的移位寄存器使得使數據位移位是一個非常低效的遞歸過程。當要移位的單元是字節或字的時候，移位就更簡單了，這是因為字節之間是沒有進位的。但是，移位過程仍然是一個遞歸、低效的過程。
在典型的實施例中，線性反饋移位寄存器是用循環的緩存器或滑動窗口來實現的。圖3A和3B中分別示出了在n時刻和n+1時刻循環緩存器24a中內容的圖。對於循環緩存器24a，移位寄存器中的每一個元件是存儲在存儲器中的相應的位置處的。一個索引或指示符30保留了圖3A中存儲器如Sk-1中儲存的最新元素的儲存位置。如圖3B所示，在時刻n+1，計算新的元素SK，並存儲在存儲器中最老的元素S0處。因此，所進行的不是使存儲器中的所有元素移位，而是將指示符30移位到新元素Sk的儲存位置上。當指示符30到達循環緩存器24a的末端時，將其復位到開頭的地方(如圖3A和3B所示)。這樣，循環緩存器24就象是一個圓，而不是一條直線。
如圖3A和3B所示，循環緩存器24a可以從左到右移位，或者從右到左移位。相應地，如圖3A和3B所示，指示符30從左到右移動，或者從右到左移動。移位方向的選擇是一種實施風格，並不會影響輸出結果。
為了按照遞歸關係產生輸出元素，通常要求從存儲器中得到一個以上的元素。可以用一個單獨的指示符來表示與每一所要求的元素相關的儲存位置，而指示符在使寄存器移位時被更新。也可以根據需要，從指示符30，計算與每一所需元素相關的儲存單元。由於每一元素與儲存單元有一個一一對應的變換關係，通過(按照遞歸關係)確定該元素與最新元素的偏差、在指示符30中加入該偏差，以及對被更新的指示符所表示的儲存單元進行尋址，可以得到某一特定的元素。由於存儲器的循環特性，被更新的指示符的計算是通過對指示符30的偏差的相加模k來確定的。當k是2的冪時否則在處理器上會是一種低效運算操作。
在本較佳實施例中，移位寄存器是用如圖3C所示的滑動窗口來實現的。滑動窗口24b的長度至少是循環緩存器24a的兩倍，並且包含相鄰排列的兩個循環緩存器32a和32b。循環緩存器32a和32b中的每一個就象是上述循環緩存器24a。循環緩存器32b完全與循環緩存器32a相同。在正常操作時，緩存器32b含有一些有意義的值。接著，根據緩存器32b中的值，計算緩存器32a中儲存的值。因此，移位寄存器中的每一個元素存儲在存儲器中的兩個相應的位置處，循環緩存器32a和32b各有一個。指示符34保留了循環緩存器32a中儲存的最新元素的儲存位置，即，圖3C中的Sk-1。在本典型實施例中，指示符34在滑動窗口24b的中間部分開始，從右移動到左，並且在到達左邊結束部分的時候再恢復到中間位置。
從圖3C可以看到，不管指示符34出現在循環緩存器32a的什麼地方，前面的k-1個元素可以被尋址至指示符34的右邊。因此，為了按照遞歸關係對移位寄存器中的某一元素進行尋址，將k-1或更小的偏差加到指示符34上。由於被更新的指示符總是指向指示符34的右側的，並且具有一定的計算效率，所以無需進行加法模k。對於這種結構，滑動窗口24b的長度任意，至少是循環緩存器24a的兩倍，並且忽略所有多餘的字節。另外，更新時間是固定的，並且較短。
IV.基於GF(28)上LFSR的典型數據流密碼可以通過基於GF(28)上的線性反饋移位寄存器的典型數據流密碼發生器來很好地描述本發明。下面描述的數據流密碼採用上述在階數為8的伽羅瓦域上的字節運算，在伽羅瓦域上，分別具有相加和相乘的_和_的表述。在本典型實施例中，表格查詢是用於與常數C進行相乘的。在本典型實施例中，滑動窗口用來進行移位寄存器的快速更新。
典型發生器的方框圖如圖4所示。在本典型實施例中，線性反饋移位寄存器52是17個8位字節(或136個數據位)長，使得移位寄存器52能夠有2136-1(或者約為8.7×1040)個狀態。整個寄存器為0的狀態不是一種有效的狀態，不會在任何一種狀態中出現這種狀態。以特定的非零元素數，按遞歸關係更新寄存器52的時間是常數，與寄存器52的長度無關。所以，可以在存儲器中額外字節的標定成本下，來實現添加寄存器52的長度(對於更高階的遞歸關係來說)。
在本典型實施例中，按照下面的遞歸關係來更新線性反饋移位寄存器52Sn+17＝(100Sn+9)Sn+4(141Sn) (4)這裡，運算是定義在GF(28)上的，_是由伽羅瓦加法器58所表示的兩個字節的異或運算，而_是伽羅瓦乘法器54所代表的多項式模乘法(見圖4)。在本典型實施例中，對係數56的模相乘是如上所述採用對預計算表進行字節表格查詢來進行的。在本典型實施例中，用等式(3)所定義的不可約多項式來計算多項式模乘法表。將等式(4)中遞歸關係選擇為最大的長度、具有極少的非零係數，從而所使用的移位寄存器元素不同於下述非線性函數所使用的移位寄存器元素。
在本典型實施例中，為了掩飾移位寄存器52的線性特徵，採用上述兩種技術，即擾動和採用非線性函數。採用的其他的非線性技術如下所述。在本典型實施例中，通過在多個移位寄存器52元件上進行非線性運算，來引入非線性特徵。在本典型實施例中，用非線性函數將移位寄存器52中的四個元件組合起來。典型的非線性函數如下所述Vn＝(Sn+Sn+5)(Sn+2+Sn+12) (5)這裡，Vn是非線性輸出(或發生器輸出)，_是由算術加法器60所代表的加法舍位模256，_是由模乘法器62所代表的乘法模257，並且將在下文中描述。在本典型實施例中，所使用的四個字節是Sn，Sn+2，Sn+5和Sn+12，這裡，Sn是按照等式(4)中的遞歸關係而在序列中最早計算的元素。選擇這些元素，從而當寄存器移位時，在兩個發生器輸出的計算中不會使用兩個元素。這些元素之間按對計算的距離是明顯不同的值。例如，Sn+12是不與Sn+5、Sn+2以及Sn組合的，因為它是通過寄存器52移位的。這一特性稱作是「全正差值組(full positive difference set)」。
簡單的字節與結果舍位模256相加由數據位之間的進位而在GF(28)中是非線性的。在本典型實施例中，寄存器中的兩對元素{(Sn和Sn+5)和(Sn+2和Sn+12)}用加法模256組合起來，而產生兩個中間結果。但是，由於最小有效位是沒有進位輸入的，並且仍然是線性組合在一起的，因而加法模256是不理想的。
另一種在處理器上可以方便地進行計算的非線性函數是乘法。但是，將普通的乘法舍位成只有一個字節不可能給出很好地結果，這是由於乘法模256因結果不是很好分布在數據域中的而不會形成一個編組。對素數257取整數模的一組相乘的數據域是可以使用的。這一數據組包含在1到256範圍內的整數，帶有分組運算是乘法約減模257。注意，0值是不會出現在該編組內的，但256值會出現在編組內。在本典型的實施例中，256值可以用0的字節值來表示。
一般說來，處理器可以有效地執行乘法指令，但許多的處理器卻不能執行或者說是有效地執行除法或取模運算。所以，模約減257可以代表一個性能頸瓶。但是，可以用計算模2n，來計算約減模257，在n＝8時在公共處理器上有效的。可以看到，對於在1到216-1範圍內的值X(這裡，X是兩個第8階運算對象相乘的結果)，約減模257可以計算為X257=X256-X256 257 ----(6)]]>式中，X257是X的約減模257，而X256是X的約減模256。等式(6)表示，一個16位的數的約減模257可以通過從8個最小有效位(X256)中減去8個最大有效位(X/256)而得到。相減的結果在-255和255之間，並且可以是負值。如果結果是負值，則可以通過加上257而將其調節到正確的範圍內。在另一種實施例中，採用包含65,536個元素而每一元素為8個數據位寬來執行約減模257運算。
兩個中間結果的相乘是可以利用的許多非線性函數中的一個。採用查詢表，也可以執行其他的非線性函數，如曲折函數或者在將它們組合起來之前對字節值進行置換。本發明指出使用各種非線性函數，以產生非線性輸出。
在本典型實施例中，採用擾動來注入附加的非線性關係。可以採用從上述線性反饋移位寄存器的狀態得到的非線性輸出來重新構築移位寄存器的狀態。這種重新構築由於不代表發生器輸出處的某些狀態並且是以不可預計的方式選擇的而變得更加困難。在本典型實施例中，採用非線性輸出來確定輸出數據流中會出現的非線性輸出的後續字節。當啟動發生器時，第一輸出字節用作擾動控制字節。在本典型實施例中，將每一個擾動控制字節分成四個數據位對，首先使用最小有效位。當已經使用了全部四個數據位對的時候，從發生器得到的下一個非線性輸出字節用作下一個擾動控制字節，等等。
每一對擾動控制數據位可以取四個值中的一個值。在本典型實施例中，表3中列出了每一對值中執行的動作。
表 3
如表3所示，在本典型實施例中，當數據對值是(0，0)時，使寄存器循環一次，但不產生輸出。寄存器的循環表示按照等式(4)進行下一個序列輸出的計算，並使新的元素移位到寄存器內。隨後，用下一個擾動控制對確定下一步要進行的動作。
在本典型實施例中，當數據對值是(0，1)時，使寄存器循環，並按照等式(5)來產生非線性輸出。使非線性輸出與常數(01101001)2異或，並提供結果作為發生器輸出。接著，使寄存器再次循環。圖4中，由異或門66執行異或功能處理，並由多路復用器(MUX)64用來自緩存器70的擾動控制數據位對來選擇常數。將異或門66的輸出提供到轉換器(switch)68，由它按照擾動控制數據位對的值提供發生器輸出和用於擾動控制的輸出字節。擾動控制的輸出字節被提供到緩存器70。
在本典型實施例中，當數據位對值是(1，0)時，使寄存器循環兩次，並給出按照等式(5)產生的非線性輸出，作為發生器輸出。
在本典型實施例中，當數據對值是(1，1)時，使寄存器循環，並按照等式(5)產生非線性輸出。接著使非線性輸出與常數(11000101)2進行異或，給出結果作為發生器輸出。
在本典型實施例中，選擇用在上述步驟中的常數，使得當產生發生器輸出時，使輸出中有一半的數據位相對於其他擾動控制對產生的輸出被交換。對於擾動控制對(1，0)，可以將非線性輸出看作是與常數(000000000)2的異或。所以，任意三個常數之間的海明Hamming距離是4。數據位變換還屏蔽了發生器的線性關係，並阻礙了根據發生器的輸出對狀態進行的重新構築。本發明支持多層密鑰控制結構。支持多層密鑰控制結構的數據流密碼特別適用於數據是在幀中發送出去的無線通信系統，這些數據幀有可能在接收中出現錯誤或失序。下面將描述典型的二層密鑰控制結構。
在本典型實施例中，採用一個密鑰來使發生器初始化。使用密鑰來使發生器在序列中有一個不可預計的跳躍。在本典型實施例中，密鑰的長度是4到k-1個字節(或者對於階數為17的典型遞歸關係為32到128個數據位)。最好不要採用小於4個字節的密鑰，這是因為初始隨機化是不合適的。也可以採用大於k-1個字節的密鑰，但這樣有些浪費，並且必須小心，使得密鑰的值不會使寄存器狀態被設置成全0，這是一種不會隨當前限制而出現的狀態。
典型密鑰初始化過程的流程圖如圖5中所示。過程在方框110處開始。在本典型實施例中，在方框112處，開始時，用斐波那契數模256來使移位寄存器的狀態初始化。所以，分別用1，1，2，3，5，8等等，使元素S0，S1，S2，S3，S4，S5等等初始化。儘管採用的是斐波那契數，但可以採用在伽羅瓦域中不是線性相關的任何一組非零數來使寄存器初始化。這些數不應當再具有可以用來重新構築寄存器的狀態的線性關係。
接著，在方框114處，將循環數n設置成零。接著，密鑰初始化進入一個循環。在該循環的第一個步驟中，即，在方框116處，將密鑰材料中第一個不用的字節加到Sn上。加上密鑰材料使得發生器在序列中進行了一次不可預計的跳躍。接著，在方框118處，使密鑰移位一個字節，從而刪去方框116中所使用的字節。隨後，在方框120處，使寄存器循環。方框116和120的組合有效地進行下面的計算Sn+17＝(100Sn+9)Sn+4(141(SnK)) (7)這裡，K是密鑰材料第一個不用的字節。循環數n在方框122處遞增。接著，在方框124處，判斷是否使用了所有的密鑰材料。如果回答是否，那麼過程就回到方框116。否則，過程繼續進行到方框126。
在本典型實施例中，在方框126處，將密鑰的長度加到Sn上。密鑰長度的添加使得發生器在序列中出現另外的跳躍。隨後，過程進入第二個循環。在第二個循環中的第一個步驟中，在方框128處，使寄存器循環。循環指數n在方框130處遞增，並且在方框132處，將其與發生器的階數k比較。如果n不等於k，那麼過程就回到方框128。否則，如果n等於k，那麼過程就繼續進行到方框134，將發生器的狀態儲存起來。接著，過程在方框136處終止。
除了密鑰以外，本發明中還可以使用第二密鑰。第二密鑰不能被看作是保密的，但卻是用在典型的無線電話系統中產生每一數據幀的唯一的密碼。這就確保了擦除的幀或失序的幀不會使信息流中斷。在本典型實施例中，數據流密碼以4個8位碼無符號的整數的形式來接受每一幀密鑰，稱作是幀密鑰。每一幀密鑰初始化與上述密鑰初始化的相似的，但卻是為每一數據幀而進行的。如果使用數據流密碼使得沒有必要使用每一幀密鑰信息，例如，對於一可靠線路上的文件轉發，那麼每一幀初始化過程是可以略去的。
採用密鑰的典型每一幀初始化過程的流程圖如圖6A所示。該過程在方框210處開始。在本典型的實施例中，在方框212處，用上述從密鑰初始化過程中儲存的狀態，來使發生器的狀態初始化。接著，在方框214處，將循環指數n設置成0。隨後，使每一幀初始化過程進入一個循環。在循環中的第一個步驟中，在方框216處，幀密鑰的最小有效位被模256加到Sn上。接著，在方框218處，使幀密鑰移位三個數據位，從而刪除在方框216中使用的三個最小有效位。接著，在方框220處，使寄存器循環。在本典型實施例中，使循環指數n在方框222處遞增，並在方框224處與11比較。方框224中所使用的11值對應於用作幀密鑰的32個數據位以及幀密鑰一次移位三個數據位這樣一個事實。幀密鑰的不同選擇以及一次移位不同數量的數據位會產生方框224中使用的不同的比較值。如果n不等於11，那麼過程就回到方框216。相反，如果n等於11，那麼過程就繼續進行到方框226，並且使寄存器繼續循環。在方框228處使循環指數n遞增，並在方框230處與2k比較。如果n不等於2k，那麼過程就回到方框226。相反，如果n等於2k，那麼過程就在方框232處中止。
上文中已經針對具有256個元素的典型伽羅瓦域描述了本發明。也可以採用不同的有限域，從而使元素的多少與用於計算元素的處理器以及/或者構成移位寄存器的存儲器的字節或字的長短一致起來，或者還具有其他的優點。因此，可以採用具有兩個以上元素的各種有限域，這也是屬於本發明的範圍的。
上述例子採用各種非線性處理器來屏蔽遞歸關係的線性關係的。可以採用不同的非線性處理過程，或上述非線性處理過程與其他的非線性處理過程的組合，來設計其他的一些發生器。因此，可以設計採用各種非線性處理過程來產生非線性的輸出，這也屬於本發明的範圍。
上述例子採用的是具有階數為17以及由等式(4)定義的遞歸關係。也可以產生具有其他階數的遞歸關係，這也屬於本發明的範圍。此外，對於給定的階數，可以產生各種不同的遞歸關係，這同樣屬於本發明的範圍。本發明中，最長長度的遞歸關係將給出最佳結果。
V.基於GF(28)上LFSR的第二種典型數據流密碼遞歸關係和非線性函數都對移位寄存器的元素進行訪問。僅選擇訪問哪一個元素，從而元素之間的距離形成「全正差值組」(「On Security of NonlinearFilter Generators」，J. Dj. Golic，in Proceedings of Fast SoftwareEncryption 1996 Cambridge Workshop，Springer-Variag 1996)。隨後，在遞歸關係和非線性函數之間劃分這些元素，以使每一個的擴展程度為最大。在這些限制下，可以進一步將本發明發展成增強密碼的保密性和計算的有效性。與第一種典型的實施例相比，第二種典型實施例提供了一種改進的密碼保密性。
在數學上，在GF(28)上的LFSR等效於在長度為136的GF(2)上的八個移位寄存器，每一個移位寄存器具有相同的遞歸關係。本發明的典型實施例包括在GF(28)上的遞歸關係，它等效於一種特徵多項式具有51個非零係數的二進位遞歸關係。遞歸關係中的三個抽頭位置是由上文中給出的標準來決定的(即，「全正差值組」)。
在理想情況下，GF(2)上階數為136的多項式，對於密碼分析和最大值擴散的最佳長度應當近似具有其一半的係數為1。在GF(28)上有許多的多項式，有三個係數接近於這一目標，但所有三個係數都大於1。這就是說，採用這些多項式需要三個查詢表和參照對象(reference)，其效用與本發明的當前結構相比較差。然而，這些多項式在理論保密性的基礎上是完全可以接受的。
以獲取可能的等效二進位多項式為目標，同時保留係數為1的當前結構(避免了乘法表和查詢)，分析表明，使用65個非零二進位係數可以給出近乎實現68個非零係數目標的較佳實施例。在GF(28)上滿足這些標準的多項式有16個。在GF(28)上總是按8個多項式編組，它們具有相同等效二進位多項式；這些多項式字節中的數據位發生了位置偏移。(可以找到每一等效的二進位多項式，例如，通過Berlekamp-Massey規則。)所以，如表4所示，有兩種類型完全不同的多項式滿足這一標準。對於本發明第二種典型的實施例，採用表4中第一組係數。
表4-遞歸係數
第二種典型發生器的方框圖如圖7中所示。在本典型實施例中，線性反饋移位寄存器82是17個八數據位長。當然，也可以採用其他長度的寄存器82(用於不同階數的遞歸關係)，這也屬於本發明的保護範圍。階數為17的遞歸關係很適合於採用多達128個數據位密鑰材料的應用場合。在本典型實施例中，按照下面的遞歸關係來更新線性反饋移位寄存器82Sn+17＝(206Sn+15)Sn+4(99Sn)(8)式中的運算是定義在GF(28)上的，是由伽羅瓦加法器88所代表的兩個字節上的異或運算，並且是由伽羅瓦乘法器84所代表的多項式模乘法器(見圖7)。在本典型實施例中，對係數86的模乘法是通過對上述預先計算的表格進行字節表格查詢來進行的。將等式(8)中的遞歸關係選擇為最大長度。
在本典型實施例中，為了掩飾移位寄存器82的線性關係，採用上述兩種技術，即，擾動和採用非線性函數。本說明書中還描述了其他的非線性技術。
在本典型實施例中，用相對於在GF(28)的線性運算是非線性的函數(或輸出等式)，通過將移位寄存器82的四個元素組合起來，引入非線性關係。在本典型實施例中，所使用的四個字節是Sn，Sn+2，Sn+5和Sn+12，這裡，Sn是按照等式(8)中的遞歸關係而在序列中最早計算的元素。
本發明的許多密碼保密性是由於採用了非線性函數而戰勝了對擾動相位的攻擊而得到，只要儘可能地非線性就可使該函數更強。
可以嘗試各種可能的函數，用以將非線性函數與最接近的線性近似按位比較，並計算與0.5的平均絕對偏差和均方根偏差，這在理論上是一個完美的結果。研究表明，最優秀的技術方案是從旋轉部分和得到的，這是一個在高階數據位中帶有影響的過程，從而將這些數據位與其他元素的最小有效位組合起來。
在微處理器上，加法函數通常一次僅接受兩個運算操作，因而最好的策略是在一次中間加法以後進行旋轉。將旋轉運算操作記為ROTL(x)，這意味著使x的數據位左移一個位置，因而更優越的非線性函數是Vn＝ROTL(Sn+Sn+2)+Sn+5+Sn+12(9)這裡，Vn是非線性輸出，而+是由算術加法器90所代表的加法舍位模256(捨棄溢出)。ROTL表示旋轉算符91。
加上Sn+5以後的附加旋轉似乎不會產生更好的結果。正如本說明書中所討論的那樣，採用明顯為非線性排列的查詢表給出了另一種方法，但這種方法明顯會有損本發明的計算效率。
在本典型實施例中，用於遞歸關係(8)的字節包含Sn，Sn+4和Sn+15，而用於輸出等式(9)的字節包含Sn，Sn+2，Sn+5和Sn+12。在本典型實施例中，選擇這些字節，使之具有特有的數據對距離。對於遞歸關係等式(8)，所使用的三個字節具有的數據對距離是4(Sn和Sn+4之間的距離)、11(Sn+4和Sn+15之間的距離)和15(Sn和Sn+15之間的距離)。同樣，對於輸出等式(9)，所使用的四個字節所具有的距離是2(Sn和Sn+2之間的距離)、3(Sn+2和Sn+5之間的距離)、5(Sn和Sn+5之間的距離)、7(Sn+5和Sn+12之間的距離)、10(Sn+2和Sn+12之間的距離)和12(Sn和Sn+12之間的距離)。遞歸關係(8)中的數據對距離(即，4，11和15)是在第一編組中唯一的，並且輸出等式(9)中的數據對距離(即，2，3，5，7，10和12)在第二編組內也是特有的。另外，遞歸關係(8)中的數據對距離與輸出等式(9)中的數據對距離也是明顯不同的。明顯不同的數據對距離確保了當移位寄存器82移位時，無論是在遞歸關係(8)中還是在非線性輸出等式(9)中都不會兩次使用移位寄存器82中特定的元素對。這一特性去掉了後續輸出等式(9)中的線性關係。
在本典型實施例中，圖7中所示的多路復用器(MUX)92、XOR門94、交換器(switch)96以及緩存器98是以與圖4中的MUX64、XOR門66、轉換器68以及緩存器70相同的方式工作的。
第二種典型的按幀初始化處理過程的流程圖如圖6B所示，它是圖6A所示流程圖的修改形式。
本實施例在第二密鑰裝載過程中採用非線性函數，從而以比以前更快的速度混合密鑰信息，使得在產生輸出之前進行的混合運行更短。這一特徵防止了寄存器的狀態形成寄存器總的狀態組的線性子空間。
將密鑰字節加到寄存器第5個字節上，而不是第0個字節上，而使擴展速度加快，這是遞歸關係元素之一。當加載「數據幀」時，一次放入8個數據位。除了進入來自「數據幀」的8位數據位以外，這一方法還在寄存器的第8個字節中加入了來自「nltap」的輸出。在「數據幀」已被加載以後，這種方法繼續使寄存器循環，並加入一些用於某些循環的輸出。
因此，將圖6B與圖6A相比，方框218被修改，從而使該數據幀移位了8個數據位，去掉了8個最小有效數據位。新的方框219加入了來自非線性函數的輸出。並且最終方框224中值的檢驗從11變到了4。
VI.基於GF(28)上LFSR的第三種典型的數據流密碼如上所述，可以進一步將本發明發展以加強密碼的保密性和計算效率，同時保持「全正差值組」。第三種典型實施例與第一種典型的實施例相比，使計算效率得到提高。
可以採用更簡單的遞歸關係，其方法是採用更簡單的二進位等效多項式，這樣將使密碼分析更為簡單。首先，給定全正差值組的約束，使Sn+4的係數都是1，就可以避免乘法表和相應的表格查詢。有8種這樣的遞歸，有相同的等效二進位多項式，含有35個非零係數。這些Sn的係數分別是40，45，46，57，110，117，132和140。
如果允許某些內部係數是零，則可以有更簡單的多項式。這時，去除的不僅可以是乘法，也可以是額外項的整個標記(reference)。有32個這樣的遞歸關係；其中的8個是具有11個非零係數的等效二進位多項式，而其餘的24項是具有13個非零係數的三個等效的二進位多項式。這些多項式中，8個多項式具有與Sn+1項相關的1係數，而其餘的16項使之與Sn+4項相關。前8個的等效二進位多項式看上去比其他的具有更加「擴展」的非零係數，因而對於本發明最短時間來說，將採用這樣的遞歸關係。Sn項的係數可以是79，83，166，187，225，239，243和252中任何數。對於本發明的第三種典型的實施例來說，採用第一個係數。因而遞歸關係變成Sn+17＝79Sn+Sn+15(11)在普通8位微處理器上，對移位寄存器元素的標記相當煩瑣。似乎可以完全去掉這些標記之一，也不會對保密性有太多的影響。選擇去掉元素Sn+2，儘可能地使這些值「擴展」。然而，最好使中間和旋轉，這是因為最小有效位的非線性關係不象所希望的那樣好。事實上，這時的最佳旋轉有四個位置。許多微處理器在實現這一操作時是執行「nybble-swap(半字節對換)」指令的。採用標記SWAP以表示使字節旋轉4個位置，非線性函數變成Vn＝SWAP(Sn+Sn+5)+Sn+12(12)第三種典型實施例發生器的方框圖如圖8所示。在本典型實施例中，線性反饋移位寄存器102的長度是17個8位數據位，當然，也可以採用其他長度的寄存器102(用於不同階數的遞歸關係)，並且這也屬於本發明的範圍內。階數為17的遞歸關係很適合於採用多達128個數據位的密鑰材料的應用場合。在本典型實施例中，線性反饋移位寄存器102是按照下面的遞歸關係(11)來更新的，這時的運算是定義在GF(28)上的，是對伽羅瓦加法器108所代表的兩個字節進行的異或運算，而是對伽羅瓦乘法器104所代表的兩個字節進行的多項式模乘法運算。本典型實施例中，對係數106進行的模乘法運算是對上述預計算表格進行字節表格查詢來進行的。可以將等式(11)中的遞歸關係選擇成是最大長度。
這裡，Vn是非線性輸出，而+是算術加法器110所代表的加法舍位模256計算(捨棄溢出)。SWAP表示對換算符111。
在本典型實施例中，圖8中的轉換器116和緩存器118是以上述圖4中的轉換器68和緩存器70所描述的方式工作的。
在擾動期間，在兩種情況下，非線性輸出是與常數項進行異或的。(見表3)在本例中，這些計算被取消。
VII.具有實時條件的系統中採用抽取數據流密碼發生的方法上述對數據進行加密的方法和裝置是許多數據流密碼的一個子集，它在設計中含有「擾動」，用於保密。其他經常使用的項是「不規則抽取」或「時鐘控制」。其意義是，以假定很難預計的方法，通過忽略某些更大密鑰數據流的元素來生成輸出密鑰數據流。在上述算法中，平均基礎移位寄存器有7次循環會產生3個8位數據位的輸出。其他在本領域中眾所周知的抽取發生器是收縮發生器(見D. Coppersmith等人的「收縮發生器」，Proc.Crypto』93，Springer-Verlag，1994)以及「自收縮發生器」(W.Meier和O.Staffelbach的「自收縮發生器」，Communications and CryptographyTwo sides of onetapestry，R.E.Blahut等人，eds，Kluwer Academic Publishers，1994)。
在行動電話應用中，經常採用數據流密碼來對相對較小的數據幀進行加密。移動站(蜂窩電話)通常有一個計算能力相對較小的計算機，以降低成本和功耗。移動站在將數據幀發送出去或者收聽者檢測到聲音的「丟失」的時機之前，有一個固定的時間進行加密或解密。
抽取上下文中的數據流密碼的問題是，它們對數據進行解密所花費的時間(或者說是輸出密鑰數據流的生成速率)是可變的。當數據量較大時，生成相同數量的密鑰數據流的總的時間統計變化不是很明顯的。但是，當每一數據幀中的數據量相對較小的時候(即，與上述線性反饋移位寄存器的尺寸具有相同的數量級的時候)，輸出中生成率的變化就很明顯了。這就會產生這樣的一種情況，即，移動站沒有充分的時間進行加密或解密。
上述算法在最後階段通過抽取(「擾動」)早先階段產生的輸出數據量來工作的。這是用輸出中的一個8位數據位(擾動控制字節)確定以後四個階段的行為來完成的。平均說來，每一這樣的字節控制從早先階段得到的6個值的消耗(最少4個，最多8個)，並產生3個輸出值(最少0個，最多4個)。在長時間取平均的基礎上對擾動控制字節本身進行計數，上述算法將生成基礎寄存器N次循環的輸出的3/7N個8位數據位。然而，也會有這樣的情況，即，抽取所引起的延遲會產生明顯更大的延遲。
本發明提供了一種方法，即，通過在產生過度延遲之前使抽取過程中斷，來限制對數據進行加密所需的時間。在本發明的第一種實施例中，加密系統識別加密時間是什麼時候變得過大的，並用在固定速率下產生輸出的保密性略弱的方法來產生其餘的密鑰數據量輸出。在另一種實施例中，加密系統將抽取過程限制在預定個數的抽取。
由於這種情況出現的可能性較少，並且出現這些情況對於預計或檢測加密的相反過程來說是不可能的，而且少量的輸出是用保密性較弱的方法來產生的，所以，輸出的加密分析仍然是不採用的。下面的例子給出，對於上面提供的算法，這是怎樣來完成的，但這一原理是應用於鍾控發生器，如，上面提到的收縮發生器。
該算法中，有兩個擾動特徵會引起密鑰數據量輸出產生率的變化。四種情況中有兩種情況下，採用兩個寄存器循環來產生一個8位數據位的輸出。在其餘的兩種情況下，執行一次循環，但僅在一半的時間裡產生一個8位數據位的輸出。所以，在四分之一的情況中，是沒有一點輸出產生的；而在其餘的時間裡產生一個8位數據位的輸出。另一方面，寄存器總循環數的變化控制整個抽取持續時間的變化。考慮到這些因素，有兩種不同的方法可以用來檢測發生器捨棄太多輸出的情況，同時這樣花費的時間太長。
1.初始化以後，可以對發生器不產生任何輸出的次數進行計數。當該計數達到某一閾值的時候，算法轉向到採用保密性較弱並更可能預計的方法。
2.初始化以後，計數器會對基礎移位寄存器的總循環數進行計數。當該計數器達到一個(不同的)閾值的時候，算法將會相反回到保密性稍差並具有更多可預計性的方法。
上述方法在組合的時候採用了兩種機制，以給出保密性。一種是移位寄存器的非線性函數功能。另一種是擾動機制。對於輸出量相對較少的情況，即到達幾百個8位數據位的情況，非線性函數本身將令給出合適的保密性。在本典型的實施例中，對數據進行加密的保密性較差的方法是簡單地取消輸出擾動，並從非線性函數中為基礎寄存器的每一循環產生一個輸出。對於其他的數據流密碼，需要採用其他的方法。比如，在收縮發生器中生成數據位的保密性較差的方法是採用從時鐘控制寄存器得到的輸出數據位來選擇來自其他寄存器的哪兩個連續的數據位將用於輸出。儘管該後退方案在由其自身使用時是不保密的，但在本上下文中還是足夠保密的。
上述第一種方法的變異形式是連續地監視沒有輸出生成的次數，並且無論什麼時候，只要有預定次數的循環數沒有輸出產生，就強迫產生一個輸出。例如，當有四次循環中沒有輸出產生時，就可以生成一個輸出。這就保證有一個輸出生成率的特別約束，因而在算法的每四次遞歸中永遠不會落到一個輸出以下。(可以將這種情形看作是對上文中提到的情形的略微複雜的擾動方法。)每次結束時必須使密鑰數據流發生器具有相同的配置參數，並且在同一時間上轉到保密性較弱的方法。
應當選擇用於轉向的參數，從而使給定數據幀加密強度較小的機率會很小，比方說是104個中有一個或更少。採用數學方法，可以從給定密碼的已知特徵得到這些參數，或採用模擬的方法來確定。這同時確保了採用保密性較弱的方法加密的數據量是很小的。在本典型實施例中，在104個寄存器循環的情況下，加密系統轉向到保密性較弱的密碼。採用上述加密系統，將意味著，在10,000個數據幀中，只有一個以下的數據幀會轉到保密性較弱的加密情況，並且其中，採用保密性較弱的方法，100中只有約一個會產生6個或更多個8位的數據位輸出(這是根據從104個循環到116個循環得到產生的8位數據位而估計的)。這種情況由加密分析檢測到是極為不可能的，這是因為6個8位數據位中的任何一個數據流代表的是二分之一不到的寄存器狀態，這在正常操作運行的隨機情況下同樣也會發生。
參見圖9，來描述加密過程中對延遲進行限制的加密系統。加密子系統A302執行較佳的加密操作。即，加密子系統A 302比起通過加密子系統B 300來說，具有更大的保密性。但是，與加密子系統B 302所執行的加密操作相比，加密子系統B 300所執行的加密操作具有較少的延遲。
加密子系統A 302所提供的有關密鑰數據流的信息被提供到超時檢測器306，由該檢測器檢測產生密鑰數據流連續部分的時間，或者在另一些監視器中是產生對數據幀進行加密的累計時間。當從加密子系統A 302產生連續部分的密鑰數據流的時間或者對一部分數據幀進行加密的累計時間超過了預定的門限值的時候，超時檢測器306就向轉換器304發送一個信號，指令轉換器300應當採用加密子系統B 300所提供的密鑰數據流，以替代加密子系統A 320所提供的密鑰數據流。
將轉換器304選擇的密鑰數據流提供到混合器308的第一輸入。混合器308將要加密的數據與選擇的密鑰數據流混合，並輸出經加密的數據。
圖10描述的是圖9中本發明的特定實施結構。在圖10實施的特定實施結構中，較佳的加密操作按照線性運算操作、非線性運算操作以及隨機抽取操作，產生密鑰數據流。當抽取過程預示將會在加密過程引起過度的延遲的時候，那麼將轉變成退出該操作。
圖10中，加密過程的線性部分是由線性反饋移位寄存器(LFSR)328執行的，其結構在本領域中是眾所周知的，其結構如上所述。線性反饋移位寄存器328將其輸出和一組寄存器的內容提供至非線性運算處理器324。非線性運算處理器324對線性反饋移位寄存器328的輸出以及線性反饋移位寄存器328提供的寄存器內容進行非線性處理，並將非線性運算操作的結果輸出到抽取器322和轉換器326。
抽取器322對非線性運算器324的輸出進行隨機化的抽取，由它按照偽隨機選擇過程，刪除非線性運算器324提供的一部分數據，並將隨機抽取的數據流提供到轉換器326。
在正常操作時，轉換器326將抽取的密鑰數據流從抽取器322輸出到異或門330。但是，當抽取控制器320檢測到抽取過程預示著會在加密數據中引入過度的延遲的時候，抽取控制器320向轉換器326發送一個信號，而由轉換器326根據輸出，輸出從非線性運算處理器324提供的密鑰數據流，而不進行抽取。在本典型實施例中，抽取控制器320通過對線性反饋移位寄存器328的移位數進行計數，或者通過對抽取器322提供的抽取量進行計數，來檢測變得過長的抽取過程。由抽取器322抽取的線性反饋移位寄存器328的移位數或者從非線性運算器324的輸出數由抽取控制器320用來確定何時抽取過程變得過長了。
本實施例的方框圖如圖11所示。圖11是圖7中所描述的發生器的修改形式，其中加入了對加密延遲進行限制的裝置。在本典型實施例中，線性反饋移位寄存器382有17個8位數據位長。當然，寄存器382也可以採用其他的數據長度(用於不同階數的遞歸關係)，這也屬於本發明的範圍。階數為17的遞歸關係很適合於採用多達128個數據位的密鑰材料應用場合。在本典型實施例中，線性反饋移位寄存器382是按照下面的遞歸關係來更新的Sn+17＝(206Sn+15)Sn+4(99Sn) (13)
這裡，運算是定義在GF(28)上的，是對伽羅瓦加法器388所代表的兩個字節進行異或運算，而是對伽羅瓦乘法器384所代表的多項式模乘法運算。在本典型實施例中，對係數386進行的模乘法運算是通過對上述預先計算的表格進行查詢來實行的。將等式(13)中的遞歸關係選擇為最大長度。
在本典型實施例中，為了捨棄移位寄存器382的線性關係，採用上述兩種技術，即，擾動和採用非線性函數。其他的非線性技術在本說明書的其他部分也有描述。
本典型實施例中，非線性關係是通過將移位寄存器382的四個元素採用相對於在GF(28)上的線性運算是非線性的函數(或輸出等式)進行合併而引入的。在本典型實施例中，所採用的四個字節是Sn，Sn+2，Sn+5和Sn+12，這裡，Sn在按照等式(13)中的遞歸關係的序列中是最早計算的元素。
本發明的許多密碼保密性是利用非線性函數來防止對擾動階段產生攻擊而得到的，因而要求該函數儘可能是足夠非線性的。
發明人嘗試了許許多多種可能的函數，從而將非線性函數與每一數據位位置中最接近的線性近似進行比較，並計算與0.5的平均絕對偏差和根均方偏差，而「0.5」是在理論上完美的結果。研究表明，優秀的技術方案是通過使部分和旋轉而得到的，這是一個在高階數據位上具有進位效果的過程，從而使這些數據位與其他元素的最小有效位混合起來。
在一個微處理器處，加法運算通常一次僅接受兩個運算，從而最好的策略是在一次中間加法以後進行旋轉。將旋轉運算記為ROTL(x)，這就是說使x的數據位左旋一個位置，那麼更好的非線性函數是Vn＝ROTL(Sn+Sn+16)+Sn+1Sn+6+Sn+13(14)這裡，Vn是非線性輸出，而+是由運算加法器390進行的加法舍位模256(捨棄了溢出)運算。ROTL表示旋轉運算391。
在加上Sn+5以後進行的附加旋轉似乎不會給出更好的結果。正如在本說明書的其他地方所討論的那樣，採用非線性置換的查詢表給出了另一種方法，但明顯會破壞本發明的計算效率。
在本典型實施例中，用於遞歸關係(13)的字節包含Sn，Sn+4和Sn+15，而用於等式(14)的字節包含Sn，Sn+1，Sn+6，Sn+13和Sn+16。在本典型實施例中，選擇的這些字節具有明顯不同的數據對距離。對於等式(13)的遞歸關係，所使用的這些字節具有數據對距離4(Sn和Sn+4之間的距離)、數據對距離11(Sn+4和Sn+15之間的距離)以及數據對距離15(Sn和Sn+15之間的距離)。同樣，對於輸出等式(14)，所使用的5個字節具有數據對距離1(Sn和Sn+1之間的距離)、3(Sn+13和Sn+16之間的距離)、5(Sn+1和Sn+6之間的距離)、6(Sn和Sn+6之間的距離)、7(Sn+6和Sn+13之間的距離)、10(Sn+6和Sn+16之間的距離)、12(Sn+1和Sn+13之間的距離)、13(Sn和Sn+13之間的距離)、15(Sn+1和Sn+16之間的距離)和16(Sn和Sn+16之間的距離)。遞歸關係(13)之間的距離(即4，11和15)在第一編組內是唯一的(或特有的)，比起輸出等式(14)中的數據對距離(即，1，3，5，6，7，10，12，13，15，和16)在第二編組內也是特有的。另外，遞歸關係(13)中的數據對距離除了一個數據對距離15以外，在輸出等式(14)中是唯一的。特有的數據對距離確保了當移位寄存器382移位的時候，無論是在遞歸關係(13)中還是非線性輸出等式(14)中都不會使用兩次。這種特性去除了後續輸出等式(14)中的線性關係。
在本典型實施例中，圖11中的多路復用器(MUX)392、異或(XOR)門394、轉換器396以及緩存器398是以上述參照圖4中的MUX64、XOR門66、轉換器68以及緩存器70的方式工作的。
來自轉換器396的抽取密鑰序列和加法器390b的輸出被提供到轉換器402。在正常操作下，轉換器402輸出來自轉換器396的抽取的密鑰序列。然而，如果抽取控制器400檢測到加密過程由於抽取過程的可變性而引入了過度的延遲，則抽取控制器400向轉換器402發送一個信號，使轉換器402輸出未抽取的序列。轉換器402的輸出與數據序列混合，提供經加密的數據。
在本典型實施例中，抽取控制器400通過對加法器390b輸出的密鑰數據流的某些部分進行選通而對來自緩存器398的輸出數進行計數，或者通過對移位寄存器382的移位數進行計數，來檢測加密延遲是否過長。也可以採用抽取擾動過程所引入的延遲的其他方法，這些方法同樣屬於本發明的範圍。
加密數據的接收機必須知道什麼時候在轉換器396輸出的抽取密鑰序列和加法元件390b輸出的未抽取的序列之間轉換。在本典型實施例中，接收機還包括相同的抽取控制器400和轉換器402，並將以與加密數據的發射機處相同的方式，在抽取和未抽取的序列之間轉換。因此，就不必具有抽取的和未抽取的密鑰序列之間的時間變換的明確提示了。
第二種典型的按數據幀初始化過程的流程圖如圖6B所示，它是圖6A所示流程圖的修改形式。
本實施例在第二密鑰裝載過程中採用非線性函數，以比以前更快的方式來混合密鑰信息，從而使得在產生輸出之前的混合時間更短。這一特徵防止了寄存器成為寄存器總狀態數的線性子空間。
將密鑰字節加到寄存器的第15個字節上，而不是加到第0個字節上，從而使擴展加速，這是遞歸關係元素中的一個。當裝入「數據幀」的時候，一次輸入8個數據位。除了加入來自「數據幀」的8位數據位以外，本方法還將來自「nltap」的輸出加到了寄存器的第8個字節上。在已經裝載了「數據幀」以後，本方法繼續使寄存器循環，並加入某幾個循環的輸出。
因此，比較圖6B和6A，方框218被修改，從而數據幀移位了8個數據位，以去掉8個最小有效位。新的方框219加入了來自非線性函數的輸出。並且最終在方框224中檢驗的值從11變到了4。
前文中對較佳實施例的描述使得本領域中的普通技術人員能夠製造和使用本發明。很明顯，本領域中的普通技術人員還能對這些實施例作各種修改，可以無需發明人的幫助，將本文中所描述的基本原理應用於其他的實施例。所以，本發明並非僅限於這些實施例，應當從最寬的範圍來理解本發明的原理和新特徵。
權利要求
1.一種對數據進行加密的裝置，其特徵在於，它包含產生第一密鑰數據流的第一發生器；產生第二密鑰數據流的第二發生器；接收所述第一密鑰數據流和所述數據以及將所述第一密鑰數據流和所述數據混合起來以提供加密數據的混合器；以及測量由所述第一發生器產生所述第一密鑰數據流時的延遲的延遲測量裝置；其中，所述混合器還用來接收所述第二密鑰數據流和所述數據，並將所述第二密鑰數據流和所述數據混合，在所述測量的延遲超過某一閾值的時候，提供經加密的數據。
2.如權利要求1所述的裝置，其特徵在於，所述第一發生器按照預定的抽取算法，產生所述第一密鑰數據流。
3.如權利要求1所述的裝置，其特徵在於，所述第一發生器包含按照一種線性發生格式產生隨機碼元序列的線性發生器裝置；對所述隨機碼元序列執行非線性運算以提供第二隨機碼元序列的非線性裝置；以及選通所述第二隨機碼元序列的一些部分的偽隨機抽取器。
4.如權利要求3所述的裝置，其特徵在於，所述第二發生器包含按照一種線性發生格式產生隨機碼元序列的線性發生器裝置；以及對所述隨機碼元序列執行非線性運算以提供第二隨機碼元序列的非線性發生器。
5.如權利要求1所述的裝置，其特徵在於，所述遞歸關係的階數為17。
6.如權利要求3所述的裝置，其特徵在於，所述第一發生器按照遞歸關係Sn+17＝(206Sn+15)Sn+4(99S)，產生所述第一隨機序列，這裡的運算是定義在GF(28)上的，_是對兩個字節的異或運算，而_是多項式模乘法。
7.如權利要求3所述的裝置，其特徵在於，所述線性發生器是用線性反饋移位寄存器來實施的。
8.如權利要求7所述的裝置，其特徵在於，所述延遲測量裝置測量所述線性反饋移位寄存器的移位數。
9.如權利要求7所述的裝置，其特徵在於，所述延遲測量裝置測量由所述偽隨機數抽取器選通的所述第二隨機碼元序列的部分數。
10.如權利要求8所述的裝置，其特徵在於，所述線性反饋移位寄存器是用滑動窗口構成的。
11.一種對數據進行加密的方法，其特徵在於，它包含產生第一密鑰數據流；產生第二密鑰數據流；將所述第一密鑰數據流和所述數據混合，給出經加密的數據；以及測量所述第一密鑰數據流的步驟中的延遲；將所述第二密鑰數據流和所述數據混合，當所述測量得到的延遲超過預定的閾值的時候，提供經加密的數據。
12.如權利要求11所述的方法，其特徵在於，生成所述第一密鑰數據流的所述步驟是按照預定的抽取算法來進行的。
13.如權利要求11所述的方法，其特徵在於，生成所述第一密鑰數據流的所述步驟還包含下述步驟按照一線性生成格式，產生隨機的碼元序列；對所述隨機碼元序列執行非線性運算，以提供第二隨機碼元序列；以及選通所述第二隨機碼元序列的一些部分。
14.如權利要求13所述的方法，其特徵在於，生成所述第二密鑰數據流的所述步驟包含下述步驟按照線性生成步驟，產生一隨機的碼元序列；以及對所述隨機的碼元序列執行非線性運算，以提供第二隨機碼元序列。
15.如權利要求13所述的方法，其特徵在於，所述線性生成格式的階數是17。
16.如權利要求所述的方法，其特徵在於，按照線性生成格式生成所述第一隨機碼元序列的所述步驟按照遞歸關係Sn+17＝(206Sn+15)Sn+4(99S)產生所述第一隨機序列，式中，運算是定義在GF(28)上的，_是對兩個字節的異或運算，而_是多項式模乘法。
17.如權利要求13所述的方法，其特徵在於，生成所述第一隨機序列的所述步驟是用線性反饋移位寄存器來實施的。
18.如權利要求17所述的方法，其特徵在於，測量實施延遲的所述步驟是通過對所述線性反饋移位寄存器的移位數進行計數來進行的。
19.如權利要求17所述的方法，其特徵在於，測量所述延遲即對所述偽隨機抽取器選通的所述第二隨機碼元序列的部分數進行計數。
20.如權利要求18所述的方法，其特徵在於，所述線性反饋移位寄存器是用一滑動窗口來實現的。
21.一種生成數據流密碼的方法，其特徵在於，它包含選擇具有階數大於2的有限域；在所述有限域上選擇一種遞歸關係；選擇一種輸出函數；以及按照所述遞歸關係和所述輸出函數來計算所述數據流密碼，其中，所述遞歸關係和所述輸出函數具有明顯不同的數據對差，並且根據密碼保密性和計算效率，選擇所述遞歸關係和所述輸出函數，以使特性標準為最佳。
22.如權利要求1所述的方法，其特徵在於，所述有限域是根據用於計算所述數據流密碼的處理器的字長來選擇的。
23.如權利要求1所述的方法，其特徵在於，所述有限域是含有256個元素的伽羅瓦域。
24.如權利要求1所述的方法，其特徵在於，所述遞歸關係是最大長度。
25.如權利要求1所述的方法，其特徵在於，所述遞歸關係的階數是17。
26.如權利要求1所述的方法，其特徵在於，所述遞歸關係是用線性反饋移位寄存器來實現的。
27.如權利要求6所述的方法，其特徵在於，所述線性反饋移位寄存器是用循環緩存器來構成的。
28.如權利要求6所述的方法，其特徵在於，所述線性反饋移位寄存器是用滑動窗口構成的。
29.如權利要求1所述的方法，其特徵在於，所述性能標準是僅僅根據密碼的保密性來實現的。
30.如權利要求1所述的方法，其特徵在於，所述性能標準是僅僅根據計算效率來實現的。
31.如權利要求1所述的方法，其特徵在於，所述輸出函數包含計算所述發生器的狀態的非線性函數。
32.如權利要求11所述的方法，其特徵在於，所述輸出函數包含數據位的旋轉。
33.如權利要求11所述的方法，其特徵在於，所述輸出函數包含數據位的對換。
34.如權利要求1所述的方法，其特徵在於，所述計算步驟包含域相乘和模相加。
35.如權利要求14所述的方法，其特徵在於，所述域相乘的結果是由素數的模來約減的。
36.如權利要求15所述的方法，其特徵在於，所述的素數是257。
37.如權利要求14所述的方法，其特徵在於，所述的域相乘是用查詢表來實現的。
38.如權利要求17所述的方法，其特徵在於，所述的查詢表是預先計算並存儲在存儲單元內的。
39.如權利要求14所述的方法，其特徵在於，所述域相乘是通過下述步驟來實現的對兩個運算對象中的每一個的對數值表格進行查詢；對所述兩個運算對象的對數值進行模相加，以得到一個組合的對數值；以及對所述組合的對數值的指數值表格進行查詢。
40.如權利要求1所述的方法，其特徵在於，它還包含下述步驟用一個密鑰來使所述發生器初始化。
41.如權利要求20所述的方法，其特徵在於，所述初始化步驟包含下述步驟將所述密鑰的最小有效字節加到所述遞歸關係上；使所述密鑰移位一個字節；以及重複所述相加步驟和所述移位步驟，直到所述密鑰內的所有的字節都被加到了所述遞歸關係上。
42.如權利要求20所述的方法，其特徵在於，所述密鑰的長度小於所述遞歸關係的階數。
43.如權利要求20所述的方法，其特徵在於，它還包含下述步驟按照數據幀的密鑰，對所述發生器進行初始化。
44.如權利要求23所述的方法，其特徵在於，按照數據幀的密鑰對所述發生器進行所述初始化包含下述步驟將所述按照數據幀的密鑰的最小有效字節加到所述遞歸關係上；使所述按照數據幀的密鑰移位三個數據位；重複所述相加步驟和所述移位步驟，直到所述數據幀的密鑰中的所有的字節被加到了所述遞歸關係上。
45.如權利要求23所述的方法，其特徵在於，所述按照數據幀的密鑰的長度是4個8位數據位長。
46.如權利要求23所述的方法，其特徵在於，用數據幀密鑰使所述發生器進行所述初始化的步驟是針對每一數據幀進行的。
47.一種生成數據流密碼的裝置，其特徵在於，它包含接收用於執行遞歸關係和輸出函數的指令的處理器，所述處理器按照所述指令執行對元素的運算，其中，所述遞歸關係和所述輸出函數具有明顯不同的數據對差異，以及根據密碼的保密性和計算效率，選擇所述遞歸關係和所述輸出函數，以使性能標準為最佳。
48.如權利要求27所述的裝置，其特徵在於，所述遞歸關係是定義在具有大於1的階數的有限域上的。
49.如權利要求28所述的裝置，其特徵在於，所述有限域是按照所述處理器的字長來選擇的。
50.如權利要求28所述的裝置，其特徵在於，所述有限域是含有256個元素的伽羅瓦域。
51.如權利要求27所述的裝置，其特徵在於，所述遞歸關係是最大長度。
52.如權利要求27所述的裝置，其特徵在於，所述遞歸關係的階數是17。
53.如權利要求27所述的裝置，其特徵在於，所述遞歸關係是用線性反饋移位寄存器來實現的。
54.如權利要求33所述的裝置，其特徵在於，所述線性反饋移位寄存器是用循環緩存器來構成的。
55.如權利要求33所述的裝置，其特徵在於，所述線性反饋移位寄存器是用一個滑動窗口來實現的。
全文摘要
產生加密數據流密碼的方法和裝置是基於一種遞歸關係的,該遞歸關係是在大於GF(2)的有限域上工作的。可以採用一種或組合的非線性過程以形成輸出函數來獲得非線性輸出。可以選擇遞歸關係和輸出函數使之具有明顯不同的數據對距離,從而當移位寄存器(52)移位時,無論是在遞歸關係中還是在輸出函數中,都不會在移位寄存器(2)中兩次使用相同的數據對元素。在這些條件下,還可以選擇遞歸關係和輸出函數,以使密碼保密性或計算效率為最佳。另外,本發明另一要解決的問題是提供一種確保形成加密過程的延遲不會超過預定的界限的方法。為此,測量加密延遲,如果估計的延遲超過了預定的閾值,則採用第二種加密方法,來限制加密操作的累計延遲。
文檔編號H04L9/22GK1347607SQ00803505
公開日2002年5月1日 申請日期2000年2月4日 優先權日1999年2月8日
發明者G·G·羅斯, 小R·F·奎克 申請人:高通股份有限公司