[發明專利]并行循環移位寄存器PRR

在審

• 申請號: 201410809169.1
• 申請日: 2015-08-03
• 公開（公告）號: CN104506303A
• 公開（公告）日: 2015-07-29
• 發明（設計）人: 黃玉劃;蘇菲;陶怡婷;丁莉莉;汪駿
• 申請（專利權）人: 蘇州中科啟慧軟件技術有限公司
• 主分類號: H04L9/06
• 分類號: H04L9/06
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

并行循環移位寄存器PRR是保密通信領域用于產生非線性偽隨機序列的密碼部件，主要用途：設計流密碼算法；設計分組密碼中的密鑰編排算法；設計雜湊(Hash)函數中的消息擴展算法；擴頻通信中用于提高可靠性。

背景技術

密碼編碼中產生偽隨機序列的常用密碼部件有線性反饋移位寄存器LFSR^[1]和非線性反饋移位寄存器NLFSR^[2]等，以下合稱(N)LFSR。例如，第2代移動通信系統GSM的加密標準A5算法^[3，4]、藍牙加密標準E0算法^[4]和流密碼國際標準SNOW2算法^[3]都采用了LFSR；Hash函數標準SHA1和SHA2的消息擴展算法^[3]以及第3代標準SHA3的多個候選算法采用了(N)LFSR或其它發生器。

n級(N)LFSR的當前輸出比特都是前n比特的邏輯函數，這樣的邏輯函數共有個，其中線性的有2ⁿ個，非線性的有個。LFSR采用以下反饋模式由前n比特a_，～a_n+i-1線性遞推下一比特a_n+i：

a_n+i＝a_i^c_n-1a_i+1^…^c₁a_n+i-1

其中，常數c_k＝0或1，1≤k≤n-1，^是異或即模2加法。如果輸入的初始n比特a₀～a_n-1全為0，則LFSR輸出恒為0，因此，n級LFSR的最大周期為2ⁿ-1。當且僅當LFSR的反饋多項式為本原多項式時，LFSR的周期才達到最大。產生一個本原多項式并不容易，需借助數學軟件包。SHA1的消息擴展算法采用以下模式由前16個字w_t-16～w_t..1遞推下一個字w_t：

w_t＝(w_t-3^w_t-8^w_t-14^w_t-16)＜＜＜1

其中，＜＜＜1表示循環左移1位，字長m為32比特。這相當于字長m為32b(比特)的16級發生器，如果輸入的初始16個字w₀～w₁₅全為0，則輸出恒為0，因此，其最大周期小于等于(2³²)¹⁶-1。n級NLFSR的最大周期為2ⁿ。當字長為m比特時，n級并行循環移位寄存器PRR的周期大于(2^m)ⁿ。(N)LFSR軟件實現慢，解決的辦法是并行m個(N)LFSR，相當于字長為m比特，但最大周期還是小于等于2ⁿ，除非象SNOW2一樣采用模2^m的本原多項式，最大周期才小于等于(2^m)ⁿ。也就是說，對于不同的字長m和不同的級數n，(N)LFSR要尋找不同的反饋模式。不管字長m和級數n為多大，NRSR存在統一的反饋模式，無須尋找達到最大周期的反饋模式，可以直接適應各種平臺，包括將來128位以上的平臺。在32位平臺下(2.4GHz雙核CPU、2GB內存、Windows?XP、C語言)，SNOW2的LFSR速度為630MB/s。SHA1和SHA256的消息擴展算法速度都小于400MB/s。PRR的速度為700MB/s。對于A5和E0算法采用的LFSR，除非同時并行32個LFSR，效率才和PRR相當。對于周期達到最大的(N)LFSR，其輸出是絕對均勻的，遍歷了所有狀態才會重復。測試表明，PRR產生的輸出是偽隨機均勻的，又能遍歷所有狀態。

[1](美)Schneier?B.應用密碼學——協議、算法與C源程序.吳世忠等譯.機械工業出版社，2000-1.264～269

[2](中)王育民，劉建偉.通信網的安全——理論與技術.西安電子科技大學出版社，1999-04.81～82

[3](中)谷利澤，鄭世慧，楊義先.現代密碼學教程.北京郵電大學出版社，2009-08.169～175，189～204

[4](中)徐勝波，馬文平，王新梅.無線通信網中的安全技術.人民郵電出版社，2003-07.149～150，183～187

發明內容