一、A5 算法

背景

A5 算法是 GSM 系统中使用的加密算法之一,主要用于加密手机终端与基站之间传输的语音和数据。该算法由一个 22 比特长的参数(帧号码,Fn)和 64 比特长的参数(会话密钥Kc),生成两个114比特长的序列(密钥流)。这样设计的原因是GSM会话每含228比特通过与 A5 算法产生的 228 比特密钥流进行异或实现保密。A5 算法有 3 种版本 A5/1 算法限制出口,保密性较强;A5/2 算法没有出口限制,但保密性较弱;A5/3 算法则是更新的版本,它基于 KASUMI 算法,但尚未被GSM标准采用。

流程 （详细）

A5算法是一种典型的基于线性反馈移位寄存器的序列密码算法,构成 A5 加密器主体的LFSR有3个,组成了一个集互控和停走于一体的钟控模型。线性移位寄存器(ABC)的长度各不相同:A有19位,B有 22位,C有 23位,它们的移位方式都是由低位移向高位。每次移位后,最低位就要补充一位,补充的值由寄存器中的某些抽头位进行异或运算的结果决定,如运算的结果为“1”,则补充“1”,否则补充“0”。在 3 个 LFSR 中 A 的抽头位置为 18,17,16,13;B的抽头位置为 21,20,16,12;C 的抽头位置为 22,21,18,17。3个LFSR输出的异或值作为 A5算法的输出。A5算法的主体部分如图 5-26 所示。

1.png

这 3个 LFSR 的移位是由时钟控制的,且遵循“服从多数”的原则。即从每个寄存器中取出一个中间位(图5-26中的xyz,位置,分别为 ABC的第 9,11,11位)进行运算判断,若在取出的3个中间位中至少有 2个为“1”,则为“1”的寄存器进行一次移位,而为“0”的不移反过来,若3个中间位中至少有 2个为“0”,则为“0”的寄存器进行一次移位，而为“1”的不移。

显然，这种机制保证了每次至少有 2个 LFSR 被驱动移位。一个GSM消息被转换成一系列的帧，每帧具有 228位。A5算法在会话密Kc和数Fn 的作用下输出相应的密钥序列,与GSM消息逐比特的异或,完成对消息的加密，如图 5-27 所示。

2.png

流程（总结）

1.原始密钥:

A5 算法的输入为22bit长的帧序号 $F_n$和64bit长的密钥 $K_c$，输出为 228bit 的流密钥序列。

2. A5 算法的构成：

A5 算法由3 个 m 序列 LFSR 构成，这三个 LFSR 的级数分别为 19、22、23。其特征多项式分别为：

  • LFSR1： $g_1(x) = x^{19} + x^{18} + x^{17} + x^{14} + 1$
  • LFSR2： $g_2(x) = x^{22} + x^{21} + x^{17} + x^{13} + 1$
  • LFSR3： $g_3(x) = x^{23} + x^{22} + x^{19} + x^{18} + 1$

3、流密钥序列的产生过程：

A5 算法流密钥序列的产生包含初始化和不规则动作两个阶段。

（1）初始化阶段：

首先将 3 个 LFSR 的初始状态全设为 0。

然后在 64bit 密钥 $K_c$的作用下，3 个 LFSR 分别移位64 次。每次（假设第 i 次）移位时，反馈函数计算的结果需要先与$K_c$的第 i 位进行异或，然后才作为反馈结果填充到每个 LFSR 的最末端。

之后在 22bit 帧序号$F_n$ 的作用下，3 个 LFSR 分别移位22 次。每次（假设第 i 次）移位时，反馈函数计算的结果需要先与 $F_n$ 的第 i 位进行异或，然后才作为反馈结果填充到每个 LFSR 的最末端。

初始化阶段的目的是给三个 LFSR 提供随机性良好的非全零的初始状态，为后面产生流密钥做准备。

（2）不规则动作阶段：

接下来的阶段中，需要时钟脉冲来控制 3 个 LFSR 进行移位输出。

所谓不规则动作，就是指 3 个 LFSR 的移位是不规则的。A5 算法采取的方法是，分别从 LFSR1、LFSR2、LFSR3 中选取第 9 位、第 11 位、第 11 位作为检测位（分别记为 x，y，z），进行钟控移位。移位规则是：多数移位，少数不移位。假如 x、y、z 中至少有 2 个为“1”，则为“1”的 LFSR 移位一次，为“0”的不移位；假如 x、y、z 中至少有 2 个为“0”，则为“0”的 LFSR 移位一次，为“1”的不移位。这种机制保证了每次时钟脉冲到来时，至少有 2 个 LFSR 移位。
3.png

采取这种移位方法，A5 算法的不规则动作阶段的具体流程为：

加密

  • 1、在时钟脉冲的作用下，3 个 LFSR 采取上述移位方式，动作100 次，但不输出。
  • 2、在时钟脉冲的作用下，3 个 LFSR 采取上述移位方式，动作114 次，产生输出。每次动作后，先对产生的 3 个输出进行异或，然后作为流密钥序列的一位。
  • 3、在时钟脉冲的作用下，3 个 LFSR 采取上述移位方式，再次动作100 次，不输出。

解密

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

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

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

如下图

1.png

4、加解密方式：

同其他流密码加密方式相同，A5 算法也是直接将明文与产生的流密钥序列进行按位异或，得到密文。密文与流密钥序列异或后，也可得到明文。

GSM 消息通常使用 A5 算法对每个会话分别加密，其每个会话的长度为 224bit，与 A5 算法流密钥序列长度相同，因此加密方式就是简单地异或。如下图所示，对于每帧会话，A5 算法的输入$F_n$是有变化的。

C++代码

下面代码介绍了生成比特密钥流的例子！！

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 256; /*循环次数*/

/*A、B、C三个线性移位寄存器*/
int A[19] = { 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1 };
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 };

void lfsr(int a, int b, int c, int d, int T[])/*移位寄存器函数*/
{
	for (int i = d; i > 0; i --)
	{
		T[i] = T[i - 1];
	}
	T[0] = T[a] ^ T[b] ^ T[c] ^ T[d];
}

int main()
{
	for (int i = 0; i<N; i++)
	{
		if (i % 8 == 0)
			printf("\n");
		//分别从LFSR1、LFSR2、LFSR3中选取第9位、第11位、第11位作为检测位
		//钟控移位规则是：多数移位，少数不移位
		int j = A[9] + B[11] + C[11];
		/*j可能等于0-3之间*/
		if (j == 0)
		{
		    // 三个比特的异或就是当前时刻输出的1比特密钥。
			cout << " " << (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)
		{
			cout << " " << (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)
		{
			cout << " " << (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)
		{
			cout << " " << (A[18] ^ B[21] ^ C[22]) << " ";
			lfsr(13, 16, 17, 18, A);
			lfsr(12, 16, 20, 21, B);
			lfsr(17, 18, 21, 22, C);
		}
	}
}

结果

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
1  1  1  1  1  1  1  1
1  1  0  1  1  0  1  0
1  1  0  1  0  1  0  1
0  1  1  1  0  0  0  1
1  1  1  0  0  0  0  0
1  0  1  0  1  0  0  0
0  1  0  1  1  1  0  0
0  1  0  0  0  0  0  0
0  1  1  1  0  0  1  0
0  1  1  1  0  0  1  1
1  0  1  0  1  0  0  1
1  1  1  1  0  1  1  1
1  1  0  0  0  0  0  0
0  0  1  1  0  0  0  0
1  1  0  1  1  1  0  0
0  1  1  1  1  0  0  0
0  0  0  0  0  1  1  1
1  0  0  0  0  0  1  1
0  1  0  1  1  1  1  1
0  1  0  1  1  0  0  1
0  1  1  1  1  0  0  1
0  0  1  1  1  1  0  0
0  0  1  0  0  0  1  0
1  0  0  0  1  1  1  0
1  0  1  0  1  1  0  1
0  1  0  1  1  0  1  1
1  0  0  0  0  0  1  1
0  0  1  0  0  0  1  1
0  0  0  1  1  1  1  1
1  1  1  0  1  0  1  1
0  1  1  0  1  0  0  0
1  0  0  0  1  0  1  0

总结

A5算法的初始密钥长度为64 比特。为了对该算法进行攻击，已知明文攻击法只需要确定其申两个寄存器的初始值就可以计算出另一个寄存器的初始值，这说明政击 A5一般要用$2^{40}$次尝试来确定两个寄存器的结构，而后从密钥流来决定第3个 LFSR。A5 的设计思想优秀,效率高,可以通过所有已知统计检验标准。其唯一缺点是移位寄存器级数短、其最短循环长度为$4/3\times 2^k$(k是最长的LFSR 的级数)总级数为19十22+23=64，这样就可以用穷尽搜索法破译,如果 A5算法能够采用更长的、抽头更多的线性反馈移位寄存器,则会更为安全 。