（概率论与数理统计专业论文）周期序列复杂度的分布.pdf

流密码学是一个古典的课题近十年来，对序列密码的研究一直比较热门自9 0 年 代以来，国内的学者如丁存生，肖国镇，魏仕民，戴宗铎开展了这方面的研究工作，丁存 生的主要工作包括对特定周期序列的模式分布的研究( 【8 7 】，【8 8 】，【1 0 0 l ，【1 0 1 】，) 削虱镇老 师的工作主要是针对特定周期序列如= 2 矿周期的周期序列的线性复杂度快速算法的 研究，魏仕民的工作包括对特定周期的周期序列的k 错线性复杂度快速算法的研究；戴 宗铎老师的工作包括对周期序列的扰动( 如添加，删除) 后序列线性复杂度的变化情况 ( 【7 j ) 。以及般情形下的随机周期序列的线性复杂度的期望，方差( m j ) 国外学者n i e d 舸r e 很早就开始了有关序列复杂度的研究工作。对于特定长度的。 特定周期的序列的线性复杂度有很多的估计结果。尤其是给出了周期序列的线性复杂度 的分布( 【3 6 】) ，线性复杂度与错线性复杂度之翱的关系( 【4 锄，【7 6 】) m 龇对于随机周期 序列的七错线性复杂度的统计性质，包括期望的再有了很多的研究结果( 删，阳j ，f 3 9 】) 在研究周期序列线性复杂度，k 错线性复杂度快速算法方面。早期的工作包括g m 船和 c h m ( i l 叫，1 9 船) 的工作，对于= 2 t r 的周期序列给出了一种快速算法，大大优于原先 的b 曰】e b m p m a 哆算法拄 着m s t m p dc f m a r t m ( 【5 嘲，l 3 ) 提出了= 2 t 的周 期序列女错线性复杂度的算法，于是后面引发了一系列的研究。通过探询内在的代数结 构，找到递归算法的依据。现在对于= 铲，= 矿，= 2 矿的周期序列都有了类似的 快速计算的方法此外，还有一些其他的工作，比如k 确m b 咖8 f s a 土0 ，t s 出t b 和 w i ( i s h i m t o 的工作( 例) ，得到了在特定周期= 2 t ，矿的周期序列的线性复杂度发生 最小跳变的错误值比如a l g b l n d 目dk 僦h g p a t 0 n 的工作( 【7 3 1 ) ，给出 一种高效算法得到二元周期序列线性复杂度的错误谱并用于r e e d 码的译码中 说到这里，要谈一谈对研究序列的性质的原始动机笔者对序列的兴趣并不是从密 码学意义角度来的当时笔者2 0 0 2 年在缎袄亚洲研究院实习的时侯，碰到了个问题t 有个研究小组用极长序列( m 嘶m a ll e n g t hs e q m n c e ) 折叠后来进行定位，直观的说。 因为极长序列的冗余很大，这样做可以用比较少的比特来实现定位但是有这么一个问 题，如果出错了怎样解决? 笔者试图从编码理论的角度解决这样的问题，但是没有想到 这个问题的难度会很大，这涉及到序列的稳定性的问题国外曾经有这样的工作，试图从 线性复杂度的图象变化来进行判断。这种线性复杂度的跃迁或者是幅度的变化可以给错 误提供一定的判断信息，从而进行纠错( 1 7 3 】) 这样的问题引发了笔者的思考，究竟序列 的稳定性是怎么进行度量和判断的? 兴趣引起了对序列复杂度性质的研究于是发现国 内国外有一些这方面的研究工作，特别是对序列线性复杂度和女错线性复杂度的研究 笔者博士论文中主要的研究工作是对周期序列线性复杂度和k 错线性复杂度按照不 同的周期类另进行了近步的细划。对随机周期序列的线性复杂度和k 错线性复杂度的 统计性质。包括期望，方差的界的些估计有一些更紧的结果另外还有一些多熏序列 方面的研究工作此外，对于周期为2 n 的二元随机周期序列的= 1 ，2 - 错线性复杂度进 行了深入的研究，给出了精确的数学公式描述分布的规律；并给出了周期为2 n 的二元周 期序列的l 一错线性复杂度的新算法，另外还在得到了二元随机周期序列的线性复杂度为 固定值时，内在结构的一些性质基础之上，提出了新算法去定位这些可能发生错误的位 置 事实上这样的研究是还是非常的理论的。试图从序列本身固有的定量的东西( 如周 期，长度，错误值。有限域的元素数目分圆陪集的结构) 来揭示序列的线性复杂度和k 错线性复杂度的统计性质，这样的研究结果会很定量而且很深刻；但是这样的结果毕竟 是太理论了一些；如果能够参与到一些与数字版权相关的，与安全工程相关的实际项目 中，会对实际的应用背景和要求会有更深的理解笔者有幸能够到微软亚洲研究院，m m 中国研究中心参与这样的一些项目，包括数字版权管理，安全存储，数字水印的应用项 目从中收获也非常大 这篇博士沦文的结构是这样的t 第一章主要是介绍序列各种复杂度的基本概念和近 几年国内外对序列复杂度研究的方法和进展；第二章主要是介绍自己在周期序列线性复 杂度和女错线性复杂度方面所傲的一些研究工作和结果以及未来工作的展望；第三章 主要是介绍自己在周期为2 n 的随机周期序列l 一错线性复杂度和2 错线性复杂度分布及 算法方面眵澈的最新的研究工作；第四章主要是介绍自己在微软亚洲研究院。m m 中国 研究中心所参与的一些与数字版权管理( d 砌哪相关的项目和所做的研究工作最后是附 录，介绍自己独立设计的周期为2 f l 的周期序列1 错线性复杂度的新算法( 用c 语言实 现】 a b s t r a c t t h e8 t r e a md p h e ri sat r a d i t i o n a lr e s e 缸c ht o p i c i t 88h o tr e s e a “血d j r e c t i o nt h e t e n y e 缸s m a n yr 髑e a r d l e r sd o m 船t i cs u c h 船c 1 l n s h e n gd i n g ，g u o z h e n a 0 ，s h i m i nw 西，z h o n g d u 0d a i ，b e g _ mt h er e 8 e a r c hw o r k 吕i c e1 9 9 0 c u s h e i l gd i n g 8w o r ki n d u d 嚣t h ea r e a0 fp a t t e m 曲埘b n t i 彻0 fs p e c i a lp 嘶d d j c8 e q u 肋o e s ( 8 7 j ， 8 8 】，f 1 0 0 j ，f l o 】) ，t h e 矸r o 矗o fg u o z b e n 粥8 0 m a i n l yf o c u 8o n 虹i ef h s ta 】g o f i 恤f b rt h eu n e 盯伽p l 唰t yo fs p e d a ll 血d0 fp e r i o d i cs e q u e n c e ， 饯= 带；s h i 】试n w h b w o r k i 8t d 曲e d w i t h t h e 融8 培试e h m6 叫t h e k 程r o ru n e a r 卜 p l 脚乜ro f 渊t 8 i np 耐o d q u 衄嘲；z o n g d u od a i 8w o r k 。o m i d 鲫甜t h ec h 眦8 曙i nt h el i 叫 m p l 母d t y0 fp e r - o d i c8 e q l l e n o t h 且t 删l l l t 8 舶t h es d b s t i t u t i o n ，i n r t i o n ，o r 山d 札i o no f t 咖b ( f 7 j ) ，劬嘶h 汀而t ht h eg e 鼬r a ir 倒小0 f 麟p e c t 缸i o n 蝴d 训a n c ef o rt h e 蛐缸衄p 硒t y 0 fr d 掣( 【7 9 1 ) t h er 嗍r 曲瑚蔼a b 耐s l l c h 蛔h a r a l dn i e d e 邛m e rp 撕da t t 伽出i o nt 0t h eo m n p l 喇t y0 f b 。q 、唧吣h eh b 8 m y 砌m 怕a b i 附t h e 硎a i 埘h8 e q _ 咖，耐8 i n p e 望i o d q u e n o 瞄，箦p e c i a l l yh ec o m r i b l 曲e d 七ot h er 锄山o ft h e 丑t 8 t i s t i c 8 ld i s t r m u t i o no ft h e l i 魄r 唧l 积i 妙o fr 蛳d o mp 捌o d i c 明掣衄嘲( i 删) t o g e t h 付埘t hm a yr 圆m ba b a u tt h e r e l a t i o n s h i p b e t 啪呱t h el i n w m p b d t ya n dk 蜘u n 斟唧衄母0 f 魁岬( 阻】，【7 6 】) ； w j 】舾e dm e i mh 龋m a 日ym 8 e a 础瑚l d t 吕a b o u tt h e8 t 8 t i 8 t i c a lp r o p t i 鲳o fk - e r r o rl i n e 甜强 p 蛐0 f 赋8 e q 嘞懈，蛐m d u d e 也e b 饥趣do f t h e 唧e c 乞她妇t h e k 蝴l 妇 n p l 商锣0 f “l u e n 懒( 删，阳1 ，【3 9 | ) a s f 8 r 船t h ea m0 f 丑n d 堍t b e 缸g t 出o r i t b m 如r t h el i n 船r p 1 自d t y ，h r r o rl i n e 盯衄p 蛔t yo fp 田i o d i c 嬲揶m c e 宕c o i 蹴m e d ，t h ee 盯u 仃w o r k j n d u d et h e 嘲此o fr a g 咖，a h c h 腿( 【1 0 4 l ，1 9 8 3 ) ，t h e yp r o p 0 8 ebn 州f a b ta l g 嘶t h mf o r t h eu n e 暂m p t y0 fp e r i o d i c 船掣雌c 皓，w i t h t h ep e r i o d = 2 ”，w h i c h j 8 f 鹪t 叩de 丑i d e n t t h 眦t h eb e r l e k a m p - m 哪e ya l 菪嘶t h m a f t e 删州，m s t a m p 柚dc f m a r t i n ( 【5 8 】，1 9 9 3 ) g 8f 8 s ta 】鲥t h m 0 rt h ek rh n e 盯c o m p l 。d 坶o ft h b tp e r i o d t h 雕ea r ea1 0 to fr e l 删 w o r k8 i n o et h e n ，t h e 瑚嘲_ r t 血棚墨t r yt o 唧l o r et h ea l g e b r 8 i cs t r u c t u f ei 舳i d et o 丘n dt h ee 韶e n c e o ft h er e 肌r s i v e 删h m ，t h e 缸t 出鲥t h m 祈t ht h ep e r i o do f = 2 “，= 矿，= 2 矿 h a sb e e o b t a i n e dr 伽t l y b 器i d e s ，t l 埒r ea r ea1 0 to f0 t h e rv a l u d b l ew o r k ，s u c l la st h ew o r k o fk k l l r o s a w a ，f s a t o ，t s 池t 8 ，8 l l dw k i b h i m o t o ( 【3 0 】) ，t h e yg e tt h er e s u l to ft h el n i n i 。 m u me v a l u ef o r h el i n e 盯o o m p k d t yo f8 e q u 蜘c et od e c r e a s ew h 芒ne r r 。ro c c u r s ta n dt h e w o r k0 fa l 姐g b l 8 u d e ra n dk e m l e t h g p 捌t e r 8 0 n ( 7 3 】) ，t h e y 西v ea ne m c i e n ta l g o r i t h mf o r c o m p u t m gt h eb r r o rl i n e 缸c o m p l 喇t ys p e c t r u ma n da p p l i e di tt ot h ed e c o d i n gd l g o r i t h m o f r e e d m u l l e rc o d e s a b 8 t “地t ni 8i n t e 蒯a gt h a tt h e 砸g m 越m o t i 删o n 丘l rt h e 瑚e 缸c ho f8 e q u 豇嗍i sn o t m 口y p t o 口a p h i cm n i n g ap m b l 咖o c c l l r e dw h 衄1w 鹕a “s i t i g8 t u d e n ti t h em i 口0 臼o f t r 朗e 疵ha s i a0 f2 0 0 2 ，8r e 8 e 甜出芦伽i p 瑚et h em 8 耐m 础l 蛐酵hs e q u 朗c et ol o c 8 t et h ep 0 8 i t i o l l s 谢t h f o l d e r i n g i t m i v 叱酗t h 啪i 8 删曲r e d 吼d 啦呵i n t h e m a ) 【i m 8 ll e n g t hs e q u e n c e ，i t 玲p s i b l e t o l o c 咖ap 0 面t i o nw i t hn o t 础b i t s b u th o w t o l v e t h ep r o b k m i f t h ee r r o r s o c c i l 聃? 1 w 8 n t t o8 0 ：i t 妇。0 d i n g t h f y b u tn o tr e 8 1 j 雕d t h ep m b l e m i sr 魄u yd i _ 匝c u l t f b rt h ep m b l e mi 8r e l 缸e d 稍t ht h e8 t a b i t yt h ”r yo f q u 衄o t h e r eh a 8b 艚nb u 血舶明8 r c ：hw o r kt h a td o i g 既t o rc c 盯僦i o nw i t ht h eb l o w l 啦eo ft h e c r i t i c b l p o i n t 8 h 吼t h e 硼k o f l i n 鲥c o l n p l 嘶0 f 蹦l u 姐嘲( 【7 3 】) t h o u 曲t h ep r o b l e m i s8 伽 n o t 砌v e d 耐，t h e 珥蛐妇ma j t h 8 c tt h ea t t e n t i o fh 侧t h e8 t a b m 时0 f 明q l l 衄j sm e 鹅u r e d t h i 缸da1 0 t0 f 懒e a r d hw 砌【i nt h i sa 瑚，朗p e l 3 i a yt h ew o r ko f l i 哪c o m p l 商t y 柚d k - 唧l i n e ”c o m p l 积i 钟0 f8 e q u e 蝴 t h em a i nh 玛e 棚恤w 砌【i t h ed i 8 t i o n 删n 8t h ed e t a i l e dd a 船遍c a 艇o nf b rt b el i n e 盯唧l 仞d 妒仰dk 忸t 强啤时。o 衄阚t y0 fp 曾j o d i c 的q u 如嘲卸c 0 曲n gt od i 伍删h n 凼 o f 删，8 n d t h e w o 拙8 b o u t t h e 咖曲t i c a lp r 嘞o f t h e l i n e 缸】山哟；h m r l i n e 盯 m p k 白d 晦o fn n d 伽p e r i o d i c q u e n 懒，i n c l l l d i i n g 柚o mt i g h tb o u 曲o ft b e 麟p e c t a t i o n ，a d t h e l l p p 盯b a u n d 8 n d b w 目b o i d o f t h e v a r i 8 n o f t h ek 曲舯r h n e 缸m 曲酣七yo f r 甜l d o m8 争 q 1 】肌嘲，t o g e t h 汀耐t h 舳m ew o r kr e i a e dw 托ht t l ej o i n tn n e 时瑚p l d 衄o f m i d t i p i 髑以撙肌。鹪 s 帆ep t 叩酬朗o f t h er 姐d o m b i 舢搿q u 衄。嘣o f t h e p 仃j o d2 f l 谢t h 丘删、f a ：i u e0 f l i n e 钾c o m p t yw a 8f o u n d ；b a b e do nt h e8 _ b o v em 吼d t ，t h ed i s t r i b u t i o no fn 坶l - e 鳓u n e 虹a m l p l 喇t y o f 珀n d o mp 盯i 0 ( 1 i cb i n 8 r y 鼬q i 埔n c e 8w i t hp 由i o d2 ”w a 8 伽咖岫l y i v e d ，t o g e t h e rw i t ht h e e 糊成m a t h e m 8 t i 鹪妇皿l l a ；t h e 麟p e c t a t i o n0 ft h el 盯r o ru n e 缸唧l d t yo fr 蛐d o mp 一池 b i n a r y q 呦o e 8w 够d e d l l c e d ，柚dt h e 曙t i m 曲e dr 蚴学w 船g i v 粗b 鹪e do ni t a c o o r d i n gt ot h e 删t s ，an e wf a s ta 1 9 0 一t h mf b rc o m p u t i gt h el 。e r r o ru n e 壮伽m p l d t y0 ft h eb i n a r y8 e q 嗍 w i t hp 喇o d2 ”w 蠲p r o p 删，w m 曲捌u c et h es t o r a g ea n d 】a wt h e0 0 m p l l t a t i o nc o m p k d t y - a n e w 啦昏o d t l l 】nf o rk a t i h gt h ee m rp o b i t i a nw 蛔g i 、r e na f t e rt h 砒m 0 r v 盯，帕d i 8 t r i b u t i o n o ft h e2 - e r r o r1 i n e 盯。0 m p i 曰【i t yo fr 皿d 咖p 耐o d i cb i n 8 r y q u 肌懈埘t hp e r i o d 妒w 聃l v e d w i t ht h ee ) c a c tf o r m 】a se ) 日口r e 8 s i o n s o m e h o w 娃【er e s e a r c hr e s l l i t sa b o v ei sv e r yt 胁i t i c a i ，i tt r yt oi n v 鹤t g a t et h es t a t i s t i c a 工 p r 印e r t i e so ft h eu i l e a rc o m p l e ) d t ya n dk _ e r r o ru n e 日rc o m p l 忱i t yo fr 8 n d o mp e r i o d i c8 e q u e n c e s f r o mt h e 铝s e n t i a lp 甜啦甙e r s0 ft h es 。q u e n o 蛄( 8 u c h 船p e r i o d ，k n g t h ，e r r o rv a l u e ，t h e6 n i t e 丑e l dp 盯a 珥e t e r ，c 8 r d i n a l j t i 髑o ft h 8c y d o t o m i cc o s e t 8 ) ，t h er 1 l l ti 8v e r ym 8 t h e m a t i c 咄b u ti t s i n d e e dt o oi 丑阳d ht h e o r i t i c a li nm yp o i n to fv i e w ，1w mg e td e 印u n d e r s t 姐d i n go ft h et h e o r y r e 8 l l l t s 姐d 舢c h 舶o r ee 】【p e r i e n c e s 丘o me n g i n e e r i n gb 碰k 盯o l m d 舡l dd e m a n d si fit “【ep a r t a b s t r a c t i n t 王瞻t a s k s8 b o u tn 【es e c u r e 鼬l g i n e e d n ga n dd i g i t 8 l g h t sm 8 n 8 l 筘m e tp r o j e c t s i t sl u c k y e n o u g ht h a tit a bi t e r ni nt h ei i i 妇n e tm e d i ag r o u pi nm i c r 0 b o f tr e 8 e a r c ha s i a ，观di b m c h i ar e s e 盯曲l a b ，t h ep r o j e c t sa r ea b o u td i g i t a lr - 曙h t 8m 卸矗g e m e n t ，s e c u r es t o r a g e m 衄t ， d i g i t a lw h t e r m a r k i n g ，w h i c hig e ta1 0 t0 fp r a c t i c a l 唧e r i 曲c e sa n dt h ek n 胛d e d g e0 ft h e d e m 8 n d 8o fe n g i n d n gb a c l 【口0 1 l d t h e8 t n l c t t l r eo ft h ed o c t o rd i 弱e r 8 t i o ni s 船f 0 u 订g ：t h ef i 馏tc h 叩t e ri n t r o d u c et h e b a s i cc o n c e p to ft h ec c 眦p l 咖t yo fs e q u e n c e 8 虹mt h er e o e tr e 鼬8 r c hm e 址1 0 d 8 毗l da d 吼c e si n t h e8 r e ao f 啪p l 曰d 蚵o f 鼬q u 眦i 嘲；t h e n dd h a p t e r a i n l yf o c l l s0 n 功【y 瑚e a r c hw m k 蛆dt h e 弛眦l t 8i nt h ea r 0 fl i n e 盯o o m p l d 镛雠dk - e r r o ru 啦rc o m p k d 时m “衄p 啦i o d i c q u e n 嘲，皿d t h e p 曲l e w o r k i t h e f i l t t l r e ；t h e t h i r d c h a p t 盯a 弛t h er e c e n t 瑚髑r c h 删t 8 a _ b o l l tt h ed i 8 t r i b u 廿o no f1 ，二蜘o ru n e a r m p l 喇锣o f 瑚d o mb i n 8 r yp 瑚蛐c 明q l l 既嘲w i t h t h ep e 咖d2 n ，8 n dt h e 蜊t h mf o rc o m p u t i n gt h e1 一e r r o rh n e 盯m 】，l 。d t yo fb i n a r yp 面o d i c s e q u e 嗍而t ht h 雠8 p e c i a lp 耐o d ，t o g 乱h e r 吼t ht h e8 l g o 畦t h mt o1 0 c a 乞et h ep o 鹃i b l eo e 啦t o r p k 魈t h ef 妇t hc h a p t 盯i t r o d l l 伪t h ed r mp r o j e c t 88 埘t h er e a r c hw o r kw 姗it a k e i n t 锄i nm j 憷哦晷e a r 出a e 妇姐d 田mc h i n am 学e 8 础l 8 b 吼ea p p 朗d i st h en 钾 8 l 刚b f m p u t i n gt h e1 删rl i n e 甜c o m p l 毋d 姆o fb i 姐呵p 嘶o d i c 鼬q 删蝴w i t hp 烈 o d 2 ，id e b i 口e d b y 哪e l f w h i d l i s i m p k m e i l t e db y c l a n g i l a 辟 s u m i n g n 眦l 沮iu n i v 订8 i 坝a u t u m n ，2 0 0 4 第一章基本概念及研究方向介绍 本章的主要内容是介绍与序列相关的密码性质的一些度量和定义，以及近几年在这 个领域里面几个主要的研究方向和一些研究结果 本论文中用蜀来表示定义在其上的有限域序列可分为两种；有限序列与无限序列 后者又可分为终归周期序列与非终归周期序列我们用表示有限序列s o ，。- ，s “ 用8 ”表示无限序列加，s l ，对于无限序列护，如果存在正整数p o 和n 伽。使 得s n + p = s 。对所有n 珊都成立。则称该序列是终归周期的，且称p 是该序列的一个 周期所有可船周期的最小者称为序列的最小周期特别地，如果，l o = o ，则称该序列 为周期序列着p 是。”的最小终归周期，则称使+ p = h 对所有n ，1 0 都成立的最小 珊为删习期( p = 嘲埘i o d ) 设有正整数二和g ! 黝中的一组数匈，q ，屯，口使得序列柳 或满足 + c l 勺一1 + + 屯町一厶+ n = o o l ) 则豫。或是一个工阶线性递归序列确定序列其他顼的知，s l 一1 称为初始值 上述关系式称为工阶线性递归关系如果n = o ，则称其为齐次线性递归关系。否则称为 非齐次线性递归关系对应的序列本身称为齐次的和非齐次的线性递归序列线性递归 序列的生成可由线性反馈移位寄存器来实现 可以知道，有限域上的线性递归序列具有下述周期特性t 定理1 1 1 若s ”满足上面的线性递归关系，且q o ，则8 。是周期的 现在来介绍序列线性复杂度的概念所谓线性复杂度就是8 或s ”所满足的阶数 最小的齐次线性递归关系的阶数如果用线性反馈移位寄存器来实现一个序列。则它的 线性复杂度是能产生该序列的最短线性反馈移位寄存器( l i r m ”d b a c l 【s l l i f tr e g i s