第十六讲 A5流密码算法

Bertha 。 2023-03-02 14:54 25阅读 0赞

# 1 A5流密码算法的基本用法 #

用于蜂窝式移动电话系统语音和数字加密。

A5/1算法用于用户的手机到基站之间的通信加密，通信内容到基站后先解 密变成明文，然后再进行基站到基站之间、以及基站到用户手机之间的信息加密，完成通信内容在通信过程的加密保护。

![20200729184812303.png][] 通信模式

### 应用环节 ###

只需考察用户A到基站1之间通信内容的加解密，中间消息的传送由基站到基站之间的加密完成，而接收方用户B对消息的加解密与用户A到基站1之间的通信完全类似，只不过是用户B先解密消息。

![20200729184916961.png][]

![20200729184932528.png][]

![20200729185512594.png][]

### A5/1序列密码算法中的线性反馈移位寄存器 ###

![20200729185936698.png][]

### 算法初始化 ###

初始化是利用一次通话的会话密钥k和帧序号设定三个移存器的起点，即初始状态。

Step 1：将三个LFSR的初态都设置为全零向量；

Step 2：(密钥参与) 三个LFSR都规则动作64次，每次动作1步。

在第i步动作时，三个LFSR的反馈内容都首先与密钥的第i比特异或，并将异或结果作为LFSR反馈的内容。

### 密钥参与过程举例 ###

![20200729191643187.png][]

### 帧序号参与 ###

![20200729191926842.png][]

# 2 A5流密码算法的基本原理 #

### 密钥流生成与加解密 ###

![20200730170121629.png][]

**钟控**将第一个寄存器的第八位，第二个寄存器的第10位，第三个寄存器的第10位。抽取这三个位用于控制三个LSFR的动作与否。他们决定的原则类似少数服从多数，三位一共有8种排列方式，当三位中1的个数多余0的个数时，那么这三位是1的对应的寄存器将会移动， 为0的不会，如果三位数中0的个数多余1的个数时，那么三位之中是0的对应的寄存器将会移动。

![20200730170418639.png][] 图中钟控序列为001，0多，故0移动，1不动。LFSR1和LFSR2左移一位。LFSR3不动。

### 关于加密 ###

Step 4：三个LFSR以钟控方式连续动作100次，但不输出密钥流；

Step 5：三个LFSR以钟控方式连续动作114次，在每次动作后，三个LFSR都将最高位寄存器中的值输出，这三个比特的异或就是当前时刻输出的1比特密钥。

连续动作114步，共输出114比特密钥流，用于对用户手机到基站传送的 114比特数据的加密；

![20200730170748670.png][]

### 关于解密 ###

Step 6：三个LFSR以钟控方式连续动作100次，但不输出密钥流；

Step 7：三个LFSR以钟控方式连续动作114次，在每次动作后，三个LFSR都 将最高级寄存器中的值输出，这三个比特的模2和就是当前时刻输出的1比 特密钥流。

连续动作114步，共输出114比特密钥流，这114比特用于对基站到用户手机 传送的114比特数据的解密。

![20200730170851479.png][]

### A5/1算法的弱点 ###

**移位寄存器太短容易遭受穷举攻击**

A5/1算法把主密钥作为算法中三个寄存器的初始值，长度为64比特。如果利用已知明文攻击，只需要知道其中两个寄存器的初始值，就可以计算出另一个寄存器的初始值，这只需要![2^\{ 40\}][2_ 40]步就可以得出寄存器LFSR-1 和LFSR-2的结构。

**事实上，A5/1加密算法中存在严重的安全问题**

利用了GSM通信加密中的两个安全漏洞，可以通过离线迭代计算生成一 个彩虹表，它包含有密钥和其相对应的输出密码。这个彩虹表的大小为 984GB。得到了彩虹表之后，安全专家就可以在短短的九秒内确定用于 加密通信数据的密钥。

### 密钥流生成器的基本原则 ###

设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性”，它可分解为下述基本原则：

① 长周期。

② 高线性复杂度(用最少的移位寄存器来实现)。

③ 统计性能良好。

④ 足够的“混乱” 。

⑤ 足够的“扩散” 。

⑥ 抵抗不同形式的攻击。

/*A5算法C语言实现，不是C++噢！！！*/
    #include<stdio.h>
    #define N 256                          /*循环次数*/
    lfsr(int a, int b, int c, int d, int T[]); /*移位寄存器函数*/
    void main()
    {
    	int  A[19] = { 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1 };   /*A、B、C三个移位寄存器*/
    	int  B[22] = { 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1 };
    	int  C[23] = { 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1 };
    	int i;
    	for (i = 0; i<N; i++)
    	{
    		if (i % 8 == 0)
    			printf("\n");
    		int j = A[9] + B[11] + C[11];
    		if (j == 0)            /*j可能等于0-3之间*/
    		{
    			printf("%d	", A[18] ^ B[21] ^ C[22]);
    			lfsr(13, 16, 17, 18, A);
    			lfsr(12, 16, 20, 21, B);
    			lfsr(17, 18, 21, 22, C);
    		}
    		else if (j == 1)
    		{
    			printf("%d	", A[18] ^ B[21] ^ C[22]);
    			if (A[9] == 0)
    				lfsr(13, 16, 17, 18, A);
    			if (B[11] == 0)
    				lfsr(12, 16, 20, 21, B);
    			if (C[11] == 0)
    				lfsr(17, 18, 21, 22, C);
    		}
    		else if (j == 2)
    		{
    			printf("%d	", A[18] ^ B[21] ^ C[22]);
    			if (A[9] == 1)
    				lfsr(13, 16, 17, 18, A);
    			if (B[11] == 1)
    				lfsr(12, 16, 20, 21, B);
    			if (C[11] == 1)
    				lfsr(17, 18, 21, 22, C);
    		}
    		else if (j == 3)
    		{
    			printf("%d	", A[18] ^ B[21] ^ C[22]);
    			lfsr(13, 16, 17, 18, A);
    			lfsr(12, 16, 20, 21, B);
    			lfsr(17, 18, 21, 22, C);
    		}
    	}
    }
    lfsr(int a, int b, int c, int d, int T[])
    {
    	int i;
    	for (i = d; i>0; i--)
    	{
    		T[i] = T[i - 1];
    	}
    	T[0] = T[a] ^ T[b] ^ T[c] ^ T[d];
    }

[20200729184812303.png]: /images/20230208/194386347f664523b6ce45bbafa1c109.png
[20200729184916961.png]: /images/20230208/05408b1a24ec49ad8592b24ff0fc626a.png
[20200729184932528.png]: /images/20230208/e0d69072eea74bb5ab19369b0b22b974.png
[20200729185512594.png]: /images/20230208/6c6c29da7a2646648ae266446b9200b1.png
[20200729185936698.png]: /images/20230208/30c7e0904fdc4f209e5f72bd283710e4.png
[20200729191643187.png]: /images/20230208/ccdee0b0a25d49e799dca422195b941f.png
[20200729191926842.png]: /images/20230208/f9081499d0ba46c5bf4aa5889dec0156.png
[20200730170121629.png]: /images/20230208/3b36a7b65aa84d0da863e847a25d1c43.png
[20200730170418639.png]: /images/20230208/4c7ca8104cae43eb893e297f9e0c6f51.png
[20200730170748670.png]: /images/20230208/6d925a4cf4ff4a6da53dbc14c7a459e0.png
[20200730170851479.png]: /images/20230208/fa14b0f7de5541d1844a5b718ef73006.png
[2_ 40]: https://private.codecogs.com/gif.latex?2%5E%7B%2040%7D