【安全課件】第14講-序列密碼

01四月2024【安全課件】第14講—序列密碼31三月2024【安全課件】第14講—序列密碼1移位寄存器序列的三種表示方法：線(xiàn)性遞推式（一元多項(xiàng)式）：at+n=c1at+n-1+c2at+n-2+…+cnat,t>=0聯(lián)結(jié)多項(xiàng)式：f(x)=1+c1x+c2x2+…+cnxn狀態(tài)轉(zhuǎn)移矩陣：滿(mǎn)足：st+1=stTf稱(chēng)st=(at,at+1,at+2,…,at+n-1)為n維狀態(tài)2移位寄存器序列的三種表示方法：線(xiàn)性遞推式（一元多項(xiàng)式）：2實(shí)例（畫(huà)出移存器的邏輯框圖，寫(xiě)出相應(yīng)的線(xiàn)性遞推式）多項(xiàng)式答案：線(xiàn)性遞推式：at=at-4+at-3+at-2x1x2x3x43實(shí)例（畫(huà)出移存器的邏輯框圖，寫(xiě)出相應(yīng)的線(xiàn)性多項(xiàng)式x1x2x3非退化的移位寄存器

若反饋函數(shù)形如：，其中，則稱(chēng)其為線(xiàn)性反饋寄存器；否則稱(chēng)其為非線(xiàn)性反饋移為寄存器。其中，若我們說(shuō)該寄存器是退化的，否則是非退化的。4非退化的移位寄存器若反饋函數(shù)形如：4移位寄存器序列空間符號(hào)說(shuō)明：G(f)表示以f(x)為聯(lián)結(jié)多項(xiàng)式的n級(jí)線(xiàn)性移位寄存器序列構(gòu)成的空間定理1：G(f)是GF(q)上的一個(gè)n維線(xiàn)性空間。證明：只需證明G(f)中的任意兩個(gè)序列的任意線(xiàn)性組合也屬于G(f)即可。即證：

特例：當(dāng)q=2時(shí)，G(f)中任意兩個(gè)序列之和仍然屬于G(f)。5移位寄存器序列空間符號(hào)說(shuō)明：G(f)表示以f(x)為聯(lián)結(jié)多項(xiàng)(不)可約多項(xiàng)式定義：若存在g(x),h(x)，使得f(x)=g(x)h(x)，則稱(chēng)f(x)是可約多項(xiàng)式；否則，稱(chēng)其為不可約多項(xiàng)式。(不)可約多項(xiàng)式6(不)可約多項(xiàng)式(不)可約多項(xiàng)式6定理2：若f(x)|h(x)，則G(f)G(h).

例1：聯(lián)結(jié)多項(xiàng)式為f(x)=x4+x3+x+1=(x+1)2(x2+x+1)線(xiàn)性遞推式：at=at-4+at-3+at-1輸出序列：000111//000111//……周期為6011//011//……周期為3001//001//……周期為301//01//……周期為2111111…..周期為1000000……周期為17定理2：若f(x)|h(x)，則G(f)G(h).極小多項(xiàng)式定義：對(duì)于一條移位寄存器序列a，稱(chēng)其聯(lián)結(jié)多項(xiàng)式中次數(shù)最低的多項(xiàng)式為a的極小多項(xiàng)式。定義：滿(mǎn)足f(x)|1-xr的最小正整數(shù)r為f(x)的周期，記為p(f(x))，簡(jiǎn)記為p(f)。例子：x4+x3+x2+x+1的周期為5

(x4+x3+x2+x+1)(x+1)=x5+18極小多項(xiàng)式定義：對(duì)于一條移位寄存器序列a，稱(chēng)其聯(lián)結(jié)多項(xiàng)式中次序列和周期一般地，一個(gè)移存器序列表示為：對(duì)于序列，若存在整數(shù)p使得對(duì)任意正整數(shù)k有成立，稱(chēng)滿(mǎn)足該式的最小正整數(shù)p為序列的周期。r級(jí)線(xiàn)性反饋移存器的最長(zhǎng)周期:，能達(dá)到最長(zhǎng)周期的線(xiàn)性移存器序列稱(chēng)為m序列。在密碼學(xué)中，我們希望參與變換的序列周期越長(zhǎng)越好，因此對(duì)線(xiàn)性反饋移存器我們更感興趣的是能達(dá)到最長(zhǎng)周期的序列，即m序列。9序列和周期一般地，一個(gè)移存器序列表示為：9本原多項(xiàng)式若n次多項(xiàng)式f(x)是不可約多項(xiàng)式且p(f)=qn-1，則稱(chēng)f(x)是GF(q)上的本原多項(xiàng)式。以本原多項(xiàng)式為連接多項(xiàng)式產(chǎn)生的非零序列均是m序列。10本原多項(xiàng)式若n次多項(xiàng)式f(x)是不可約多m序列特性m序列的統(tǒng)計(jì)特性1、m序列的“0、1”信號(hào)的頻次規(guī)律性質(zhì)1：r級(jí)m序列的一個(gè)周期中，1出現(xiàn)個(gè)，0出現(xiàn)個(gè)。11m序列特性m序列的統(tǒng)計(jì)特性性質(zhì)1：r級(jí)m序列的一個(gè)周期中，m序列的游程分布規(guī)律若干個(gè)信號(hào)連續(xù)出現(xiàn)的現(xiàn)象稱(chēng)游程。對(duì)于序列a，稱(chēng)a中形如01…10或10…01的段為一個(gè)1游程或0游程，游程中所含1或0的個(gè)數(shù)稱(chēng)為該游程的長(zhǎng)度，如0110為一個(gè)長(zhǎng)為2的1游程，101為一個(gè)長(zhǎng)為1的0游程。12m序列的游程分布規(guī)律若干個(gè)信號(hào)連續(xù)出現(xiàn)的現(xiàn)象稱(chēng)游程。對(duì)于序列m序列的游程分布規(guī)律性質(zhì)2：將r級(jí)m序列的一個(gè)周期段首尾相接，其游程總數(shù)為N=2r-1；其中沒(méi)有長(zhǎng)度大于r的游程；有1個(gè)長(zhǎng)度為r的1游程，沒(méi)有長(zhǎng)度為r的0游程；沒(méi)有長(zhǎng)度為r-1的1游程，有1個(gè)長(zhǎng)度為r-1的0游程；有個(gè)長(zhǎng)度為的1游程，有個(gè)長(zhǎng)度為的0游程。13m序列的游程分布規(guī)律性質(zhì)2：將r級(jí)m序列的一個(gè)周期段首尾相接二、m序列特性（一）統(tǒng)計(jì)特性1、“0、1”信號(hào)頻次

性質(zhì)1：r級(jí)m序列的一個(gè)周期中，1出現(xiàn)個(gè)，0出現(xiàn)個(gè)。2、游程分布性質(zhì)2：在r級(jí)m序列的一個(gè)周期中，有1個(gè)長(zhǎng)度為r的1游程和1個(gè)長(zhǎng)度為r-1的0游程；長(zhǎng)度為的1游程和0游程各有個(gè)。14二、m序列特性（一）統(tǒng)計(jì)特性1、“0、1”信號(hào)頻次2、游程分二、m序列特性（二）移加特性L(fǎng)(t)(a)是左移變換，就是將序列a

左移t位所得到的序列。性質(zhì)3：若是由r級(jí)本原線(xiàn)性移存器產(chǎn)生的m序列,則是與平移等價(jià)的m序列。性質(zhì)4：周期為p的m序列，左移t位得到序列，將與按位對(duì)齊。則在一個(gè)周期段中，序列與序列（0，0）的有(p-3)/4對(duì)，（1，1）、（1、0）、（0、1）的各有(p+1)/4對(duì)。15二、m序列特性（二）移加特性性質(zhì)3：若是由r級(jí)本二、m序列特性（三）自相關(guān)特性若是一個(gè)周期為p的0、1序列，定義{01}上的映射η為：，定義序列的自相關(guān)函數(shù)為性質(zhì)5：若是一個(gè)r級(jí)m序列，那么16二、m序列特性（三）自相關(guān)特性若習(xí)題一、一個(gè)線(xiàn)性移存器如圖，（1）寫(xiě)出該線(xiàn)性移存器的線(xiàn)性遞推式。（2）寫(xiě)出該線(xiàn)性移存