密碼學(xué)教程 課件 -5-公鑰密碼

第五章公鑰密碼

5．1概述

5．2RSA公鑰加密算法

5．3ElGamal公鑰加密算法

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

5.5數(shù)字簽名

5.6

SM2

5.7*后量子密碼公開(kāi)鑰明文密文私鑰明文秘密鑰秘密鑰明文密文明文5．1概述公鑰密碼與對(duì)稱密碼的比較：公鑰密碼：

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

速度快，密鑰短，可作為基本單元構(gòu)建各種密碼

工具,如偽隨機(jī)數(shù)產(chǎn)生器、Hash函數(shù)；

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

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

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

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

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

由x計(jì)算

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

以“計(jì)算復(fù)雜性理論”為基礎(chǔ)。數(shù)論+計(jì)算陷門(mén)(trapdoor)單向函數(shù)：

有陷門(mén)（私鑰）可以求f的逆。

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

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

一個(gè)155位十進(jìn)制長(zhǎng)（約500比特）的整數(shù)：1999年（網(wǎng)絡(luò)）分解為：當(dāng)今分解技術(shù)更強(qiáng)。目前RSA的n至少1024比特長(zhǎng)。同樣，ElGamal算法的素?cái)?shù)p也應(yīng)較大。128個(gè)字節(jié)。而AES的一個(gè)分組只16個(gè)字節(jié)2002年圖靈獎(jiǎng)5．2

RSA公鑰加密算法第一個(gè)公鑰算法1978年

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

1.密鑰生成

2.加密過(guò)程3.解密過(guò)程解密過(guò)程的正確性：上面最后一個(gè)等式是因?yàn)椋寒?dāng)m與n互素時(shí)，由歐拉定理可得；

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

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

對(duì)于明文m=165，則密文（3）解密過(guò)程：

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

＝10010011

為下一步做準(zhǔn)備！x存放中間結(jié)果！從右到左迭代法！

x=xy

x=xy

x=xy

x=xy

再如：322mod12=9

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

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

模逆算法：

可以寫(xiě)出迭代算法：

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

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

3-1mod220=-73=147

三、RSA的安全性

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

強(qiáng)素?cái)?shù)是p-1、p+1都有大素因子p1、p2，并且p1

1，p2

1還有大素因子。

4、e和d的選擇

e不能太小，應(yīng)使其階最大。d應(yīng)大于n的長(zhǎng)度的1/4。

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

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

1024bit或2048bit。3、p和q應(yīng)為安全素?cái)?shù)或強(qiáng)素?cái)?shù)。

p=2p1+1的素?cái)?shù)為安全素?cái)?shù)，其中p1為素?cái)?shù)。

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

解：7101501221-11-23

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

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

g稱為G的生成元。

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

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

例題-4：

對(duì)于一般離散對(duì)數(shù)問(wèn)題，沒(méi)有有效算法（多項(xiàng)式時(shí)間的）。只有指數(shù)時(shí)間的算法，所以是困難的…….

明文空間為，密文空間為

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

二、ElGamal密碼體制

1.密鑰生成2.加密過(guò)程

3.解密過(guò)程

對(duì)任意密文明文為（1）選取素?cái)?shù)p＝19，生成元

g=2

；

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

三、ElGamal密碼體制的安全性

2、素?cái)?shù)p至少為300位十進(jìn)制數(shù)；3、p-1至少有一個(gè)大素因子。

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

group）方法

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

橢圓曲線就是方程所確定的平面曲線。經(jīng)過(guò)坐標(biāo)變換可轉(zhuǎn)化為

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

橢圓曲線上的點(diǎn)，關(guān)于定義的加法，構(gòu)成交換群。5．4橢圓曲線上公鑰加密算法系數(shù)域的特征不是2，3實(shí)數(shù)域上的橢圓曲線才能畫(huà)出連續(xù)的曲線有限域（p為大于3的素?cái)?shù)）上的橢圓曲線：由點(diǎn)再加上一個(gè)無(wú)窮遠(yuǎn)點(diǎn)------所組成的集合E。保證有三個(gè)根可以在橢圓曲線上定義加法運(yùn)算：對(duì)于任意點(diǎn)

設(shè)PQ直線的方程為：將帶入當(dāng)P≠Q(mào)時(shí)：

根據(jù)根和系數(shù)的關(guān)系：因?yàn)镻Q和E的第三個(gè)交點(diǎn)為：可以證明：橢圓曲線E關(guān)于加法構(gòu)成一個(gè)交換群。當(dāng)P＝Q時(shí)：的導(dǎo)數(shù)為

如何求出橢圓曲線的加法群？對(duì)每個(gè)x，計(jì)算再求同余方程：

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

(2，4),(2，7),(3，5),(3，6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(10,2),(10,9),再加上無(wú)窮遠(yuǎn)點(diǎn)O，共13個(gè)點(diǎn)。

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

橢圓曲線上的離散對(duì)數(shù)問(wèn)題：設(shè)p>3是一個(gè)素?cái)?shù)，E是有限域上的橢圓曲線，

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

ECC-ElGamal公鑰密碼體制:

加群的階數(shù)

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

三、橢圓曲線上公鑰密碼的特點(diǎn)

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

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

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

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

B能夠證實(shí)A對(duì)消息M的簽名；（可驗(yàn)證性）（2）

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

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

生成簽名者所需的公私鑰對(duì)；（2）簽名過(guò)程：

對(duì)于m，利用私鑰進(jìn)行簽名s=S(m)，輸出(m,s)；（3）驗(yàn)證過(guò)程：

驗(yàn)證者驗(yàn)證簽名，如果驗(yàn)證方程成立，則承認(rèn)該簽名；

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

驗(yàn)證算法公鑰合格

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

而B(niǎo)收到密文后首先應(yīng)當(dāng)解密，得到A的消息-簽名對(duì)。

之后，B再驗(yàn)證A的簽名是否有效。

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

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

B的公開(kāi)密鑰是例題-8：解：（1）（注意：為防止算錯(cuò)，應(yīng)對(duì)求逆結(jié)果進(jìn)行驗(yàn)證！）（2）（3）

可分別驗(yàn)證與前面的結(jié)果一致。

i11=1011

0123

i7=111

012

i13=1101

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

RSA簽名的安全性：

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

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

3.驗(yàn)證過(guò)程

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

例題-9：ElGamal簽名（2）簽名過(guò)程

若A對(duì)消息m=5進(jìn)行簽名，秘密選取k=9（1）密鑰生成設(shè)p＝11，g＝2是Z11的本原元，選x＝8，則（3）驗(yàn)證過(guò)程

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

（使用Hash）1.密鑰生成過(guò)程

/∫no:r/

2.簽名過(guò)程3.驗(yàn)證過(guò)程

mod

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

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

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

簽名者A對(duì)消息M的簽名過(guò)程為：

我國(guó)商用密碼標(biāo)準(zhǔn)SM9（2016/3）：

基于身份的密碼（標(biāo)識(shí)密碼）；

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

CRYSTALS-Dilithium

Falcon

SPHINCS+5.7*

后量子密碼PQC

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

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

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

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

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

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