[XJTU計算機網(wǎng)絡安全與管理]——第五講公鑰加密算法

一、數(shù)論知識補充

素數(shù)

素數(shù)是除了1與自身無其他因子的數(shù)；它們無法被寫為數(shù)字的乘積；1一般不再考慮之內(nèi)

例如：2，3，5，7是素數(shù)，4，6，8，9不是

素數(shù)是數(shù)論研究的中心

200以內(nèi)的素數(shù)有：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

素因子

N的分解就是將N寫為其他數(shù)字的分解：n=a x b x c

分解一個數(shù)要比通過將因子相乘得到一個數(shù)要困難得多

素分解：因子都是素數(shù)

互質與最大公約數(shù)GCD

當兩個數(shù)最大公約數(shù)是1時稱兩個數(shù)互素

相反的，我們可以通過比較它們的素因子的最小階數(shù)得到

最大公約數(shù)可以用歐幾里得算法得到

費馬小定理——記住

a^p-1 mod p = 1 ，這里的p為素數(shù)且GCD(a,p)=1

3⁶ mod 7 = 1

在公鑰加密與素性檢驗中很有用

歐拉函數(shù)——記住

對于模n的算術運算

其完全剩余集為：0…n-1

將完全剩余集中與n互素的元素的個數(shù)稱為歐拉函數(shù)Euler Totient Function ?(n)——記住

例：n=10

完全剩余集為{0,1,2,3,4,5,6,7,8,9}

其中與n互素的為{1,3,7,9}

歐拉函數(shù)值為4

歐拉定理

費爾馬定理的推廣

若gcd(a,n)=1則對于任意的a，n有$a^{\Phi (n)}\mathrm{m}\mathrm{o}\mathrm{d}n=1$

舉例

1、a=3;n=10; ?(10)=4;

因此3⁴= 81 = 1 mod 10

2、a=2;n=11; ?(11)=10;

1~10都和11互素，一個素數(shù)p的歐拉函數(shù)值為p-1，費馬小定理是歐拉定理的特殊情況

因此2¹⁰= 1024 = 1 mod 11

素性檢驗

經(jīng)常被用來尋找大素數(shù)

傳統(tǒng)的方式是試除法：該方法通常用于較小的數(shù)字

實際應用中通常利用素數(shù)的統(tǒng)計學特征進行選擇：

測試所有的素數(shù)都滿足的特性

但有些合數(shù)也同樣滿足

素數(shù)大約是每ln n出現(xiàn)，由于可以忽略偶數(shù)所以實際上在n中平均下來看大約尋找一個素數(shù)需要的運算量是$0.5\ln n$

本原根

歐拉定理我們有：$a^{\Phi (n)}\mathrm{m}\mathrm{o}\mathrm{d}n=1$

考慮$a^m=1(\mathrm{m}\mathrm{o}\mathrm{d}n),\text{GCD}(a,n)=1$

M是一定存在的（因為可以$m=\Phi (n)$）

一旦階數(shù)達到m則出現(xiàn)循環(huán)

若$m=\Phi (n)$那么a被稱為本原根

若p為素數(shù)則連續(xù)不斷的a的階生成了模p的群。

二、公鑰密碼學

公鑰密碼與傳統(tǒng)密鑰比較

公鑰密碼學的引入

私鑰密碼學

傳統(tǒng)的私鑰加密使用單一的密鑰

發(fā)送方與接收方共享密鑰

若密鑰泄露則通信會出現(xiàn)泄密

是對稱的，當事雙方地位均等。因此無法避免當接收方偽造消息并聲稱來源于發(fā)送方

背景

對稱密鑰編碼所面臨的難題：

密鑰分配：通信密鑰太多，管理和分發(fā)困難。

數(shù)字簽名和認證。

密碼體制上的突破

Diffie & Hellman,“New Direction in Cryptography”,1976。

首次公開提出了“公開密鑰密碼編碼學”的概念。

這是一個與對稱密碼編碼截然不同的方案。

提出公開密鑰的理論時，其實用性并沒有又得到證明：

當時還未發(fā)現(xiàn)滿足公開密鑰編碼理論的算法；

直到1978 年，RSA 算法的提出。

公鑰密碼學

也許是3000年來密碼學發(fā)展史中最巨大的進步

使用兩個密鑰-私鑰與公鑰

非對稱，因此參與者地位不再相當

通過巧妙的利用數(shù)論觀念實現(xiàn)

是私鑰密碼學的補充而不是取代

為解決兩個關鍵性問題

1?? 密鑰分配（key distribution）-如何在不需要密鑰分配中心KDC的前提下安全通信

2?? 數(shù)字簽名-如何驗證消息來源于被聲稱的發(fā)送方

公開提出：Whitfield Diffie & Martin Hellman 1976

其實在60年代中期已在NSA中提出

公鑰密碼體制

公鑰/雙密鑰/非對稱密碼學涉及兩個密鑰

公鑰：可被所有人知道，可被用來加密消息與驗證簽名

私鑰：僅被接受者所知，用來解密消息與創(chuàng)建簽名。

拿私鑰加密就是創(chuàng)建簽名

公鑰加的密，私鑰解開；私鑰加的密，公鑰解開

該類算法被稱為非對稱因為：加密消息或驗證簽名的那一方無法解密消息或創(chuàng)建簽名

其主要步驟如下：

1?? 每一用戶產(chǎn)生一對密鑰，用來加密和解密消息。

2?? 每一用戶將其中一個密鑰存于公開的寄存器或其他可訪問的文件中，該密鑰稱為公鑰，另一密鑰是私有的。如圖9.1(a)所示，每一用戶可以擁有若干其他用戶的公鑰。

3?? 若Bob要發(fā)消息給Alice,則Bob用Alice的公鑰對消息加密。

4?? Alice收到消息后，用其私鑰對消息解密。由于只有Alice知道其自身的私鑰，所以其他的接收者均不能解密出消息。

利用這種方法，通信各方均可訪問公鑰，而私鑰是各通信方在本地產(chǎn)生的，所以不必進行分配。只要用戶的私鑰受到保護，保持秘密性，那么通信就是安全的。在任何時刻，系統(tǒng)可以改變其私鑰，并公布相應的公鑰以替代原來的公鑰。

在這種方法中，發(fā)送方首先用其私鑰對消息加密，得到數(shù)字簽名，然后再用接收方的公鑰加密，所得的密文只能被擁有相應私鑰的接收方解密，這樣可保證消息的保密性，但這種方法的缺點是，在每次通信中要執(zhí)行四次復雜的公鑰算法而不是兩次。

公鑰密碼算法的特征

公鑰密碼算法依賴于兩個密鑰，這里：

如果僅知道算法與加密密鑰那么要獲取解密密鑰在計算上是不可行的

當知道相應的加/解密密鑰時進行加解密運算在計算上是比較容易的

相關聯(lián)的兩個密鑰都可以被用來加密消息而另一個則被用來解密

公鑰密碼學的應用

通常被用在三個范疇

1?? 加密消息（提供安全性）

2?? 數(shù)字簽名（提供鑒別）

3?? 密鑰交換（會話密鑰）

公鑰密碼策略的安全性

像私鑰密碼算法一樣，采用暴力破解理論上是可行的。

密鑰非常長（512bit）（目前2048~3072bit）

安全性依賴于足夠大的加解密與密碼分析之間的難度差異

需要非常大的數(shù)字

相比于私鑰加密要慢

公鑰密碼算法基礎

單向函數(shù)：對于一個函數(shù)$f(x)$，如果對于其定義域上的任意 x，$f(x)$都容易計算，同時，對于其值域中幾乎所有的取值 y ，計算其逆函數(shù)$f^{?1}(y)$都是不可行的，則函數(shù)$f(x)$被稱為單向函數(shù)

可以提供單向函數(shù)的三大數(shù)學難題

大整數(shù)分解問題（簡稱IFP）；

離散對數(shù)問題（簡稱DLP）；

橢圓曲線離散對數(shù)問題（簡稱ECDLP）。

單向陷門函數(shù)：對于一個單向函數(shù)$f(x)$，如果其逆函數(shù)$f^{?1}(y)$在已知某些輔助信息的情況下容易求解得出，則稱該單向函數(shù)$f(x)$為單向陷門函數(shù)。

構造公鑰密碼系統(tǒng)的關鍵是如何在求解某個單向函數(shù)的逆函數(shù)的NP完全問題中設置合理的“陷門”

一些常用的公鑰密碼算法

基于因子分解問題的Rabin算法；

橢圓曲線公鑰算法；

基于有限域中離散對數(shù)難題的ElGamal公鑰密碼算法

基于代數(shù)編碼系統(tǒng)的McEliece公鑰密碼算法；

基于*“子集和”難題的Merkle-Hellman Knapsack**公鑰密碼算法；*

目前被認為安全的Knapsack型公鑰密碼算法Chor-Rivest

三、RSA算法——重點

Rivest, Shamir & Adleman of MIT in 1977

最為人所知與廣泛采用的公鑰策略

基于整數(shù)有限域中模p的指數(shù)運算

指數(shù)運算需要O((log n)³) （容易）

使用大整數(shù)（1024bits）

安全性來源于大整數(shù)的分解困難

分解需要$O(e^{\log n\log \log n})$（困難）

RSA密鑰的建立

用戶通過如下過程生成密鑰對

1?? 選擇兩個隨機的大素數(shù)p，q

2?? 計算它們的乘積（系統(tǒng)的模）$n=p\times q$

注意歐拉函數(shù)值$\Phi (n)=(p?1)(q?1)$

3?? 隨機選取加密密鑰e

這里

4?? 解下面的等式獲得解密密鑰d

$e.d=1\mathrm{m}\mathrm{o}\mathrm{d}\Phi (n)and0\le d\le n$

5?? 公開其公鑰： P U = { e ， n } PU=\{e，n\} PU={e，n}；保留私鑰： P R = { d ， n } PR=\{d，n\} PR={d，n}

RSA的使用

1?? 加密一條消息M，發(fā)送方需要：

獲取公鑰PU={e,n}

計算C = M^e mod n, where 0≤M<n

2?? 解密C，接收方需要

利用私鑰PR={d,n}

計算M = C^d mod n

3?? 必要的時候需要進行分塊

舉例

1?? $p=17\&q=11$

2?? $n=pq=17\times 11=187$

3?? $\Phi (n)=(p–1)(q?1)=16\times 10=160$

4?? $e:\text{gcd}(e,160)=1;e=7$

5?? $d:d?e=1\mathrm{m}\mathrm{o}\mathrm{d}160andd<160Valueisd=23since23\times 7=161=1\times 160+1$

6?? P U = { 7 , 187 } PU=\{7,187\} PU={7,187}

7?? P R = { 23 , 187 } PR=\{23,187\} PR={23,187}

加密解密過程如下：

選取M=88(88<187)

加密：$C=88^7\mathrm{m}\mathrm{o}\mathrm{d}187=11$

解密：$M=11^{23}\mathrm{m}\mathrm{o}\mathrm{d}187=88$

數(shù)學的破解有三種：

分解n，從而獲得?(n) 然后是 d

直接確定?(n) ，然后是d

直接d

目前大家覺得1024-2048bit是安全的。

四、Diffie-Hellman密鑰交換

第一個提出的公鑰類策略

Diffie&Hellman

是一個使用的公開交換密鑰的方法

在大量的商業(yè)應用中使用

該算法的有效性是建立在計算離散對數(shù)很困難的基礎上

算法

共享的參數(shù):

大素數(shù) q或多項式

一個 mod q的本原根a：即a mod q，a² mod q，… ，a^q-1 mod q各不相同

在這種方法中，素數(shù)q和本原根α是兩個公開的整數(shù)，假定用戶A和B希望交換密鑰，那么用戶A選擇一個隨機整數(shù)$X_A<q$，并計算$Y_A={\alpha }^{X_A}\mathrm{m}\mathrm{o}\mathrm{d}q$，類似的，用戶B也隨機選擇一個隨機整數(shù)$X_B<q$，并計算$Y_B={\alpha }^{X_B}\mathrm{m}\mathrm{o}\mathrm{d}q$

A和B保持其X是私有的，但是對另一方而言Y是公開訪問的，即$X_A和X_B$是私有的，$Y_A和Y_B$是公開的。

用戶A計算$K=(Y_B{)}^{X_A}\mathrm{m}\mathrm{o}\mathrm{d}q$并將其作為密鑰；用戶B計算$K=(Y_A{)}^{X_B}\mathrm{m}\mathrm{o}\mathrm{d}q$并將其作為密鑰，這兩種計算所得的結果相同。

至此雙方完成了密鑰的交換。通常這個秘密值被用于對稱密碼的密鑰?，F(xiàn)在考慮一個敵手能夠觀察到密鑰交換的全過程并且期望得到這個秘密K。由于X_A和X_B是私有的，所以攻擊者只能通過q，α，Y_A，Y_B來進行攻擊，這樣，他就必須求離散對數(shù)才能確定密鑰。例如，要對用戶B的密鑰進行攻擊，攻擊者就必須先計算
$$X_B=d{\log }_{\alpha ,q}(Y_B)$$
然后他就可以像用戶B那樣計算出密鑰K。
$$K=(Y_A{)}^{X_B}\mathrm{m}\mathrm{o}\mathrm{d}q$$
計算過程如下：

Diffie-Hellman密鑰交換的安全性建立在下述事實之上：求關于素數(shù)的模素數(shù)冪運算相對容易，而計算離散對數(shù)卻非常困難：對于大素數(shù)，求離散對數(shù)被認為是不可行的。

舉例說明

Alice 和 Bob 希望交換密鑰:

1?? 共享 q=353 與 α=3

2?? 選擇密鑰:

A 選擇X^A=97, B 選擇X^B=233

3?? 計算公鑰:

Y^A=3⁹⁷ mod 353 = 40 (Alice)

Y^B=3²³³ mod 353 = 248 (Bob)

4?? 會話密鑰:
$$\begin{gathered} K_{AB}=(Y_B{)}^{X_A}\mathrm{m}\mathrm{o}\mathrm{d}353=248^{97}\mathrm{m}\mathrm{o}\mathrm{d}353=160Alice計算得到 \\ {K}_{AB}=(Y_A{)}^{X_B}\mathrm{m}\mathrm{o}\mathrm{d}353=40^{233}\mathrm{m}\mathrm{o}\mathrm{d}353=160Bob計算得到 \end{gathered}$$

五、EIgamal 密碼體制——基于離散對數(shù)

與Diffie-Hellman一樣，ElGamal的系統(tǒng)用戶也是共同選擇一個素數(shù)q，α是q的素根。

?? 用戶A生成的密鑰對如下：

1?? 隨機生成整數(shù)X_A使得1<X_A<q-1。

2?? 計算$Y_A={\alpha }^{X_A}\mathrm{m}\mathrm{o}\mathrm{d}q$

3?? A的私鑰為$X_A$，公開密鑰為 { q , α , Y A } \{q,\alpha,Y_A\} {q,α,YA?}。

?? 其他任何用戶B通過A的公開密鑰可以加密信息：

1?? 將信息表示為一個整數(shù)M,其中1≤M≤q-1,以分組密碼序列的方式來發(fā)送信息，其
中每個分塊的長度不小于整數(shù)q。

2?? 選擇任意整數(shù)k,使得1≤k≤q-1。

3?? 計算一次密鑰$K=(Y_A{)}^k\text{mod}q$。

4?? 將M加密成明文對$(C_1,C_2)$,其中

$C_1={\alpha }^k\text{mod}q;C_2=KM\text{mod}q$

?? 用戶A恢復明文：

1?? 通過計算$K=(C_1{)}^{X_A}\text{mod}q$恢復密鑰。

2?? 計算$M=(C_2{K}^{?1})\text{mod}q$。

可用下一個圖進行說明：

若信息需要分組加密后發(fā)出則要求每個分組必須使用唯一的$k$，否則對手可用一個已知的分組M₁計算其他

六、橢圓曲線密碼體制

優(yōu)點：

密鑰尺度較?。?/p>

參數(shù)選擇較靈活；

具有由數(shù)學難題保證的安全性；

實現(xiàn)速度較快。

參考資料

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

[2] 密碼編碼學與網(wǎng)絡安全（第七版），William Stallings著，王后珍等譯文章來源地址http://www.zghlxwxcb.cn/news/detail-426597.html

到了這里，關于[XJTU計算機網(wǎng)絡安全與管理]——第五講公鑰加密算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！