第七講 流密碼的基本概念

一次一密密碼(one-time pad)

一次一密密碼又稱一次性板子，是一種絕對安全的密碼，但是非常不實用。

如下圖所示，明文和密鑰都是字符串，經過異或之后生成密文。

其絕對安全性來自密鑰完全隨機，而且只使用一次。

具體加密流程如下圖所示：

一次一密密碼缺點和優點一樣明顯：

優點：

• 密鑰完全隨機，一次只使用一次
• 絕對安全
• 加解密都是加法運算，便于用硬件實現，所以效率非常高

缺點：

• 密鑰共享困難
• 非常不實用

流密碼

流密碼，又稱序列密碼，stream cipher

主要特點：

• 明文按比特或字符逐位加密
• 主要基于硬件實現
• 用移位寄存器電路來產生，促進了線性和非線性移位寄存器的發展

主要思想：

? 用密鑰k產生一個密鑰流z=z0z1z2z3....，并按照規則E對明文進行逐位進行加密，即

---

密鑰流的產生：

• 由密鑰流發生器f產生，zi＝f(k,σi)
• σi是加密器中記憶元件在i時刻的狀態
  • 即每個密鑰的產生，依賴于k和上個時刻的密鑰的狀態
• f是由k，σi產生密鑰的函數

---

流密碼和分組密碼最大的不同在于有無記憶元件，即流密碼是串行的，分組密碼是并行的

記憶元件內部是一組移位寄存器

同步流密碼

這里的同步考察的是 記憶元件狀態σ 和 明文字符 之間是否同步，

如果相互獨立，則稱為同步流密碼。（如果相互獨立，為什么不干脆叫異步流密碼？）

否則，如果 記憶元件狀態σ 和 明文字符 同步，則成叫做自同步流密碼

在同步流密碼中，由于zi=f(k,σi)和明文字符無關，

因而此時密文字符yi=Ezi(xi)也不依賴于此前的明文字符。

因此，密鑰的產生和加密就可以分開了。

可將同步流密碼的加密器分成滾動密鑰生成器器和加密變換器兩個部分。

注意到，如果滾動密鑰生成器生成的密鑰是完全隨機的，那么流密碼就退化成一次一密密碼。

密碼設計者最大的愿望是設計出一個滾動密鑰生成器，使得密鑰經其擴展成的密鑰流具有如下性質：

• 極大的周期
• 良好的統計特性
• 抗線性分析

第八講 有限狀態自動機

有限狀態自動機模型

有限自動機，我們可以顧名思義——狀態是有限的。

那么這些有限的狀態是如何狀態的呢？當然是通過狀態轉移函數！

既然是函數，那么就需要輸入和輸出。

于是乎有限狀態自動機的定義就呼之欲出了：

定義看起來復雜，只要抓住輸入和輸出，以及狀態轉移前后的兩個狀態即可。

有限狀態自動機也可以用有向圖來表示，也稱轉移圖：

頂點對應于自動機 的狀態，

若狀態si在輸入A(1)i 時轉為狀態sj，且輸出一字符 A(2)j，

則在轉移圖中，從狀態 si到狀態sj有一條標有(A(1)i, A(2)j)的弧線。

---

舉個栗子：

狀態s1在輸入A(1)1 時轉為狀態s2，且輸出一字符 A(2)1，對應于紅箭頭

狀態s2在輸入A(1)2 時轉為狀態s2，且輸出一字符 A(2)1，對應于藍色箭頭

除了轉移圖，也可以用矩陣表示：

有限狀態自動機實例

對于剛剛給定的自動機，輸入序列為：

A (1)1 -> A (1)2 -> A (1)1 -> A (1)3 -> A (1)3 ->A (1)1

對初始狀態s1，

請問狀態序列是？

請問輸出字符序列？

---

解析：

從s1開始，輸入為A(1)1，轉移到s2,輸出為A(2)1，對應于圖中紅線；

此時轉移到s2，輸入為A(2)1，轉移到s2，輸出為A(2)1，對應于圖中藍線。

所以得到轉移序列：s 1-> s 2-> s 2 -> s 3 -> s 2-> s 1-> s 2

所以得到輸出序列：A(2)1 -> A(2)1 -> A(2)2 -> A(2)1 -> A(2)3 -> A (2)1