（基础数学专业论文）矩阵上的线性递归序列及密码学特性.pdf

摘要本文给出了尬上线性递归矩阵序列分量序列的1 一重量复杂度和二重量复杂度，同时分析了分量序列及矩阵序列的稳定性；并且引入了一种下标序列，用该下标序列对分量序列采样，得到一种新的序列，新序列的周期和线性复杂度均得到了提高，又分析了它对矩阵序列安全性的影响；最后改进了m 2 上线性递归矩阵序列的构造方法，得到了非线性递归矩阵序列的两种新的模型，这两种非线性递归矩阵序列的安全指标，均优于线性递归矩阵序列关键词：线性递归矩阵序列；周期；线性复杂度；重量复杂度；极小多项式；采样；下标序列；j e n n i n g s 复合序列a b s t r a c ti nt h i sp a p e r ，w ep r o p o s et h ew e i g h tc o m p l e x i t y 叫c l ( 西w h e nt i so n ea n dt w oo ft h ec o m p o n e n ts e q u e n c eo ft h el i n e a rr e c u r r i n gm a t r i xs e q u e n c e ，a n a l y s i st h es t a b i l i t yo ft h ec o m p o n e n ts e q u e n c ea n dt h em a t r i xs e q u e n c e b yi n t r o d u c i n gas u b s c r i p ts e q u e n c e ，w eo b t a i nan e ws e q u e n c ew i t hl a r g e rp e r i o da n dh i g h e rl i n e a rc o m p l e x i t yf r o mad e d m a t i o no nt h ec o m p o n e n ts e q u e n c e ，a n da n a l y s i st h ea f f e c t i o no ft h en e ws e q u e n c et ot h es e c u r i t yo ft h em a t r i xs e q u e n c e a tl a s t ，w ei m p r o v et h em e t h o do ft h ec o n s t r u c t i o na b o u tt h el i n e a rr e c u r r i n gm a t r i xs e q u e n c e ，a n dp r e s e n tt w on e wn o n - l i n e a rr e c u r r i n gm a t r i xs e q u e n c em o d e l sw h o s es e c u r i t yi n d e x e sa r eb o t he x c e lt ot h ef i n e a rr e c u r r i n gm a t r i xs e q u e n c e k e yw o r d s ：l i n e a rr e c u r r i n gm a t r i xs e q u e n c e ；p e r i o d ；l i n e a rc o m p l e x i t y ；w e i g h tc o m p l e x i t y ；m i n i m a lp o l y n o m i a l ；d e c i m a t e ；s u b s c r i p ts e q u e n c e ；j e n n i n g sc o m p o s i t es e q u e n c e l l第一章引言在近几十年里，越来越多以抽象代数作为工具的理论，比如典型的有限域理论和有限域上的多项式知识，一直被广泛地应用于密码学和电子工程技术等其它分支中事实上，密码学中用到的移位寄存器，就始终离不开有限域上的线f 生递归序列密码学，通常用到的线性递归序列的有限域都是易，那么是否能把它推广到环上；王锦玲老师在文献【2 】中，将有限域上的线性递归序列推广到了环上，构造了一类特殊的环，矩阵环m 2 上的线性递归序列厶得到它的周期由原来易上的线性递归序列周期的一1 ) 增大为( 2 2 n 一1 ) ，a 的分量序列的线性复杂度相应的由礼提高为2 n ，因此有很好的密码学性质在本篇论文中，作者给出了矩阵环上的线性递归矩阵序列丛的分量序列的1 重量复杂度和2 - 重量复杂度，分析了分量序列和矩阵序列的稳定性，它们不足以抗击b a a 攻击；所以进一步，通过用一种满足一定条件的特殊的下标序列，对的分量序列采样，从而获得一种新序列，新序列的周期和线性复杂度，在已提高的基础上又增加到q ，倍，因此获得了安全性更好的序列，而且增强了整个矩阵序列抵抗攻击的能力；不仅如此，作者进一步构造了两种新的上的非线性递归矩阵序列模型，把矩阵序列的周期和分量序列的线性复杂度由常数倍提高到了指数量级第二章矩阵上的线性递归序列2 1基础知识定义2 1 1 设k z + ，给定o ，a o ，n 一l 日，若序列量= 8 0 ，s l ，( & 日，i = 0 ，1 ，2 ，) 满足关系式s n + 知= a k 一1 8 n + k 一1 + a k 一2 8 n + k 一2 + + a 0 8 n + a( 2 1 1 )就称该序列为b 上的k 阶线性递归序列称( 3 0 s 1 ，8 * 一。) 为序列的初始状态注：满足( 2 1 1 ) 式的一个关系被称为k 阶线性递归关系分两种情形：( i ) 若a = 0 ，称其为齐次线性递归关系，相应的序列称为齐次线性递归序列( i i ) 若a 0 ，称其为非齐次线性递归关系，相应的序列称为非齐次线性递归序列在此仅讨论a = 0 的情况，此时把多项式，( z ) = z 膏- a k 1 x 七一1 - - a k 一2 x 2 一一a o ，( z ) 乃( z )( 2 1 2 )称为线性递归序列的特征多项式，序列墨的次数最低的特征多项式称为序列量的极小多项式定义2 1 2 设f ( x ) 是f 。上的一个次数大于或等于1 ，零次项不等于零的多项式定义f ( x ) 的周期为最小正整数f ，使f ( x ) 整除一一1 ，记作p ( ，( z ) ) 或p ( ，) 定义2 1 3 对于日上的几次不可约多项式，( z ) ，其周期若等于q n 一1 ，则称f ( x )是n 次本原多项式定义2 1 4 设f 口上的一个无限序列a = ( a o 砌，) ，a i f 口( i = 0 ，1 ，2 ，) ，我们说盟是周期序列，如果有z z + 存在，使0 f 十= a k ，对一切非负整数k 把满足上式的最小正整数f 叫做a 的周期，记作p ( 立) 即p ( a ) = m i n l ia l + k = a k ，v k z + ) 定义2 1 5 当n 级线性移位寄存器序列的周期达到最大值q n 一1 时，它就叫最2大长度的q 元n 级线性移位寄存器序列，简称q 元m - 序列，也简称僻序列定义2 1 6 设q 是一个素数的幂，( z ) 是f 。上的一个t t 次不可约多项式，而且，( z ) z ，( z ) 的周期定义为f ( x ) 在f 旷中的礼个根在f + 。n 中的公共的阶如果f ( x ) 的周期是q ”一1 ，那么f ( x ) 就叫f 。上的本原多项式，即，( z ) 的根都是f 。的本原元定义2 1 7 线性复杂度就是序列墨所满足的，阶数最小的齐次线性递归关系的阶数，如果用线性移位寄存器来实现某一个序列，则它的线性复杂度就是能生成该序列的最短线性移位寄存器的阶数，通常用l ( s ) 表示定义2 1 8 设量是f q 上的一个长序列，也是f 。上的一个长序列，量的“重量复杂度为：w c 。( _ s n ) = m i nl ( _ 8 n + ) i l i ( t n ) = “) ( 2 1 3 )其中，名( ) 表示序列的h a m m i n g 重量，即中非零分量的个数定义2 1 9 设a 是f z 上的一个周期序列，记a = ( a o ，a 。，a 。，) ，再设8 z + ，令鱼( a ) = ( a o ，a 8 ，a 2 ) ，它叫做a 的一个采样定义2 1 1 0 设川；z + ，g c d ( n ，b ) = 1 ，k 是使b k 兰l ( m o d n ) 成立的最小正整数，即若有b h ；l ( m o d n ) ，则限我们把k 叫做b ( m o d n ) 的乘法阶引理2 1 1f q 上的所有非奇异k 阶矩阵在普通乘法下构成一个有限群，称之为一般线性群，记为g l ( k ，日) 证明见参考文献( 1 5 】引理2 1 2 设f ( z ) = a o + a l x + a 2 x 2 + + 矿是r 上的一个n 次多项式，而a o n 。0 ，我们把，( z ) = 茹”，( ；) = a o x “+ a l z ”1 + a 2 z ”2 + + 叫做，( z ) 的互反多项式，进一步有：( 1 ) ，( z ) 与，( 。) 同时可约或不可约；( 2 ) ，( 石) 与f ( x ) 同时不可约时，设q f 驴是，( 茹) 的一个根，那么q 一1 f 矿就是，( z ) 的一个根( 因为。和o 。在f + 矿中有相同的阶) 所以f ( x ) 和，( z ) 的周期相等( 3 ) ，( z ) 与f ( x ) 同时是本原多项式或不是本原项式一般地，不可约多项式未必是本原多项式3证明见参考文献【4 】( 2 1 2 ) 式的互反多项式_ ( z ) = 1 一a k - l x a k - 2 x 2 一a o x ，我们通常把此式称为定义2 1 1 中序列量的联结多项式反过来，递归关系式( 2 1 1 ) 由，( z )完全确定，我们把适合递归关系式( 2 1 1 ) ( = 0 ) 的q 元k 级线性递归序列，叫做由，( z ) 生成的q 元k 阶线性移位寄存器序列，简称由，( z ) 生成的序列，常用o ( y ) 表示适合递归关系式( 2 1 1 ) 的q 元惫阶线性移位寄存器序列的全体组成的集合0 序列属于g ( ，) ，并且容易证明c ( f ) 构成r 上的一个向量空间引理2 1 ，3 设点= ( 8 0 ，s h - ) 是b 上的一个齐次线性递归序列，而且它有非零的初始状态向量若序列s 的特征多项式，( z ) f q ( z ) 在f 。上不可约而且满足f ( 0 ) 0 ，则序列量是周期序列而且最小周期等于，( z ) 的阶数o r d ( f ( x ) ) 证明见参考文献1 4 】引理2 1 4 设，( z ) 是f 。上的一个次数大于或等于1 ，零次项等于1 的多项式，那么对于c ( f ) 中任一非零二元k 级线性移位寄存器序列岛周期p ( 墨) 整除p ( ，)证明见参考文献【4 】引理2 1 5 设i ( x ) 是f 2 z 】上一个次数k 1 而零次项等于1 的多项式，那么以，( z ) 为极小多项式的线性移位寄存器序列的周期就等于，( z ) 的周期证明见参考文献【4 】引理2 1 6 设，( z ) 是f 。上的一个零次项不等于零的不可约多项式，那么p ( ，)整除q d e g ( i ( z ) ) 一1 证明见参考文献【4 】引理2 1 7 若f 。上的序列a 的特征多项式夕( z ) 不可约，则有p ( 亟) = p ( 9 ( z ) ) 证明见参考文献【4 】引理2 1 8 设，和护是f 。上周期为v 的序列，r , l ，丘分别为这两个序列的既约有理分式表示，则w c u ) = m i nd e g 酮百夤丽lw t - ：( w ) = “) ( 2 1 4 1 )特别地，护的1 一重量复杂度为：w c l ) = 1 1 1 i nd 昭同面考若而j0 i n 一1 ，o f + g ) ( 2 1 5 )这里9 ( z ) = ( 1 一x n ) 肛( z ) 4证明见参考文献【6 】引理2 1 9 设a 是一个日上周期为p ( 蓟的q 元周期序列，8 z + ，那么盟( 。) 也是周期序列，它的周期是p ( _ n ) g c d o ，p ( 垒) ) 的一个因子证明见参考文献【4 】引理2 1 1 0 设a 同引理2 1 9 8 是与p ( a ) 互素的正整数，那么8 ) 也是周期为p ( 鱼) 的周期序列证明见参考文献【4 】引理2 1 1 1 设a 是f 2 上的一个周期为2 ”一1 的僻序列，g c d ( s ，妒一1 ) = 1 ，则s ) 也是周期为2 n 一1 的m - 序列进一步，如果a 的极小多项式以口为其一根，那么。) 的极小多项式就是以口8 为其一根的本原多项式证明见参考文献【4 】引理2 1 1 2 设鱼是f 2 上的一个周期为2 t i 一1 的僻序列，那么f 。上的任意一个周期为2 t l 一1 的m - 序列都与a 的某一采样平移等价更进一步，设g c d ( r ，2 “一1 ) = g c d ( s ，妒一1 ) = 1 ，那么鱼( ) 与尘5 ) 平移等价甘r 兰8 2 t m o d ( 2 “一1 )对某一整数t ，0 t n 一1 恒成立证明见参考文献【4 】引理2 1 1 3 设f 。上周期序列护的一个特征多项式为，( z ) ，设，( z ) 的全部根为( x 。，) ，重数分别为( e 1 e 。，e 。) ，则在扩域上有唯一的一组 b i j ，i =1 一m ，j = 0 一e 一1 ，使得对任意n ，有s 竹= 量缸“量嚷钾b o 证明见参考文献【1 3 】引理2 1 1 4 设，是b m 上的一个次数为m 的不可约多项式，则，在日上的分裂域是r 。证明见参考文献【1 1 引理2 1 1 5 如果f 是一个含有q 个元素的有限域，k 是f 的子域，则多项式( x q z ) k z 在f m 中可以分解为：护一x = 1 - i 一o ) ，n f5而且f 是妒一z 在k 上的分裂域证明见参考文献”以下我们用到的日仅为q = 2 的情形2 2m 2 上的线性递归序列的构造及密码学特性现在把足上线性递归序列构造到二阶矩阵构成的环上设尬： l 口6i ln ，6 c d f 2 ) ，在通常的矩阵加法和乘法下：c d ( 1 ) 矩阵尬对加法构成交换群5( 2 ) 矩阵对乘法有结合律；( 3 ) 矩阵尬对两种运算有分配律因此二阶矩阵m 2 在上述两种运算下构成环定义2 2 1 设a ：( 山，a 1 ，a 2 ，) 是m 2 上的矩阵序列，其中a ：i 啦啦l ，玩屈0 4 ，坟，o t i ，屈f 2 ( i = 0 ，1 ，2 ，) 若有中的元素g ，a ，g l 使得丛满足：a 件n = 五一1 a 件。一l + c k 一2 a i + n - - 2 + + c o a i ( i = 0 ，1 ，2 ，) ( 2 2 1 )则称序列4 是上的礼级线性递归矩阵序列称立= ( ( z i ) ，= ( 魄) ，立= ( 啦) ，卢=( 屈) ，是4 的分量序列对于这样的矩阵序列有如下的性质定理2 2 1 设丛是( 2 2 1 ) 式产生的飓上的线性递归矩阵序列若岛是可逆矩阵，则丛一定是周期序列证明设丛的初始状态为( 山，a 。，a 。一t ) ，因为丛满足关系式( a 1 ，a 2 ，a 。) = ( a o ，a 1 ，a 。一1 ) c( 2 2 2 )其中c =e 中的0 为二阶矩阵，j ；三g 尬( i = 0 ，l ，2 ，) 因为i c l = i c o | 0 ，所以根据引理2 1 1 ，g f ( 2 n ，f 2 ) 构成有限群所以( a 2 ，a 3 ，a t l + 1 ) = ( , 4 0 ，a 1 ，a 一1 ) c 2 ，( 也，如+ 1 ，如押) = ( a o ，a 1 ，a 一1 ) c j因为c 可逆，所以c ，c 2 ，g f ( 2 n ，昂) ，存在后，j z + ，使得c 。= ，又c的阶有限，则存在t 矿，使c t = e 所以，( a ，a t + 1 ，a t + 。一1 ) = ( a o ，a 1 ，a 。一1 ) c = ( a o ，a a ，a 。一1 ) 所以，a t = a o ，a 件l = a 1 ，a t “= a ( i = 0 ，1 ，2 ，) 所以，t 为丛的一个周期定理2 2 2 设丛是( 2 2 1 ) 式产生的 如上的礼级线性递归矩阵序列，旦 b ，岛生，是相应的四个分量序列，则矩阵序列丛的周期p ( a ) 等于四个分量序列的周期p ( 鱼) ，p ( ) ，p ( 立) ，p ( 生) 的最小公倍数，记为i c m ( p ( a ) ，p ( ) ，p ( 立) ，p ( 壁) ) 证明设t 是的一个周期，则有即旧a i + to i i + ti = la i ：)所以，啦+ t = 吼，n 件t = n i ，玩+ t = 晚，屈+ t = 屈( v i = 0 ，1 ，2 ，) 即丁也是分量序列的鱼，b ，鸟p 的周期反之要满足( 2 2 3 ) 式，必有p ( a ) =l c m ( p ( a ) ，p ( ) ，p ( 丛) ，p ( 卢) ) 定理2 2 3 设是由( 2 2 1 ) 式生成的礼级线性递归矩阵序列，则矩阵序列丛的周期p ( a ) = 铲一1 净a 是非零矩阵序列，且丛中的分量序列有同一的特征多项式，为2 n 次本原多项式因为a = la i 差) ，所以a 件。= a i + n 乏：) 于是依次可以写出a 佃乩a m 锄，以又g ：f 铅以l ，同样依次也可 以写出c o ，c 1 ，g 廿将以上式子代入递归关系式( 2 2 1 ) ，可得到以下四个等式：7玩+ n = e n - l a i q - n - 1 + + e 1 啦+ 1 + e o 啦+ 一l 晚+ n 一1 + + 魂+ l + 矗饥o + n = c n 一1 0 q + n - 1 + + c t o q + l + c 0 q i + 厶一1 屈+ n l + + d 1 臃+ l + d o 屈屈+ n = e r r - - 1 0 t i + n - 1 + 十e l q 件1 + e 0 0 4 + 厶一1 屈+ n 一1 + + f l 屈+ l + f o 展根据( 2 2 5 ) 式可以写出饥押一1 = e n - - l a i + n - 2 + + e o a i 一1 + 厶一1 玩4 - n 一2 + + f o b i 一1玩+ 1 = e n - 1 0 4 + + e o a i - n + l + 厶一1 岛+ + 知峨一n + 1b i = e n l 毗一1 + + e o a i n + ，n l 堍一1 + + f o b i 一”再将这n 个式子代入( 2 2 4 ) 中，得啦+ n = c o a i + + 一1 啦+ 一1+ d o ( e o a t 一。+ + e n l a i 一1 + f o b i n + + 厶一t b i 一1 )+ d l ( e o g i - n + l + + e n 一1 g i 十f o b , 一n + l + + 厶一1 b i )+ 2 2 52 2 62 2 7+ d n 一1 ( e o 凸t 一1 + + e n - 1 a 件m 一2 + f o b i 一1 + + 厶一i b i + n 一2 ) = c o a i + + e m l a i + n 一1+ e o ( d o a i n + d x a i - - n + l + + d n l a i 一1 )+ e l ( d o a i - - n + l + d i a l - - n + 2 + - + d n 一1 。t )+ + e n - 1 ( d o a i 一1 + d l a + + d n l a 件n 一2 ) + f o ( d o b i n + d l b i n + 1 + + d n i b i 一1 )+ f i ( d o b i - n + l + d l b i - - n + 2 + + 如一l 玩)+十，竹一1 ( d o b i l + d l b i + + d j l 玩+ 。一2 ) ，( 2 2 4 ) 式也可写为从而啦+ n = c k a i + + d k b i + kk = ok = on - 1n ld k b i + k = a i h + c k a i + 将( 2 2 9 ) 代入( 2 2 8 ) 中，得8( 2 2 8 )( 2 2 9 )啦+ n = ( c 0 啦+ c l a i + 1 + + a n l a i + n 一1 )+ ( ，0 啦+ ，1 口件1 + + 厶一l a t + n 一1 ) )+ ( e o d o + f o c o ) a 一n + ( e o d l + e l d o + f o c l + f l c o ) a i 一，l + l + + ( e 0 靠一1 +e l d i 一2 + + e n - 1 d o + ，0 e m 一1 + 一2 + + ，n 一1 c o ) a i - - 1 + ( e l d n 一1 + e 2 d n 一2 + + e n - - l d l + c n 一1 + ，2 c ，i 一2 + + 厶一l c l ) a i +( e 2 如一1 + e 3 蟊一2 + + e n l d 2 + ，2 c n 1 + f 3 e n 一2 + + 厶一l c 2 ) 啦+ 1 +( e 3 d n 一1 + e 4 厶一2 + + e n - - 1 d 3 + 厶c n 1 + ，4 c n 一2 + + 厶一1 c 3 ) a i + 2 + ( e n - 1 d n 一1 + 厶一1 c n 1 ) 啦+ n 一2 )= e ( c k + ) 啦+ i +n k = 一0 lt占蓦( e j d k - j + 厶。) 虬+占毒1 ( 勺厶州+ 胁+ k - j ) a i + 2 妊e 。 o k + + j 美l ( e j d n + 一j + i s - + k j ) 】吼+ k +占伽e ( e j d k j + f j c k j ) a i - n + k + ( 铀+ 厶一1 ) 吣( 2 2 1 0 )( 2 2 1 0 ) 式变形为：n - - 2n 一1n 件n = c l + ，l + ( e j d n + t - j + f j c n + l j ) o 件j +1 = 0j = + l盖善( 啦一j + 乃c l j ) 。撕+ f +( c n 一1 + f n 一1 ) a i + n - 1以k + 礼替换in-2，l1a k + 2 n = 【e l + 五+ ( 勺如+ j 叫+ h c + l j ) 】o + 。+ l +1 = 0j = l + l 。n - 1l函磊( 嘲一j + 厶c l j ) 。州+( c n 一1 + ，j x ) a k + 2 。一1( k = 0 ，1 ，2 ，)再以i 替换f ，n - 2一1a k + 2 n = 三、b + 十e ( e j d n “- j 十力+ l 叫) 】o + 。+ t +l = uf = l + 1磊。e 。( e j d i _ j + 乃铀) +( ( 一1 + ，j 一1 ) a k + 2 。一1= ( 岛一1 + 厶一1 ) 口k + 凯一1 +9【c i + 十e ( e j d , , + - j + 厶+ i o ) 】+ n 州+忙。u，= l 十ln 一1t量。( e j d i - i + 厶q j ) 口脚( k = 0 ，1 ，2 ，)( 2 2 1 1 )类似地，我们可以得到序列b 的线性递归式：靠+ 2 n = ( c n 一1 + ，一1 ) b k + 鼽一1 + c i + + 写( 勺d ，i + t j + 乃c ，l + _ j ) 】+ t l + +l = uj = i 十in ( e j d t - i + f j c _ j ) b e + i ( k = 0 ，1 ，2 ，)( 2 2 1 2 )由( 2 2 1 1 ) 式与( 2 2 1 2 ) 式，分量序列a , b 是满足同一递归关系式的2 n 级线性递归序列同样地，也可得到旦，卢的递归式它们也是满足同一递归关系式的2 扎级线性递归序列于是就得到定理2 2 3 的推论推论2 2 3 设是( 2 2 1 ) 式产生的n 级线性递归矩阵序列，则矩阵序列丛的四个尼上的分量序列a ，b ，o l ，卢，有同一个2 n 级线性递归式生成由( 2 2 1 1 ) 式，( 2 2 1 2 ) 式与推论2 2 3 ，矩阵序列的四个分量序列立，b ，o l ，壁，满足同一个2 札级线性递归式，而且有共同的特征多项式；g ( x ) = 。2 “+ ( c 。一1 + 厶一1 ) x 2 4 1 +【c + + ( 也e 。+ i 叫+ 勺厶+ 一，) 】z ”“+l = uj = z + ln 一1i( 奶e o 十c j 一j ) x 4 ( 2 2 1 3 )由以上的准备，下面对定理2 2 ，3 进行证明证明( # ) 因为g ( x ) 是2 n 次本原多项式，根据定义2 1 5 ，定义2 1 6 ，g ( x ) 对应的分量序列是2 n 级m 一序列p ( 立) = p ( ) = p ( 立) = p ( z ) = 4 ”一1 ，所以p ( a ) 4 n 一1 ，又由定理2 2 ，2 知p ( a ) 铲一1 ，从而p ( a ) = 4 n 一1 ( 净) 因为互( 茹) 在f 。上不可约，所以g ( x ) 在f 。上也不可约，而g ( x ) 是分量序列的特征多项式根据引理2 1 6 ，g ( x ) 就是f 。上的本原多项式鱼，b 曲卢，满足同一个特征多项式夕( z ) ，它们的互反多项式：雪( z ) = z 2 n 夕( ) = 1 + ( c ，l 一1 + 厶一1 ) x +【c i + + ( 嘞e 。一j + i + 勺，n - j + t ) 】z ”1 +l = uj = l 十1n 一】ie ( 嘭e t 叫+ c 一j ) z 鼽1 0就是这四个分量痔梦| j 的联接多项式，它的零次项非零根据弓l 理2 1 4 ，结合引理2 1 2 得到；尹( 建) 整除p ( 筘) ，p ( b ) 整除尹( 萝) ，p ( 建) 整除p ( 9 ) 舻( 圆整除p ( 9 ) 荐由定理2 2 2 ，就得到p ( 国= l c m 0 , ( _ - ) ，p ) ，p ( 垡) ，p ( 卿) ，所以p ( a ) 整除p 办根据弓i 理2 1 5 ，可得到p ( 萝( 算) ) 整除2 2 n 一1 ，也有p ( g ) 整除妒一1 根据定义2 1 7 ，结合耍( z ) 的表达式与g 浈z ) ) 的定义，可以得到四个分量序列的线性复杂度为：l ( 照) 2 n ，l ( 妨冬2 珏，l ( 囝2 n ，l ( 妒) 2 n a ，b 悬声由同一个孙级线往递衄式生成再结合定理2 2 3 知，m 2 上的n级线性递麴矩阵序列的最长周期是铲一1 ，如果m 2 上的珏级线性递归矩阵序列的最长属期是4 n 一1 ，就称这样的矩阵序列为m 2 上的n 级m ，- 矩阵序列推论2 2 4a 燕m 2 上的! r t 级彬一矩阵序列，则它们的所有非零分量序列是f 2上的孰级r n , - 序刭证明因为非零分量序列的特征多项式g ( x ) 是2 髂次本原多璎式，根据定义2 1 5 ，得劲它们都是2 n 级肌序列下面一节我们主要讨论捣上的n 级 讧矩阵序列的分量序列的一些安全性指标，以及由此带来的对线性递归矩阵序列的安全性的分析2 3r t 级m t _ 矩阵序列的分量序列的安全性指标根据流密码的一些基本理论，如果一个序列的线性复杂度为l ，则知道它的任意2 个连续的元索就可通过解线性方程组确定整今序列，因此，较高的线性复杂度是提高密钥流序列安全性的一个重要指标，但足够大的线性复杂度也未必难以预测例如一个毪上的有限序列：墨一1 1 1 1 0 l ( a n ) 一n ，只要改变一个比特0 ，线性复杂度就降到了1 0 7 觅，序列的线性复杂度并不稳定因此，有必要度量序列的稳定性。薅度量稳定性的重要指标是由丁存生等老师在1 9 8 7 年弓l 入的重量复杂度笔者通过它的定义得到了以下两个主要定理定理2 3 1 设，是一个m 2 上的扎级m ，一矩阵序列的分量序列，则该分量序列的l 一重量复杂度满足：w c i ( s 。) 4 ”一2 礼一1 ( 2 3 1 )证明根据推论2 2 4 及n 级m ，一矩阵序列的定义，是一条2 礼级僻序列再根据定义2 i 5 ，它是f z 上的一条最大长度序列，所以，的周期为n = 2 “一1 = 4 - 1 ( 2 2 1 3 ) 式中的g ( x ) 是序列，的极小多项式，d e g ( g ( x ) ) = 2 n 设护也是f 2 上周期为的一条序列，且设( x ) l ( x ) 是扩的既约有理分式，这里厶( z ) = 9 ( z ) 令f ( x ) = ( 1 一z ) g ( z ) ；h ( z ) = g c d ( t z ，z + r 。( z ) ( 1 一x n ) 夕( 。) ) 则h ( x ) l ( 1 一z ) ； ( z ) l k + r s ( z ) ( 1 一x n ) 9 ( 霉) 】l ( x ) 不可约，如果h ( x ) g ( z ) ，则一定有a ( x ) l g ( z ) ，也有h ( x ) l x ，这与h ( x ) f ( 1 一)矛盾，所以g ( x ) = 危( z ) ，根据定义2 1 8 ，引理2 1 8 及( 2 1 5 ) 式，所以有：、v c - ( ，) = m i nd e g 专著) 1 w ) = l ，n d e g ( g ( x ) ) = 2 2 ”一2 仃一1 由此定理可得护，护，垡o o ，矿的1 一重量复杂度的下界为驴一2 n 一1 定理2 3 2 设序列护是一个m z 上的n 级m 矩阵序列的分量序列，肼为( 4 “一1 ) 的最大真因子，则该分量序列的2 一重量复杂度满足：w c 2 ( 量0 。) 4 “一2 n - 1 一m ( 2 3 2 )证明序列扩的周期n = 4 “一1 ，设序列护也是一个易上周期为的二元序列，并且( ) = 2 ，假设t = 巧= 1 ，t 女= 0 ，0 ksn 一1 ，k i j 设g = g c d o 一i ，) 五0 ) = ( 1 + x ) ( 1 + z g ) ；r t ( x ) = ( x i + ) ( 1 + z g ) 由于l ( x ) = g ( z )是序列，的极小多项式，而且g n ，所以g ( x ) 不整除( 1 + x g ) ，g ( z ) 整除( 1 + x ) 设h ( x ) 是g c d ( f t ( x ) ，r t ( x ) + ( z ) i t ( x ) l g ( z ) ) 的一个不可约因子，则h ( x ) l r t ( 。) ； ( 删h ( z ) + r 。( z ) ( z ) 向( z ) 】g ( x ) 不可约，如果h ( x ) 9 ( z ) ，又g c d ( ，r t ) = 1 ，所以h ( x ) = 1 因此，只有h ( x ) = ( 9 ( z ) ) ”，( n z + ) g c d ( x + 1 ，n x - 1 ) = 1 ，所以1 + 无重因子，所以 ( z ) 无也重因子所以n = 0 或n = 1 无论哪种情形，都有w c 2 妒) = m i nd e g 吾而g1 1r t + ri t ) l0si j n 一1 )= r a i nd e g 虿鬲丌五_ ) 10 i j n 一1 )n o t m f a x 一1d e g ( 1 + 茁g ) g c d ( ，t ，r t + r , f j g ) = n 一( g - i - d e g ( g ( x ) ) )= 2 凯一1 一m 一2 n其中m = g = g c d ( j i ，) ，即为v 的最大真因子由以上两个定理的证明过程可以看到：在序列的每个周期段内的任意一个位置上改变一个比特，序列的线性复杂度就会陡增至上面的两个界值因此得到的序列的线性复杂度很不稳定这种分量序列及整个矩阵序列丛不足以抗击b a a 攻击所以，下一章对凡级m ，一矩阵序列的分量序列来构造特殊下标采样，增强分量序列对整个矩阵序列抵抗攻击的能力1 3第三章分量序列的安全性及对矩阵序列安全性的影响3 1礼级m 7 一矩阵序列分量序列的下标序列的构造根据引理2 1 9 及引理2 1 1 0 ，m 2 上的竹级m 7 一矩阵序列分量序列的采样序列的周期，不可能超过原来竹级僻序列的周期，因此这不是我们想要的结果。那么能否找到一种特殊的采样，来提高n 级m 一矩阵序列分量序列的周期呢?文献【9 】9 给出了一种下标采样序列，通过对序列平移和采样相结合的方法，在理论上提高了它的周期，并且这种下标序列可以在实际中得以实现，j e n n i n g s复合序列( 本人有关j e n n i n g s 复合序列的一些结果已被郑州大学学报录用) 就是该下标序列的一种特例这种方法不仅提高了序列的周期而且还能增大序列的线性复杂度笔者采用了这种方法，得到了一些较为理想的结论设x = ( 观) 是二元周期序列，则用幻( 观) m ) 来表示( 2 7 t ) 先左平移t o 位再取m 采样所得到的序列，即若x = ( x t ) = ( ：t o ，x l ，x 2 ，x t ，) ，则t o ( 勋) ( m ) = ( z z 如+ m ，z t o - f 2 1 l f ，x t o + k m ，) ( 3 1 1 )定义移位算子：t ：t x _ = t ( x t ) = 1x = 1 ( x t ) = ( x l + t ) = ( x l ，z 2 ，x l + t ，)即( x t ) 向左平移一位而得到的序列定义数乘算子：a x _ = a ( x t ) = ( a x t ) = ( a x o ，a x l ，a ：r , t ，) ，t x = t k ( x ) = ：七( z t ) = ( 茁，x k + 1 ，x k + t ，) = ( z b + f ) ( 3 1 2 )即( 既) 向左乎移k 位而得到的序列因为a = ( 吼) ，b = ( 6 t ) ，立= ( a t ) ，壁= 慨) 均为f 2 上的2 n 级m - 序列，而且这四个分量序列的特征多项式为本原不可约多项式，从而可设1 49 ( z ) = 兀( $ 一c 吣2 )( 3 1 3 )其中o r 0 是某一p = 4 n 一1 阶本原单位根，则根据引理2 1 1 2 ，b ，g ，p 都可以看作立的的某一采样平移序列，即存在自然数0 ，1 ，n 2 ，t o 0 ，t 1 0 ，t 220 ，而且g c d ( n o l n 2 ，p ) = 1 使( b t ) = 如( 毗) 0 ；( q 1 ) = t 。( n t ) ( 1 ) ；( 屈) = 。( a t ) ( 2 ) 再根据引理2 1 1 2 知道，b ，o t ，p 的极小多项式分别为2 礼次本原不可约多项式跏( z ) ：2 i i l ( z c t o n 。) ；(1ctono3 1 4 )跏( z ) = 兀( z 一；(4 )g l ( x ) ：2 7 i 1 ( z o l d n l 2 ) ；) = 兀扛一) ；i = 0仍( z ) ：爷1 ( x - - ，0 脚)t = u再使用引理2 1 1 2 ，若任意0 t 2 n ，有n o 2 t 1 ( m o d p ) ；n o 2 t 2 ( m o d p )则，鱼坦非平移等价( 3 1 5 )( 3 1 6 )在此基础上来构造一种特殊的下标采样序列定义3 1 1 设m z + ，q l z + ，q lil ( m o d 2 ) ，m t 。z + ( o t o q 1 1 ，t o z + )v t n ，当t = t o + g l 时，定义：m t = m t o + 口1 = m t o + k m ( k ) ( 3 1 7 )我们称 是模m 周期为q 。的下标函数，它的具体形式如下：m 0 ，m l ，m 2 ，m q l 1 m o + m ，m l + m ，m 2 + m ，m q l 1 + m ， 。m o + k m ，m l + k m ，m 2 + k m ，m q l 一1 + k m ， ，定义3 1 2 设 是模m 周期为q ，的下标函数，设序列t = ( s 。) 是n 级m 7 一矩阵序列的分量序列立，k ，舀卢中的任意一条序列，则曼是f 。上的2 佗级胁序1 5列令u t = s 。，( o t + o o ) 称u = ( 札t ) 是量= ( 8 t ) 相应于 的下标序列设p 是量的周期，g c d ( m ，p ) = 1 设p 是f 。中的一个本原单位根，则墨的极小多项式：9 ( z ) ：最( z ) ：2 前1 ( z 一) ( 1 3 1 8 )9 ( z ) = 最( z ) = n ( z 一卢掣) ( )根据引理2 1 1 3 知，存在唯一的f f 2 。，f 0 ，使得巩；2 笼1 f 掣( 卢) 0 o )( 3 1 9 )因为g c d ( m ，p ) = 1 ，根据引理2 1 1 1 ，t 0 ( 撕) q ，) = 。( 3 f ) m ) 也是2 n 级m - 序列，所以它的极小多项式为：h ( x ) = e ( ”) ( z ) = l i l ( z p 肼) ( 3 1 1 0 )结合引理2 1 1 4 和引理2 1 1 5 ，于是下标序列笪的生成多项式为：h ( x a l ) ：爷1 ( z 。- 一卢m ) ：爷14 打1 一。t u 掣)( 3 1 1 1 )其中，口f 2 。为q 1 阶本原单位根，2 m 三l ( m o d q l ) ，u f 2 c 满足u q - = p m ，h ( x q - ) 在f 。上分裂由序列的根表示，结合文献【8 】，则存在唯一一组钧f 。，使而且满足：4 董12 n - - 1 u t锄( 口 “掣) t ( 0 )= 仇j ( 口1 “) ( )i = 0j = o乜是魄( z ) 的根铺0 以下求的表达式及序列u = ( u t ) 的极小多项式根据( 3 1 1 2 ) 式和u 。- = 卢m ，a 为q ，阶本原单位根，可得t t t o + k q l t t t o + k ：氅1 【9 董1 锄( q t ) 如】矿m t ( t 0 )= | 【7 硒( q 。u 掣) t 0 】卢掣。肘2 ( )j = ul = u根据( 3 1 9 ) 式，可得=2n-8to+km1 偿尹如) 掣卢m 七( t20 )= ( f f 即亡0 ) 掣卢掣朋2 ( 2 )根据定义3 1 2 ，可得u t o + 衄= 8 t o + k m1 6( 3 1 1 2 )( 3 1 1 3 )( 3 l 1 4 )( 3 1 1 5 )( 3 1 1 6 )令6 ( o ) = ( f 矿幻) 分联立( 3 1 1 4 ) 式，( 3 1 1 5 ) 式和( 3 1 1 6 ) 式，可得j ( t o ) = 1 妄钧( o l i o , ) 掣) 幻( 3 1 1 7 )根据参考文献【8 】，可得= ：j ( t o ) ( o u 掣) ( 3 1 1 8 )再令啦( z ) = 篁：白( 如) ( z ) 如，噶( z ) 是仍( z ) 的互反多项式，根据引理2 1 2 ，可得g - 是仍( z ) 的根 净e 一是谚( z ) 的根令由( z ) = g c d ( 嘞( z ) ，z n 一卢尹肘) ；d ( x ) = p 由( z ) (，)_o3 11 9根据( 3 1 1 8 ) 式和( 3 1 1 9 ) 式，可得q 不是嘭( z ) 的根仁争0 但o u 是( x q - 一肘) 的根，所以a 不是d j ( x ) 的根，也不是d ( x ) 的根，再根据( 3 1 1 9 )式，可得f 笪( z ) = h ( x 仉) d ( z ) ( 3 1 2 0 )根据以上构造及推导过程，所以得到以下定理和推论：定理3 1 1 是模m 周期为q 1 的下标函数，量= ( s t ) 是2 礼级胁序列，u = ( 。) 是对应下标序列，则当g c d ( m ，2 轨一1 ) = 1 时，有( 1 ) 序列盟具有生成多项式h ( x q l ) ，序列盟的线性复杂度满足l ( u ) q 。2 n ；( 2 ) 序列u 的极小多项式为垃( z ) = h ( x q t ) d ( z ) 推论3 1 1 下标序列笪满足( 3 1 1 2 ) 式，而且魄( z ) = h ( x 4 1 ) 号v i ，j ，0 ( 3 1 2 1 )取定义3 1 2 中的m = q 1 ，于是有g c d ( q - ，p ) = 1 序列皇= ( 8 t ) 是扎级m 7 一矩阵序列的分量序列a ，b ，立，p 中的任意一条序列，它仍为2 n 级m 一序列，设g c d ( m ，n ) = 1 ，m 仍满足2 m 兰l ( m o d q l ) 令巩= r n t 一， 2o ) ，根据的定义知， 是一模q 。周期为q l 的序列限定0 巩s2 n 一1 ，令0 - 1 ( 1 ) = k l e k = ，0 k q l 一1 ) 结合推论3 1 1 可得定理3 1 2 设 是模吼周期为q 1 的下标采样函数，2 ”三l ( m o d q l ) ，序列墨= ( 8 。) 是n 级m ，矩阵序列的分量序列a ，b ，立，p 中的任意一条序列，若下列条件成立( 1 ) g c d ( m ，n ) = 1 ；1 7( 2 ) 0 兰e t = r m t 兰2 u 一1 ；( 3 ) 存