推薦6-m序列特性

1、密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件 移位寄存器基礎(chǔ)移位寄存器基礎(chǔ) m序列特性序列特性 序列密碼編碼技術(shù)序列密碼編碼技術(shù) 前饋函數(shù)設(shè)計準則前饋函數(shù)設(shè)計準則 快速相關(guān)攻擊快速相關(guān)攻擊第三章第三章 序列密碼序列密碼密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件n主要內(nèi)容：主要內(nèi)容：隨機性的描述、隨機性的描述、m序列特性序列特性n重點：重點：m序列特性序列特性n難點：難點：m序列的采樣特性序列的采樣特性m序列特性序列特性密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件一、隨機性的描述一、隨機性的描述1、golomb隨機性假設(shè)隨機性假設(shè) 為了度量周期序列的隨機性，為了度量周期序列的隨機性，golomb提出了下提

2、出了下列三條標(biāo)準：列三條標(biāo)準：（1）一個周期中）一個周期中0、1的個數(shù)相差不超過的個數(shù)相差不超過1個；個；（2）一個周期段中，長度為）一個周期段中，長度為i的游程占游程總數(shù)的的游程占游程總數(shù)的 這里假定至少有兩個長為這里假定至少有兩個長為i的游程；的游程；（3）周期自相關(guān)函數(shù)是二值函數(shù)。）周期自相關(guān)函數(shù)是二值函數(shù)。i2/1密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件二、二、m序列特性序列特性（一）統(tǒng)計特性（一）統(tǒng)計特性1 1、“0 0、1 1”信號頻次信號頻次 性質(zhì)性質(zhì)1 ：r級級m序列的一個周期中，序列的一個周期中，1出現(xiàn)出現(xiàn) 個，個， 0出現(xiàn)出現(xiàn) 個。個。12r121r密碼學(xué)密碼學(xué)課程多媒體課

3、件課程多媒體課件1320 0 10 0 10 0 10 0 11 0 01 0 01 1 01 1 01 1 11 1 10 1 10 1 11 0 11 0 10 1 00 1 0產(chǎn)生序列為：產(chǎn)生序列為：1001110密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件2、游程分布、游程分布性質(zhì)性質(zhì)2：在在r級級m序列的一個周期中，序列的一個周期中，（1）長度為）長度為r的的1游程有游程有1個；個；（2）長度為）長度為r-1的的0游程有游程有1個；個；（3）長度為）長度為 的的0、1游程各有游程各有 個；個；（4）游程總數(shù)為）游程總數(shù)為 個，且個，且0、1游程各占一半。游程各占一半。)21 (rkkkr

4、2212r密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件1320 0 10 0 10 0 10 0 11 0 01 0 01 1 01 1 01 1 11 1 10 1 10 1 11 0 11 0 10 1 00 1 0產(chǎn)生序列為：產(chǎn)生序列為：1001110密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件（二）移加特性（二）移加特性性質(zhì)性質(zhì)3：若若 是由是由r級本原線性移存器產(chǎn)生的級本原線性移存器產(chǎn)生的m序列序列, 則則 是與是與 平移等價的平移等價的m序列。序列。aa) 12mod0()()(rttala注：注：其中其中l(wèi)(t)(a)表示序列表示序列a左移左移t位所得序列。位所得序列。密碼學(xué)密碼學(xué)課程多

5、媒體課件課程多媒體課件1320 0 10 0 10 0 10 0 11 0 01 0 01 1 01 1 01 1 11 1 10 1 10 1 11 0 11 0 10 1 00 1 0產(chǎn)生序列為：產(chǎn)生序列為：10011101001110密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件性質(zhì)性質(zhì)4：周期為周期為p的的m序列序列a，左移，左移 t 位位得到序列得到序列b，將，將a與與 b按位對齊，按位對齊，則在一個周期段中，序列則在一個周期段中，序列a與序列與序列b （0，0）的對有）的對有(p-3)/4對；對；（1，1）的對有）的對有(p+1)/4對；對；（1、0）的對有）的對有(p+1)/4對；對；

6、（0、1）的對有）的對有(p+1)/4對。對。) 12mod0(rt密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件（三）自相關(guān)特性（三）自相關(guān)特性 若若 是一個周期為是一個周期為p的的0 0、1 1序列，序列，定義定義0 10 1上的映射上的映射為：為： ，定義序，定義序列列 的自相關(guān)函數(shù)為的自相關(guān)函數(shù)為)(210aaaa 1) 1 (, 1)0()()()(10tipiiaatc)(210aaaa性質(zhì)性質(zhì)5：若若 是一個是一個r級級m序列，那么序列，那么120, 10, 12)()()(220rrtiiittaatcr)(210aaaa 密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件 （四）（四）m序列

7、的采樣特性序列的采樣特性 為序列為序列a的以的以t為起點的為起點的k采樣序列，并稱采樣序列，并稱k為采為采樣距。樣距。 設(shè)設(shè) 是周期為是周期為2n1的的m序列，序列，k為正整為正整數(shù)，數(shù)，t為非負整數(shù)，則稱序列為非負整數(shù)，則稱序列0 iiaa( , )0k tik tiaa密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件 定理：定理：設(shè)設(shè)a是周期為是周期為2n1的的m序列，序列，k為正整數(shù)。則為正整數(shù)。則 (1) 當(dāng)當(dāng)gcd(k,2n1)1時，序列時，序列a的的k采樣序列都是周采樣序列都是周期為期為2n1的的m序列序列; (2) 當(dāng)存在非負整數(shù)當(dāng)存在非負整數(shù)d：0dn,使使k2d時，序列時，序列a的的

8、k采樣序列都與序列采樣序列都與序列a平移等價。平移等價。 (3) 當(dāng)當(dāng)gcd(k,2n1)1時，序列時，序列a的的k采樣序列仍是線采樣序列仍是線性遞歸序列，但周期可能性遞歸序列，但周期可能2n1。 推論：推論：利用采樣方法可采出所有的利用采樣方法可采出所有的n次本原多項式次本原多項式,共共 個。個。(21)/nn密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件1320 0 10 0 10 0 10 0 11 0 01 0 01 1 01 1 01 1 11 1 10 1 10 1 11 0 11 0 10 1 00 1 0產(chǎn)生序列為：產(chǎn)生序列為：10011101001110密碼學(xué)密碼學(xué)課程多媒體課件課

9、程多媒體課件三、線性移存器綜合三、線性移存器綜合 一條線性遞歸序列由一條線性遞歸序列由: : (1) (1) 線性遞推式線性遞推式( (包括級數(shù)包括級數(shù)n)n); (2) (2) 初始信號初始信號兩個因素決定。兩個因素決定。 這兩個因素都可設(shè)置為密鑰的一部分。這兩個因素都可設(shè)置為密鑰的一部分。 因此因此, ,m序列的還原問題就是在已知序列的還原問題就是在已知m序列或僅序列或僅已知其部分信號的條件下已知其部分信號的條件下, ,求解未知因素的問題。求解未知因素的問題。 密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件（一）解方程法（一）解方程法 已知序列已知序列a是由是由r級線性移存器產(chǎn)生的，且知級線性移存器產(chǎn)生的，且知a的連續(xù)的連續(xù)2 2r位，可用解線性方程組的方法得到線性遞位，可用解線性方程組的方法得到線性遞推式。推式。密碼學(xué)密碼學(xué)課程多媒體課件課程多媒體課件例：設(shè)例：設(shè)a=01111000=01111000是是4 4級線性移存器產(chǎn)生的序列的級線性移存器產(chǎn)生的序列的8 8個連續(xù)信號，求該移存器的線性遞推式。個連續(xù)信號，求該移存器的線性遞推式。分析：序列信號必滿足遞推式所確定的關(guān)系，要得到分析：序列信號必滿足遞推式所確定的關(guān)系