线性反馈与对偶移位寄存器的功能实现.doc

线性反馈与对偶移位寄存器的功能实现
091234 谢锦仪
一、实验目的：
该实验为验证性实验。
通过本实验，使学生切实理解线性反馈移位寄存器与对偶移位寄存器的工作原理，学会编写和运用两种移位寄存器“进动一拍”的程序，培养和锻炼学生对于密码学中各种基本“构造”的编程实现能力。

二、实验内容及完成情况：
1. 分别写出实现n-LFSR与 n-DSR（n为正整数）进动一拍的程序（旨在能“由寄存器的一个状态算出紧接着的下一个状态”），要求：寄存器状态的各分量自然地与相应数据存储区的各比特位一一对应，不允许仅1个状态分量就占据1个存储单元（字节、字或双字等）。

2. 基于上述程序完成以下工作：选定一个8次联接多项式，这时检验状态存储区自然形成的1字节二进制数是否与前出现者相同就可判定状态是否开始成圈（即进入周期性重复），据此编制
i) 分别计算LFSR与DSR在一个给定初态（由外部响应给出）下输出序列
ii) 求出LFSR或DSR之一状态图的程序。

三、实验要求：
1．对较低次数的联接多项式，程序计算结果须与手工推算一致；
2．抓图显示“输出序列”与“状态图”（附页），不能出现明显错误。

四、结果：
1、LFSR

2、DSR

五、实验体会：
这次实验有很大的难度，尤其是对其中移位的操作难倒了不少人。并且看了老师给的程序后理解不是很深，看了很长时间后才有所了解，后来经过复习以前的课程对LFSR和DSR有了更深层次的理解之后终于明白了程序改如何编写了。
总的来说，这次实验不但是我对LFSR和DSR两种古典密码有了很好的理解，而且也是我对C语言编程中的位运算也熟悉了不少，相信在以后的工作中会给我带来很大的便利。

六、思考题：
为什么“检验状态存储区自然形成的二进制数是否与前出现者相同就可判定状态是否开始成圈（即进入周期性重复）”？
答：因为每个状态都有唯一的前一拍状态，对应的所有的状态应该是一一连接的（不一定都在一条线上）。所以如果出现了2个一样的状态，那么后续的对应状态一定相同。

附录
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

unsigned char *DSR_go(unsigned char *pzt,unsigned char *pjg,unsigned char count)
{
unsigned char t;int a=128,b;
t=pzt[0];
pzt[0]=pzt[0]<<1;
t<<=(8-count);
b=t&a;
if(b==128)
pzt[0]^=pjg[0];
return(pzt);
}

unsigned char *LFSR_go(unsigned char *pzt,unsigned char *pjg)
{
unsigned char t=0;
int c=0,i,m=0;t=pzt[0]<<1;
for(i=0;i<8;i++)
{
if(((pjg[0]<<i)&128)==128)
{
if(((pzt[0]<<i)&128)==128)
m++;
}
}
if(m%2==0)
t=t;
else
t|=1;
pzt[0]=t;
return (pzt);
}

void d_to_b(unsigned char n ,unsigned char count)
{
int a=128,b,i;
n<<=(8-count);
for(i=0;i<count;i++)
{
b=n&a;
if (b==128)
printf("1");
else
printf("0");
n=n<<1;
}
}
b_to_d(int n)
{
int a=0,i;
char c;
for (i=0;i<n+1;i++)
{c=getchar();
if(c=='1')
{a=a<<1;a++;}
else a=a<<1;
}
return a;
}

void main()
{int count,choose_c=0,a=1,i,k;int b;
unsigned char *p,pzt[32],pjg[32],xchg1,tihuan[100];
printf("请输入n值:\n");
scanf("%d",&count);
for(i=1;i<count+1;i++)
{ choose_c=choose_c+a;
a*=2;
}
printf("请输入初始状态：\n");
pzt[0]=b_to_d(count);
xchg1=pzt[0];
printf("请输入计算反馈函数（为反馈函数倒序）：例f=x1+x2+x5,输入10011\n");
pjg[0]=b_to_d(count);
printf("请选择LFSR或者DSR,LFSR为1,DSR为2:\n");
scanf("%d",&b);
if(b==1)
{ printf("各状态如下：\n");
d_to_b(xchg1 , count);
tihuan[0]=xchg1;
i=0;
do
{ i++;
printf("---");
p=LFSR_go(pzt,pjg);
pzt[0]=*p&(unsigned char)choose_c;
tihuan[i]=pzt[0];
d_to_b(pzt[0] , count);
}
while(pzt[0]!=xchg1);
printf("\nLFSR周期为：%d\n",i);
printf("LFSR的0,1序列为：\n");
choose_c=1;
for(k=1;k<count;k++)
choose_c=choose_c<<1;
for(k=0;k<i;k++)
if(tihuan[k]>=choose_c) printf("1");
else printf("0");
}
else if(b==2)
{
printf("各状态如下：\n");
d_to_b(xchg1 , count);
tihuan[0]=xchg1;
i=0;
do
{ i++;
printf("---");
p=DSR_go(pzt,pjg,count);
pzt[0]=*p&(unsigned char)choose_c;
tihuan[i]=pzt[0];
d_to_b(pzt[0] , count);
}
while(pzt[0]!=xchg1);
printf("\nDSR周期为：%d\n",i);
printf("DSR的序列为：\n");
choose_c=1;
for(k=1;k<count;k++)
choose_c=choose_c<<1;
for(k=0;k<i;k++)
if(tihuan[k]>=choose_c) printf("1");
else printf("0");
}
}