了得網工業技術_格理論與密碼學

內容簡介

《格理論與密碼學》主要介紹格理論中的基礎理論、關鍵技術及其在密碼學中的典型應用。主要包括三方面內容：格理論與密碼學的基礎知識，包括數論基礎、抽像代數基礎、向量空間、對稱密碼體制、公鑰密碼體制、哈希函數等；格理論的基礎理論和關鍵技術，包括格的基本定義、格中的計算性難題、短向量問題、近向量問題、二維格中的高斯格基約減算法、LLL格基約減算法及其衍生和變形、LLL與apprCVP問題以及格基約減算法的MATLAB實現；格理論在密碼學中的典型應用，包括基於格的密碼繫統分析方法以及基於格理論的哈希函數。

《格理論與密碼學》可供從事信息安全、密碼學、數學、計算機、通信等專業的科技人員參考，也可供高等院校相關專業的師生參考。

前言
第1章數學基礎
1.1 數論基礎
1.1.1 整除性和公因子
1.1.2 模運算
1.1.3 中國剩餘定理
1.1.4 利用中國剩餘定理求解二次同餘式
1.1.5 分解性和有限域
1.1.6 有限域中的乘方和原根
1.2 抽像代數基礎
1.2.1 群
1.2.2 環
1.2.3 可約性和商環
1.2.4 多項式環與歐幾裡得算法前言
第1章數學基礎
1.1 數論基礎
1.1.1 整除性和公因子
1.1.2 模運算
1.1.3 中國剩餘定理
1.1.4 利用中國剩餘定理求解二次同餘式
1.1.5 分解性和有限域
1.1.6 有限域中的乘方和原根
1.2 抽像代數基礎
1.2.1 群
1.2.2 環
1.2.3 可約性和商環
1.2.4 多項式環與歐幾裡得算法
1.2.5 多項式環的商和素數階有限域
1.2.6 卷積多項式環
1.3 向量空間
1.3.1 基本概念
1.3.2 範數與正交基
習題
第2章密碼學
2.1 對稱密碼體制
2.1.1 對稱密碼體制原理
2.1.2 DES算法
2.1.3 AES算法
2.2 公鑰密碼體制
2.2.1 公鑰密碼體制的產生
2.2.2 公鑰密碼體制原理
2.2.3 Diffie-Hellman密鑰交換協議
2.2.4 RSA密碼繫統
2.2.5 ElGamal密碼繫統
2.2.6 橢圓曲線密碼繫統
2.3 哈希函數
習題
第3章格的定義與相關性質
3.1 格的基本定義
3.2 格中的計算性難題
3.3 短向量問題
3.3.1 Hermite定理和Minkowski定理
3.3.2 高斯啟發式
3.4 近向量問題
習題
第4章格基約減算法與實現
4.1 二維格中的高斯格基約減算法
4.2 LLL格基約減算法及其衍生和變形
4.2.1 LLL格基約減算法
4.2.2 LLL算法的衍生和變形
4.3 LLL與apprCVP問題
4.4 格基約減算法的MATLAB實現
4.4.1 基本函數
4.4.2 計算Hadamard比率函數
4.4.3 生成優質基函數
4.4.4 計算矩陣的行範數函數
4.4.5 向量正交化函數
4.4.6 LLL算法的實現
習題
第5章格理論在密碼學中的應用
5.1 基於格難題的密碼繫統
5.1.1 概述
5.1.2 GGH公鑰密碼繫統
5.1.3 基於格的GGH密碼學分析
5.2 同餘密碼繫統及分析
5.2.1 同餘密碼繫統
5.2.2 基於格的同餘密碼學分析
5.3 背包密碼繫統及分析
5.3.1 背包問題
5.3.2 超遞增序列背包
5.3.3 MH背包公鑰密碼繫統
5.3.4 基於格的背包密碼學分析
5.4 NTRU密碼繫統及分析
5.4.1 NTRU密碼繫統
5.4.2 NTRU的安全性
5.4.3 基於格的NTRU密碼學分析
習題
第6章基於格理論的哈希函數及應用
6.1 預備知識
6.1.1 抗踫撞哈希函數
6.1.2 Merkle樹
6.1.3 認證數據結構概述
6.2 基於格理論的哈希函數
6.2.1 LBH的數學基礎
6.2.2 LBH的基本結構
6.2.3 LBH的安全性
6.2.4 LBH的代價分析
6.3 基於LBH的更新優化認證數據結構
6.3.1 LBH-UOADS基本思想
6.3.2 LBH-UOADS構建方案
6.3.3 LBH-UOADS的關鍵算法
6.3.4 LBH-UOADS的正確性和安全性證明
6.3.5 LBH-UOADS的代價分析
6.4 基於LBH-UOADS的數據查詢認證方案
6.4.1 數據查詢認證框架
6.4.2 查詢認證過程
6.4.3 安全性分析
6.4.4 代價分析和比較
習題
參考文獻

在線試讀

第1 章數學基礎
本章將介紹本書用到的一些基本的數學概念和符號。1.1 節和1.2 節分別簡
要介紹數論和抽像代數的基礎知識，對這些內容不熟悉的讀者可以參考更詳細的
參考書籍；1.3 節主要介紹定義在?m 上的向量空間的概念和性質。充分理解本
章內容對於其餘各章的學習是非常必要的。
1.1 數論基礎
數論和代數學是現代密碼學的基礎。本節將介紹數論中的一些重要定理和
結論。數論是研究整數性質的一個數學分支，其研究對像是整數（自然數）。整數
在計算機科學、密碼學與信息安全、數字信號處理等領域起到了重要的作用。本
節將介紹整除性和整數的分解，帶餘除法以及求解公因子的相關算法；並介
紹模運算的運算法則與性質，以及求解線性同餘方程組的方法；此外還介紹了素
數、有限域、模除法運算的概念；後介紹了有限域中的乘方和原根的性質。
1.1.1 整除性和公因子
若a ，b 是整數，則可以分別計算a + b ，a - b ，a ? b ，且所得結果均是整數。這
種性質素運算的封閉性。
但是對除法運算並不能總是滿足這種運算封閉性。例如，不能用2 去除3 ，因
為3/2 並不是整數，由此引出了整除性的基本概念。
定義1.1 設a ，b 是整數，b ≠ 0 。若存在整數c ，滿足a ＝ bc ，則稱b 整除a 或a
被b 整除，記為b｜ a 。第1 章數學基礎

本章將介紹本書用到的一些基本的數學概念和符號。1.1 節和1.2 節分別簡

要介紹數論和抽像代數的基礎知識，對這些內容不熟悉的讀者可以參考更詳細的

參考書籍；1.3 節主要介紹定義在?m 上的向量空間的概念和性質。充分理解本

章內容對於其餘各章的學習是非常必要的。

1.1 數論基礎

數論和代數學是現代密碼學的基礎。本節將介紹數論中的一些重要定理和

結論。數論是研究整數性質的一個數學分支，其研究對像是整數（自然數）。整數

在計算機科學、密碼學與信息安全、數字信號處理等領域起到了重要的作用。本

節將介紹整除性和整數的分解，帶餘除法以及求解公因子的相關算法；並介

紹模運算的運算法則與性質，以及求解線性同餘方程組的方法；此外還介紹了素

數、有限域、模除法運算的概念；後介紹了有限域中的乘方和原根的性質。

1.1.1 整除性和公因子

若a ，b 是整數，則可以分別計算a + b ，a - b ，a ? b ，且所得結果均是整數。這

種性質素運算的封閉性。

但是對除法運算並不能總是滿足這種運算封閉性。例如，不能用2 去除3 ，因

為3/2 並不是整數，由此引出了整除性的基本概念。

定義1.1 設a ，b 是整數，b ≠ 0 。若存在整數c ，滿足a ＝ bc ，則稱b 整除a 或a

被b 整除，記為b｜ a 。

命題1.1 設a ，b ，c ∈ ￠，則有

（1）若a｜ b ，b｜ c ，則a｜ c ；

（2）若a｜ b ，b｜ a ，則a ＝ ± b ；

（3）若a｜ b ，a｜ c ，則a｜（ b + c）且a｜（ b - c）。

定義1.2 a 和b 的公因子是能夠同時整除二者的正整數。顧名思義，公

因子就是滿足d｜ a ，d｜ b 的的正整數d ，用gcd（ a ，b）來表示。在不存在歧義的

情況下也可以表示成（ a ，b）。

公因子的概念雖然簡單，但有很多應用。下面介紹幾種計算公因子

的方法。

定義1.3（帶餘除法）設a ，b 是正整數，則存在的q 和r 滿足

a ＝ b ? q + r ，0 ≤ r ＜ b

若求a 和b 的公因子，首先對a 作帶餘除法，即

a ＝ b ? q + r ，0 ≤ r ＜ b

若d 是a 和b 的公因子，則d 也能夠整除r ；若e 是b 和r 的公因子，e 也能夠

整除a 。換言之，有

gcd（ a ，b）＝ gcd（ b ，r）

重復此過程，對b 作帶餘除法，即

b ＝ r ? q′ + r′ ，0 ≤ r′ ＜ r

則有

gcd（ b ，r）＝ gcd（ r ，r′）

此過程將使餘數越來越小，終為0 ，此時有

gcd（ s ，0）＝ s ＝ gcd（ a ，b）

這種方法常稱為輾轉相除法，或歐幾裡得算法。

定理1.1（歐幾裡得算法）設a ，b 是正整數（ a ≥ b），下述算法能夠在有限步

內計算出gcd（ a ，b）：

（1）設r0 ＝ a ，r1 ＝ b ；

（2）令i ＝ 1 ；

（3）對ri - 1 作帶餘除法，ri - 1 ＝ ri ? qi + ri + 1 ，0 ≤ ri + 1 ＜ ri ；

（4）若ri + 1 ＝ 0 ，則ri ＝ gcd（ a ，b），算法結束；

（5）若ri + 1 ＞ 0 ，令i ＝ i + 1 ，轉到第（3）步。

其中，第（3）步多執行2log2 b + 1 次。

證明定理1.1 所進行的帶餘除法過程可以用下列步驟來表示：

a ＝ b ? q1 + r2 ，0 ≤ r2 ＜ b

b ＝ r2 ? q2 + r3 ，0 ≤ r3 ＜ r2

r2 ＝ r3 ? q3 + r4 ，0 ≤ r4 ＜ r3

r3 ＝ r4 ? q4 + r5 ，0 ≤ r5 ＜ r4

?

rt - 2 ＝ rt - 1 ? qt - 1 + rt ，0 ≤ rt ＜ rt - 1

rt - 1 ＝ rt ? qt

rt ＝ gcd（ a ，b）

ri 的值嚴格遞減，當ri + 1 ＝ 0 時算法結束。這就證明了算法能夠在有限步內結束。

此外，在迭代過程中有

ri - 1 ＝ ri ? qi + ri + 1 ，0 ≤ ri + 1 ＜ ri

這表明

gcd（ ri - 1 ，ri ）＝ gcd（ ri ，ri + 1 ），i ＝ 1 ，2 ，3 ，…

當rt + 1 ＝ 0 時，有rt - 1 ＝ rt ? qt ，故

gcd（ rt - 1 ，rt ）＝ gcd（ rt ? qt ，rt ）＝ rt

再由迭代等式可知

gcd（ a ，b）＝ rt

也就是說後一個不為零的餘數就是a 和b 的公因子。

證畢

下面分析算法的效率。因為ri 的值嚴格遞減，且r1 ＝ b ，故算法多執行b 步

就能夠終止。然而，這樣求出的隻是一個上界。注意，隨著步驟（3）的每兩次迭

代，ri 的值至少能夠減半：ri + 2 ＜ 1

2 ri ，i ＝ 0 ，1 ，2 ，… 。下面分兩種情況證明此不

等式。

情況1 ：ri + 1 ≤ 1

2 ri 。

由於ri 嚴格遞減，故

ri + 2 ＜ ri + 1 ≤ 1

2 ri

情況2 ：ri + 1 ＞ 1

2 ri 。

考慮ri + 1 除ri ，即

ri ＝ ri + 1 ? 1 + ri + 2

則有

ri + 2 ＝ ri - ri + 1 ＜ ri - 1

2 ri ＝ 1

2 ri

綜合兩種情況，能夠證明

ri + 2 ＜ 1

2 ri ，i ＝ 0 ，1 ，2 ，…

反復利用這個等式將得

r2 k + 1 ＜ 1

2 r2 k - 1 ＜ 1

4 r2 k - 3 ＜ 1

8 r2 k - 5 ＜ 1

16 r2 k - 7 ＜ … ＜ 1

2k r1 ＝ 1

2k b

因此，若有2k ≥ b ，則

r2 k + 1 ＜ 1 痴r2 k + 1 ＝ 0

算法結束。

在定理證明過程中，rt + 1 ＝ 0 ，則t + 1 ≤ 2 k + 1 痴t ≤ 2 k ，且在上述算法中共執行

了t 次除法，故歐幾裡得算法至多在2 k 次迭代後結束。選取滿足2k ≥ b ＞ 2k - 1 的

小的k ，則迭代次數≤ 2 k ＝ 2（ k - 1） + 2 ＜ 2log2 b + 2 。

上述定理證明了歐幾裡得算法至多執行2log2 b + 1 次迭代。然而，這個估計

值可以被改進。已有文獻證明，迭代次數不超過1.45log2 b + 1.68 ，且對於隨機選

取的a 和b ，平均迭代次數約為0.85log2 b + 0.14 。

定理1.2（擴展的歐幾裡得算法）設a ，b 是正整數，存在u ，v 滿足

au + bv ＝ gcd（ a ，b）

證明從歐幾裡得算法得知

a ＝ b ? q1 + r2

將其代入

b ＝ r2 ? q2 + r3

可得

b ＝（ a - b ? q1 ） ? q2 + r3

故

r3 ＝ - a ? q2 + b ? （1 + q1 q2 ）

再將結果代入

r2 ＝ r3 ? q3 + r4

終得

a - b ? q1 ＝［ - a ? q2 + b ? （1 + q1 q2 ）］ q3 + r4

整理可得

r4 ＝ a ? （1 + q2 q3 ） - b ? （ q1 + q3 + q1 q2 q3 ）

即為r4 ＝ a ? u + b ? v 的形式。

重復此過程將得

rt ＝ a ? u + b ? v ＝ gcd（ a ，b）

證畢

定義1.4 設a ，b 是整數，當gcd（ a ，b）＝ 1 時，稱a 和b 互素。

一般地，可以在等式A u + B v ＝ gcd（ A ，B）兩端同除gcd（ A ，B），得

A

gcd（ A ，B） u + B

gcd （ A ，B） v ＝ 1

則A

gcd（ A ，B）和B

gcd（ A ，B）互素。

1.1.2 模運算

本小節介紹模運算的概念和相關性質。

定義1.5 設m 為自然數，a 和b 是任意整數，如存在關繫a ＝ b + km ，其中k

為整數，則定義a ≡ b（modm），其含義為：b 是a 除以m 的餘數（ b 為a 模m 的餘

數，或a 與b 模m 同餘）。

定義1.6 amodm 表示a 模m 運算，表示a 除以m 的餘數，其值能夠取遍0

到m - 1 之間的整數。

例如，（7 + 8）mod12 ＝ 15mod12 ＝ 3 ，也可表示成：15 ≡ 3（mod12）。

模運算（ + ，- ，× ）滿足交換律、結合律和分配律。按模運算原理：對中間結

果做模運算，與做完全部運算後再做模運算的所得結果相同。

命題1.2 設整數m ≥ 1 ，則有

（1）若a1 ≡ a2 （modm），b1 ≡ b2 （modm），則a1 ± b1 ≡ a2 ± b2 （modm），且a1 ? b1 ≡

a2 ? b2 （modm）。

（2）設a 為整數，當且僅當gcd（ a ，m）＝ 1 時，存在整數b 滿足a ? b ≡ 1

（modm）。若這樣的b 存在，稱其為a 模m 的，也可以是a- 1 表示a。

證明

（1）設

a1 ＝ a2 + k1 m ，b1 ＝ b2 + k2 m

則

a1 ± b1 ＝ a2 ± b2 + （ k1 ± k2 ） m

即

a1 ± b1 ≡ a2 ± b2 （modm）

對於a1 ? b1 ≡ a2 ? b2 （modm），有

a1 ? b1 ＝（ a2 + k1 m） ? （ b2 + k2 m）＝ a2 ? b2 + （ k1 b2 + k2 a2 + k1 k2 m） ? m

即

a1 ? b1 ≡ a2 ? b2 （modm）

（2）必要性：設gcd（ a ，m）＝ 1 ，由定理1.2 知，存在整數b ，v 滿足ab + mv ＝ 1 ，

即ab - 1 ＝ - mv ，能夠被m 整除，由同餘定義知ab ＝ 1（modm）。

充分性：設a 存在模，即a ? b ≡ 1（modm），則存在整數c 使得ab - cm ＝ 1 。

又因為gcd（ a ，m）能夠整除ab - cm ＝ 1 ，故gcd（ a ，m）＝ 1 。

證畢

當除數與模m 互素時，可以進行模除法運算。例如，已知7 - 1 ≡ 8（mod11），計

算

5

7 ＝ 5 ? 7 - 1 ≡ 5 ? 8 ≡ 40 ≡ 7（mod11）。

繼續討論模運算的性質。若對a 做帶餘除法a ＝ m ? q + r ，0 ≤ r ＜ m 。這表明

滿足a ≡ r（modm）的r 能夠取0 到m - 1 之間的所有整數。所以，若要研究模m

的整數，隻需要取0 ≤ r ＜ m 即可。這就引出了同餘類的概念。

定義1.7 記整數模m 同餘類環為

￠ / m ￠＝｛0 ，1 ，2 ，… ，m - 1｝

注意到在同餘類環中所進行的運算，所得結果均需模m 以保持運算的封

閉性。

定義1.8 命題1.2 中的命題（2）證明了若gcd（ a ，m）＝ 1 ，則a 存在模m 的乘

集合：

（￠ / m ￠）倡＝｛ a ∈ ￠ / m ￠：gcd（ a ，m）＝ 1｝

集合（￠ / m ￠）倡稱為整數模m 單位群。

例1.1 整數模24 單位群為（￠ /24 ￠）倡＝｛1 ，5 ，7 ，11 ，13 ，17 ，19 ，23｝；整數模

7 單位群為（￠ /7 ￠）倡＝｛1 ，2 ，3 ，4 ，5 ，6｝。

密碼學領域中很重要的一個問題就是如何表示（￠ / m ￠）素個數。定

義這個量為歐拉函數。

定義1.9 歐拉函數表示（￠ / m ￠）素的個數，記為

?（ m）＝ # （￠ / m ￠）倡＝ # ｛0 ≤ a ＜ m ：gcd（ a ，m）＝ 1｝

從例1.1 中可得，?（24）＝ 8 ，?（7）＝ 6 。

1.1.3 中國剩餘定理

在一千多年前的?孫子算經?中，有這樣一道算術題：今有物不知其數，三三數

之剩二，五五數之剩三，七七數之剩二，問物幾何？按照今天的話來說就是：一個

數除以3 餘2 ，除以5 餘3 ，除以7 餘2 ，求這個數。

這樣的問題，也有人稱為“韓信點兵” 。它形成了一類問題：初等數論中如何

解線性同餘式。這類問題的有解條件和解的方法被稱為“中國剩餘定理”或“孫子

定理” 。

簡單的情形是隻有兩個同餘式

x ≡ a（modm）和x ≡ b（modn） gcd（ m ，n）＝ 1

則由中國剩餘定理可得上述方程組有解。下面來看一個簡單的例子。

例1.2 求下面同餘方程組的解：

x ≡ 1（mod5）

x ≡ 9（mod11）

（1.1）

解由模運算的定義可知個等式的解具有以下形式：

x ＝ 1 + 5 y ，y ∈ ￠（1.2）

將式（1.2）代入式（1.1）的第2 個等式可得

1 + 5 y ≡ 9（mod11）

因此

5 y ≡ 8（mod11）（1.3）

為了解出y ，將式（1.3）兩端乘以5（mod11）的9 ，即

y ≡ 9 ? 8 ≡ 72 ≡ 6（mod11）

將y 的值代入到式（1.2）中，終算出

商品搜索

商品分类

【醫學】

【各大出版社】