文档介绍：序列密码的编码层次及几个序列密码算法
量子密码研究室
王滨
2005年4月6日
1
序列密码的编码层次
一、编码层次
前馈逻辑、时序逻辑、筛选逻辑和控制逻辑
(一)前馈逻辑
主要由初始乱源发生器(线性或非线性的反馈移位寄存器等),抽头的变换以及前馈函数三部分组成。
2
1、初始乱源发生器:为前馈函数f(x)提供具有良好统计特性的输入序列。在应用中,以线性反馈移位寄存器作为初始乱源发生器是最常见的,给一个n级本原线性移存器注入n比特初态,便可以产生周期为2n-1的二元序列, “代价”是非常低的,
但低廉的代价,同时也导致了序列比特间“强烈的”线性制约关系, 对于n级本原移存器只需截收到2n个连续信号就可求出唯一解。因此它不能直接作为密钥(乱数)输出使用。利用非线性前馈函数f(x)就可以“破坏”这种线性制约性,起到提高序列线性复杂度的作用。
3
2、抽头变换:
3、前馈函数:
r 个抽头l1,l2,…,lr作为前馈函数f(x)的输入,它可以由密钥因素来控制,起到增加密钥变化量的作用,它与前馈函数一起构成一个前馈网络。
前馈函数f(x)是一个非线性布尔函数或多输出的非线性布尔函数,它一方面“破坏”输入序列连续比特的线性制约关系,即提高输入序列的线性复杂度;另一方面, f(x)又不能破坏输入序列良好的伪随机特性,同时还要考虑到输入信息在输出序列中的泄漏。
非线性变换应满足:能将LFSR序列的良好统计特性传递给所生成的密钥序列,使输出序列的周期足够大;输出序列能抗线性逼近,且不能泄露LFSR的结构和状态。
4
(二)、时序逻辑
时序逻辑是一种有记忆变换,使输出不仅与当前时刻的输入因素有关,而且与以前时刻的输入和输出因素有关,从而实现输入信息的纵向扩散。
1、累加器变换
输入为: ;输出为:
累加器变换定义为: ;且
可以看出:
5
2、实数和序列()
设输入序列为a、b,定义实数和序列z如下:
其中s称为进位序列,假设。
则
实数和序列实现数据的由低位向高位的扩散,即高位不仅受当前输入的影响,而且受以前输入的影响。
6
M
3、调换存储变换
调换存储区M包含个存储单元,a是输入序列,b是输出序列,c是k路控制序列。
工作过程如下:
在第i时刻,由序列c的k比特确定M中存储单元的地址,从该地址中读出的数据即为输出,然后把a中相应的值置入该存储单元中。
7
(三)、筛选逻辑
筛选逻辑的作用就是破坏二元序列比特间的跟随关系,增加算法的复杂性。
自控采样:就是控制序列对其自身进行采样,当它的某一位为1时,走两步输出;为0时,走一步输出。
例如:控制序列为:111110001101110**********...
得到的输出序列为:1 1 1 001 01 1 1 1 0001 01...
8
(四)、控制逻辑
作用:控制算法中的各个编码环节,例如控制源移存器的不等距采样、抽头位置的选取、前馈函数的选择等。控制逻辑本身还起到了增加密钥变化量,提高算法复杂性的作用。
9
模拟的序列密码算法
注:所谓n阶拉丁方阵,是一个仅含有n个不同元素的方阵,且方阵的每行和每列正好包括每个元素各一次。
前馈函数f(x)
调换存储
控制移存器
抽头
10