密碼學系列文(2)--流密碼

一、流密碼的基本概念

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$

三、非線性序列

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/89224.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/89224.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/89224.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！