西电《网络空间安全数学基础》 网安数基

西电网络空间安全数学基础《第一章：线性系统与矩阵乘法》

讲在前面

大二下学期网络与信息安全学院开展了网络空间安全数学基础（网安数基）
个人认为这个对于只有概率论基础的普通大二学生是比较困难的，如果只听一遍基本消化不了，甚至我经常听着听着就听不懂了。
课程分两位老师讲解，第一位老师讲课很是有趣，并且在带着学生学知识，但是我说实话，有一些比较困难的的东西有点难听懂。并且老师对于考试的考察也比较灵活。
第二位老师讲课也是比较有趣的，但是第二部分的内容我感觉整体上是难度高于第一部分的，而且课程的知识量变多了，也挺难的，基本都是自己自学了，好的一点是由于比较困难，加上有ppt，考的内容比较固定，考试会相对轻松一点。
在此写出本课程的总结，方便后续的复习，并且帮助在这门课上迷茫的同学们。

平时作业建议： 本课程是没有教材的，也没有练习题和标准答案。所以需要自己在网上搜索相关的资料，并且根据出题人的意图对题目进行猜测，自己平常经一些练习。并且由于本课程的存在一下比较难的积分计算，所以需要大家了解一些积分公式。

备考建议： 平时作业认真做，老师上课讲过的题目都复习一遍，包括一些证明，不懂就背下来记忆，千万不要有侥幸心理（我就吃了这个亏），考试会出现比较多的作业题，这些复习到了基本就是80+的卷面分，剩下的就是曾老师的变式题，需要对知识了解的深刻一些。

个人总结：
本课程学到的东西确实是不少的，对于一些方法的实现，在编程的作业中有所感受，但是我认为这门课的考核是需要一些思考的。没有书，没有习题，没有答案，这个是一个比较开发的方式在锻炼我们的开放性思维，但是考试是有标准答案的，这个时候考生就不知道应该怎么办了。
一个建议，如果老师考察的知识变得灵活起来，建议老师可以讲解习题，或者可以把答案发给学生供学生思考，供学生参考。不然，建议老师考察的知识就是平时讲的习题，因为对于掌握知识比较少的学生是比较痛苦的一件事。

章节脉络

课程一共分为2个部分，每个部分6次课

1. 线性系统与矩阵乘法
2. 矩阵的分解
3. 范数、距离与相似度
4. 最优化入门
5. 概率+矩阵
6. pagerank的两个数学解释
7. bloom过滤器
8. 贝叶斯推理
9. 信息熵与决策树
10. 差分隐私
11. 网络传播
12. 随机过程

第一章 线性系统与矩阵乘法

概述

本章节主要讲了下关于矩阵乘法的的几何意义：伸缩和旋转。
并讲解了线性反馈移位寄存器，实现的原理，代码，求解其输出（用到了关于矩阵乘法的思想）。
重要考点：线性反馈移位寄存器的原理以及求解其输出；
ps：现在不懂不着急，下面将详细讲解，看完后在思考，便可以理解。

一、线性反馈移位寄存器（LFSR）的引入

1.1 移位寄存器：

移位寄存器（Shift Register，SR）曾在《数字电路与设计基础》，是指有若干个寄存器排成一行，每个寄存器中都存储着一个二进制数（0或1）。移位寄存器每次把最右端（末端）的数字输出，然后整体向右移动一位。
图片：

图1： D触发器构成的移位寄存器

假设一个5位移位寄存器中存储着数据10110，则不断移位、输出的效果如图所示：

图2：输出效果示意图

1.2 反馈移位寄存器：

在移位寄存器向右移位一位以后，左边就会空出一位（如上图所示），这时如果采用一个反馈函数，以寄存器中已有的某些序列作为反馈函数的输入，在函数中经过一定的运算后，将反馈函数输出的结果填充到移位寄存器的最左端，那么这样的移位寄存器就会有源源不断的输出。通俗来讲，就是通过已知的 r₁ 到r_n-1，可以对这些数字通过定义一定的运算，从而得到r_n，下面将会有具体实例讲到。这样的，拥有反馈函数的移位寄存器称为反馈移位寄存器（Feedback Shift Register，FSR）

1.3 线性反馈移位寄存器：

如果反馈移位寄存器的反馈函数是线性函数（即只进行简单线性运算的函数），那么这种寄存器就被称为线性反馈移位寄存器（Linear Feedback Shift Register，LFSR）。
图3 线性反馈移位寄存器示意图

二、线性反馈移位寄存器（LFSR）

2.1、LFSR的反馈函数：

LFSR的反馈函数就是简单地对移位寄存器中的某些位进行异或，并将异或的结果填充到LFSR的最左端，如图所示。对于LFSR中每一位的数据，可以参与异或，也可以不参与异或。其中，我们把参与异或的位称为抽头。

图4 笔记
如c_i表示第i位是否是抽头，如果是，则c_i=1，表示该位将参与运算；如果不是，则 c_i=0，表示该位将不参与运算。上式表示了LFSR的一种递推关系，在这个式子中，可以明显看出，ci将抽头位选出并留下来参与运算，并且将不是抽头的位剔除掉。

2.2、LFSR的级数：

我们通常把LFSR中的寄存器个数称为LFSR的级数。
状态的概念：一个LFSR寄存器中当前存储的序列被称为一个状态。在LFSR输出一位，由反馈函数补充一位后，LFSR就移动到了下一个状态。

2.3 运用矩阵的形式表达

可以看出，通过使用矩阵的可以实现状态的变换

三 实例分析：以三级线性反馈移位寄存器为例

图5 分析案例示意图

四 实战演练：编程实现130级的线性反馈移位寄存器

题目：基本要求：80分

实现130级的线性反馈移位寄存器

不使用大数库提供的数据结构

至少给出一组测试向量，即给定初始寄存器的值，给定反馈多项式，移位129次以后，连续的32比特是多少

按照自己的理解给出实验报告，要求原理部分手写截图放入报告，代码部分给出核心代码并注释，测试向量列表展示
附加要求：20分
采用西电学报的论文模板10分
使用大数库提供的数据结构，和自己写的代码进行效率比较10分（本人尚未理解使用大数库是在哪里使用，欢迎大家提供思路）

4.1.问题的转化：

移位129位后，在该状态下，再移位32比特。
等价于向右移动161位，其中a₁₃₀——a₁₆₁，即为所求的连续的32位比特。

4.2.代码的实现：

结合老师上课讲的伪代码可以更好的理解代码

图六 核心代码：反馈多项式部分

4.3 测试用例：

移位寄存器：1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1

反馈多项式：1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 0 1

具体的实现代码：

#include<stdio.h>
#define weishu 130 										//移位寄存器的寄存器个数 :130 
#define yiweishu 161 									//希望移位寄存器移位的数目 ：161 
int main()
{
//	int weishu,yiweishu;
//	printf("请输入移位寄存器的级数:");
//	scanf("%d",&weishu);
//	printf("请输入移位数:");
//	scanf("%d",&yiweishu);
	
	int a[weishu+yiweishu]={0};									//寄存器中初始的130位  +移位129位 

	int x[weishu]={0};											//描述反馈函数表达式 寄存器130位 
	int function1,function2,temp;								//均作为临时变量 
	printf("请输入130级移位寄存器的数值 a1到a130："); 
	for(int i=0;i<weishu;i++)  									//寄存器130位 
	{
		scanf("%d",&a[i]);										//输入 
	}
	printf("请输入反馈多项式的系数：c1到c130") ;
	for(int i=0;i<weishu;i++)									//寄存器130位 
	{
		scanf("%d",&x[i]);
	 } 
 
	int first_cnt;												//先找到第一个系数不是零的项,用来记录第一个不是零的项在第几位 
	for(int i=0;i<weishu;i++)
	{
		if(x[i]!=0)
		{
			first_cnt=i; 
			break;
		}
	 } 
	 int a_left=0; 												//开始时最右侧的项 
	 for(int i=0;i<yiweishu;i++)								//一共需要移位161次 
	 {	
 
	 	temp=a[first_cnt+a_left];								//找到在该状态下第一个系数不是零的项 								
	 	for(int j=a_left;j<a_left+weishu;j++)					//反馈多项式部分：关于反馈函数所有抽头的异或 
	 	{
	 		if(j!=first_cnt+a_left && x[j-a_left]!=0 ) 			//此时的j不是第一个系数不为零的项 //  表示此时a[j]的系数想不为零 
			
	 		{
	 			temp=temp^a[j];									//	进行异或 
			 }
		 }
		 a[a_left+weishu]=temp;									//将反馈函数的结果填到最左端 
		 a_left++;												//该状态下的第一位  下标加一 ，也就是向右面移一位 

	  } 

//	for(int i=0;i<weishu+yiweishu;i++)							
//	{
//		printf("%d %d\n",i+1,a[i]);
//		
//	}
	printf("\n移位129次后，线性反馈移位寄存器中的值（从左往右即a259到a130）\n");
	for(int i=258;i>=129;i--)
	{
		printf("%d",a[i]);
		
	 } 
//向右移动129位后，在移位32比特
//	等价于向右移动161位，其中输出连续的32比特就是a130-a161，所以连续的32位比特为

//	for(int i=129;i<161;i++)
//	{
//		printf("%d",a[i]);
//	
//	 } 
	printf("\n再次经过32位移位后连续输出的32比特（从左往右即a161到a130）：") ; 
	for(int i=160;i>=129;i--)
	{
		printf("%d",a[i]);
	 } 

	return 0;
 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

五 求解线性反馈移位寄存器的输出（考试重点考察）

5.1 反馈多项式已知，通过观测连续的输出，可以得到Y₀

5.2反馈多项式未知

反馈多项式未知，那么我们就求解得到反馈多项式，从而转换为情形一，进而求解

线性反馈多项式的状态输出我们是可以通过观测得到的，那么我们就可以构造上面的4个等式，并且四个等式中的未知量有4个，这样我们转换为情形1了。

参考文献：

[1] url：https://zhuanlan.zhihu.com/p/366067972
[2] url: https://blog.csdn.net/Drifter_Galaxy/article/details/107618275