[XJTU計算機網絡安全與管理]第二講 密碼技術

密碼學（密碼術）作為許多安全機制（如加密，解密，驗證等）的一項基本元素，在信息安全中具有非常重要的地比特。其地比特如圖所示——會畫圖

一、加密技術概述

Cryptography源自希臘語單詞“kryptos”（hidden）與“graphia”（writing）。

定義：密碼學是針對如機密性，數據完整性，實體認證，數據源認證等信息安全課題進行的數學技術研究。

密碼學研究的主要目標是：

• 機密性
• 數據完整性
• 認證(真實性)
• 不可抵賴(可審計性)

密碼學的主要研究方向可分為如下四類(了解即可)：

• 對稱加密技術
• 非對稱加密技術
• 哈希函數
• 偽隨機數生成

二、對稱加密Symmetric Encryption

• 或私鑰加密/常規加密/單密鑰加密
• 發送方和接收方使用相同的密鑰
• 所有傳統的加密算法都是對稱加密
• 20世紀70年代（公鑰加密提出）之前是唯一的類型
• 目前仍舊具有廣泛的應用

基本術語

明文（plaintext） - 源消息

密文（ciphertext） - 編碼後的消息

cipher （密碼，加密技術）- 將明文轉換為密文的算法

密鑰（key） - 加密程序所使用，僅被發送者/接收者所知的信息。

加密 encipher (encrypt) – 將原文轉換為密文

解密 decipher (decrypt) – 將密文恢複為原文

密碼編碼學 cryptography – 針對加密原理/方法的研究

密碼分析 cryptanalysis (codebreaking) – 在不知道密鑰的情况下對密文進行解密的原則/方法的研究

密碼研究 cryptology – 密碼編碼學與密碼分析的領域之和

P：明文

C：密文

$E_{K_e}(P)\to C:加密$

$D_{K_d}(C)\to P:解密$

要求

對稱加密的安全使用有下面兩個要求

一個健壯的加密算法

密碼僅為發送方*/*接收方所知

數學錶示：
$$\begin{gathered} C=E(K_e,P)P=D(K_d,C) \\ P=D(K_d,E(K_e,P))=P \end{gathered}$$
算法是公開的

提供一個安全信道以分享密鑰

密碼編碼學

我們刻畫/描述一個密碼系統通常可以通過：

1️⃣ 加密操作的方法

替代/轉置/乘積

2️⃣ 使用的密鑰數

單密鑰或私鑰/雙密鑰或公鑰

3️⃣ 明文的處理方式

塊加密/流加密

密碼分析學與密碼攻擊

密碼分析可看作是試圖發現密鑰或原文的過程

密碼分析的原則：

破譯改密碼的成本超過被加密信息的價值

破譯該密碼的時間超過該信息有用的生命周期

密碼分析的方法：

用密碼分析方法的破解（cryptanalytic attack）

暴力破解 （ brute-force attack）

密碼攻擊的類型（了解即可）

攻擊的類型	密碼破譯者已知的
僅有密文	加密算法 帶破譯的密文
已知明文	加密算法 待破譯的密文 由密鑰形成的一個或多個明文-密文對
選擇明文	加密算法 待破譯的密文 有密碼破譯者選擇的明文消息，連同它對應的由其密鑰生成的密文
選擇密文	加密算法 待破譯的密文 由密碼破譯者選擇的猜測性的密文，連同它對應的由密鑰生成的已破譯的明文
選擇文本	加密算法 待破譯的密文 由密碼破譯者選擇的明文消息，連同它對應的由密碼生成的密文 由密碼破譯者選擇猜測性的密文，連同它對應的由密鑰生成的已破譯的明文

無條件安全：不論計算機的能力與時間如何，由於密文所提供的信息不足以唯一的確定相應的明文，密碼均不能被破解。

計算安全：所具備的受限的計算資源不足以破解密碼

三、古典替代密碼

明文中的每一個元素（比特，字母，比特組合或字母組合）被映射為另一個元素。

這裏可能是字母被替換為其他字母或符號

也可能是比特組合被替換為另外的比特組合

凱撒碼Caesar

已知的最早的替代碼

Julius Caesar

最初應用於軍事，將每個字母替換為其後的第三個字母。

例：

meet me after the toga party

PHHW PH DIWHU WKH WRJD SDUWB

其變化可描述為以下方法

a b c d e f g h i j k l m n o p q r s t u v w x y z

D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

我們可以數學的給字母以如下錶示

a b c d e f g h i j k l m n o p q r s t u v w x y z

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

凱撒碼可以錶示為

c = E§ = (p + k) mod (26)

p = D = (c – k) mod (26)

特點分析

只有26個可能的密碼，可以很容易的依次驗證——暴力破解

對於已知密文，只需依次移動字母

當明文產生時需要能够識別

單錶代替密碼

比單純的移動字母錶要更進一步

可以任意的進行字幕替換

每個原文字符都可以被映射為一個任意的密文字符

密碼長度為26個字母

例：

Plain: abcdefghijklmnopqrstuvwxyz

Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN

Plaintext: ifwewishtoreplaceletters

Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA

安全性說明

總共的密碼數為26！總數大於$4x\times 10^{26}$

有如此多的密碼，是不是更安全呢？

事實上是錯誤的。

主要問題在於語言的特性——某些字母出現的頻率高，有些用的少

關鍵概念-單一字母替代碼不會改變字母的出現的頻率

該特點由阿拉伯科學家於公元9世紀發現

計算字母出現頻率

將計算值於已知值進行對比

如果我們查看凱撒碼的峰/槽值我們有

峰值在A-E-I,NO,RST

槽值在JK,X-Z

應當針對每個字母結合二元組，三元組進行驗證

Playfair 密碼

單一替代碼雖然增加了密碼數量但並沒有增加安全性

一種改進的方案是多字母加密

Playfair即是一例

由英國科學家Charles Wheatstone 1854年發明用的是他的朋友的名字Barron Playfair

Playfair矩陣

M	O	N	A	R
C	H	Y	B	D
E	F	G	I/J	K
L	P	Q	S	T
U	V	W	X	Z

本例使用的密鑰詞是monarchy。填充矩陣的方法是：首先將密鑰詞（去掉重複字母）從左至右從上至下填在矩陣格子中，再將剩餘的字母按字母錶的順序從左至右、從上至下填在矩陣剩下的格子裏。字母I和J暫且當成一個字母。對明文按如下規則一次加密兩個字母：

1️⃣ 如果該字母對的兩個字母是相同的，那麼在它們之間加一個填充字母，比如x。例如balloon先把它變成ba Ix lo on這樣四個字母對

2️⃣ 落在矩陣同一行的明文字母對中的字母由其右邊的字母來代替，每行中最右邊的一個字母就用該列中最左邊的第一個字母來代替，比如ar變成RM

3️⃣ 落在矩陣同一列的明文字母對中的字母由其下面的字母來代替，每行中最下面的一個字母就用該列中最上面的第一個字母來代替，比如mu變成CM。

4️⃣ 其他的每組明文字母對中的字母按如下方式代替，該字母所在行為密文所在行，另一字母所在列為密文所在列。比如hs變成BP,ea變成IM(或JM)。(對角變對角)

特點

比單一字母替換安全性好

頻率錶項增加到了26x26=676

曾被廣泛應用多年（如第一次世界大戰）

提供幾百個字母下可破解

仍能够保留部分明文結構特征

多字母密碼

性質：使用一系列相關的單字母替代規律

一個密鑰决定對一個給定的變換選擇那種特定的規則

Vigenère碼:

相隔的單字母替代規則集合由26個凱撒碼組成

加密過程為：給定一個密鑰x一個明文y，密文為x與y的交叉點V

key: deceptivedeceptivedeceptive

plaintext: wearediscoveredsaveyourself

ciphertext：ICVTWQNGRZGVTWAVZHCQYGLMGJ

安全性

每個明文字母都對應多個密文

字母的統計信息被隱藏了

但並非完全隱藏

開始首先統計字母出現頻率。查看是否為單一替代碼。如果不是則通過確定關鍵詞長度來繼續分析：

比如前面的例子通過red的密文VTM猜測關鍵詞長度為9，然後可以通過一直頻率特征考慮攻擊

一次一密One-Time Pad

采用與明文一樣長的隨機串為關鍵詞

具備很强的安全性，統計學特征被隱藏

一次一密

密鑰的生成與共享是存在的難題

沒多大用——難以把密鑰傳過去

四、置換技術

該方法通過將字符重新排列隱藏信息

並不改變使用的字符

該方案可以通過原文，密文中字符出現的頻率相同進行識別

栅欄技術

按照對角線順序寫出明文，然後按照行的順序讀取作為密文，例如：用深度為2的栅欄技術加密信息“meet me after the toga party”，可寫作

m e m a t r h t g p r y

e t e f e t e o a a t

密文為：MEMATRHTGPRYETEFETEOAAT

行置換技術

一個更複雜的方案是：

將消息按照特定的列數寫成矩陣形式

按照密鑰值依次讀出按照行排列

Key: 3 4 2 1 5 6 7

Plaintext: a t t a c k p

​ o s t p o n e

​ d u n t i l t

​ w o a m x y z

Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ

乘積

通過將加密方案複合可以增大破解的難度。

單純的替代組合可以得到更複雜的替代

單純的置換組合可以得到更複雜的置換

置換之後進行替代將構成新的難以破解的密碼方案。（這也是傳統密碼學向現代密碼學過度的橋梁）

五、轉子機

在現代密碼學之前，轉子機是最常用的複雜加密設備

第二次世界大戰中被廣泛使用：德國的 Enigma, 日本的Purple

提供了非常複雜的替代密碼

由一系列獨立轉動的圓柱體構成。每個提供一個替代加密，並且在每次擊鍵後能够進行更改。

參考資料

[1] 西安交通大學計算機網絡安全與管理2022年春PPT 田暄

[2] 密碼編碼學與網絡安全（第七版），William Stallings著，王後珍等譯

[3]【密碼學】Vigenere 維吉尼亞算法加解密