广义自缩序列生成器的安全性.pdfVIP

广义自缩序列生成器的安全性1 董丽华，胡予濮 西安电子科技大学计算机网络与信息安全国家教育部重点实验室(710071) email:lih_dong@ 摘 要：本文研究了广义自缩序列生成器在已知明文攻击下的安全性，得到如下结果：设已 知线性组合向量G ，k长的密钥流片段以及线性反馈移位寄存器 （LFSR）的长度为n ，则为找 到 LFSR 的正确初始状态 及反馈逻 辑需要测 试 O(nk- 1) 次 ，其中k ，n 满足关系 式： (k-1)(n+1-log2(k-1))≥2n 。但是当线性组合向量G满足一定的已知特性时（例如第一类和第四 类广义自缩序列生成器中的线性组合向量），测试的复杂度将与所获得的密钥流片段中所含 的比特“0”的个数密切相关。 关键词：序列密码 广义自缩序列 m 序列 1．引言 在新一代的移动通信系统中，巨大的信息吞吐量需要简单快速的信息加密体制，如序列 密码和分组密码。传统的序列密码生成效率低且易受攻击，近年来出现的一些新型序列密码 虽具有良好的伪随机性，但生成方式又过于复杂，而自缩序列[1,2.3]却具有结构简单，均衡， 等一系列密码学优点，因而倍受关注。最近，我们于文[4]引入了广义自缩序列的概念，定义 如下： 定义 1 设a=a a a …是GF(2)上的n级m序列，另设GF(2)上的n维向量G= （g ,g ,…,g ）， 0 1 2 0 1 n-1 定义序列v=v v v …使得v =g a +g a + …+g a ，对于k=0,1,2,…，如a =1 ，则输出v ，否 0 1 2 k 0 k 1 k-1 n- 1 k-n+1 k k 则放弃输出。如此得到的输出序列b=b b b …，记为b(v)或b(G) ，称其为基于m序列a 的广义 0 1 2 自缩序列。 广义自缩序列生成器的结构仍然非常简单只需要一个m序列发生器及一个线性组合器， 并具有一系列的良好特性[4-12]。本文，我们将对广义自缩序列安全性进行分析，主要是线性 组合向量G 已暴露（m序列未暴露）时丢失部分密钥的安全强度。 以下我们总设已知LFSR 的长度n ，线性组合向量 G 以及k 长的密钥流片段b ，我们的 目标是要找到与该密钥流片段b 相对应的 LFSR 的初始状态，即广义自缩序列生成器的密 钥。 定义 2[4] 设{t : j 0,1,2, L}满足0 ≤t t t L; a 1对每个j 成立；a =0 对 j 0 1 2 tj t 每个t ∉{t : j 0,1,2, L}成立。称t 为序列b 的第j 个输出时刻，称 {t ,t ,t , L} 为序列b 的输 j j 0 1 2 出时间序列。 引理 1：将 r 个相同元素分配到 n 个不同的匣子里，有 Cr 种分配方法。 r n + −1 引理 2 ：设向m序列a 的k个独立的 “1”串 （其中共包含u个“1”）中间添加 “0 ”串，则 我们至多可添加k-1 个“0 ”串，其中至多共包含(k-1)n-(k-1)log2(k-1)-1 个“0 ”，且u，n满足 关系式：(k-1)n-(k-1)log2(k-1)-1+u≥2