【密码学】（八）A5算法、RC4算法

1. 一、A5算法
2. 二、RC4算法

本文转载自：《现代密码学》课程笔记知乎专栏
仅作个人学习记录。

一、A5算法

A5算法是一种常用于GSM系统中的流密码算法，用于为GSM网络中的无线通信链路提供加密保护。

1、原始密钥：

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

2、A5算法的构成：

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

LFSR1：
LFSR2：
LFSR3：

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

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

（1）初始化阶段：

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

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

之后在22bit帧序号的作用下，3个LFSR分别移位22次。每次（假设第次）移位时，反馈函数计算的结果需要先与的第位进行异或，然后才作为反馈结果填充到每个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移位。

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

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

如下图所示：

图11-1 A5算法产生流密钥的方法

4、加解密方式：

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

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

图11-2 GSM使用A5算法加解密

二、RC4算法

RC4是Ron Rivest在1987年设计的一种流密码。它的运行速度很快，应用很广，常用于SSL/TLS网络浏览器和服务器间通信标准中。

1、概述：

RC4算法简单、易于描述，主要使用一个S表来生成流密钥，分为密钥调度算法（KSA）和伪随机数生成算法（PRGA）两个步骤。其中KSA使用原始密钥生成S表，PRGA利用S表来产生流密钥序列。

RC4算法的原始密钥是可变的，它可以在1字节~256字节（8~2048bit）范围内任意取值。

RC4的加密单位为一个字节。在下文中对加解密过程的描述中，常以字节为单位进行描述。

2、密钥调度算法（Key Scheduling Algorithm，KSA）：

前面提到，密钥调度算法的作用是，利用原始密钥来生成S表。

这里的密钥的长度为1~256字节。S表类似于一个数组，其大小为256，表示为 ~，其中每个S表单元可以存放一个字节（8位）。

S表的生成分为初始化和置换两部分。

（1）初始化：

首先对S表的每个单元依照编号从0~255依次填充（二进制序列）。即S[0]=0；s[1]=1；……s[255]=255；
然后，建立一个临时数组T，称为T表，其大小与S表相同。使用原始密钥对T表进行填充。如果的长度等于256，则直接将赋值给T表。如果的长度小于256，则T表剩余的部分继续使用密钥循环填充，直到填满为止。假设密钥K=123，T表长度为7，则T表=1231231。

以上过程使用伪代码描述为：

for(int i = 0; i < 256; i++)//对S表、T表的每个单元进行填充
{
    //填充S表
    S[i] = i;
    //填充T表，使用密钥K循环填充，keylen为密钥K的长度
    T[i] = K[i % keylen];
}

（2）置换：

置换过程就是根据一定的规则，对S表中的单元交换位置。

交换的规则为：

初始化一个变量。然后对于S表的第个单元，计算得，括号中的为上一次计算得出的值。

每次计算出后，交换和的位置。

以上过程的伪代码如下：

int j = 0;//初始化j
for(int i = 0; i < 256; i++)//对S表的每个单元进行遍历
{
    //计算新的j值
    j = (j + S[i] + T[i]) % 256;
    //交换S[i]和S[j]
    swap(S[i], S[j]);
}

经过置换后，S表中的内容也没有发生实质性的变化，只是各个字节被打乱了位置而已。

3、伪随机数生成算法（Pseudo-Random Generation Algorithm，PRGA）：

在经过KSA后，S表被建立了起来，之后的任务就是从S表中选取字节单元，输出密钥流序列。

为了使生成的密钥流序列更加的随机，PRGA每生成一个字节的密钥流，就会打乱一次S表。

生成密钥流、打乱S表的步骤如下：

初始化：首先初始化两个变量。
递增：然后每次在生成一字节的密钥流之前，自增1（但不能超过256，需要）：；自加上的值（但不能超过256，需要）：。
交换打乱：之后交换和的值，用来打乱S表。
输出：这时就可以输出一字节的密钥流，密钥流取自S表的第个单元（需要）。

重复上述步骤，即可生成多个字节的密钥流序列。

以上过程的伪代码如下：

int i = 0,j = 0;//初始化i，j为0
while(true)
{
    //i自增1
    i = (i + 1) % 256;
    //j自增S[i]
    j = (j + S[i]) % 256;
    //交换，打乱S表
    swap(S[i], S[j]);
    //使用变量t保存输出S表的第几个单元
    t = (S[i] + S[j]) % 256;
    //输出一字节的密钥流序列k
    k = S[t];
}

通过以上方式，就可以得到一系列字节的流密钥序列。之后，使用一字节的流密钥序列与一字节的明文序列异或可以得到密文；同理，使用一字节的流密钥序列与一字节的密文序列异或可以得到明文。

整个过程可以总结为：

图11-3 RC4密钥流序列的生成流程

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

魏欣怡的博客

一、A5算法

二、RC4算法