應用密碼學原理、分析與Python實現

刘卓，飞行器总体设计工程师，毕业于香港中文大学数学系。

赵勇焜，日本学术振兴会（JSPS）外籍研究员，英国帝国理工学院博士研究生。

黄领才，研究员级高级工程师。现任中航通飞华南飞机工业有限公司党委委员、总工程师、AG600总设计师。

第一部分 基礎背景知識

第 1 章 密碼學簡介 2

1.1 密碼學簡史 2

1.1.1 古代密碼學發展 2

1.1.2 近代密碼學發展 5

1.1.3 現代密碼學發展 9

1.2 密碼學概念 10

1.2.1 密碼學的基本要素 10

1.2.2 密碼學的基本原則 10

1.2.3 密碼分析方式 13

1.2.4 對稱/非對稱加密 15

1.3 編碼 16

1.3.1 ASCII 編碼 16

1.3.2 異或運算 18

第 2 章 數學基礎 19

2.1 集合 19

2.2 除法定理 21

2.3 歐幾里得算法 22

2.4 模運算 25

2.4.1 模運算定義 25

2.4.2 身份證校驗碼 27

2.5 歐拉函數 29

2.6 默比烏斯函數 31

2.7 模的冪運算 33

2.7.1 歐拉定理 33

2.7.2 快速模冪運算 34

2.7.3 方程 xe ≡ c (mod N) 求解 37

2.8 二次剩餘 38

2.9 代數基礎 42

2.9.1 群 42

2.9.2 環 44

2.9.3 域 44

2.10 有限域 45

2.11 多項式運算 49

2.12 GF(2n)

52

2.13 本章習題 54

第 3 章 密碼學中的信息理論 57

3.1 熵 57

3.1.1 熵的定義 57

3.1.2 一些重要不等式 64

3.1.3 英語的熵 66

3.1.4 中文的熵 68

3.1.5 摩斯電碼 69

3.2 霍夫曼編碼 70

3.3 一次一密/Vernam 密碼 75

3.3.1 加密步驟 76

3.3.2 重復使用密鑰的後果 77

3.4 完善保密性 77

3.4.1 理論安全性 77

3.4.2 唯一解距離 79

3.4.3 實際保密性 81

3.5 多項式時間 81

3.6 本章習題 85

第二部分 對稱密碼學

第 4 章 古典密碼學 88

4.1 凱撒密碼/移位密碼 88

4.1.1 加密步驟 88

4.1.2 密碼分析 89

4.1.3 凱撒密碼的改進 90

4.2 反切碼 92

4.3 維吉尼亞密碼 93

4.3.1 加密步驟 94

4.3.2 密碼分析 96

4.3.3 弗里德曼檢驗 99

4.3.4 卡西斯基檢驗 100

4.4 仿射密碼 103

4.4.1 加密步驟 103

4.4.2 密碼分析 105

4.5 希爾密碼 106

4.5.1 線性代數基本運算 106

4.5.2 加密步驟 109

4.5.3 密碼分析 110

4.6 默克爾-赫爾曼背包密碼 112

4.6.1 加密步驟 112

4.6.2 密碼分析 116

4.7 其他密碼 119

4.7.1 普費爾密碼 119

4.7.2 ADFGVX 密碼 122

4.7.3 矩形換位密碼 125

4.7.4 矩形換位密碼分析 126

4.7.5 單字母替換密碼分析 134

4.8 本章習題 135

第 5 章 流密碼 138

5.1 RC4 138

5.1.1 加密步驟 139

5.1.2 RC4 密碼示例 141

5.1.3 密碼分析 142

5.2 祖沖之密碼 143

5.2.1 加密描述 143

5.2.2 祖沖之密碼示例 147

5.2.3 密碼分析 148

5.3 無線通信應用 148

5.4 本章習題 150

第 6 章 分組密碼 151

6.1 分組密碼模式 152

6.1.1 ECB 152

6.1.2 CBC 152

6.1.3 CFB 154

6.1.4 其他模式 155

6.2 費斯妥密碼結構 157

6.3 DES 159

6.3.1 初始置換與逆初始置換 161

6.3.2 輪函數 161

6.3.3 密鑰擴展 166

6.3.4 完整 DES 加密示例 168

6.3.5 解密步驟 169

6.3.6 密碼分析 170

6.4 AES 172

6.4.1 發展歷史 172

6.4.2 字節替代 174

6.4.3 行位移 178

6.4.4 列混淆 179

6.4.5 輪密鑰加 181

6.4.6 密鑰擴展 182

6.4.7 完整 AES 加密示例 185

6.4.8 應用場景 189

6.4.9 密碼分析 190

6.5 SM4 191

6.5.1 加密步驟 191

6.5.2 密鑰擴展 192

6.5.3 完整 SM4 加密示例 195

6.5.4 解密步驟 197

6.5.5 密碼分析 197

6.6 本章習題 198

第三部分 非對稱密碼學

第 7 章 RSA 加密算法 202

7.1 RSA 簡介 202

7.2 為何使用素數 204

7.2.1 整數分解難題 205

7.2.2 整數分解的難度 207

7.3 RSA 加密和解密 208

7.3.1 RSA 加密步驟 208

7.3.2 RSA 加密示例 210

7.3.3 在 ATM 上應用 RSA 211

7.3.4 飛參數據加密中的應用 212

7.4 密碼分析 212

7.4.1 RSA 安全性 212

7.4.2 維納攻擊 214

7.4.3 小公鑰指數攻擊 217

7.4.4 側通道攻擊 217

7.5 素數檢驗 219

7.5.1 試除法 220

7.5.2 AKS 素性檢驗 220

7.5.3 費馬素性檢驗 222

7.5.4 米勒-拉賓素性檢驗 226

7.5.5 Solovay-Strassen 素性檢驗 229

7.5.6 APRCL 素性檢驗 230

7.5.7 生成工業級素數 230

7.5.8 有了大素數，就一定安全嗎 232

7.6 本章習題 234

第 8 章 ElGamal 加密算法 236

8.1 迪菲-赫爾曼密鑰交換 236

8.1.1 密鑰交換步驟 237

8.1.2 中間人攻擊 238

8.1.3 零知識證明 238

8.2 離散對數問題 240

8.3 ElGamal 密碼 247

8.4 密碼分析 249

8.4.1 大步小步算法 250

8.4.2 Pollard's Rho 算法 252

8.4.3 中國剩餘定理 253

8.4.4 Pohlig-Hellman 算法 257

8.4.5 指數計算法 260

8.5 本章習題 261

第 9 章 橢圓曲線密碼 264

9.1 橢圓曲線 264

9.1.1 實數域上的橢圓曲線 264

9.1.2 有限域 GF (p) 上的橢圓曲線 268

9.1.3 有限域 GF (2n) 上的橢圓曲線 275

9.1.4 橢圓曲線離散對數問題 277

9.2 橢圓曲線 ElGamal 279

9.2.1 橢圓曲線迪菲-赫爾曼密鑰

交換 279

9.2.2 加密步驟 280

9.2.3 加密示例 282

9.2.4 圖像加密技術 283

9.3 SM2 284

9.3.1 SM2 簡介 284

9.3.2 加密步驟 285

9.3.3 解密步驟 287

9.4 標量乘法的快速算法 288

9.4.1 Double 和 Add 方法 288

9.4.2 非相鄰形式法 289

9.4.3 射影坐標 292

9.5 密碼分析 294

9.5.1 解決 ECDLP 294

9.5.2 密鑰長度 298

9.5.3 側通道攻擊 299

9.6 本章習題 300

第 10 章 格密碼 303

10.1 格 303

10.2 格距離問題 307

10.2.1 最短距離 307

10.2.2 最短向量問題 310

10.2.3 最近向量問題 312

10.3 格基規約算法 314

10.3.1 Gram-Schmidt 正交化 314

10.3.2 高斯算法 315

10.3.3 LLL 算法 318

10.4 GGH 公鑰密碼系統 322

10.4.1 加密步驟 322

10.4.2 Babai 算法 323

10.4.3 GGH 密碼示例 325

10.4.4 密碼分析 326

10.5 NTRU 328

10.5.1 捲積多項式模 328

10.5.2 加密步驟 332

10.5.3 安全性分析 336

10.6 本章習題 338

第 11 章 全同態加密 341

11.1 容錯學習問題 341

11.1.1 背景介紹 341

11.1.2 LWE 問題 342

11.1.3 基於 LWE 問題的加密

算法 344

11.1.4 環 LWE 347

11.1.5 基於環 LWE 問題的加密

算法 348

11.2 同態加密 349

11.3 全同態加密 351

11.3.1 全同態加密的定義 351

11.3.2 電路 353

11.4 BGV 全同態加密算法 354

11.4.1 同態基本加密算法 355

11.4.2 密鑰切換FHE.SwitchKey 356

11.4.3 模數切換 FHE.Moduli 357

11.4.4 BGV 算法過程 359

11.5 DGHV 全同態加密算法 361

11.5.1 近似 GCD 問題 362

11.5.2 DGHV 全同態加密方案 362

11.5.3 DGHV 全同態加密示例 365

11.6 其他全同態加密算法 367

11.7 本章習題 367

第四部分 數據完整性

第 12 章 哈希函數 370

12.1 什麽是哈希函數 370

12.2 哈希函數的實例 372

12.2.1 MD2 372

12.2.2 MD4 376

12.2.3 SHA-1 381

12.3 哈希函數的安全性 387

12.3.1 3 個安全問題 387

12.3.2 生日攻擊 389

12.4 本章習題 392

第 13 章 消息驗證碼 393

13.1 MAC 393

13.2 MAC 安全性分析 395

13.3 HMAC 397

13.4 CBC-MAC 399

13.5 隨機數的產生 402

13.5.1 真隨機數與偽隨機數 402

13.5.2 平方取中法與倍積取中法 405

13.5.3 線性同餘法與乘同餘法 405

13.5.4 密碼學安全偽隨機數

生成器 408

13.6 本章習題 411

第 14 章 數字簽名技術 413

14.1 數字簽名的發展 413

14.1.1 數字簽名的應用 414

14.1.2 數字簽名的基本性質 414

14.1.3 傳統簽名與數字簽名的區別 416

14.2 RSA 數字簽名方案 417

14.3 ElGamal 數字簽名方案 418

14.4 Schnorr 數字簽名方案 420

14.5 DSA 數字簽名方案 421

14.6 橢圓曲線數字簽名方案 422

14.7 GGH 數字簽名方案 425

14.8 數字簽名安全分析 427

14.8.1 唯密鑰攻擊 428

14.8.2 中間人攻擊 428

14.8.3 已知消息攻擊 428

14.8.4 選擇消息攻擊 429

14.8.5 偽造攻擊 429

14.9 證書 431

14.9.1 證書使用流程 431

14.9.2 實體驗證的方案 432

14.9.3 什麽是 SSL/TLS 432

14.9.4 為什麽需要 SSL/TLS 435

14.10 本章習題 435

參考文獻 437