A5/1加密算法

一、A5/1 简介

  A5 算法在 1989 年由法国人开发，先后开发了三个版本记作 A5/1、A5/2、A5/3，如果没有特别说明，通常所说的 A5 是指 A5/1，这是一种流密码加密算法。该算法用于 GSM 系统的序列密码算法，最初是保密的，但通过泄漏和逆向工程公开。

流密码加密

  流密码加密(类似于一次性密码本)，用 n 位长度的密钥 S，并将其延展至长长的密钥流中，然后该密钥流与明文 P 进行异或运算生成密文 C。

  假设给定密钥流 S = S0，S1，S2 …以及明文 P = P0，P1，P2 …，我们通过按位的异或运算即可生成密文 C = C0，C1，C2 …。

二、A5/1 生成密钥

1、三个线性反馈移位寄存器（X:19位，Y:22位， Z:23位）

2、假设当前寄存器状态如下

3、生成密钥

找到 X8 = 1, Y10 = 0, Z10 = 1（算法规定）。

选取数量最多的作为结果 m = maj(X8, Y10, Z10) = maj(1, 0, 1) = 1（eg：maj(0, 0, 1) = 0）。

根据 m 与 (X8, Y10, Z10) 的值对寄存器进行移位。

因为 X8 = m = 1，所以 X 寄存器需要右移一位，第一位 X0 = X13 ⨁ X16 ⨁ X17 ⨁ X18(移位前) = 0 ⨁ 1 ⨁  0 ⨁  1 = 0，移位后 X 寄存器状态：

因为 Y10 = 0， m = 1，所以 Y 寄存器不需要进行移位（如果 Y10 = m = 1，则 Y 寄存器需要右移一位，第一位 Y0 = Y20 ⨁  Y21），移位后 Y寄存器状态：

因为 Z10 = m = 1，所以 Z 寄存器需要右移一位，第一位 Z0 = Z7 ⨁  Z20 ⨁  Z21 ⨁  Z22(移位前) = 1 ⨁  0 ⨁  0 ⨁  1 = 0，移位后 Z 寄存器状态：

最后得到三个寄存器的状态如下，然后将 X、Y、Z 寄存器的最后一位进行异或操作得到一位密钥，即 K0 = X18 ⨁  Y21 ⨁  Z22 = 0 ⨁  1 ⨁  0 = 1。

假设需要 64 位秘钥，则按照上述步骤进行 64 次循环操作即可得到 64 位密钥。

三、A5 算法特点

密钥被延展到长长的密钥流中，密钥流用途类似于一次性密码本。

A5 算法的基本思路是好的，它的效率非常高，能通过所有已知的统计测试。

已知的仅有的弱点是寄存器太短(密钥较短)而不能抗穷举攻击。

带较长寄存器和稠密反馈多项式的 A5 算法的变型是安全的。

四、题目解析

1、在实现A5/1算法中，假设在特定步骤之后，寄存器中的值为X=(x0,x1,...,x18)=(1010 1010 1010 1010 101)，Y=(y0,y1,...,y21)=(1100 1100 1100 1100 1100 11)，Z=(z0,z1,...,z22)=(1110 0001 1110 0001 1110 000)，在生成这些32位之后列出接下来的1个密钥流比特，并给出X、Y和Z的内容。

1）因为x8=

原文始发于微信公众号（豆豆咨询）：A5/1加密算法