現(xiàn)代密碼學(xué)第二章ppt課件-資料下載頁
2025-05-01 12:16本頁面
【正文】 一定的浪費(fèi)。 2022/5/29 49 四、鐘控序列 停 走生成器 此工作屬于 Beth T.。所給出的停 走生成器如下。設(shè) GF(2)上兩個(gè) n級(jí) m序列： 控制序列 a=a0a1a2… ； 受控序列 b=b0b1b2… 。 記 G(t)=a0+a1+a2+ …+ at1。（不是 (mod2)加法） 停 走序列 u=u0u1u2… 為： ut=bG(t)， t=0, 1, 2, … 。 2022/5/29 50 四、鐘控序列 縮減序列：互縮序列 此工作屬于 Don Coppersmith。所給出的 互縮序列 如下。設(shè) GF(2)上兩個(gè) n級(jí) m序列： 控制序列 a=a0a1a2… ； 受控序列 b=b0b1b2… 。 當(dāng) at=1時(shí)，輸出 bt；當(dāng) at=0時(shí)，放棄輸出。如此得到的輸出序列 u=u0u1u2… 稱為 互縮序列 。 2022/5/29 51 四、鐘控序列 縮減序列：廣義自縮序列 所給出的廣義自縮序列如下。 設(shè) GF(2)上一個(gè) n級(jí) m序列 a=a0a1a2… 。 取 G=(g0, g1,…, gn1)∈ GF(2)n。 記 vt=g0at‘ +’g1at1‘ +’… ‘ +’gn1atn+1。 當(dāng) at=1時(shí)，輸出 vt；當(dāng) at=0時(shí)，放棄輸出。如此得到的輸出序列 b=b0b1b2… 稱為廣義自縮序列。 可以看出，控制序列是 a=a0a1a2… ，受控序列是 v=v0v1v2… ，其中 vt=g0at‘ +’g1at1‘ +’… ‘ +’gn1atn+1 。 2022/5/29 52 四、鐘控序列 注解一：關(guān)于受控序列 v 當(dāng) G=(g0, g1,…, gn1)∈ GF(2)n是全 0向量時(shí)，受控序列 v是全 0序列； 當(dāng) G=(g0, g1,…, gn1)∈ GF(2)n是不為全 0的向量時(shí)，受控序列v是控制序列 a的平移序列。 （即： v=v0v1v2…= akak+1ak+2… 。這是 m序列的一個(gè)基本結(jié)論，不給出證明。此時(shí)，控制序列 a 與受控序列 v具有相同的極小多項(xiàng)式，僅僅初始狀態(tài)不同。這就是序列被稱為“廣義自縮序列”的理由） 2022/5/29 53 四、鐘控序列 注解二：關(guān)于廣義自縮序列的最小周期 控制序列 a 的最小周期是 2n1，在一個(gè)最小周期中，“ 1”出現(xiàn) 2n1次 ；當(dāng) G=(g0, g1,…, gn1)∈ GF(2)n是不為全 0的向量時(shí)，受控序列 v的最小周期也是 2n1。 這就是說，每當(dāng)廣義自縮序列輸出了 2n1個(gè)比特后，再輸出就是重復(fù)這 2n1個(gè)比特。 換句話說， 2n1是廣義自縮序列的周期。 再換句話說，廣義自縮序列的最小周期是 2n1的因子。 2022/5/29 54 四、鐘控序列 因此，一個(gè)問題是怎樣選擇向量 G∈ GF(2)n，使得廣義自縮序列的最小周期達(dá)到最大（即 2n1）。 理論分析表明： （ 1）當(dāng) G是全 0向量時(shí)，廣義自縮序列是全 0序列； （ 2）當(dāng) G=(1, 0,…, 0) 時(shí)，廣義自縮序列是全 1序列； （ 3）當(dāng) G=(0, g1,…, gn1)或 G=(1, g1,…, gn1)時(shí)，廣義自縮序列是 0101… 或 1010… ；其中 g1=c1， g2=c1‘+’c2， … ， gn1=c1‘+’~‘+’1， c1~是控制序列 a 的抽頭系數(shù)。 2022/5/29 55 四、鐘控序列 部分試驗(yàn)結(jié)果表明： 除了以上三種特殊情況以外，廣義自縮序列的最小周期似乎總是達(dá)到最大（即 2n1）。至今還沒有找到這樣的廣義自縮序列：其最小周期既不是 1，也不是 2，也不是 2n1。 于是有猜想：廣義自縮序列的最小周期總是屬于 {1， 2，2n1}。 這個(gè)猜想目前還沒有得到證明。 2022/5/29 56 四、鐘控序列 注解三： 關(guān)于廣義自縮序列的均衡性 當(dāng) G是全 0向量時(shí)，廣義自縮序列是全 0序列； 當(dāng) G=(1, 0,…, 0) 時(shí)，廣義自縮序列是全 1序列； 當(dāng) G不是以上兩種情況，廣義自縮序列在其任意連續(xù)2n1個(gè)比特都是 01均衡的，即“ 1”和“ 0”各出現(xiàn) 2n2次。 2022/5/29 57 四、鐘控序列 注解四： 關(guān)于廣義自縮序列的線性復(fù)雜度 由于所有的廣義自縮序列的最小周期都是 2的冪，因此其線性復(fù)雜度大于其最小周期的一半。 特別當(dāng)廣義自縮序列的最小周期是 2n1時(shí)，其線性復(fù)雜度大于 2n2。作為密鑰流這是非常理想的結(jié)果。 2022/5/29 58 四、鐘控序列 注解五： 關(guān)于廣義自縮序列的游程分布 當(dāng)廣義自縮序列不是全 0序列或全 1序列（即 G不是全 0向量，也不等于 (1, 0,…, 0) ）： 廣義自縮序列連續(xù)出現(xiàn)的 0的個(gè)數(shù)不超過 n2n； 廣義自縮序列連續(xù)出現(xiàn)的 1的個(gè)數(shù)不超過 n2n。 (這個(gè)理論結(jié)果遠(yuǎn)遠(yuǎn)不夠理想。不過試驗(yàn)結(jié)果為：連續(xù)出現(xiàn)的 0的個(gè)數(shù)和連續(xù)出現(xiàn)的 1的個(gè)數(shù)總不超過 2n) 2022/5/29 59 四、鐘控序列 注解五： 關(guān)于廣義自縮序列的自相關(guān)性 當(dāng)廣義自縮序列不是全 0序列或全 1序列（即 G不是全 0向量，也不等于 (1, 0,…, 0) ）： 令 k固定。當(dāng) n趨向于無窮大時(shí)， k階自相關(guān)函數(shù)值 A(k)趨向于 0。 其中 A(k)如下式。 ???????121)1()(nkllluukA
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1