非線性循環移位寄存器的製作方法

2023-10-05 10:26:49 4

專利名稱：非線性循環移位寄存器的製作方法
技術領域：
非線性循環移位寄存器(NRSR)是保密通信領域用於產生非線性偽隨機序列的密碼部件，主要用途設計流(序列)密碼算法；設計分組密碼中的密鑰編排算法；設計雜湊 (Hash)函數中的消息擴展算法。
背景技術：
密碼編碼中產生偽隨機序列的常用密碼部件有線性反饋移位寄存器(LFSR)[1]和非線性反饋移位寄存器(NLFSR)[2]等，以下合稱(N)LFSR。例如，第2代移動通信系統GSM 的加密標準A5算法[3』4]、藍牙加密標準EO算法M和流密碼國際標準SN0W2算法[3]都採用了 LFSR ；雜湊(Hash)函數標準SHAl和SHA2的消息擴展算法[3]以及第3代標準SHA3的多個候選算法採用了(N) LFSR或其它發生器。η級(N) LFSR的當前輸出比特都是前η比特的邏輯函數(η彡2)，這樣的邏輯函數共有22η個，其中線性的有2η個，非線性的有22η-2η個。LFSR採用以下反饋模式由前η比特 (a, 『Η)線性遞推下一比特^vi an+i = Bi-C^aw"-"cliWl (其中常數 ck = 0 或 1，1 彡 k 彡 n_l，~ 是模 2 加法，i 一般從0開始)如果輸入的初始η比特( 全為0，則LFSR輸出恆為0，因此，η級 LFSR的最大周期為2η-1。若且唯若LFSR的反饋多項式為本原多項式時，LFSR的周期才達到最大。產生一個本原多項式並不容易，可藉助數學軟體包。SHAl的消息擴展算法採用以下模式由前16個字(wt_16 WtJ遞推下一個字Wt wt = (wt_3"wt_8"wt_14"wt_16) <<< 1 ( <<< 1 表示循環左移 1 位，字長 m 為 32 比特)這相當於字長m為32b (比特)的16級發生器，如果輸入的初始16個字(wQ W15)全為0，則輸出恆為0，因此，其最大周期小於等於032)16_1。11級^^51 的最大周期為2\當字長為m比特時(m—般取平臺的位數，例如8、16、32、64)，n級非線性循環移位寄存器(NRSR) 的周期大於Om)n。(N) LFSR軟體實現慢，解決的辦法是並行m個(N) LFSR，相當於字長為m 比特，但最大周期還是小於等於2n，除非象SN0W2 —樣採用模2m的本原多項式，最大周期才小於等於Om)n。也就是說，對於不同的字長m和不同的級數n，(N)LFSR要尋找不同的反饋模式。不管字長m和級數η為多大，NRSR存在統一的反饋模式，無須尋找達到最大周期的反饋模式，可以直接適應各種平臺，包括將來1 位以上的平臺。在32位平臺下0.4GHz 雙核 CPU、2GB 內存、Windows XP、C 語言)，SN0W2 的 LFSR 速度為 630MB/s。SHAl 和 SHA256 的消息擴展算法速度都小於400MB/S。NRSR的速度為700MB/s。對於A5和EO算法採用的 LFSR，除非同時並行32個LFSR，效率才和NRSR相當。對於周期達到最大的(N)LFSR，其輸出是絕對均勻的，遍歷了所有狀態才會重複。測試表明，NRSR產生的輸出是偽隨機均勻的， 又能遍歷所有狀態。[1](美)Schneier B.應用密碼學——協議、算法與C源程序.吳世忠等譯.機械工業出版社，2000-1. 264 269[2](中)王育民，劉建偉.通信網的安全——理論與技術.西安電子科技大學出版社，1999-04. 81 82[3](中)谷利澤，鄭世慧，楊義先.現代密碼學教程.北京郵電大學出版社， 2009-08. 169 175，189 204W](中)徐勝波，馬文平，王新梅.無線通信網中的安全技術.人民郵電出版社， 2003-07. 149 150，183 18
發明內容
發明目的為了快速產生偽隨機性更好的輸出序列，用於設計安全高效的對稱密碼算法和雜湊(Hash)函數，非線性循環移位寄存器(NRSR)相比(N) LFSR而言，擴大了輸出序列的周期，改善了輸出的偽隨機性，增強了多平臺適應性，提高了效率。技術方案非線性循環移位寄存器(NRSR)是一種新型反饋移位寄存器(FSR)，其採用的技術方案是當字長為m比特時(111一般取平臺的位數，例如8、16、32、64)，11級殿51 採用以下反饋模式由前η個字( h)遞推下一個字 +n(n彡2，i從0或從1開始均可)al+n = {[c x r (b X a,+n-,) ......Θ C1X X a,)] + C0} mod 2m其中，rk(a) (1 ^ k ^ n)表示a循環移位，至少有一個循環移位數在0 m_l之間循環變化，其它可以不移位； 表示模2加(逐位異或)或者模2m加，X表示模2m乘，mod 2m表示模2m運算(求餘數)；bx、cy為0 2m-l之間的整數(1彡χ彡n，0彡y彡n)，但cQ、 Vc1為奇數，還有1對(bx，cx)為奇數O 彡η)，一般bn、Cn取奇數；輸入的初始η個字 (a0 取值都不限，輸入的每個字都可以是任意m比特長的數。為提高效率，我們推薦使用簡單的NRSR，由前η個字( + _》中的2個字遞推下一個字(首字 必選，一般取首尾2個字，如附圖1所示)α,+η = {[( δ X α,+ -ι) (a, < j)] + 1 } mod 2m其中，b為3 2m_l之間循環變化的奇數，可取b = 2 +1 ；<<< j表示循環左移 j位，j在0 m-Ι之間循環變化，可取j = i mod m。當m較大時，例如m彡32，從應用上來說，b在3 2m-l之間循環變化與b在1 2m-l之間循環變化的性能差異不大。
如果平臺處理乘法的能力差，可取al+ = {[( ,+ -1< /) <3, ] + 1 } mod ImNRSR與(N) LFSR不同之處在於(1)乘法係數b循環變化；( 循環移位數j循環變化；(3)計數加1。有益效果相比(N)LFSR而言，非線性循環移位寄存器(NRSR)有以下優點(1)周期更大、安全性更高。由於乘法係數b和循環移位數j不固定，η級NRSR的周期大於(2m)n(字長為m比特)。對於反饋模式[( + <<< 216B (字節)；3 級 NRSR 的周期為 81，782456 > 224 (16MB) ；4 級 NRSR 的周期為 27，251403552 > 232 (4GB)。當字長為16b時，2級NRSR的周期為37，540033008 > 4G個短整數。對於反饋模式 *= [(bXai+nl) + (ai << 216(64KB)。如果b取3 2m_l之間循環變化的奇數，周期更大。測試表明，周期與寄存器的初值、循環移位數j的初值及乘法係數b的初值無關。對於周期達到最大的LFSR，其輸出狀態1 2n_l是絕對均勻的；對於周期達到最大的NLFSR，其輸出狀態0 2n-l是絕對均勻的，遍歷了所有狀態才會重複。測試表明，NRSR 產生的輸出是偽隨機均勻的，沒有遍歷所有狀態也可能出現重複(寄存器狀態重複不一定是周期重複，當寄存器的狀態和循環移位數j的狀態以及乘法係數b的狀態同時重複才是周期重複)。因此，NRSR的不可預測性和安全性優於(N)LFSR。NRSR輸入的初始η個字( ^v1)取值都不限，可以全為0。對於雜湊(Hash)函數標準SHAl和SHA2的消息擴展算法，如果初始消息全為0，則擴展消息也全為0。NRSR不存在該問題。另外，有個分組密碼算法叫RC6，需要5輪加密才能實現偽隨機性。其加密輪函數 f(i, a, b, c, d)為{u = [d(2d+l)] <<< 5 ;t = [b(2b+l)] <<< 5 ;a = [(a"t) <<< u]+k[i]； c = [(c"u) <<< t]+k[i+l] ；}用NRSR直接取代2個緩存變量u和t，對d和b進行可逆更新{t = d ;d = [(t+1) < < < i]+b ；b = (d < < < i)+t+l ；a = [(a"d) <<< b]+k[i] ；c = [(c"b) <<的本原多項式，最大周期才小於等於Qm)n。也就是說，對於不同的字長m和不同的級數n，(N)LFSR要尋找不同的反饋模式。不管字長m和級數η為多大，NRSR存在固定的反饋模式如》= ([( α 1 + -, < j) a, ] + U mod 2m (j在 m_l之間循環變化， 表示模2加或者模2m加)和α,+ = {[( bXal+n-x)&(a,< j)] + 1 } mod 2m (b為3 2m_l之間循環變化的奇數)，無須尋找達到最大周期的反饋模式，可以直接適應各種平臺，包括將來1 位以上的
D ο


圖1非線性循環移位寄存器(NRSR)說明<<< j表示循環左移j位， 表示模2加(逐位異或)或者模2m加，X表示模2m乘，mod m表示模m運算(求餘數)；m—般取平臺的位數，例如8、16、32、64 ;i從0 或從1開始均可，η彡2。
具體實施例方式(1)當字長為m比特時(m—般取平臺的位數，例如8、16、32、64)，η級非線性循環移位寄存器(NRSR)由前η個字( 中的首尾2個字( , Bi^1)遞推下一個字ai+n(如附圖1所示，η彡2，i從0或從1開始均可)al+ = {[( 6 X α,+η-ι) (a, <j·)] + 1 } mod 2"其中，b為3 2m_l之間或1 2m_l循環變化的奇數，可取b = 2 +1 ；<<< j表示循環左移j位，j在0 m-1之間循環變化，可取j = i mod m 表示模2加(逐位異或) 或者模2m加，X表示模2m乘，mod 2m表示模2m運算(求餘數)。輸入的初始η個字( an_i)取值都不限，輸入的每個字都可以是任意m比特長的數。當m較大時，例如m彡32，從應用上來說，b在3 2m-l之間循環變化與b在1 2m-l之間循環變化的性能差異不大。(2)如果平臺處理乘法的能力差，當字長為m比特時，η級非線性循環移位寄存器 (NRSR)由前η個字( + _)中的首尾2個字( , +」遞推下一個字 +η，可取al+n= {[( α,+ , < ; ) α, ] + 1 } mod 2m其中，<<< j表示循環左移j位，j在0 m-Ι之間循環變化，可取j = i mod m 表示模2加或者模2m加。(3)當字長為m比特時，η級非線性循環移位寄存器(NRSR)由前η個字遞推下一個字 +η，也可取al+ = {[c X r (b X a,+frl) ...... d Xr1C^X a,)] + C0} mod 2m其中，rk(a) (1彡k彡n)表示a循環移位，至少有一個循環移位數在0 m_l之間循環變化，其它可以不移位；bx、cy為0 2m-l之間的整數(1彡χ彡n，0彡y彡η)，但cQ、 bp C1為奇數，還有1對(bx，cx)為奇數0彡乂彡11)，一般1^、(^取奇數； 表示模2加(異或)或者模2m加，X表示模2m乘，mod 2m表示模2m運算(求餘數)。
權利要求
1.非線性循環移位寄存器(NRSR)是一種新型反饋移位寄存器(FSR)，其總體特徵是 當字長為m比特時(m—般取平臺的位數，例如8、16、32、64)，η級NRSR採用以下反饋模式由前η個字( h)遞推下一個字 +n(n彡2，i從0或從1開始均可)al+n= {[c Xr (0 Xa,+ -,) ...... C1 Xr1Pi Xa,)] +c0} mod 2m其中，rk(a) (1 ^ k ^ n)表示a循環移位，至少有一個循環移位數在0 m_l之間循環變化，其它可以不移位； 表示模2加(逐位異或)或者模2m加，X表示模2m乘，mod 2m 表示模2m運算(求餘數)；bx、、為0 2m-l之間的整數(1彡χ彡n，0彡y彡n)，但cQ、 Vc1為奇數，還有1對(bx，cx)為奇數O 彡η)，一般bn、Cn取奇數；輸入的初始η個字 (a0 取值都不限，輸入的每個字都可以是任意m比特長的數。
2.根據權利要求1所述的非線性循環移位寄存器(NRSR)，為提高效率，只由前η個字 ㈨ +㈣)中的2個字遞推下一個字，首字 必選，一般取首尾2個字( , +^),其特徵是當字長為m比特時，η級NRSR採用以下反饋模式由前η個字中的2個字Gi，遞推下一個字彡 k 彡 i+n-1)a,+ = {[{bXak) {a, <j)] + c } mod 2m其中，b為3 2m-l之間循環變化的奇數，可取b = 2 +1 ；<<< j表示循環左移j位， j在0 m-Ι之間循環變化，可取j = i mod m ;c為1 2m_l之間的奇數，可取c = 1 ； 表示模2加(逐位異或)或者模2m力卩，X表示模2m乘，mod 2m表示模2m運算(求餘數)，m — 般取平臺的位數；當m較大時，例如m ^ 32，從應用上來說，b在3 2m_l之間循環變化與 b在1 2m-l之間循環變化的性能差異不大；輸入的初始η個字( an_i)取值都不限， 輸入的每個字都可以是任意m比特長的數。
3.根據權利要求1所述的非線性循環移位寄存器(NRSR)，如果平臺處理乘法的能力差，為提高效率，只由前η個字( + _)中的2個字遞推下一個字，首字 必選，一般取首尾2個字，其特徵是當字長為m比特時，η級NRSR採用以下反饋模式由前η個字中的2 個字( ，ak)遞推下一個字ai+n(i+l彡k彡i+n-1)al+n= {[(ak <j) α, ] + c } mod 2m其中，<<< j表示循環左移j位，j在0 m-1之間循環變化，可取j = i mod m ；c 為1 2m-l之間的奇數，可取c = 1 ； 表示模2加(逐位異或)或者模2m加，mod 2m表示模2m運算(求餘數)，m—般取平臺的位數；輸入的初始η個字(％ ％_》取值都不限，輸入的每個字都可以是任意m比特長的數。
全文摘要
反饋移位寄存器(FSR)是保密通信領域用於產生偽隨機序列的密碼部件，有線性FSR(LFSR)和非線性FSR(NLFSR)等。非線性循環移位寄存器(NRSR)是一種新型FSR。n級LFSR的最大周期為2n-1；n級NLFSR的最大周期為2n。字長為m比特時，n級NRSR採用以下反饋模式由前n個字遞推下一個字(＜＜＜表示循環左移，表示模2加或者模2m加)上式中，m一般取平臺的位數，例如8、16、32、64；mod表示模運算(求餘)，i從0或1開始均可，n≥2。字長為m比特時，n級NRSR的周期大於(2m)n，即安全性高於(N)LFSR；NRSR效率也高於常用的(N)LFSR。主要用途設計流密碼算法；設計分組密碼中的密鑰編排算法；設計雜湊(Hash)函數中的消息擴展算法。
文檔編號H04L9/06GK102176693SQ20111005150
公開日2011年9月7日 申請日期2011年3月4日 優先權日2011年3月4日
發明者任勇軍, 杜慶偉, 王俊波, 薛英花, 黃玉劃 申請人:南京航空航天大學