密码学——序列密码序列线性复杂度 B-M算法例题演示-EW帮帮网

前言

B-M算法

文字描述

图片描述

前言

由于课本企图用世界上最精炼的文字描述这个算法的高深思想
以及我搜出来的CSDN博客，全部都完全不是人的只会CtrlC+CtrlV般的抄课本描述
而且且加上密码学本身的冷门性
导致没有一篇现有博客我看懂了B-M算法

还好B站讲解视频甚至也不多，但是好在有一个视频讲的很好。
在此感谢这个老哥，同时为了把密码学精神发扬光大（为了别再吃信息安全这坨，尤其是当你的老师根本不会讲课的时候），我希望我写下的东西能让大家渡劫。

附上参考文献：BM算法 15min速通_第二章序列密码3_哔哩哔哩_bilibili

B-M算法

文字描述

课本不到半张纸就把算法描述完了，真是太有实力辣！

图片描述

图来自上面的参考视频。

这张流程图真的就能很显然的讲明白，我真的搞不懂教材一张图不配，例题也不给出分析（当然例题分析要的纸更多）是想干什么。

我再给一张自己画的图（极简版）

计算过程大体是你知道d(n)，去算f(n+1)和l(n+1)，中间你可能还需要计算一个参量m。

如果得出了f(n+1)，我们就需要知道：c1到cn是f函数的系数（牢记！！！这一点困扰了我很久），所以就可以计算下一个d，也就是d(n+1)。

然后有一个整体的判断：
计算过程主要是走左边这条路和中间这条路，右边这条路基本上只会在开头的计算才会出现。

例题

为了书写方便我有的地方没用latex公式

课本例题1

初始化工作：由题a0a1a2a3a4a5a6a7=10101111，n=0，f0=1，L0=0

第一次循环：n=0

计算d0，得出d0=a0=1，走右边的路。

n=0，而现在已知L0=0，那么进入最右边的路。

$f_1=1+x,L_1=1$

第二次循环：n=1

f1=1+x，那么c1=1（也就是x前面的系数）

计算d1，d1=a1+c1*a0=1，走右边的路。

因为L0=0<L1=1，那么m=0，走中间的路。（此时因为L列出现了非0的数，那么最右侧的路就可以跟我们说拜拜了）

$f_m=f_0=1$

$f_2=f_1+x^{(1-0)}*f_0=1+x+x=1,L_2=max(L_1,2-L_1)=1$

第三次循环：n=2

f2=1，那么c1c2=00

计算d2=a2+c1*a1+c2*a0=1，走右边的路。

因为L0=0<L1=L2=1，那么m=0，走中间的路。

$f_m=f_0=1$

$f_3=f_2+x^{(2-0)}*f_0=1+x^2,L_3=max(L_1,3-L_1)=2$

第四次循环：n=3

f3=1+x^2，那么c1c2c3=010

计算d3=a3+c1*a2+c2*a1+c3*a0=0，走左边的路（终于可以休息了）。

$f_4=f_3=1+x^2 ,L_4=L_3=2$

第五次循环：n=4

f4=1+x^2，那么c1c2c3c4=0100

计算d4=a4+c1*a3+c2*a2+c3*a1+c4*a0=0，走左边的路。

$f_5=f_4=1+x^2 ,L_5=L_4=2$

第六次循环：n=5

f5=1+x^2，那么c1c2c3c4c5=01000

计算d5=a5+c1*a4+c2*a3+c3*a2+c4*a1=1，走右边的路。

因为L1=L2=1<L3=L4=L5=2，那么m=2，走中间的路。

$f_m=f_2=1$

$f_6=f_5+x^{(5-2)}*f_2=1+x^2+x^3,L_6=max(L_5,6-L_5)=4$

第七次循环：n=6

f6=1+x^2+x^3，那么c1c2c3c4c5c6=011000

计算d4=a4+c1*a3+c2*a2+c3*a1+c4*a0=0，走左边的路。

$f_7=f_6=1+x^2+x^3 ,L_7=L_6=4$

第八次循环：n=7

f7=1+x^2+x^3，那么c1c2c3c4c5c6c7=0110000

计算d5=a5+c1*a4+c2*a3+c3*a2+c4*a1=1，走右边的路。

因为L3=L4=L5=2<L6=L7，那么m=5，走中间的路。

$f_m=f_5=1+x^2$

$f_8=f_7+x^{(7-5)}*f_5=1+x^2+x^3+x^2+x^4=1+x^3+x^4$

$L_8=max(L_8,6-L_7)=4$

因此本题答案为<1+x^3+x^4,4>

课本例题2

初始化工作：由题a0a1a2a3a4a5a6a7a8a9a10a11=111001111001，n=0，f0=1，L0=0

（垃圾课本a12中间少写了个1）

第一次循环：n=0

计算d0，得出d0=a0=1，走右边的路。

n=0，而现在已知L0=0，那么进入最右边的路。

$f_1=1+x,L_1=1$

第二次循环：n=1

f1=1+x，那么c1=1。

计算d1，d1=a1+c1*a0=0，走左边的路。

$f_2=f_1=1+x ,L_2=L_1=1$

第三次循环：n=2

f2=1+x，那么c1c2=10。

计算d2，d2=a2+c1*a1+c2*a0=0，走左边的路。

$f_3=f_2=1+x ,L_3=L_2=1$

第四次循环：n=3

f3=1+x，那么c1c2c3=100。

计算d3，d3=a3+c1*a2+c2*a1+c3*a2=1，走右边的路。

因为L0=0<L1=L2=L3=1，那么m=0，走中间的路。

$f_m=f_0=1$

$f_4=f_3+x^{(3-0)}*f_0=1+x+x^3,L_4=max(L_3,4-L_3)=3$

(f4这里和书上答案的不一样，但是其余的结果完全一致，而且如果不用我的f4计算结果反而会不一致，所以不得不怀疑是书的问题。)

第五次循环：n=4

f4=1+x+x^3，那么c1c2c3c4=1010。

计算d4，d4=a4+c1*a3+c2*a2+c3*a1+c4*a0=1，走右边的路。

因为L1=L2=L3=1<L4=3，那么m=3，走中间的路。

$f_m=f_3=1+x$

$f_5=f_4+x^{(4-3)}*f_3=1+x+x^3+x+x^2=1+x^2+x^3$

$L_5=max(L_4,5-L_4)=3$

第六次循环：n=5

f5=1+x^2+x^3，那么c1c2c3c4c5=01100。

计算d5，d5=a5+c1*a4+c2*a3+c3*a2+c4*a1+c5*a0=0，走左边的路。

$f_6=f_5=1+x^2+x^3 ,L_6=L_5=3$

第七次循环：n=6

f6=1+x^2+x^3，那么c1c2c3c4c5c6=011000。

计算d6，d6=a6+c1*a5+c2*a4+c3*a3+c4*a2+c5*a1+c6*a0=1，走右边的路。

因为L1=L2=L3=1<L4=L5=L6=3，那么m=3，走中间的路。

$f_m=f_3=1+x$

$f_7=f_6+x^{(6-3)}*f_3=1+x^2+x^3+x^3+x^4=1+x^2+x^4$

$L_7=max(L_6,7-L_6)=4$

第八次循环：n=7

f7=1+x^2+x^4，那么c1c2c3c4c5c6c7=0101000。

计算d7，d7=a7+c1*a6+c2*a5+c3*a4+c4*a3+c5*a2+c6*a1+c7*a0=0，走左边的路。

$f_8=f_7=1+x^2+x^4 ,L_8=L_7=4$

第九次循环：n=8

f8=1+x^2+x^4，那么c1c2c3c4c5c6c7c8=01010000。

计算d8，d8=a8+c1*a7+c2*a6+c3*a5+c4*a4+c5*a3+c6*a2+c7*a1+c8*a0=0，走左边的路。

$f_9=f_8=1+x^2+x^4 ,L_9=L_8=4$

第十次循环：n=9

f9=1+x^2+x^4，那么c1c2c3c4c5c6c7c8c9=010100000。

计算d9，d9=a9+c1*a8+...+c9*a0=0，走左边的路。

$f_{10}=f_9=1+x^2+x^4 ,L_{10}=L_9=4$

第十一次循环：n=10

f10=1+x^2+x^4，那么c1c2c3c4c5c6c7c8c9c10=0101000000。

计算d10，d10=a10+c1*a9+...+c10*a0=0，走左边的路。

$f_{11}=f_{10}=1+x^2+x^4 ,L_{11}=L_{10}=4$

第十二次循环：n=12

f11=1+x^2+x^4，那么c1c2c3c4c5c6c7c8c9c10c11=01010000000。

计算d11，d11=a11+c1*a10+...+c11*a0=0，走左边的路。

$f_{12}=f_{11}=1+x^2+x^4 ,L_{12}=L_{11}=4$

因此本题答案为<1+x^2+x^4,4>

课后习题5.8

n	dn	fn(x)	Ln(x)	m	fm(x)
0	1	1	0
1	0	1+x	1
2	0	1+x	1
3	1	1+x	1	0	1
4	1	1+x+x^3	3	0	1
5	0	1+x^2+x^3	3	3	1+x
6		1+x^2+x^3	3

初始化工作：由题a0a1a2a3a4a5=111001，n=0，f0=1，L0=0

第一次循环：n=0

计算d0，得出d0=a0=1，走右边的路。

n=0，而现在已知L0=0，那么进入最右边的路。

$f_1=1+x,L_1=1$

第二次循环：n=1

f1=1+x，那么c1=1。

计算d1，d1=a1+c1*a0=0，走左边的路。

$f_2=f_1=1+x ,L_2=L_1=1$

第三次循环：n=2

f2=1+x，那么c1c2=10。

计算d2，d2=a2+c1*a1+c2*a0=0，走左边的路。

$f_3=f_2=1+x ,L_3=L_2=1$

第四次循环：n=3

f3=1+x，那么c1c2c3=100。

计算d3，d3=a3+c1*a2+c2*a1+c3*a2=1，走右边的路。

因为L0=0<L1=L2=L3=1，那么m=0，走中间的路。

$f_m=f_0=1$

$f_4=f_3+x^{(3-0)}*f_0=1+x+x^3,L_4=max(L_3,4-L_3)=3$

(f4这里和书上答案的不一样，但是其余的结果完全一致，而且如果不用我的f4计算结果反而会不一致，所以不得不怀疑是书的问题。)

第五次循环：n=4

f4=1+x+x^3，那么c1c2c3c4=1010。

计算d4，d4=a4+c1*a3+c2*a2+c3*a1+c4*a0=1，走右边的路。

因为L1=L2=L3=1<L4=3，那么m=3，走中间的路。

$f_m=f_3=1+x$

$f_5=f_4+x^{(4-3)}*f_3=1+x+x^3+x+x^2=1+x^2+x^3$

$L_5=max(L_4,5-L_4)=3$

第六次循环：n=5

f5=1+x^2+x^3，那么c1c2c3c4c5=01100。

计算d5，d5=a5+c1*a4+c2*a3+c3*a2+c4*a1+c5*a0=0，走左边的路。

$f_6=f_5=1+x^2+x^3 ,L_6=L_5=3$

因此线性综合解为<1+x^2+x^3,3>。

然而，以下是老师给的参考答案，从f5开始不一样。

认真算了几遍，我还是坚持我的答案。而且就算不从计算的角度来看，f5比f4多了一个x^4，但是f3是1+x，那么乘上一个x^n（无论是不是x^1）他都不可能只会冒出来一个x^4，一定还会多出来或者消除一个非x^4的项。所以现在打死我都不信这答案是对的。

更正：现在发现，这题的序列a就是课本例题2的序列，我释怀地笑了。

密码学——序列密码序列线性复杂度 B-M算法例题演示

前言

B-M算法

文字描述

图片描述