密码学系列文(2)--流密码-EW帮帮网

一、流密码的基本概念

RC4（Rivest Cipher 4）是由密码学家 Ron Rivest（RSA 算法发明者之一）于 1987 年设计的对称流加密算法。它以简单、高效著称，曾广泛应用于网络安全协议（如 SSL/TLS、WEP/WPA），但因存在严重安全漏洞，现已逐渐被淘汰。

1.1 流密码概念

流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如0，1数字)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现；

流密码强度完全依赖于密钥序列的随机性和不可预测性；
核心问题是密钥流生成器的设计
保持收发两端密钥流的精确同步是实现可靠解密的关键技术；

流密码框图如下：KG指密钥流生成器

消息流： $m=m_1m_2...m_i$ ，其中 $m_i\in M$
密文流： $c=c_1c_2...c_i...=E_{k_1}(m_1)E_{k_2}(m_2)...E_{k_i}(m_1)...$ ，其中 $c_i\in C$
密钥流： $\left \{ k_i \right \},i\geq 0$
加法流密码： $c_i=E_{k_i}(m_i)=m_i\bigoplus k_i$

密钥流：是一个完全随机的非周期序列，可以实现一次一密体制。但需要无限存储单元和复杂的输出逻辑函数 $f$ 。 $\sigma_i$ 是第 $i$ 时刻密钥流生成器的内部状态，以存储单元的存数矢量描述。

1.2 有限状态自动机FA

具有离散输入和输出(输入集和输出集均有限)的一种数学模型

有限状态集 $S=\left \{ s_i|i=1,2,...,l \right \}$
有限输入字符集 $X=\left \{ X_i|i=1,2,...,m \right \}$
有限输出字符集 $Y=\left \{ Y_k|i=1,2,...,n \right \}$
转移函数 $Yj=f_1(s_j,X_j)$ ； $S_{j+1}=f_2(s_j,X_j)$ ，第 $j$ 时刻输入 $X_j\in X$ ，输出 $Y_j\in Y$ ;

例如2-1： $S=\left \{ s_1,s_2,s_3 \right \},X=\left \{ X_1,X_2,X_3 \right \},Y=\left \{ Y_1,Y_2,Y_3 \right \}$

转移函数：

$f_1$	$X_1$	$X_2$	$X_3$
$s_1$	$Y_1$	$Y_3$	$Y_2$
$s_2$	$Y_2$	$Y_1$	$Y_3$
$s_3$	$Y_3$	$Y_2$	$Y_1$

$f_2$	$X_1$	$X_2$	$X_3$
$s_1$	$s_2$	$s_1$	$s_3$
$s_2$	$s_3$	$s_2$	$s_1$
$s_3$	$s_1$	$s_3$	$s_2$

那么FA的状态图表示为：初始状态为 $s_1$

若输入为 $x_1,x_2,x_1,x_3,x_3,x_1$

那么输出为 $y_1,y_1,y_2,y_1,y_3,y_1$ ，状态转移为 $s_2,s_2,s_3,s_2,s_1,s_2$ 。

1.3 作为FA的密钥流产生器

同步流密码的密钥流产生器可看为一个参数为 $k$ 的FA；
输出集 $Z$ ，状态集 $\sum$ ，状态转移函数 $\varphi :\sigma_i\rightarrow \sigma_{i+1}$ 和输出函数 $\Psi$ ，初始状态 $\sigma_0$
设计的关键是 $\varphi$ 和 $\Psi$ ；

具有非线性 $\varphi$ 的的FA理论很不完善，通常采用线性 $\varphi$ 以及非线性的 $\Psi$
可将此类产生器分为驱动部分和非线性组合部分
驱动部分控制状态转移
非线性组合部分提供统计特性良好的序列

两种目前最为流行和实用的密钥流产生器如图所示，其驱动部分是一个或多个线性反馈移位寄存器：

1.4 流密码的分类

1.4.1 同步流密码SSC

$\sigma_i$ 与明文消息无关，密钥流将独立于明文

同步流密码的特点

对于明文而言，这类加密变换是无记忆的，但它是时变的；
只有保持两端精确同步才能正常工作；
对主动攻击时异常敏感而利于检测；
无差错传播

1.4.2 自同步流密码SSSC

$\sigma_i$ 依赖于 $\left ( k_i,\sigma _{i-1},m_i \right )$ ，使密文 $c_i$ 不仅与当前输入 $m_i$ 有关，而且由于 $k_i$ 对 $\sigma_i$ 的关系而与以前的输入 $m_1,m_2,....m_{i-1}$ 有关。一般在有限的 $n$ 级存储下将与 $m_{i-1},...,m_{i-n}$ 有关。

优点：具有自同步能力，强化了其抗统计分析的能力；

缺点：有 $n$ 位长的差错传播；

如图所示：

1.5 序列的伪随机性

1.5.1 周期

周期：序列 $\left \{ a_i \right \}_{i\geq 0}$ ，使对所有 $i$ ， $a_{i+p}=a_i$ 成立的最小整数 $p$ ;
长度为 $l$ 的串 $\left ( a_t,a_{t+1}...a_{t+l-1} \right )$ ,在序列 $\left \{ a_i \right \}$ 的一个周期中， $a_{t-1}\neq a_t=a_{t+1}=...=a_{t+l-1}\neq a_{t+l}$

例如：长度为 $l$ 的1串和长度为 $l$ 的0串：...011...10...和...100...01...

1.5.2 自相关函数

$GF(2)$ 上周期为 $T$ 的序列 $\left \{ a_i \right \}$ 的自相关函数定义为：

$R(\tau )=\frac{1}{T}\sum_{k=1}^{T}(-1)^{a_k}(-1)^{a_k+\tau},0\leq \tau \leq T-1$

当 $\tau =0$ 时， $R(\tau)=1$ ；当 $\tau \neq 0$ 时，称 $R(\tau )$ 为异相自相关函数。

1.5.3 Golomb随机性公设

Golomb对伪随机周期序列提出了应满足的如下三个随机性公设：

在序列的一个周期内，0与1的个数相差至多为1;
在序列的一个周期内，长为1的游程占游程总数的 $\frac{1}{2}$ ，长为2的游程占游程总数的 $\frac{1}{2^2}$ ，... ，长为 $i$ 的游程占游程总数的 $\frac{1}{2^{i}}$ ，，且在等长的游程中0的游程个数和1的游程个数相等;
异自相关函数是一个常数;

1.5.4 密码系统随机性条件

一个伪随机序列应满足另外的三个条件：

$\left \{ a_i \right \}$ 的周期相当大。
$\left \{ a_i \right \}$ 的确定是计算上容易的。
$\left \{ a_i \right \}$ 由密文及相应的明文的部分信息,不能确定整个 $\left \{ a_i \right \}$ 。（不可预测性）

二、线性反馈移位寄存器序列

2.1 相关概念

级数(Stages)：存储单元数；
状态(State): $n$ 个存储单元的存数 $(a_i,...,a_{i+n-1})$ ；
反馈函数： $f(a_i,a_{i+1},...,a_{i+n-1})$ 是状态 $(a_i,...,a_{i+n-1})$ 的函数；
线性反馈移位寄存器(LFSR): $f$ 为线性函数
非线性反馈移位寄存器： $f$ 为非线性函数

如图所示：n级反馈移位寄存器

2.2 线性反馈移位寄存器

如果移位寄存器的反馈函数 $f(a_1,a_2,...,a_n)$ 是 $a_1,a_2,...,a_n$ 的线性函数，则称之为线性反馈移位寄存器LFSR,此时可写为 $f(a_1,a_2,...,a_n)=c_na_1\bigoplus c_{n-1}a_2\bigoplus ...\bigoplus c_1a_n$ ;

那么输出序列 $\left \{ a_i \right \}$ 满足 $a_{n+t}=c_na_t\bigoplus c_{n-1}a_{t+1}\bigoplus ...\bigoplus c_1a_{n+t-1}$ ,其中 $t$ 为非负正整数。

2.2.1 最长周期

在线性反馈移位寄存器中总是假定 $c_1,c_2,....,c_n$ 中至少由一个不为 0，

否则 $f(a_1,a_2,...,a_n)=0$ ，这样的话，在 $n$ 个脉冲后状态必然是 $00....0$ ，且这个状态必将一直持续下去。

因此线性移位器序列的最长周期为 $2^n-1$ ；

2.2.2 m序列

为 $2^n-1$ 的LFSR序列称为 $m$ 序列
$n$ 级 $m$ 序列 $\left \{ a_i \right \}$ 循环地遍历所有 $2^n-1$ 个非零状态，且任一非零输出皆为 $\left \{ a_i \right \}$ 的移位，或为其循环等价序列；
初始状态不同 $2^n-1$ 个的 $m$ 序列共有 $2^n-1$ 个，他们的全体记为 $\Omega(f)$ ，他们只是状态前后次序之别。

m序列满足Golomb的三个随机性公设

2.2.3 特征多项式

LFSR的特征多项式为： $p(x)=1+c_1x+...+c_{n-1}x^{n-1}+c_nx^n$

密码学系列文(2)--流密码