




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
第二章序列密碼
2.1概述
2.2線性反饋移位寄存器
2.3m序列及其性質2.4對偶移位寄存器2.5
B-M算法2.6非線性組合與算法舉例
2.1概述序列密碼將明文編碼為比特串:
同時產生與明文相同長度的密鑰流:
或者GF(p)效仿一次一密加密方式:
(1)密鑰和明文長度相同;
(2)每次加密采用不同的密鑰;
(3)密鑰是隨機的。古典密碼中的
Vernam密碼(1917年):
但密鑰如何實現?偽隨機數發生器:產生性能接近隨機的二進制序列。種子密鑰序列密碼主要任務:設計安全的偽隨機密鑰產生器。對KG(KeyGenerator)的基本要求:(1)密鑰量大;(2)極大周期;(3)理想分布;(4)非線性度大;(5)推測K是計算不可行的。KG非線性移位寄存器(NFSR:Non-linearFeedbackShiftRegister)
----M序列(周期最大)線性反饋移位寄存器(LFSR:Linear
FeedbackShiftRegister)
----m序列(周期最大)線性移位寄存器的非線性組合(實用的)序列密碼與分組密碼的比較:(1)序列密碼:
處理速度快,實時性好;
適用于軍事、外交等保密系統。
但是適應性差,需要密鑰同步。(2)分組密碼:
不需密鑰同步,較強的適應性;適宜作為加密標準。
但是加密速度稍慢,錯誤易擴散和傳播。
(但比公鑰密碼快得多,軟件上約100倍。)2.2線性反饋移位寄存器1.反饋移位寄存器KG!
例題-1:初始狀態:s0=101f10110111111011011011移位寄存器的一個狀態(開始時為初始狀態):反饋函數
反饋寄存器的狀態序列:必然是周期的!因為狀態有限,進入一個相同狀態后則重復。當觸發脈沖到來時,寄存器狀態移位更新為一個新狀態。
例題-1的輸出序列:10111011…..完整的狀態圖:如何使狀態都在一個圈里?這樣周期最大。2.線性移位寄存器-LFSR(Fibonacci-LFSRs)反饋函數為線性函數(否則為非線性反饋移位寄存器)
稱為結構常數。
結構常數反序是為了將來有理表示方便(不必求互反多項式)。例題-2:
這是一個4階線性反饋移位寄存器:4-LFSR。
布爾函數!f110001000011000110001101111010110100001000
初始狀態記為:
最重要的關系!結構常數不動
可以劃出相應的狀態轉移圖。
圖形和公式是對應的
上例中:反饋函數為,
初始狀態:(1000),輸出序列:(1000110)
,周期為7初始狀態:(0010),輸出序列:(0010111)
,周期為7
初始狀態:(0110),輸出序列:(0110100)
,周期為7
第三個初態!第一個初態!第二個初態!
反饋函數為:初始狀態:(1000),輸出序列:(100010011010111)
,周期為
初始狀態:(0110),輸出序列:(011010111100010)
,周期為
的序列稱為n階m序列。另一:f110001000010000100001001110011000110001101111010f111010110101001011110111001111111110111100111000110001續前:第二個初態!第一個初態!只要進入,就得循環!
結論:(1)n-LFSR的結構由其結構常數唯一確定;(2)n-LFSR的結構常數與反饋函數互相唯一確定;(3)n-LFSR序列由其結構常數和初態唯一確定;(4)一個n-LFSR可以產生個不同序列;(5)一個n-LFSR的序列的最大周期是。關鍵問題:如何產生m序列?LFSR的聯接多項式為本原多項式。f(x)稱為線性移位寄存器的聯接多項式或生成多項式。
3.LFSR的有理表示
a(x)稱為序列的形式冪級數或生成函數。--S(f(x))LFSR的有理表示:其中g(x)是次數小于n的多項式:a(x):表示輸出序列f(x):表示結構常數g(x):與初態、結構常數相關
序列空間定理-1:n-LFSR有理表示中g(x)的次數小于n。證明:因為迭代關系:
LFSR:g(x)的系數和結構常數與初態都有關系。DSR
:g(x)的系數就是初態。(后面講)
當初結構常數序號與寄存器序號反向,就是為了此處。
另一簡單方法求g(x):
消最低項的長除法可求a(x):2.3、m序列及其性質1.如何構造m序列例題-4:
設的有理表示為,求其序列表示。解:通過消最低項的多項式除法,得到:
升冪排列消最低項另一種方法:定理-2:周期為p的序列的(非最簡)有理表示為:證明:
所以:分子多項式的系數(含常數項)為一個周期;分母二項式的次數為周期。
例題-5:求產生序列(100111)∞的最短的LFSR。
多項式的輾轉相除法階數最少!最簡有理表示
任何一個(周期)序列都可以表示為:
此即研究多項式形式的原因
定理-3:當f(x)為本原多項式,產生的序列為m序列。
nFeedbackpolynomialPeriod23374155316637127不止一個!是一個本原多項式。初態為(10101),求序列的表示。例題-6:兩種基本方法:(1)畫出結構圖,進行迭代,得到狀態圖。(2)求出有理表示,進行長除法,得到一個周期。(1010111011000111110011010010000)∞設一個序列的聯接多項式為
隨機性如何?m序列的取樣:設
是Fq上的一個周期序列s
是一個正整數,令:稱為序列的s采樣。定理-4:若是周期為p的m序列,則
2.m序列的偽隨機性形如的子序列段稱為一個長為k的1游程;形如的子序列段稱為一個長為k的0游程。
(1)分布特性:(2)相關特性:隨機性的三個特性:s是序列的長度
(3)游程特性:0游程
證明:將游程數目轉化為狀態的數目。
狀態最終都會出現在序列中!一個周期序列圈m序列特點:每個非零狀態都出現,且只
出現一次!狀態都在序列中!
序列圈中,長為i的1游程總會體現為:存在以下形式的狀態(一一對應!)在序列圈上數游程個數,都是從011…10開始。即使在******中也有,以后也會被數到,沒有遺漏。輸出序列的圈
看序列圖上的狀態,游程最終要顯示在序列圈上。輸出序列的圈所以當游程個數為現在只剩下的游程個數:n長的1游程有1個,
因為在狀態圈中,有一個全1狀態:111….1;沒有n長的0游程,因為沒有全0狀態;n-1長的0游程有1個;所以共有游程:不可能有n+1的1游程:不會有n-1長的1游程:因為不可能有兩個全1狀態,且相連;因為以下三個狀態是相連的:(否則全1狀態不會出現。)且每個狀態在狀態圈中,只出現一次;所以011..11與11..110不會連著出現(連著才會出現n-1長的1游程)。m序列特點:一個周期內,每個非零狀態都出現,且只
出現一次!(3)相關系數的證明:
任意5級m序列的周期環上,有個0,有16個1。
=1111100110’1001000010’1011101100’0……,是由本原多項式產生,所以是5級m序列。其周期中,15個0,16個1。游程總數:長為1的1/0游程:長為2的1/0游程:長為3的1/0游程:長為4的0游程一個,長為5的1游程一個。算游程時首尾相接例題-7:
LFSR(DSR:DualShiftRegisters)DSR2.4對偶移位寄存器LFSR:也稱FibonacciLFSRsDSR:也稱GaloisLFSRs
DSR的特點:DSR也是LFSR,這樣稱呼只是為了區別開1.DSR的狀態轉換(或稱迭代過程)
例題-8:4-DSR
序列為:(1101000)
開始循環11000111010011111110000010001000100狀態不是每位都輸出初態為(1110)時,序列為(1000110)
相同的聯接多項式4-LFSR
但是:如果上例的LFSR的初態是1101,
輸出序列為:(1101000)
,
與初態為1000的DSR輸出序列相同。因此相同的結構常數,DSR和LFSR可產生相同序列。2.DSR的有理表示a(x):表示輸出序列f(x):表示結構常數g(x):表示初態!DSR也具有有理表示:一方面:利用DSR的遞推公式所以輸出序列為
定理-6:DSR序列的有理表示中:證明:其系數就是DSR的初態:另一方面:利用消最低項方法有理表示等式的兩邊相同,得證。
由此可得到DSR的設計思路
例題-9:解:(1)LFSR的結構常數為(0,1,0,1)
初態為(0,1,0,0)。(2)DSR的結構常數為(0,1,0,1),結構圖即
或者:所以DSR和LFSR是等效的。
總結:4.當鏈接多項式f(x)為本原多項式時,產生m序列。
2.對于LFSR,g(x)的系數由初態和結構常數確定;
對于DSR,g(x)的系數即為初態;產生同一序列(具有相同有理表示),LFSR和DSR
的初態不同;另外:有理表示還可以擴展為假分式的情況,例如:
對應的LFSR的圖示為:(退化的7-LFSR)
非周期部分的位數有3位,對應的退化寄存器個數為3。線性復雜度:生成序列所需最小的LFSR寄存器個數。本例中,序列的線性復雜度=4+3。2.5B-M算法線性反饋移位寄存器雖然易于實現,但是不安全的,如果知道兩個周期,就能通過B-M算法解出生成多項式。已知階數B-M算法不需任何前提,求出序列段的線性綜合解:是一種迭代算法:階數對于n階線性移位寄存器,已知2n序列段,通過解方程組,可以求得對應的結構常數還可用于循環碼譯碼等。還有Berlekamp算法:用于分解多項式。B-M(Berlekamp–Massey)算法:
迭代型求解序列生成多項式的算法。(且不必事先知道寄存器階數)未知階數規定:f(x)=1表示0階線性移位寄存器的聯接多項式,(長度為n的全零序列由0階線性移位寄存器產生。)
且記計算對于,重復第二步和第三步N次,即可求出若(a)如果(b)否則,存在(3)若,取逐次試驗聯接多項式的方法!輸出:<1+x3+x4,4>同一行中最后才算dn!d=1才算m!寫在fn+1的上一行例10:輸入S8=10101111
當前結構常數:當前狀態
逐一試驗上題的解釋:(上述過程熟練以后,僅用表格形式做即可!)
例題-11:輸入:S10=0001101111
注意:
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 聯大學堂《建筑工程技術鋼結構(河南農業大學)》題庫附答案
- 2019-2025年中級會計職稱之中級會計實務強化訓練試卷A卷附答案
- 2024-2025學年山東省菏澤市牡丹區八年級上學期期中考試地理試卷
- 2024-2025學年安徽省安慶市八年級上學期期中綜合素質調研地理試卷
- 六年級上期生態系統保護與安全計劃
- 企業普通話溝通能力提升計劃
- 新部編版語文五年上冊網絡教學計劃
- 小學校園暴力防控工作計劃
- 北師大版七年級數學上冊知識點梳理計劃
- 九年級下學期班級評比獎勵計劃
- 【MOOC】《學術交流英語》(東南大學)章節中國大學慕課答案
- 數字經濟學導論-全套課件
- GB/T 2934-2007聯運通用平托盤主要尺寸及公差
- 國家開放大學《財務管理#》形考任務1-4參考答案
- 醫院檢驗科冰箱溫度登記表
- 常見異常心電圖識別及處理課件
- 重慶交通大學-黃璇-答辯通用PPT模板
- 中國醫院質量安全管理 第4-13部分:醫療管理住院患者健康教育 T∕CHAS 10-4-13-2020
- 新滬教牛津版七年級上冊英語全冊教案
- 《航空專業英語》課件維修專業基礎英語R1
- 【課件】第17課實驗與多元——20世紀以來的西方美術課件高中美術人教版(2019)美術鑒賞
評論
0/150
提交評論