一种伪随机序列产生方法及加密方法
专利名称：一种伪随机序列产生方法及加密方法
技术领域：
本发明涉及信息安全技术领域，具体地说，本发明提供了一种输出比特等价保熵的伪随机序列产生方法及加密方法。
背景技术：
伪随机序列源的选择与设计是序列密码设计中的一个核心内容。以移位寄存器为基础的序列源设计，大多考虑二元域GF(2)上的m序列或一般有限域GF(2n)上线性递归序列。然而，这类序列的比特之间具有明显的、多重的线性关系，这使得以其为序列源的序列密码容易受到相关攻击。另外，线性递归的方式和简单的非线性改造手段也使代数攻击建立低次方程成为可能。因此，以GF(2n)上的线性递归序列作为序列源，将导致S-盒设计的困难性和复杂性，很难达到序列密码体制简洁、安全的设计目标。
设p是2或奇素数，对于环Z/(pe)上线性递归序列，因为p-adic高权位序列由低权位序列和递归运算过程中产生的复杂进位序列复合而成，从而天然蕴含丰富的非线性结构，具备诸多优良的伪随机性质。Z/(pe)上本原序列，即极大周期的线性递归序列，其最高权位序列的密码性质更为优良，例如，保熵性，丰富的非线性结构，优良的元素分布特性和复杂度特性等。但是作为序列源，它仍然存在如下不足之处。
(1)周期特性不理想 Z/(pe)上n次本原序列的周期为pe-1·(pn-1)，参见文献[2]。参数e稍大时(例如，e＝8，16或32)，周期pe-1·(pn-1)远远小于pe·n，两者比例不足p-(e-1)(n-1)+1，这导致提高序列周期需要耗费的寄存器资源增长太快，远大于周期增长的幅度。例如，对于Z/(2e)上的情形，假设序列周期需要达到264。当e＝8时，寄存器的规模必须达到456比特；当e＝16时，寄存器规模需要784比特；当e＝32时，寄存器规模为1056比特；因此，Z/(2e)上本原序列的周期特性很不理想。
(2)权位序列不具备代数等价性 考察Z/(pe)上线性递归序列的进位序列的运算特性，可以看出，对于该序列的权位序列而言，权位越高，序列的密码性质越好，例如，随着权位的增长，权位序列的周期按照p的指数级方式增长。因此，若采用Z/(pe)上本原序列作为序列源，必须消除权位序列之间的这种不等价性。然而，掩盖序列源弱点的做法总是令人担忧的，这就类似与基于GF(2n)上的线性反馈移位寄存器的序列密码体制试图掩盖源序列的线性本质总是难以成功。
除以上两点外，对于奇素数p，因为模pe运算实现的困难性，Z/(pe)上线性递归序列的实现效率远远满足不了现实需要。
基于以上分析，本发明的发明人认为Z/(pe)上本原序列不适合用作序列密码设计的序列源。因此，需要寻求新型序列源的产生方法，既能保持Z/(pe)上本原序列的优良特性，又能避免其不足之处。
发明内容
本发明提供的一种产生伪随机序列的方法，包括 从取值空间{1，2，...，2e-1}获取元素，其中e是一个大于2的正整数；基于所获取的元素及反馈多项式采用线性递归方式生成序列，所述反馈多项式是Z/(2e-1)上的本原多项式，所生成序列的初态中至少有一个元素a与2e-1互素。
根据该方法可输出比特等价保熵的伪随机序列，它的任一比特权位包含整体序列所有信息，同时序列的信息在所有比特位置均匀分布，没有给序列攻击者留下可利用的序列差异特征。另外，该序列源蕴含丰富的非线性结构，周期增长迅速，选取合适的参数，使得序列周期和序列互异圈个数达到平衡，同时满足大周期和丰富互异圈两方面的需求。该方法在各种软件、硬件平台易于快速实现。这些优良性质将大大降低算法设计中对于序列源加工改造工作的困难性和复杂性，容易达到序列密码体制简洁、安全的设计目标。
本发明提供的一种构建流密码体制的方法，包括 采用前述方法构造的具有比特等价保熵性的伪随机序列源作为核心序列源。
按照如下方式加工序列源进而输出密钥字序列在序列源的每拍状态中，抽取固定抽头位置的取值为选择数；根据选择数提取参与密钥字合成的变化抽头位置；变化抽头的取值结合重要的固定抽头的取值综合合成两个待选数和一个控制数；最后由控制数各比特位置的0，1取值情况分别选择两个待选数对应位置的取值组合成为该拍的密钥字。
在密钥字合成过程中，采用元素异或运算消除核心序列源取值空间少一个元素的现象，使得密钥输出序列分布均衡。
体制的初始状态由密钥Key和公开随机的初始向量IV混合扩展而成，初始化运转过程中输出的密钥字与序列递归输出的元素异或综合重新置入状态最后一个位置参与下一拍运算。
进一步，作为前述序列产生方法和流密码体制构建方法的应用实例，本发明提供一个流密码体制，命名为“飞环”(“Flying-Ring”)。它是一个简洁、安全、高效的序列密码算法，在软件、硬件各种平台都易高速实现，可为数据安全提供高效的安全服务。
具体实施例方式 本发明将提供一种输出序列具有比特等价保熵性的伪随机序列产生方法，同时提供以此方法生成序列为核心序列源的一种流密码体制的构建方法，并设计了一个具体的流密码体制，命名为“飞环”(“Flying-Ring”)。
(一)序列产生方法 称本发明提供序列产生方法得到的序列为“环Z/(2e-1)上本原序列”，具体产生方法如下 (1)取参数e和n都是大于或等于2的正整数； (2)选取多项式f(x)＝xn-(cn-1xn-1+cn-2xn-2+...+c0)，ci∈{0，1，...，2e-2}，i＝0，1，...，n-1，满足如下性质对于整数2e-1的任意大于1的素数方幂因子pw，其中p是素数，f(x)(mod pw)的最小正周期为T＝pw-1·(pn-1)，即，整数T是使得xT≡1(modf(x)，pw)成立的最小正整数。
(3)取初态向量(a0，a1，...，an-1)，其中ai∈Z/(2e-1)，i＝0，1，...，n-1，至少有一个ai满足如下性质整数ai和2e-1互素(最大公因子为1)； 或者说，对于整数2e-1的任意素数因子p，ai≠0(mod p)，即p不是ai的因子。
(4)按照如下递归方式输出序列a＝(a0，a1，...，an-1，an，an+1，...)＝(at)t≥0，an+k＝an-1+k·cn-1+an-2+k·cn-2+...+a0+k·c0(mod 2e-1)，k＝0，1，2，....序列a即为Z/(2e-1)上由f(x)生成的一条本原序列。所有由f(x)生成的本原序列之集记为G′(f(x)，2e-1)，其中序列同由f(x)产生，不同的只是在生成过程中选取不同的序列初态(a0，a1，...，an-1)。
上述方法得到的Z/(2e-1)上本原序列集G′(f(x)，2e-1)可以用作流密码的序列源。
(二)序列源的性质分析 任给Z/(2e-1)上本原多项式f(x)，集合G′(f(x)，2e-1)就是本发明提供方法产生的序列源之一。该类序列源达到了如下三方面的设计目标， 充分保留Z/(pe)上本原序列的保熵性质和优良的非线性性质； 尽量避免Z/(pe)上本原序列的不足之处周期特性不理想，序列权位不等价； 容易实现序列源的快速递归生成。
下面详细分析该类序列源的密码性质。
(2.1)具备比特等价保熵性 对于元素α∈Z/(2e-1)，存在唯一的2-adic分解 α＝α0+α1·2+...+αe-1·2e-1，其中αi∈{0，1}，i＝0，1，...，e-1.称元素αi为α的第i比特权位。
同理，对于Z/(2e-1)上序列a，有如下唯一2-adic分解 a＝a0+a1·2+...+ae-1·2e-1，其中ai是0，1序列，i＝0，1，...，e-1.称序列ai是a的第i比特权位序列，简称为第i权位序列。
对于a∈G′(f(x)，2e-1)，2·a(mod 2e-1)仍然属于G′(f(x)，2e-1)；又因为Z/(2e-1)中元素的2倍运算相当于左循环移位1比特，所以任给i≠j∈{0，1，...，e-1}，序列a的第i权位序列等同与G′(f(x)，2e-1)中另外一条序列的第j权位序列。这就表明G′(f(x)，2e-1)中序列的各个比特权位序列是相互等价的(周期相同，相互之间的地位和作用也相同)，权位序列之间具备代数等价性。
另外，当本原序列的次数n≥2时，可以证明，任给a，b∈G′(f(x)，2e-1)，都有a＝b当且仅当a(mod 2)＝b(mod 2)。该结论表明G′(f(x)，2e-1)中序列的第0比特权位序列蕴含原始序列的所有信息，即环Z/(2e-1)上本原序列的第0比特权位是保熵的。再结合比特权位序列的相互等价性，可知，本原序列的任一比特权位都是保熵的。
具有比特等价保熵性，是本发明序列产生方法所得到序列源-环Z/(2e-1)上本原序列，区别其它常规(多比特输出)序列源的最重要的本质特征。该性质保证序列的信息在所有比特位置分布均匀，没有给序列攻击者留下可利用的序列差异特征。
(2.2)拥有理想的周期特性 周期特性是评价序列源的一个重要指标。如果序列的周期增长太慢，为提高序列周期，将要耗费过多的寄存器资源。一个好的序列源，应该在寄存器资源有限增长的条件下实现周期的快速增长。
因为2e-1通常含有较大素因子，环Z/(2e-1)上本原序列的周期特性非常好。设
其中{p0，p1，...，pw-1}是2e-1互异素因子之集，ei≥1。
Z/(2e-1)上n次本原多项式的周期为 其中符号“Lcm”表示最小公倍数。G′(f(x)，2e-1)中序列都是本原序列，它们的周期都等于per(f(x)，2e-1)。当参数e的取值稍大时(例如e＝8，16，32)，随着次数n的增大，周期增长非常迅速。
表1对比列出Z/(2321)和Z/(232)上本原序列周期随次数变化情况。由表1可以看出Z/(232-1)上本原序列的周期增长速度相对要快得多。假设序列周期需要达到264，采用Z/(232)上序列，次数n的取值最小为33，寄存器的规模必须达到1056＝33×32比特，采用Z/(2321)上本原序列，次数n的取值为3，寄存器的规模只需要96＝3×32比特。采用Z/(2321)上本原序列作为序列源需要耗费的资源要小得多。
表1 (2.3)序列周期和序列互异圈个数容易达到平衡 序列互异圈的个数也是评价一个序列源的重要指标。两条不同的序列如果平移等价，它们则被认为同属一个序列圈。同属一个序列圈的序列，相对比较容易从一条序列获得另外一条序列。所以一个序列源的设计通常需要它具有足够多的序列互异圈，使得不同序列同圈的概率很小。
在固定寄存器规模的条件下，序列的周期和互异圈的个数是两个相互对立的参数。对于Z/(2e-1)上本原序列而言，基于不同的次数n，两者对立的程度也有所变化。设计者容易取得合适的n，同时满足大周期和丰富互异圈两方面的需求。
表2给出Z/(232-1)上本原序列的周期和互异圈个数的取值情况。可以看出参数n取6，12，16时，序列的周期已经足够大，同时互异圈的个数分别超过261，276，265，对应序列同圈的概率分别小于2-61，2-76，2-65，同圈的可能性已经足够小。
表2 (2.4)天然蕴含丰富的非线性结构 由于在递归运算的过程中，每条比特权位序列是由其它权位序列和大量的多层进位结果复合而成，单个权位序列的生成和其它e-1条比特权位序列的任意一条直接相关。
(2.5)具备优良的伪随机特性 伪随机测试平台验证，环Z/(2e-1)上本原序列的伪随机特性优良，元素分布均衡，复杂度特性良好，线性复杂度谱在1/2线附近随机摆动。
(2.6)序列的资源非常丰富 设
其中{p0，p1，..，pw-1}是2e-1互异素因子之集，ei≥1。环
上n次本原多项式的个数为
其中
(*)表示欧拉函数。环Z/(2e-1)上n次本原多项式的个数为 表3和表4分别给出Z/(2321)和Z/(216-1)上本原多项式的周期和本原多项式数量的对比取值情况。本原多项式周期和对应本原序列的周期取值相同，前面分析可知，周期增长非常迅速，在次数n的取值很小时，周期取值就已经非常巨大；表3和表4数据显示，本原多项式的数量和周期取值相当。环Z/(2e-1)上拥有非常丰富的本原多项式资源，而每个本原多项式对应一个不同参数的序列源模型，因此，环Z/(2e-1)上本原序列的资源非常丰富。
表3 表4 (2.7)易于软件、硬件平台的快速实现 首先，序列递归生成过程中没有复杂的模运算，模2e-1运算实际上可由2次加法完成。
其次，通过选择低权重的多项式系数，序列生成过程的乘法运算可以用少量的循环移位和加法替代实现。
另外，选取模2e-1的代表元集合为{1，2，...，2e-1}，可以快速实现Z/(2e-1)上元素的模运算。模运算结果只要落入e比特表示的范围内，模运算就结束了。若采用常用的代表元集合{0，1，...，2e-2}，模运算结果落入e比特表示的范围内，我们还需要判断结果是否是2e-1，若是，需要将其置0，增加了额外的运算开销。
(2.8)序列取值空间少一个元素不影响序列源的正常使用 Z/(2e-1)上本原序列的取值空间比e比特元素集合少一个元素，这种情况不影响该序列作为序列源的正常使用。通过简单的元素异或运算就可以消除取值空间少一个元素的痕迹。
取模2e-1的代表元集合为J＝{1，2，...，2e-1}，考察可重复集合 中元素分布情况。记x在W中出现的个数为N(x)，简单计算后，可得 N(0)＝2e-1，N(t)＝2e-2，1≤t≤2e-1. 由此可知，异或运算很好地解决了序列取值空间少一个元素的问题。至于取模2e-1其他的代表元集合，可得到几乎一样的结论。
(2.9)权位序列可能存在的平移等价性不影响序列源的正常使用 对于参数e的某些取值，Z/(2e-1)上同一条本原序列的不同权位之间存在平移等价关系，但是因为序列的周期特性很理想，使得平移跨度非常大，远远大于单次加密/解密需要的序列片段长度，这种平移等价关系不影响序列源的正常使用。
例如，模数232-1的性质决定了Z/(2321)上本原序列的某些权位之间具有如下半周期平移等价性。设a＝a0+a1·2+...+a31·231是Z/(232-1)上的一条由f(x)生成的本原序列，周期为T，则由于xT/2≡216(mod f(x))在Z/(2321)上成立，故对于任意的t≥0有 at+T/2≡216·at(mod 232-1). 上式意味着序列a的比特权位之间存在如下半周期平移等价关系 xT/2ai＝ai+16，i＝0，1，...，15. 因为Z/(232-1)上本原序列的周期特性很理想，例如，如次数为16时，周期超过了2446，在实际序列源的使用过程中，单次加密/解密需要的序列片段长度不可能达到周期的量级。权位序列半周期的平移等价性不影响序列源的正常使用。
(三)序列源的使用说明 基于以上对于序列源的性质分析，下面给出序列源的使用注意事项。
参照当前计算能力，当前密码安全强度通常设定为128比特或256比特，单次加密/解密报文长度上限通常设定为264。依据这两个设定，下面讨论序列源的实施过程中的注意情况。(即使将来当前计算能力提高了，安全要求强度增加了，同样可以根据如下原则设置相应的参数。) (3.1)参数e和n的选取 参数e的选择参照计算平台的整数运算的字长设定。例如，当前主流计算机的字长为32比特，选取参数e＝32，可以充分利用32比特整数运算的特性，快速实现模232-1运算。另外，对于专用硬件平台，字长可以根据需求设定。此时可以选择参数e＝29，它可以避免出现同一条序列不同权位的平移等价情况。
参数n的选择，通常使得e·n的取值是安全强度参数的2倍左右。同时兼顾本原序列互异圈是否足够多。
当前主流计算机的字长为32比特，选取参数e＝32。依据当前安全强度，选取参数n＝12或16。
参数n取12或16时，本原序列的周期分别大于2307.9954和2446.8395；序列的周期足够大，同时本原序列互异圈也足够多，分别达到276.0045和265.1604，不同序列同圈的概率分别小于2-76.0045和2-65.1604。
因为Z/(232-1)上本原序列的周期特性很理想，在实际序列源的使用过程中，单次加密/解密需要的序列片段长度不可能达到周期的量级。权位序列半周期的平移等价性不影响序列源的正常使用。设周期为T，容易证明，对于间隔长度在T/215之内的子序列之间不存在倍数关系。由此，可以认为，作为序列源，Z/(232-1)上本原序列在实际使用过程中输出序列几乎不会出现反复，不同的输出序列之间几乎不存在简单的倍数关系。
(3.2)模2e-1的代表元集选取 建议取模2e-1的代表元集合为{1，2，...，2e-1}。
采用该代表元集，可以快速实现Z/(2e-1)上元素的模运算。模运算结果只要落入e比特表示的范围内，模运算就结束了。若采用常用的代表元集合{0，1，...，2e-2}，模运算结果落入e比特表示的范围内，我们还需要判断结果是否是2e-1，若是，需要将其置0，增加了额外的运算开销。
(3.3)反馈多项式的选取 设f(x)＝xn-(cn-1xn-1+cn-2xn-2+...+c0)是Z/(232-1)上本原多项式，可以根据以下基本原则先确定反馈抽头位置(1)反馈抽头位置之间的间隔长度尽量不同；(2)每一拍产生的新元素必须参与下一拍的反馈计算。
确定好反馈抽头位置后，可以按照以下原则确定具体的反馈多项式系数。(1)为了尽可能地提高序列源的递归生成速度，根据环Z/(232-1)上运算的特点，应选用具有低汉明重量的系数；(2)为了使反馈运算达到较好的混乱效果，非零系数的2进制展开中所有1的位置两两不同，间隔尽量不同；(3)在算法速度许可的范围内，尽量提高抽头系数cn-1，cn-2，...，c0的总重量，并且这个重量一定为偶数。
例如，取n＝16，选取抽头个数为5，选取抽头位置为15，13，10，4，0，对应的反馈多项式的形式为 f(x)＝x16-(c15·x15+c13·x13+c10·x10+c4·x4+c0)； 再按照系数确定原则，最终可以选取反馈多项式为 f(x)＝x16-((211+219)·x15+28·x13+228·x10+218·x4+(20+22+221)). (3.4)序列源不退化设定 设f(x)是Z/(2e-1)上本原多项式，G(f(x)，2e-1)中某条序列是本原序列的充要条件为该序列初态中存在某个元素，它与2e-1互素。在实际的使用过程中，可以设定初态某个位置为一个与2e-1互素的常数。
(3.5)消除源序列(序列源取值)空间少一个元素的影响 Z/(2e-1)上本原序列的取值空间比e比特元素集合少一个元素，在实际的使用过程中，可以采用简单的元素异或运算消除该现象。
(3.6)模2e-1乘法运算的替代实现 例如，设0≤a＜232，2k·a(mod 232-1)可以用左循环移位实现，即 2k·a(mod 232-1)＝(a＜＜＜k)。
可以选择系数ci权重较小的多项式 f(x)＝xn-(cn-1xn-1+cn-2xn-2+...+c0)， 使得序列递归反馈时，ci·a(mod 232-1)的计算过程可以用简单的左循环移位运算和加法运算替代完成。
对于e的其他取值，也可以同样处理，尤其是在硬件芯片实现环境中，更是如此。
(四)序列源在密码中的应用——“飞环”流密码体制 “飞环”流密码体制采用前述序列方法生成核心序列源，是一个安全、高效的流密码算法。下面详细讨论。
(4.1)有关“飞环”流密码体制中序列源选择和运算说明 参照前述序列源的使用说明，选择序列源，即选择序列的反馈多项式。“飞环”流密码体制采用如下Z/(232-1)上本原多项式 f(x)＝x16-((211+219)·x15+28·x13+228·x10+218·x4+(5+221)). G′(f(x)，232-1)就是“飞环”流密码体制的序列源，其中序列a＝(a0，a1，...)∈G′(f(x)，232-1)，满足如下递归关系 a16+k＝(211+219)·a15+k+28·a13+k +228·a10+k+218·a4+k+(5+221)·ak(mod 232-1)，k≥0. 运算N(mod 232-1)的实现取{1，2，...，232-1}为mod 232-1的剩余代表集，从而将0视为232-1。计算N(mod 232-1)只需将N按4字节为单位进行分组，将各部分进行累加，和结果中超出232的进位部分重新加到低位部分即可，最后小于232的和值即为mod 232-1的运算结果。例如，N＝N0+N1·232，N0+N1＝N2+c·232，其中0≤N0，N1，N2＜232，c为0或1，则N(mod 232-1)＝N2+c。
需要说明的是，“飞环”流密码体制中的mod 232-1运算全部按这种方式实现。
下面先给出“飞环”流密码体制中出现的运算符号说明。
符号
表示2进制对位模2加运算。
符号“||”表示数据的级联，每个参与级联的数都是8比特整数。例如，(a||b||c||d)＝a·224+b·216+c·28+d。
符号“＜＜＜”表示32比特整数的左循环移位运算。例如
(注头部是0x的数据是16进制无符号整数。) (4.2)“飞环”流密码体制的密钥装入算法 参数128比特的初始密钥K和128比特的初始向量IV。
任务将K和IV扩展为512比特的“飞环”算法工作向量(S
，S[1]，...，S[15])的初态，其中每个S[i]都是32比特长的字。
密钥装入流程如下 (4.2.1)将密钥和初始向量按字节分组，即 K＝(k0，k1，...，k15)，IV＝(iv0，iv1，...，iv15)， 其中ki和ivi都是8比特字节。
(4.2.2)选取常数D＝(d0，d1，...，d14)，要求每个di都是8比特常数，2进制展开中0、1分布均匀。下面给出D的一种选择 0x96，0x9A，0x1B，0xA5，0x4B，0x27，0x2D，0xA6， 0xAD，0x36，0x39，0x4E，0x78，0x8D，0x9C. (4.2.3)密钥扩展和填充 对于i＝0，1，...，14，计算 其中k-1＝k15，iv-1＝iv15。
设置32比特常数S[15]，它与232-1互素，2进制展开中0、1分布均匀。
S[15]＝0x4D34D349＝1295307593. (4.3)“飞环”流密码体制的工作过程 共有3个过程，先执行算法初始化过程，随后执行密钥字输出过程，最后执行算法加密/解密过程。
(4.3.1)算法初始化过程，包括如下步骤 (4.3.1.1)按照密钥装入算法设计，将K和IV进行扩展并填入 (S
，S[1]，...，S[15]). (4.3.1.2)按照如下方式运行15拍，每拍顺序计算获得选择数B 其中0≤A0，A1＜216， 其中0≤bi≤15，i＝0，1，2，3. 计算密钥字Z 完成一次序列反馈递归运算 顺序执行S[i]＝S[i+1]，i＝0，1，2，...，15。
(4.3.1.3)按照如下方式运行8拍，每拍完成一次序列独立递归运算 S[16]＝(211+219)·S15+28·S13+228·S10 +218·S4+(5+221)·S0(mod 232-1)， 顺序执行S[i]＝S[i+1]，i＝0，1，2，...，15。
(4.3.2)密钥字输出过程 重复执行如下过程，每次输出一个32比特的密钥字Z，每拍顺序执行如下步骤。
(4.3.2.1)获得选择数B 其中0≤A0，A1＜216， 其中0≤Bi≤15，i＝0，1，2，3. (4.3.2.2)输出密钥字Z (4.3.2.3)完成一次序列独立递归运算 S[16]＝(211+219)·S15+28·S13+228·S10+218·S4+(5+221)·S0(mod 232-1). 顺序执行S[i]＝S[i+1]，i＝0，1，2，...，15。
(4.3.3)加解密过程 执行前面两过程得到密钥字序列流Z＝(Z0，Z1，Z2，...)，每个Zi都是32比特字。
(4.3.3.1)加密过程 将明文转换为32比特字序列M＝(M0，M1，M2，...)，每个Mi都是32比特字。顺序执行 得到密文序列C＝(C0，C1，C2，....)。
(4.3.3.2)解密过程 已知密文序列C＝(C0，C1，C2，...)，每个Ci都是32比特字。顺序执行 得到明文序列M＝(M0，M1，M2，...)。
显然，本领域的技术人员应该明白，上述的本发明的各步骤可以用通用的计算装置来实现，它们可以集中在单个的计算装置上，或者分布在多个计算装置所组成的网络上，可选地，它们可以用计算装置可执行的程序代码来实现，从而，可以将它们存储在存储装置中由计算装置来执行，或者将它们分别制作成各个集成电路模块，或者将它们中的多个步骤制作成单个集成电路模块来实现。这样，本发明不限制于任何特定的硬件和软件结合。
以上所述仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内所作的任何修改、等同替换、改进等，均包含在本发明的保护范围内。
权利要求
1、一种伪随机序列产生方法，其特征在于，包括
从取值空间{1，2，...，2e-1}获取元素，其中e是一个大于2的正整数；
基于所获取的元素及反馈多项式采用线性递归方式生成序列，所述反馈多项式是Z/(2e-1)上的本原多项式，所生成序列的初态中至少有一个元素a与2e-1互素。
2、如权利要求1所述的方法，其特征在于，模2e-1采用{1，2，...，2e-1}代表集，该方法中包括模2e-1运算的替换实现，具体包括
对目标按e比特为单位进行分组，将各分组进行累加，和结果中超出e比特的进位部分重新加到低位部分，得到小于2e的和值为mod 2e-1的运算结果。
3、如权利要求1所述的方法，其特征在于，所述反馈多项式为f(x)＝xn-(cn-1xn-1+cn-2xn-2+...+c0)，在保证其本原的前提下，用于生成序列选择反馈多项式应遵循如下原则
(1)反馈抽头位置(ci非0的位置)之间的间隔长度尽量不同；
(2)序列生成过程中每一拍产生的新元素必须参与下一拍的反馈计算；
(3)选用具有低汉明重量的系数ci，将序列递归生成过程所需的复杂的模乘法运算转化为少量的循环移位和加法运算；
(4)非零系数的2进制展开中所有1的位置两两不同，间隔尽量不同；
(5)在算法速度许可的范围内，提高抽头系数cn-1，cn-2，...，c0的总重量，并且该重量为偶数。
4、一种构建流密码体制的方法，其特征在于，包括
采用权利要求1所述方法构造的具有比特等价保熵性的伪随机序列源作为核心序列源；
按照如下方式加工序列源进而输出密钥字序列
在序列源的每拍状态中，抽取固定抽头位置的取值为选择数；
根据选择数提取参与密钥字合成的变化抽头位置；
变化抽头的取值结合重要的固定抽头的取值综合合成两个待选数和一个控制数；
由控制数各比特位置的0，1取值情况分别选择两个待选数对应位置的取值组合成为该拍的密钥字。
5、如权利要求4所述的方法，其特征在于，采用元素异或运算消除核心序列源取值空间少一个元素的现象，使得密钥输出序列分布均衡。
6、如权利要求4所述的方法，其特征在于，每拍输出一个32比特密钥字，体制的加解密采用对位模2加运算。
7、如权利要求4所述的方法，其特征在于，初始状态由密钥Key和公开随机的初始向量IV混合扩展而成，初始化运转过程中输出的密钥字与序列递归输出的元素异或综合重新置入状态最后一个位置参与下一拍运算。
全文摘要
本发明公开了一种伪随机序列产生方法，包括从取值空间{1，2，...，2e-1}获取元素，e为大于2的正整数；基于所述元素及Z/(2e-1)上的本原多项式采用线性递归方式生成序列，该序列的初态中至少有一个元素与2e-1互素。得到具有比特等价保熵的伪随机序列，该序列蕴含丰富的非线性结构，周期增长迅速，可使得序列周期和序列互异圈个数达到平衡，可大大降低算法设计中对于序列源加工的复杂性，使得序列密码体制简洁、安全。本发明还提供一种构建流密码体制的方法，采用前述方法构造的具有比特等价保熵性的伪随机序列作为核心序列源；在密钥字合成过程中，采用元素异或运算使得密钥输出序列分布均衡，提供一个简洁、安全、高效的序列密码算法，为数据安全提供保障。
文档编号G09C1/00GK101674180SQ20081014950
公开日2010年3月17日 申请日期2008年9月10日 优先权日2008年9月10日
发明者朱宣勇, 戚文峰, 甜 田 申请人:中国人民解放军信息工程大学
技术领域：
本发明涉及信息安全技术领域，具体地说，本发明提供了一种输出比特等价保熵的伪随机序列产生方法及加密方法。
背景技术：
伪随机序列源的选择与设计是序列密码设计中的一个核心内容。以移位寄存器为基础的序列源设计，大多考虑二元域GF(2)上的m序列或一般有限域GF(2n)上线性递归序列。然而，这类序列的比特之间具有明显的、多重的线性关系，这使得以其为序列源的序列密码容易受到相关攻击。另外，线性递归的方式和简单的非线性改造手段也使代数攻击建立低次方程成为可能。因此，以GF(2n)上的线性递归序列作为序列源，将导致S-盒设计的困难性和复杂性，很难达到序列密码体制简洁、安全的设计目标。
设p是2或奇素数，对于环Z/(pe)上线性递归序列，因为p-adic高权位序列由低权位序列和递归运算过程中产生的复杂进位序列复合而成，从而天然蕴含丰富的非线性结构，具备诸多优良的伪随机性质。Z/(pe)上本原序列，即极大周期的线性递归序列，其最高权位序列的密码性质更为优良，例如，保熵性，丰富的非线性结构，优良的元素分布特性和复杂度特性等。但是作为序列源，它仍然存在如下不足之处。
(1)周期特性不理想 Z/(pe)上n次本原序列的周期为pe-1·(pn-1)，参见文献[2]。参数e稍大时(例如，e＝8，16或32)，周期pe-1·(pn-1)远远小于pe·n，两者比例不足p-(e-1)(n-1)+1，这导致提高序列周期需要耗费的寄存器资源增长太快，远大于周期增长的幅度。例如，对于Z/(2e)上的情形，假设序列周期需要达到264。当e＝8时，寄存器的规模必须达到456比特；当e＝16时，寄存器规模需要784比特；当e＝32时，寄存器规模为1056比特；因此，Z/(2e)上本原序列的周期特性很不理想。
(2)权位序列不具备代数等价性 考察Z/(pe)上线性递归序列的进位序列的运算特性，可以看出，对于该序列的权位序列而言，权位越高，序列的密码性质越好，例如，随着权位的增长，权位序列的周期按照p的指数级方式增长。因此，若采用Z/(pe)上本原序列作为序列源，必须消除权位序列之间的这种不等价性。然而，掩盖序列源弱点的做法总是令人担忧的，这就类似与基于GF(2n)上的线性反馈移位寄存器的序列密码体制试图掩盖源序列的线性本质总是难以成功。
除以上两点外，对于奇素数p，因为模pe运算实现的困难性，Z/(pe)上线性递归序列的实现效率远远满足不了现实需要。
基于以上分析，本发明的发明人认为Z/(pe)上本原序列不适合用作序列密码设计的序列源。因此，需要寻求新型序列源的产生方法，既能保持Z/(pe)上本原序列的优良特性，又能避免其不足之处。
发明内容
本发明提供的一种产生伪随机序列的方法，包括 从取值空间{1，2，...，2e-1}获取元素，其中e是一个大于2的正整数；基于所获取的元素及反馈多项式采用线性递归方式生成序列，所述反馈多项式是Z/(2e-1)上的本原多项式，所生成序列的初态中至少有一个元素a与2e-1互素。
根据该方法可输出比特等价保熵的伪随机序列，它的任一比特权位包含整体序列所有信息，同时序列的信息在所有比特位置均匀分布，没有给序列攻击者留下可利用的序列差异特征。另外，该序列源蕴含丰富的非线性结构，周期增长迅速，选取合适的参数，使得序列周期和序列互异圈个数达到平衡，同时满足大周期和丰富互异圈两方面的需求。该方法在各种软件、硬件平台易于快速实现。这些优良性质将大大降低算法设计中对于序列源加工改造工作的困难性和复杂性，容易达到序列密码体制简洁、安全的设计目标。
本发明提供的一种构建流密码体制的方法，包括 采用前述方法构造的具有比特等价保熵性的伪随机序列源作为核心序列源。
按照如下方式加工序列源进而输出密钥字序列在序列源的每拍状态中，抽取固定抽头位置的取值为选择数；根据选择数提取参与密钥字合成的变化抽头位置；变化抽头的取值结合重要的固定抽头的取值综合合成两个待选数和一个控制数；最后由控制数各比特位置的0，1取值情况分别选择两个待选数对应位置的取值组合成为该拍的密钥字。
在密钥字合成过程中，采用元素异或运算消除核心序列源取值空间少一个元素的现象，使得密钥输出序列分布均衡。
体制的初始状态由密钥Key和公开随机的初始向量IV混合扩展而成，初始化运转过程中输出的密钥字与序列递归输出的元素异或综合重新置入状态最后一个位置参与下一拍运算。
进一步，作为前述序列产生方法和流密码体制构建方法的应用实例，本发明提供一个流密码体制，命名为“飞环”(“Flying-Ring”)。它是一个简洁、安全、高效的序列密码算法，在软件、硬件各种平台都易高速实现，可为数据安全提供高效的安全服务。
具体实施例方式 本发明将提供一种输出序列具有比特等价保熵性的伪随机序列产生方法，同时提供以此方法生成序列为核心序列源的一种流密码体制的构建方法，并设计了一个具体的流密码体制，命名为“飞环”(“Flying-Ring”)。
(一)序列产生方法 称本发明提供序列产生方法得到的序列为“环Z/(2e-1)上本原序列”，具体产生方法如下 (1)取参数e和n都是大于或等于2的正整数； (2)选取多项式f(x)＝xn-(cn-1xn-1+cn-2xn-2+...+c0)，ci∈{0，1，...，2e-2}，i＝0，1，...，n-1，满足如下性质对于整数2e-1的任意大于1的素数方幂因子pw，其中p是素数，f(x)(mod pw)的最小正周期为T＝pw-1·(pn-1)，即，整数T是使得xT≡1(modf(x)，pw)成立的最小正整数。
(3)取初态向量(a0，a1，...，an-1)，其中ai∈Z/(2e-1)，i＝0，1，...，n-1，至少有一个ai满足如下性质整数ai和2e-1互素(最大公因子为1)； 或者说，对于整数2e-1的任意素数因子p，ai≠0(mod p)，即p不是ai的因子。
(4)按照如下递归方式输出序列a＝(a0，a1，...，an-1，an，an+1，...)＝(at)t≥0，an+k＝an-1+k·cn-1+an-2+k·cn-2+...+a0+k·c0(mod 2e-1)，k＝0，1，2，....序列a即为Z/(2e-1)上由f(x)生成的一条本原序列。所有由f(x)生成的本原序列之集记为G′(f(x)，2e-1)，其中序列同由f(x)产生，不同的只是在生成过程中选取不同的序列初态(a0，a1，...，an-1)。
上述方法得到的Z/(2e-1)上本原序列集G′(f(x)，2e-1)可以用作流密码的序列源。
(二)序列源的性质分析 任给Z/(2e-1)上本原多项式f(x)，集合G′(f(x)，2e-1)就是本发明提供方法产生的序列源之一。该类序列源达到了如下三方面的设计目标， 充分保留Z/(pe)上本原序列的保熵性质和优良的非线性性质； 尽量避免Z/(pe)上本原序列的不足之处周期特性不理想，序列权位不等价； 容易实现序列源的快速递归生成。
下面详细分析该类序列源的密码性质。
(2.1)具备比特等价保熵性 对于元素α∈Z/(2e-1)，存在唯一的2-adic分解 α＝α0+α1·2+...+αe-1·2e-1，其中αi∈{0，1}，i＝0，1，...，e-1.称元素αi为α的第i比特权位。
同理，对于Z/(2e-1)上序列a，有如下唯一2-adic分解 a＝a0+a1·2+...+ae-1·2e-1，其中ai是0，1序列，i＝0，1，...，e-1.称序列ai是a的第i比特权位序列，简称为第i权位序列。
对于a∈G′(f(x)，2e-1)，2·a(mod 2e-1)仍然属于G′(f(x)，2e-1)；又因为Z/(2e-1)中元素的2倍运算相当于左循环移位1比特，所以任给i≠j∈{0，1，...，e-1}，序列a的第i权位序列等同与G′(f(x)，2e-1)中另外一条序列的第j权位序列。这就表明G′(f(x)，2e-1)中序列的各个比特权位序列是相互等价的(周期相同，相互之间的地位和作用也相同)，权位序列之间具备代数等价性。
另外，当本原序列的次数n≥2时，可以证明，任给a，b∈G′(f(x)，2e-1)，都有a＝b当且仅当a(mod 2)＝b(mod 2)。该结论表明G′(f(x)，2e-1)中序列的第0比特权位序列蕴含原始序列的所有信息，即环Z/(2e-1)上本原序列的第0比特权位是保熵的。再结合比特权位序列的相互等价性，可知，本原序列的任一比特权位都是保熵的。
具有比特等价保熵性，是本发明序列产生方法所得到序列源-环Z/(2e-1)上本原序列，区别其它常规(多比特输出)序列源的最重要的本质特征。该性质保证序列的信息在所有比特位置分布均匀，没有给序列攻击者留下可利用的序列差异特征。
(2.2)拥有理想的周期特性 周期特性是评价序列源的一个重要指标。如果序列的周期增长太慢，为提高序列周期，将要耗费过多的寄存器资源。一个好的序列源，应该在寄存器资源有限增长的条件下实现周期的快速增长。
因为2e-1通常含有较大素因子，环Z/(2e-1)上本原序列的周期特性非常好。设
其中{p0，p1，...，pw-1}是2e-1互异素因子之集，ei≥1。
Z/(2e-1)上n次本原多项式的周期为 其中符号“Lcm”表示最小公倍数。G′(f(x)，2e-1)中序列都是本原序列，它们的周期都等于per(f(x)，2e-1)。当参数e的取值稍大时(例如e＝8，16，32)，随着次数n的增大，周期增长非常迅速。
表1对比列出Z/(2321)和Z/(232)上本原序列周期随次数变化情况。由表1可以看出Z/(232-1)上本原序列的周期增长速度相对要快得多。假设序列周期需要达到264，采用Z/(232)上序列，次数n的取值最小为33，寄存器的规模必须达到1056＝33×32比特，采用Z/(2321)上本原序列，次数n的取值为3，寄存器的规模只需要96＝3×32比特。采用Z/(2321)上本原序列作为序列源需要耗费的资源要小得多。
表1 (2.3)序列周期和序列互异圈个数容易达到平衡 序列互异圈的个数也是评价一个序列源的重要指标。两条不同的序列如果平移等价，它们则被认为同属一个序列圈。同属一个序列圈的序列，相对比较容易从一条序列获得另外一条序列。所以一个序列源的设计通常需要它具有足够多的序列互异圈，使得不同序列同圈的概率很小。
在固定寄存器规模的条件下，序列的周期和互异圈的个数是两个相互对立的参数。对于Z/(2e-1)上本原序列而言，基于不同的次数n，两者对立的程度也有所变化。设计者容易取得合适的n，同时满足大周期和丰富互异圈两方面的需求。
表2给出Z/(232-1)上本原序列的周期和互异圈个数的取值情况。可以看出参数n取6，12，16时，序列的周期已经足够大，同时互异圈的个数分别超过261，276，265，对应序列同圈的概率分别小于2-61，2-76，2-65，同圈的可能性已经足够小。
表2 (2.4)天然蕴含丰富的非线性结构 由于在递归运算的过程中，每条比特权位序列是由其它权位序列和大量的多层进位结果复合而成，单个权位序列的生成和其它e-1条比特权位序列的任意一条直接相关。
(2.5)具备优良的伪随机特性 伪随机测试平台验证，环Z/(2e-1)上本原序列的伪随机特性优良，元素分布均衡，复杂度特性良好，线性复杂度谱在1/2线附近随机摆动。
(2.6)序列的资源非常丰富 设
其中{p0，p1，..，pw-1}是2e-1互异素因子之集，ei≥1。环
上n次本原多项式的个数为
其中
(*)表示欧拉函数。环Z/(2e-1)上n次本原多项式的个数为 表3和表4分别给出Z/(2321)和Z/(216-1)上本原多项式的周期和本原多项式数量的对比取值情况。本原多项式周期和对应本原序列的周期取值相同，前面分析可知，周期增长非常迅速，在次数n的取值很小时，周期取值就已经非常巨大；表3和表4数据显示，本原多项式的数量和周期取值相当。环Z/(2e-1)上拥有非常丰富的本原多项式资源，而每个本原多项式对应一个不同参数的序列源模型，因此，环Z/(2e-1)上本原序列的资源非常丰富。
表3 表4 (2.7)易于软件、硬件平台的快速实现 首先，序列递归生成过程中没有复杂的模运算，模2e-1运算实际上可由2次加法完成。
其次，通过选择低权重的多项式系数，序列生成过程的乘法运算可以用少量的循环移位和加法替代实现。
另外，选取模2e-1的代表元集合为{1，2，...，2e-1}，可以快速实现Z/(2e-1)上元素的模运算。模运算结果只要落入e比特表示的范围内，模运算就结束了。若采用常用的代表元集合{0，1，...，2e-2}，模运算结果落入e比特表示的范围内，我们还需要判断结果是否是2e-1，若是，需要将其置0，增加了额外的运算开销。
(2.8)序列取值空间少一个元素不影响序列源的正常使用 Z/(2e-1)上本原序列的取值空间比e比特元素集合少一个元素，这种情况不影响该序列作为序列源的正常使用。通过简单的元素异或运算就可以消除取值空间少一个元素的痕迹。
取模2e-1的代表元集合为J＝{1，2，...，2e-1}，考察可重复集合 中元素分布情况。记x在W中出现的个数为N(x)，简单计算后，可得 N(0)＝2e-1，N(t)＝2e-2，1≤t≤2e-1. 由此可知，异或运算很好地解决了序列取值空间少一个元素的问题。至于取模2e-1其他的代表元集合，可得到几乎一样的结论。
(2.9)权位序列可能存在的平移等价性不影响序列源的正常使用 对于参数e的某些取值，Z/(2e-1)上同一条本原序列的不同权位之间存在平移等价关系，但是因为序列的周期特性很理想，使得平移跨度非常大，远远大于单次加密/解密需要的序列片段长度，这种平移等价关系不影响序列源的正常使用。
例如，模数232-1的性质决定了Z/(2321)上本原序列的某些权位之间具有如下半周期平移等价性。设a＝a0+a1·2+...+a31·231是Z/(232-1)上的一条由f(x)生成的本原序列，周期为T，则由于xT/2≡216(mod f(x))在Z/(2321)上成立，故对于任意的t≥0有 at+T/2≡216·at(mod 232-1). 上式意味着序列a的比特权位之间存在如下半周期平移等价关系 xT/2ai＝ai+16，i＝0，1，...，15. 因为Z/(232-1)上本原序列的周期特性很理想，例如，如次数为16时，周期超过了2446，在实际序列源的使用过程中，单次加密/解密需要的序列片段长度不可能达到周期的量级。权位序列半周期的平移等价性不影响序列源的正常使用。
(三)序列源的使用说明 基于以上对于序列源的性质分析，下面给出序列源的使用注意事项。
参照当前计算能力，当前密码安全强度通常设定为128比特或256比特，单次加密/解密报文长度上限通常设定为264。依据这两个设定，下面讨论序列源的实施过程中的注意情况。(即使将来当前计算能力提高了，安全要求强度增加了，同样可以根据如下原则设置相应的参数。) (3.1)参数e和n的选取 参数e的选择参照计算平台的整数运算的字长设定。例如，当前主流计算机的字长为32比特，选取参数e＝32，可以充分利用32比特整数运算的特性，快速实现模232-1运算。另外，对于专用硬件平台，字长可以根据需求设定。此时可以选择参数e＝29，它可以避免出现同一条序列不同权位的平移等价情况。
参数n的选择，通常使得e·n的取值是安全强度参数的2倍左右。同时兼顾本原序列互异圈是否足够多。
当前主流计算机的字长为32比特，选取参数e＝32。依据当前安全强度，选取参数n＝12或16。
参数n取12或16时，本原序列的周期分别大于2307.9954和2446.8395；序列的周期足够大，同时本原序列互异圈也足够多，分别达到276.0045和265.1604，不同序列同圈的概率分别小于2-76.0045和2-65.1604。
因为Z/(232-1)上本原序列的周期特性很理想，在实际序列源的使用过程中，单次加密/解密需要的序列片段长度不可能达到周期的量级。权位序列半周期的平移等价性不影响序列源的正常使用。设周期为T，容易证明，对于间隔长度在T/215之内的子序列之间不存在倍数关系。由此，可以认为，作为序列源，Z/(232-1)上本原序列在实际使用过程中输出序列几乎不会出现反复，不同的输出序列之间几乎不存在简单的倍数关系。
(3.2)模2e-1的代表元集选取 建议取模2e-1的代表元集合为{1，2，...，2e-1}。
采用该代表元集，可以快速实现Z/(2e-1)上元素的模运算。模运算结果只要落入e比特表示的范围内，模运算就结束了。若采用常用的代表元集合{0，1，...，2e-2}，模运算结果落入e比特表示的范围内，我们还需要判断结果是否是2e-1，若是，需要将其置0，增加了额外的运算开销。
(3.3)反馈多项式的选取 设f(x)＝xn-(cn-1xn-1+cn-2xn-2+...+c0)是Z/(232-1)上本原多项式，可以根据以下基本原则先确定反馈抽头位置(1)反馈抽头位置之间的间隔长度尽量不同；(2)每一拍产生的新元素必须参与下一拍的反馈计算。
确定好反馈抽头位置后，可以按照以下原则确定具体的反馈多项式系数。(1)为了尽可能地提高序列源的递归生成速度，根据环Z/(232-1)上运算的特点，应选用具有低汉明重量的系数；(2)为了使反馈运算达到较好的混乱效果，非零系数的2进制展开中所有1的位置两两不同，间隔尽量不同；(3)在算法速度许可的范围内，尽量提高抽头系数cn-1，cn-2，...，c0的总重量，并且这个重量一定为偶数。
例如，取n＝16，选取抽头个数为5，选取抽头位置为15，13，10，4，0，对应的反馈多项式的形式为 f(x)＝x16-(c15·x15+c13·x13+c10·x10+c4·x4+c0)； 再按照系数确定原则，最终可以选取反馈多项式为 f(x)＝x16-((211+219)·x15+28·x13+228·x10+218·x4+(20+22+221)). (3.4)序列源不退化设定 设f(x)是Z/(2e-1)上本原多项式，G(f(x)，2e-1)中某条序列是本原序列的充要条件为该序列初态中存在某个元素，它与2e-1互素。在实际的使用过程中，可以设定初态某个位置为一个与2e-1互素的常数。
(3.5)消除源序列(序列源取值)空间少一个元素的影响 Z/(2e-1)上本原序列的取值空间比e比特元素集合少一个元素，在实际的使用过程中，可以采用简单的元素异或运算消除该现象。
(3.6)模2e-1乘法运算的替代实现 例如，设0≤a＜232，2k·a(mod 232-1)可以用左循环移位实现，即 2k·a(mod 232-1)＝(a＜＜＜k)。
可以选择系数ci权重较小的多项式 f(x)＝xn-(cn-1xn-1+cn-2xn-2+...+c0)， 使得序列递归反馈时，ci·a(mod 232-1)的计算过程可以用简单的左循环移位运算和加法运算替代完成。
对于e的其他取值，也可以同样处理，尤其是在硬件芯片实现环境中，更是如此。
(四)序列源在密码中的应用——“飞环”流密码体制 “飞环”流密码体制采用前述序列方法生成核心序列源，是一个安全、高效的流密码算法。下面详细讨论。
(4.1)有关“飞环”流密码体制中序列源选择和运算说明 参照前述序列源的使用说明，选择序列源，即选择序列的反馈多项式。“飞环”流密码体制采用如下Z/(232-1)上本原多项式 f(x)＝x16-((211+219)·x15+28·x13+228·x10+218·x4+(5+221)). G′(f(x)，232-1)就是“飞环”流密码体制的序列源，其中序列a＝(a0，a1，...)∈G′(f(x)，232-1)，满足如下递归关系 a16+k＝(211+219)·a15+k+28·a13+k +228·a10+k+218·a4+k+(5+221)·ak(mod 232-1)，k≥0. 运算N(mod 232-1)的实现取{1，2，...，232-1}为mod 232-1的剩余代表集，从而将0视为232-1。计算N(mod 232-1)只需将N按4字节为单位进行分组，将各部分进行累加，和结果中超出232的进位部分重新加到低位部分即可，最后小于232的和值即为mod 232-1的运算结果。例如，N＝N0+N1·232，N0+N1＝N2+c·232，其中0≤N0，N1，N2＜232，c为0或1，则N(mod 232-1)＝N2+c。
需要说明的是，“飞环”流密码体制中的mod 232-1运算全部按这种方式实现。
下面先给出“飞环”流密码体制中出现的运算符号说明。
符号
表示2进制对位模2加运算。
符号“||”表示数据的级联，每个参与级联的数都是8比特整数。例如，(a||b||c||d)＝a·224+b·216+c·28+d。
符号“＜＜＜”表示32比特整数的左循环移位运算。例如
(注头部是0x的数据是16进制无符号整数。) (4.2)“飞环”流密码体制的密钥装入算法 参数128比特的初始密钥K和128比特的初始向量IV。
任务将K和IV扩展为512比特的“飞环”算法工作向量(S
，S[1]，...，S[15])的初态，其中每个S[i]都是32比特长的字。
密钥装入流程如下 (4.2.1)将密钥和初始向量按字节分组，即 K＝(k0，k1，...，k15)，IV＝(iv0，iv1，...，iv15)， 其中ki和ivi都是8比特字节。
(4.2.2)选取常数D＝(d0，d1，...，d14)，要求每个di都是8比特常数，2进制展开中0、1分布均匀。下面给出D的一种选择 0x96，0x9A，0x1B，0xA5，0x4B，0x27，0x2D，0xA6， 0xAD，0x36，0x39，0x4E，0x78，0x8D，0x9C. (4.2.3)密钥扩展和填充 对于i＝0，1，...，14，计算 其中k-1＝k15，iv-1＝iv15。
设置32比特常数S[15]，它与232-1互素，2进制展开中0、1分布均匀。
S[15]＝0x4D34D349＝1295307593. (4.3)“飞环”流密码体制的工作过程 共有3个过程，先执行算法初始化过程，随后执行密钥字输出过程，最后执行算法加密/解密过程。
(4.3.1)算法初始化过程，包括如下步骤 (4.3.1.1)按照密钥装入算法设计，将K和IV进行扩展并填入 (S
，S[1]，...，S[15]). (4.3.1.2)按照如下方式运行15拍，每拍顺序计算获得选择数B 其中0≤A0，A1＜216， 其中0≤bi≤15，i＝0，1，2，3. 计算密钥字Z 完成一次序列反馈递归运算 顺序执行S[i]＝S[i+1]，i＝0，1，2，...，15。
(4.3.1.3)按照如下方式运行8拍，每拍完成一次序列独立递归运算 S[16]＝(211+219)·S15+28·S13+228·S10 +218·S4+(5+221)·S0(mod 232-1)， 顺序执行S[i]＝S[i+1]，i＝0，1，2，...，15。
(4.3.2)密钥字输出过程 重复执行如下过程，每次输出一个32比特的密钥字Z，每拍顺序执行如下步骤。
(4.3.2.1)获得选择数B 其中0≤A0，A1＜216， 其中0≤Bi≤15，i＝0，1，2，3. (4.3.2.2)输出密钥字Z (4.3.2.3)完成一次序列独立递归运算 S[16]＝(211+219)·S15+28·S13+228·S10+218·S4+(5+221)·S0(mod 232-1). 顺序执行S[i]＝S[i+1]，i＝0，1，2，...，15。
(4.3.3)加解密过程 执行前面两过程得到密钥字序列流Z＝(Z0，Z1，Z2，...)，每个Zi都是32比特字。
(4.3.3.1)加密过程 将明文转换为32比特字序列M＝(M0，M1，M2，...)，每个Mi都是32比特字。顺序执行 得到密文序列C＝(C0，C1，C2，....)。
(4.3.3.2)解密过程 已知密文序列C＝(C0，C1，C2，...)，每个Ci都是32比特字。顺序执行 得到明文序列M＝(M0，M1，M2，...)。
显然，本领域的技术人员应该明白，上述的本发明的各步骤可以用通用的计算装置来实现，它们可以集中在单个的计算装置上，或者分布在多个计算装置所组成的网络上，可选地，它们可以用计算装置可执行的程序代码来实现，从而，可以将它们存储在存储装置中由计算装置来执行，或者将它们分别制作成各个集成电路模块，或者将它们中的多个步骤制作成单个集成电路模块来实现。这样，本发明不限制于任何特定的硬件和软件结合。
以上所述仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内所作的任何修改、等同替换、改进等，均包含在本发明的保护范围内。
权利要求
1、一种伪随机序列产生方法，其特征在于，包括
从取值空间{1，2，...，2e-1}获取元素，其中e是一个大于2的正整数；
基于所获取的元素及反馈多项式采用线性递归方式生成序列，所述反馈多项式是Z/(2e-1)上的本原多项式，所生成序列的初态中至少有一个元素a与2e-1互素。
2、如权利要求1所述的方法，其特征在于，模2e-1采用{1，2，...，2e-1}代表集，该方法中包括模2e-1运算的替换实现，具体包括
对目标按e比特为单位进行分组，将各分组进行累加，和结果中超出e比特的进位部分重新加到低位部分，得到小于2e的和值为mod 2e-1的运算结果。
3、如权利要求1所述的方法，其特征在于，所述反馈多项式为f(x)＝xn-(cn-1xn-1+cn-2xn-2+...+c0)，在保证其本原的前提下，用于生成序列选择反馈多项式应遵循如下原则
(1)反馈抽头位置(ci非0的位置)之间的间隔长度尽量不同；
(2)序列生成过程中每一拍产生的新元素必须参与下一拍的反馈计算；
(3)选用具有低汉明重量的系数ci，将序列递归生成过程所需的复杂的模乘法运算转化为少量的循环移位和加法运算；
(4)非零系数的2进制展开中所有1的位置两两不同，间隔尽量不同；
(5)在算法速度许可的范围内，提高抽头系数cn-1，cn-2，...，c0的总重量，并且该重量为偶数。
4、一种构建流密码体制的方法，其特征在于，包括
采用权利要求1所述方法构造的具有比特等价保熵性的伪随机序列源作为核心序列源；
按照如下方式加工序列源进而输出密钥字序列
在序列源的每拍状态中，抽取固定抽头位置的取值为选择数；
根据选择数提取参与密钥字合成的变化抽头位置；
变化抽头的取值结合重要的固定抽头的取值综合合成两个待选数和一个控制数；
由控制数各比特位置的0，1取值情况分别选择两个待选数对应位置的取值组合成为该拍的密钥字。
5、如权利要求4所述的方法，其特征在于，采用元素异或运算消除核心序列源取值空间少一个元素的现象，使得密钥输出序列分布均衡。
6、如权利要求4所述的方法，其特征在于，每拍输出一个32比特密钥字，体制的加解密采用对位模2加运算。
7、如权利要求4所述的方法，其特征在于，初始状态由密钥Key和公开随机的初始向量IV混合扩展而成，初始化运转过程中输出的密钥字与序列递归输出的元素异或综合重新置入状态最后一个位置参与下一拍运算。
全文摘要
本发明公开了一种伪随机序列产生方法，包括从取值空间{1，2，...，2e-1}获取元素，e为大于2的正整数；基于所述元素及Z/(2e-1)上的本原多项式采用线性递归方式生成序列，该序列的初态中至少有一个元素与2e-1互素。得到具有比特等价保熵的伪随机序列，该序列蕴含丰富的非线性结构，周期增长迅速，可使得序列周期和序列互异圈个数达到平衡，可大大降低算法设计中对于序列源加工的复杂性，使得序列密码体制简洁、安全。本发明还提供一种构建流密码体制的方法，采用前述方法构造的具有比特等价保熵性的伪随机序列作为核心序列源；在密钥字合成过程中，采用元素异或运算使得密钥输出序列分布均衡，提供一个简洁、安全、高效的序列密码算法，为数据安全提供保障。
文档编号G09C1/00GK101674180SQ20081014950
公开日2010年3月17日 申请日期2008年9月10日 优先权日2008年9月10日
发明者朱宣勇, 戚文峰, 甜 田 申请人:中国人民解放军信息工程大学
最新回复(0)