密碼學教程 課件 -5-公鑰密碼

第五章公鑰密碼

5．1概述

5．2RSA公鑰加密算法

5．3ElGamal公鑰加密算法

5．4橢圓曲線上公鑰加密算法

5.5數(shù)字簽名

5.6

SM2

5.7*后量子密碼公開鑰明文密文私鑰明文秘密鑰秘密鑰明文密文明文5．1概述公鑰密碼與對稱密碼的比較：公鑰密碼：

不需共享密鑰；可證明安全；易產生數(shù)字簽名;速度慢、密鑰長.對稱密碼：

速度快，密鑰短，可作為基本單元構建各種密碼

工具,如偽隨機數(shù)產生器、Hash函數(shù)；

需要實現(xiàn)共享密鑰，密鑰管理困難；不具有（類似公鑰的）可證明安全性；對稱密碼：有效的大量數(shù)據加密和一些數(shù)據完整性應用。

因速度快（多次迭代輪函數(shù)，產生“隨機性”）。公鑰密碼與對稱鑰密碼的應用：公鑰密碼：產生有效的數(shù)字簽名，密鑰管理；

公鑰加密常用于加密對稱密鑰，這樣的系統(tǒng)

稱為混合密碼系統(tǒng)（密鑰封裝機制KEM）。主要用于認證主要用于加密

單向函數(shù)(OWF--onewayfunction)：

由x計算

y=f(x)是容易的，但反之是計算困難的。計算難易：

以“計算復雜性理論”為基礎。數(shù)論+計算陷門(trapdoor)單向函數(shù)：

有陷門（私鑰）可以求f的逆。

用于構造單向函數(shù)的（數(shù)論）計算困難問題：公鑰密碼對明文的處理方式：不是像分組密碼那樣依靠輪函數(shù)的多次迭代；公鑰密碼是依靠計算困難問題（構成的單向函數(shù)）。計算都是在一個代數(shù)結構中進行的，例如：

密碼的安全性在于：由公鑰找不到私鑰；不知道私鑰，由密文找不到明文。

一個155位十進制長（約500比特）的整數(shù)：1999年（網絡）分解為：當今分解技術更強。目前RSA的n至少1024比特長。同樣，ElGamal算法的素數(shù)p也應較大。128個字節(jié)。而AES的一個分組只16個字節(jié)2002年圖靈獎5．2

RSA公鑰加密算法第一個公鑰算法1978年

一、RSA算法：Rivest-Shamir-Adleman(1)選擇一對不同的大素數(shù)p和q，將p和q保密。

1.密鑰生成

2.加密過程3.解密過程解密過程的正確性：上面最后一個等式是因為：當m與n互素時，由歐拉定理可得；

這里是模q例題-1：（1）密鑰生成：p＝11,q=23,n=pq=11×23=253,

取e=3，gcd(3,220)=1，e為公鑰；由擴展歐幾里的算法求出3mod220的逆為d=147。（2）加密過程：

對于明文m=165，則密文（3）解密過程：

二、模冪和模逆算法模冪算法：例題-2：只要大于253，就模運算求剩余。因此平方后就進行mod運算。147＝128＋16＋3

＝10010011

為下一步做準備！x存放中間結果！從右到左迭代法！

x=xy

x=xy

x=xy

x=xy

再如：322mod12=9

上面的平方乘算法是“從右到左”，還有“從左到右”：

x的平方相當于指數(shù)上左移1位二進制；每次乘以m，速度快

模逆算法：

可以寫出迭代算法：

注意商放在哪一行！i022010173301211-73例題-1中3-1mod220，可由下表得出：

gcd(220,3)=1=220-73*3

3-1mod220=-73=147

三、RSA的安全性

所以p和q以上方程的解，此方程是容易解的。

強素數(shù)是p-1、p+1都有大素因子p1、p2，并且p1

1，p2

1還有大素因子。

4、e和d的選擇

e不能太小，應使其階最大。d應大于n的長度的1/4。

5、隨著計算能力的不斷增加和因子分解算法能力不斷提高，

p和q的選擇越來越大。目前較安全的RSA的n一般為

1024bit或2048bit。3、p和q應為安全素數(shù)或強素數(shù)。

p=2p1+1的素數(shù)為安全素數(shù)，其中p1為素數(shù)。

6、單純的RSA不能抵抗選擇密文攻擊。泄漏一些信息，如明文奇偶性，還有：同態(tài)特性

解：7101501221-11-23

161=7*23gcd(27,161)=1一、離散對數(shù)問題群元素的階：乘法群中滿足的最小正整數(shù)m。

稱為g在群中的階。是乘法群，群的階為6。循環(huán)群：群G的每一個元都是G的某一個固定元g的乘方。

g稱為G的生成元。

本原元：循環(huán)群中的生成元稱為域的本原元。性質：域的乘法群是一個循環(huán)群！5．3

ElGamal公鑰加密算法群中元素的個數(shù)。是域，3和5是它的本原元。例題-3：

例題-4：

對于一般離散對數(shù)問題，沒有有效算法（多項式時間的）。只有指數(shù)時間的算法，所以是困難的…….

明文空間為，密文空間為

對于任意明文，秘密隨機選取一個整數(shù),密文為：

二、ElGamal密碼體制

1.密鑰生成2.加密過程

3.解密過程

對任意密文明文為（1）選取素數(shù)p＝19，生成元

g=2

；

例題-5：A將（14，17）發(fā)送給B；

三、ElGamal密碼體制的安全性

2、素數(shù)p至少為300位十進制數(shù)；3、p-1至少有一個大素因子。

數(shù)論算法舉例：1、Miller-Rabin素性檢測算法2、Pollard整數(shù)分解算法3、二次篩和數(shù)域篩分解算法4、Baby-step-giant-step離散對數(shù)算法5、Pohlig–Hellman離散對數(shù)算法6、橢圓曲線（ECC）的方法7、類群（class

group）方法

等等（算法數(shù)論）一、有限域上的橢圓曲線(ellipticcurve)

橢圓曲線就是方程所確定的平面曲線。經過坐標變換可轉化為

系數(shù)在實數(shù)域R上的，稱為R上的橢圓曲線；（畫圖）

橢圓曲線上的點，關于定義的加法，構成交換群。5．4橢圓曲線上公鑰加密算法系數(shù)域的特征不是2，3實數(shù)域上的橢圓曲線才能畫出連續(xù)的曲線有限域（p為大于3的素數(shù)）上的橢圓曲線：由點再加上一個無窮遠點------所組成的集合E。保證有三個根可以在橢圓曲線上定義加法運算：對于任意點

設PQ直線的方程為：將帶入當P≠Q時：

根據根和系數(shù)的關系：因為PQ和E的第三個交點為：可以證明：橢圓曲線E關于加法構成一個交換群。當P＝Q時：的導數(shù)為

如何求出橢圓曲線的加法群？對每個x，計算再求同余方程：

階的證明例題-6：設p＝11，E是由下列方程確定的Z11上的橢圓曲線。試確定E的所有點。06681874258933974810454是否平方剩余06No18No25Yes4，733Yes5，648No54Yes2，968No74Yes2，989Yes3，897No104Yes2，900112439455363758994101或者：所以E的所有點為：

(2，4),(2，7),(3，5),(3，6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(10,2),(10,9),再加上無窮遠點O，共13個點。

設，計算：（5,2）同樣可計算：所以，的階是13，是循環(huán)群E的生成元。

橢圓曲線上的離散對數(shù)問題：設p>3是一個素數(shù)，E是有限域上的橢圓曲線，

設G是E的一個循環(huán)子群，二、橢圓曲線ElGamal公鑰密碼體制是G的一個生成元，求滿足已知的唯一整數(shù)n。加群！

ECC-ElGamal公鑰密碼體制:

加群的階數(shù)

系數(shù)不是模p，而是模加群的階數(shù)

三、橢圓曲線上公鑰密碼的特點

5.5數(shù)字簽名概述在密碼學中利用數(shù)字簽名和認證技術來實現(xiàn)信息完整性、認證性和不可否認性等。

發(fā)布消息（電子政務）電子銀行（電子商務）

用戶記帳（（支出＋日期）的簽名）電子現(xiàn)金（銀行的簽名）電子合同：

（條款＋日期）的簽名假定A發(fā)送一個對消息M的數(shù)字簽名給B，A的數(shù)字簽名應該滿足下述三個條件：（1）

B能夠證實A對消息M的簽名；（可驗證性）（2）

任何人都不能偽造A的簽名；（不可偽造性）（3）如果A否認對消息M的簽名，可通過仲裁解決A與B之間的爭議。（不可否認性、可仲裁性）Signature利用對稱鑰加密可以實現(xiàn)簽名，但需要一個可信第三方（TTP－TrustedThirdParty）

所以一般的簽名指得是公鑰體制實現(xiàn)的簽名：知道A和B的密鑰！利用私鑰簽名；利用公鑰驗證。附加功能的簽名：盲簽名、群簽名、代理簽名、指定驗證者簽名等等。數(shù)字簽名方案的三個部分：（1）密鑰生成：

生成簽名者所需的公私鑰對；（2）簽名過程：

對于m，利用私鑰進行簽名s=S(m)，輸出(m,s)；（3）驗證過程：

驗證者驗證簽名，如果驗證方程成立，則承認該簽名；

否則拒絕。簽名的實現(xiàn)過程：簽名算法(m,s)私鑰待簽名的消息摘要編碼Hash

驗證算法公鑰合格

一、RSA簽名方案實用中，如果A要求向B傳送加密的消息-簽名對，則A必須發(fā)送

而B收到密文后首先應當解密，得到A的消息-簽名對。

之后，B再驗證A的簽名是否有效。

簽名后再加密，即簽密方案（二步合在一起的專用方案）。

（1）若你截獲由A發(fā)給B的密文C=86，試求明文M；（2）若A對消息M進行簽名S，并發(fā)給B，試求簽名S；（3）若B收到了加密的簽名，求原來的明文和簽名是什么？如何判斷它的正確性？在一個RSA公鑰密碼體制中，已知A的公開密鑰是

B的公開密鑰是例題-8：解：（1）（注意：為防止算錯，應對求逆結果進行驗證?。?）（3）

可分別驗證與前面的結果一致。

i11=1011

0123

i7=111

012

i13=1101

0123（2）如果消息的簽名分別是，則任何知道的人都可以偽造對于消息的簽名

RSA簽名的安全性：

(1)對于任意，任何人都可以計算所以任何人都可以偽造對于隨機消息x

的簽名；（3）當消息較大時，先將消息進行hash函數(shù)變換。同樣前兩項的問題，也可以利用hash函數(shù)來解決。1.密鑰生成產生一個隨機大素數(shù)p，和一個乘法群的生成元g；選擇一個隨機數(shù)x，1≤x≤p-2，計算：y是公開密鑰（或者（p，g，y））；私鑰是x。2.簽名過程設m是待簽名的消息，選擇秘密隨機數(shù)k：二、ElGamal簽名方案

3.驗證過程

處于指數(shù)位置的量

例題-9：ElGamal簽名（2）簽名過程

若A對消息m=5進行簽名，秘密選取k=9（1）密鑰生成設p＝11，g＝2是Z11的本原元，選x＝8，則（3）驗證過程

所以簽名為（6，3）。三、Schnorr簽名方案

（使用Hash）1.密鑰生成過程

/∫no:r/

2.簽名過程3.驗證過程

mod

q形成指數(shù)位置上的數(shù)加密簽名RSAElGamalECC

5.6、SM22012年3月頒布中華人民共和國密碼行業(yè)標準GM/T0003-2012：《SM2橢圓曲線公鑰密碼算法》，共含5個文件，其中包含由橢圓曲線實現(xiàn)的數(shù)字簽名、密鑰協(xié)商和公鑰加密三個算法。SM2數(shù)字簽名算法（基于身份的密碼（標識密碼））

系統(tǒng)參數(shù)：

簽名者A對消息M的簽名過程為：

我國商用密碼標準SM9（2016/3）：

基于身份的密碼（標識密碼）；

利用橢圓曲線上雙線性對實現(xiàn)，也分數(shù)字簽名、密鑰協(xié)商和公鑰加密三個算法。美國NIST-PQC簽名算法（2022/8）：

CRYSTALS-Dilithium

Falcon

SPHINCS+5.7*

后量子密碼PQC

postquantumcryptography能抵抗量子攻擊的密碼，也稱抗量子計算密碼。量子算法：

Shor算法：利用量子傅里葉變換求元素階數(shù)，

可有效求解大數(shù)分解、離散對數(shù)等問題；

Grover算法：在集合中搜索指定元素，

可比經典搜索時間指數(shù)上快1/2；

Simon算法：有效求出周期函數(shù)的周期f(x)=f(x+s)