无记忆M序列生成算法的密钥嵌入

无记忆M序列生成算法的密钥嵌入 无记忆 M 序列生成算法的密钥嵌入 1 1 1 2 贺亮, 徐克舰, 戴照鹏, 范修斌 () 1 . 青岛大学数学科学学院 , 青岛 266071 ;2 . 中国科学院信息安全国家重点实验室 , 北京 100049 摘要 : 给出了一大类距离函数 ,证明了该类中任何一种距离函数都能够无记忆快速生成 M 序列 。在此基础上 ,进一步系统给出了无记忆 M 序列生成算法的密钥嵌入方式 ,从而 基本解决了无记忆 M 序列生成算法的密钥嵌入问题。 关键词 : 移位寄存器 ; 序列 ; 距离函数 ; 密钥嵌入 中图分类号 : O153 . 2文献标识码 : A 问题 1 n n ( ) 由文献[ 1 ] ,设 n ?1 , f 是 F 到 F上的函数。对于任意 a,, a? F, 令2 n- 1 a, 0 2 2 n- 2 )( ai + n = f ai + n- 1 , ai + n- 2 ,, ai i = 0 , 1 , 2 , ( ( α ) α 则无穷序列= a, a, a,称为以 f 为反馈函数的 n 级移位寄存器序列。显然由 f 和初始值 a,0 1 2 n- 1 n a, ) ( ) Ω( ) Ω n- 2 2 。= , a唯一确定。用f 记 F上所有以 f 为反馈函数的移存器序列构成的集合 , 则有 | f |0 2 n ( ) ( (α) ) α Ωα 如果?f 是一周期序列 , 且其周期 记作 p 为 2 , 则称是 n 级 M 序列 , f 又称 M 馈。文献[ 1 ] 和[ 2 ] 等分别给出了构造全部 M 序列的几种方法 , 这些方法的一个共同特点是有记忆生成算 法 , 这些方法对生成大级数的 M 序列一般是困难的。文献[ 1 ] 给出了无记忆 M 序列生成算法 , 该算法可以较 快生成大级数的 M 序列 , 但没有讨论和解决无记忆 M 序列生成算法的密钥嵌入问题 。文献[ 3 ] 初步讨论了该 算法的密钥嵌入方式 。 本文在上述文献的基础上 , 给出了一大类距离函数 , 证明了该类中任何一个距离函数都能够无记忆快速 生成 M 序列 。在此基础上 , 进一步系统给出了无记忆 M 序列生成算法的密钥嵌入方式 , 从而基本解决了无记 忆 M 序列生成算法的密钥嵌入问题。 2 概念与基本结论 由文献[ 1 , 3 , 5 ] , 设 M 序列的反馈多项式的基本模型为 : ( ) ( ) ( ) f M an- 1 ,, a0 = a0 + f 0 an- 1 ,, a1 + f c an- 1 ,, a1 n n 其中 f 称为 M 馈 , f 称为基函数 , 下面本文的结论约定 f 为纯轮换 , f 称为控制函数 。以 F中的 2 个点2 M 0 0 c n 为顶点 , 从每个点 a =( )( | b? F} 作一条有向, , a ? F出发 , 向后继{ b =2 a, a,ab, a,1 1n- 1 n- 2 0 1 n- 1 ( ) n) ( α α( ) 弧 , 这些点和弧构成的有向图记作 G, 称为 a+ f a f , a1 的有向状态图 。若? ′= 00 , , 01, 0 0 n- 1 ,0( ) nn- 1 σσ σ α ( ) σ σ 则称它们是共轭的 。设 Gf 有 r 个圈 : 1 , 2 ,r , 2 i j , 。= a, a? F是圈, 的一条边当且仅n- 1 1 0( )n ) σσ( σσ 当 a = a,a, a跟其共轭点分别属于, , 又称, 为相邻圈 。从 G出发定义一个无向图 T ,n- 1 1 0 i j i j f f 0 ( )n σ ( ) σσ T 的顶点集记为 V T , 是 G的 r 个圈 , 这 r 个圈仍记为, ,, , 以与点区分 , T 的关联为相邻圈f f f 1 2 r f 0 ( )n 的无向连接 , 则称 T 称为 G 的因子关联图 。T 中一个含有 r - 1 条边的连通部分图称为图 T 的一个截集f f f f 0 ( )n [ 4 ]( ) σ ρ 定义 因子关联图上的距离函数设T 是一个因子关联图 , N 是非负整数集 , ? G, 函数?f f0 ) ( σσρ V T ×? N 称为 T 上相对于的距离函数 , 若满足 :f 0 f 0 ( ) n( ) ρ(σσ )σ σ σ I对于?G, , 0 = 0 Ζ= 。0 f 0( n) ( )σσρ(σσ) σ II 若?G, , > 0 , 则至少存在的一个相邻圈使得′f 0 0 ρ(σσ) ρ(σσ) ,′ < , 0 0 n- 1 i ) )( )σ (σ(σ ( ) = mi n{ N a + I ?} ,a2 , 并基于= a 文献[ 4 ] 给出了距离函数 N ,I,N ,IN aL L L L i = ?i = 0 该距离函数给出了无记忆快速生成 M 序列的算法。我们对该距离函数进行了改进 , 并给出下述结论 :( )( )n n n σσ, a, a? F, 令设 G是 任 一 有 向 状 态 图 , ? Gf, Π I ?, 设 a = ( a, ) 1 0 2 f 00 n- 1 0 0 n- 1 β i β β ( ) β( ) β (σ) aa2( ) σ N, ?S , N , I= mi n{ N a + I| a ?} 则有 :L i n L L = ?i = 0 β( n)σ(σ 上相对于的距离函数 。 ) 命题N L , 0 I是 Gf 0 ( ) β nβσ ( )) σ σσ (σ) (显然 , 对于 Π?G, 0 Ζ ϖ a ?使得 Na + I I= 证明f N L I ?0 。又因为 N L ,L = 0 Ζ= 0 ( )n β β σ( ) (σσ ) ( ) σ , 因此命题满足定义之 I。若有? G, 使得 N ,I> 0 , 即存在一个 a ?使得 N a + I= N , 那0 f L L 0 ) ( 么 ϖ k 0 ?k ?n - 1使得 a+ I ?0 。这样的 k 可能不止一个 , 我们取第一个使得上式成立的 k , 然后把 ak k ) ( ( , a, a, , a, a, a沿 f 作 k 次轮换 , 得到 a 的第 k 个后继 b , 则 b 形如 b = a,= a, , a,1 0 n- 1 1 0 0 k - 1 n- 1 k ) ) σδ ( δσ( a, a, 从作边= a,a, 得到与关联的另一个圈上′的点 b=′ a,, , a, a, a, , k +1 k k - 1 k +1 k - 1 1 0 n- 1 ) ( ) a, a, 然后用 b求它的′先导点 a,′ 则 a必有′形式 a′= a,, a, ??a, a,a1 , a0 , an- 1 ,k +1 k n- 1 k , , , 1 0 β β β ) ( ) ( (σ) (σ) σσ L L L I的相邻圈 , 满足定义之 II, 因此显然有 Na′+ I< N , 所以是′的一个满足 N,′I< N, ( )β n (σ ) σ N,I是 G上相对于的距离函数 。L f 0 0 β ) β (σ I在是自然排序时的特例。文献[ 4 ] 中定义的距离是 N,L 与文献[ 4 ] 的证明相似我们可以得到如下结论 :( )β n (σ) σσ 定理设 T 是 一 个 因 子 关 联 图 , N , I 是 T 上 相 对 于的 距 离 函 数 , 对 于 每 一 个?G,f L f 0 f 0 β β ) ) σ σ(σ(σσαασ I。由此可?, 在 T 中任意取定一条与关联的边, 使与关联的另外的圈满足′ N ,′I 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 与 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 [ M ] . 北京 : 北京中软出版社 , 2003 . 熊荣[ 3 ] () 华. M 序列反馈函数的构造方法 I [J ] . 应用数学学报 , 1986 , 9 2: 227 - 236 熊荣华. [ 4 ] () 生成 Q 元 M 序列的理论和算法[J ] . 中国科学 ,1988 , A 8: 877 - 885 [ 5 ] () 熊荣华. 移位寄存器因子关联图的同构与自同构[J ] . 应用数学学报 , 1986 , 9 1: 91 - 96 [ 6 ] Imbedding Keys into the Memoryless Algor ithm of M Sequence 1 1 1 2H E L ia ng, XU Ke2jia n, DA I Zhao2p e ng, FA N Xi u2bi n (1 . Colle ge of Mat he matic s , Qi ngdao U nive r sit y , Qi ngdao 266071 , Chi na ; 2 . St at e Key L a bo rato r y of Info r matio n Sec urit y , )Gra duat e U niver sit y of t he Chi ne se Aca de my of Scie nce , Beiji ng 100049 , Chi na Abstract : A t fi r st t hi s p ap er p re se nt ed a cla ss of di st a nce f unctio n s each of w hic h ca n p ro duce M seque nce s quickl y under t he me mo r yle ss al go rit h m of M seque nce a nd t he n ga ve a met ho d , t he w hich ca n i mbed key s i nto t he me mo r yle ss al go rit h m of M seque nce . A nd so t he p ro ble m of ho w to i mbed key s i nto t he me mo r y2 le ss al go rit h m of M seque nce i s sol ved . Key words : shif ti ng re gi st er ; M seque nce ; di st a nce f unctio n ; i mbeddi ng keys