現(xiàn)代密碼學(xué)(第二版)-第5章-公鑰密碼新課件

第5章公鑰密碼2023/9/181第5章公鑰密碼2023/8/61主要內(nèi)容公鑰密碼的理論基礎(chǔ)RSA公鑰密碼大素?cái)?shù)的生成EIGamal公鑰密碼橢圓曲線上的Menezes-Vanstone公鑰密碼2023/9/182主要內(nèi)容公鑰密碼的理論基礎(chǔ)RSA公鑰密碼大素?cái)?shù)的生成EIG5.1公鑰密碼的理論基礎(chǔ)在公鑰密碼中,加密密鑰和解密密鑰是不一樣的。加密密鑰簡(jiǎn)稱公鑰(publickey),

解密密鑰簡(jiǎn)稱私鑰(privatekey)。加密密鑰可以公開,

解密密鑰當(dāng)然必須保密。

定義5.1設(shè)f是一個(gè)函數(shù).如果對(duì)任意給定的x,計(jì)算y使得y=f(x)是容易的,但對(duì)任意給定的y,計(jì)算x使得f(x)=y是難解的,即求f的逆函數(shù)是難解的,則稱f是一個(gè)單向函數(shù)(one-wayfunction)。定義5.2設(shè)f是一個(gè)函數(shù),t是與f有關(guān)的一個(gè)參數(shù).對(duì)任意給定的x,計(jì)算y使得y=f(x)是容易的.如果當(dāng)不知參數(shù)t時(shí),計(jì)算f的逆函數(shù)是難解的,但當(dāng)知道參數(shù)t時(shí),計(jì)算f的逆函數(shù)是容易的,則稱f是一個(gè)陷門單向函數(shù)(trapdoorone-wayfunction),參數(shù)t稱為陷門.2023/9/1835.1公鑰密碼的理論基礎(chǔ)在公鑰密碼中,加密密鑰和解密密5.2

RSA公鑰密碼中國(guó)剩余定理Euler函數(shù)Euler

定理和Fermat小定理RSA

公鑰密碼體制RSA

的安全性討論模n

求逆的算法模n

的大數(shù)冪乘的快速算法.因子分解2023/9/1845.2RSA公鑰密碼中國(guó)剩余定理Euler函數(shù)Eul5.2.1

中國(guó)剩余定理定義5.3

設(shè)a、b、m都是整數(shù).如果m|(a-b)，則稱a和b模m同余，記為a≡b(modm)，m稱為這個(gè)同余式的模。定理5.1(中國(guó)剩余定理)

設(shè)是兩兩互素的正整數(shù).設(shè)是整數(shù),則同余方程組模有唯一解2023/9/1855.2.1中國(guó)剩余定理定義5.3設(shè)a、b、m都是5.2.2

Euler

函數(shù)定義5.4

設(shè)n是一個(gè)正整數(shù)稱為Euler函數(shù).Euler函數(shù)是定義在正整數(shù)集合上的函數(shù).顯然,為小于n并且與n互素的非負(fù)整數(shù)的個(gè)數(shù).定理5.2

如果

和

互素,則定理5.3

如果其中，為不同的素?cái)?shù)為正整數(shù),則定理5.4

設(shè)n是一個(gè)正整數(shù),則2023/9/1865.2.2Euler函數(shù)定義5.4設(shè)n是一個(gè)正5.2.3

Euler定理和Fermat小定理定理5.5

(Euler定理)

設(shè)x和n都是正整數(shù).如果gcd(x;n)=1,則推論5.1(Fermat小定理)

設(shè)x和p都是正整數(shù).如果p是素?cái)?shù)并且gcd(x;p)=1,則定理5.6(Fermat小定理)

設(shè)x和p都是正整數(shù).如果p是素?cái)?shù),則2023/9/1875.2.3Euler定理和Fermat小定理定理5.55.2.4

RSA公鑰密碼體制選取兩個(gè)大素?cái)?shù)p和q，p和q保密計(jì)算，公開，保密隨機(jī)選取正整數(shù)1<e<，滿足

e

是公開的加密密鑰計(jì)算d，滿足

。d是保密的解密密鑰加密變換：對(duì)明文

密文為解密變換：對(duì)密文明文為RSA

公鑰密碼體制描述如下：2023/9/1885.2.4RSA公鑰密碼體制選取兩個(gè)大素?cái)?shù)p和q，5.2.5

RSA的安全性討論

RSA公鑰密碼體制的安全性是基于大整數(shù)的素分解問(wèn)題的難解性。盡管尚未在理論上嚴(yán)格證明因子分解問(wèn)題一定是難解的,但經(jīng)過(guò)長(zhǎng)期的研究迄今沒(méi)有找到一個(gè)有效算法的事實(shí),使得因子分解問(wèn)題成為眾所周知的難題。這是RSA公鑰密碼體制建立的基礎(chǔ)。2023/9/1895.2.5RSA的安全性討論RSA公鑰密碼體制的安5.2.6

模n求逆的算法設(shè)n和u都是正整數(shù)，u<n。u模n的逆就是滿足的整數(shù)v，0<v<n。

定理5.7

設(shè)n是一個(gè)正整數(shù)，對(duì)于存在使得的充分必要條件是gcd(u;n)=1。2023/9/18105.2.6模n求逆的算法設(shè)n和u都是正整數(shù)，u5.2.7

模n的大數(shù)冪乘的快速算法如果b=0，則輸出結(jié)果c，結(jié)束如果bmod2≠0，則轉(zhuǎn)到第5步轉(zhuǎn)第3步.

轉(zhuǎn)第5步計(jì)算的快速算法2023/9/18115.2.7模n的大數(shù)冪乘的快速算法如果b=0，則5.2.8

因子分解a←2計(jì)算d←gcd(a?1，n)。p?1因子分解算法描述如下輸入奇整數(shù)n，輸入整數(shù)B對(duì)j=2到B，計(jì)算如果1<d<n，則d是n的因子，對(duì)n因子分解成功；否則，沒(méi)找到n的因子，對(duì)n因子分解失敗2023/9/18125.2.8因子分解a←2計(jì)算d←gcd(a?5.3

大素?cái)?shù)的生成模奇素?cái)?shù)的平方剩余Legendre符號(hào)Jacobi

符號(hào)Solovay-Strassen

素性測(cè)試法Miller-Rabin素性測(cè)試法素?cái)?shù)的分布2023/9/18135.3大素?cái)?shù)的生成模奇素?cái)?shù)的平方剩余Legendre符號(hào)5.3.1素?cái)?shù)的分布定理5.8

存在無(wú)窮多個(gè)素?cái)?shù)。定理5.9(素?cái)?shù)定理)

設(shè)x>0,π(x)為不大于x的素?cái)?shù)的個(gè)數(shù),則素?cái)?shù)的分布極不均勻，素?cái)?shù)越大，分布越稀疏。2023/9/18145.3.1素?cái)?shù)的分布定理5.8存在無(wú)窮多個(gè)素?cái)?shù)。定理5.3.2模奇素?cái)?shù)的平方剩余定義5.5

設(shè)p>2是一個(gè)素?cái)?shù),a是一個(gè)整數(shù),gcd(a，p)=1.如果同余方程X2≡a(modp)有解則稱a是模p的平方剩余(quadraticresidue);否則,稱a是模p的平方非剩余(quadraticnon-residue).定理5.10(Euler準(zhǔn)則)

設(shè)p>2是一個(gè)素?cái)?shù),x是一個(gè)整數(shù),gcd(x;p)=1,則1)x是模p的平方剩余當(dāng)且僅當(dāng)2)x是模p的平方非剩余當(dāng)且僅當(dāng)2023/9/18155.3.2模奇素?cái)?shù)的平方剩余定義5.5設(shè)p>25.3.3

Legendre

符號(hào)定義5.6

設(shè)p>2是一個(gè)素?cái)?shù).對(duì)任意整數(shù)a,若a≡

0(modp)若a是模p的平方剩余若a是模p的非平方剩余定理5.11

設(shè)p>2是一個(gè)素?cái)?shù),則對(duì)任意整數(shù)a,定理5.12

設(shè)p>2是一個(gè)素?cái)?shù)。如果m1≡m2(modp)，則定理5.13

設(shè)p>2是一個(gè)素?cái)?shù),q>2也是一個(gè)素?cái)?shù)，p≠

q2023/9/18165.3.3Legendre符號(hào)定義5.6設(shè)p>5.3.4

Jacobi

符號(hào)定義5.7

設(shè)n>2是一個(gè)奇整數(shù),n的素分解為其中是素?cái)?shù),對(duì)任意整數(shù)a,稱為Jacobi符號(hào)定理5.14

設(shè)n>2是一個(gè)奇整數(shù)。1)如果則2)3)4)如果m>2是奇整數(shù),則引理5.1

設(shè)n>2是一個(gè)奇整數(shù),n的素分解為其中是素?cái)?shù),則2023/9/18175.3.4Jacobi符號(hào)定義5.7設(shè)n>25.3.5

Solovay-Strassen

素性測(cè)試法由Fermat小定理可知,對(duì)于一個(gè)正整數(shù)n,如果存在正整數(shù)b滿足gcd(b，n)=1,并且不成立，則n一定是合數(shù)定理5.15

如果n>2是一個(gè)奇合數(shù),則至少有50%的使得同余式不成立。2023/9/18185.3.5Solovay-Strassen素性測(cè)試法5.3.6

Miller-Rabin

素性測(cè)試法定義5.8

設(shè)n>2是一個(gè)奇數(shù).設(shè)其中s是非負(fù)整數(shù),m>0是奇數(shù)。設(shè)0<b<n。如果或者存在一個(gè)r,06r<s,使得則稱n通過(guò)以b為基的Miller-Rabin測(cè)試。定理5.16

設(shè)p>2是一個(gè)素?cái)?shù).對(duì)任意整數(shù)b>0,如果gcd(b，p)=1,則p一定可以通過(guò)以b為基的Miller-Rabin測(cè)試。定理5.17

如果n>2是一個(gè)奇合數(shù),則至多有個(gè)b,0<b<n,使得n通過(guò)以b為基的Miller-Rabin測(cè)試.2023/9/18195.3.6Miller-Rabin素性測(cè)試法定義5.5.4EIGamal公鑰密碼EIGamal公鑰密碼體制EIGamal公鑰密碼體制的安全性有限域上離散對(duì)數(shù)的計(jì)算方法主要內(nèi)容2023/9/18205.4EIGamal公鑰密碼EIGamal公鑰密碼5.4.1

EIGamal

公鑰密碼體制EIGamal

公鑰密碼體制描述如下：選取大素?cái)?shù)

p是一個(gè)本原元.p和α公開.隨機(jī)選取整數(shù)

計(jì)算，β公開是公開的加密密，d是保密的解密密鑰明文空間為

，密文空間為加密變換：對(duì)任意明文

秘密隨機(jī)選取一個(gè)整數(shù)k，1k

p?2,密文為其中解密變換：對(duì)任意密文明文為2023/9/18215.4.1EIGamal公鑰密碼體制EIGamal5.4.2

EIGamal

公鑰密碼體制的安全性定義5.9

設(shè)p是一個(gè)素?cái)?shù),是一個(gè)本原元,已知α和β，求滿足的唯一整數(shù)n,0≤

n≤

p?2,稱為有限域上的離散對(duì)數(shù)問(wèn)題.常將n記為2023/9/18225.4.2EIGamal公鑰密碼體制的安全性定義5.5.4.3有限域上離散對(duì)數(shù)的計(jì)算方法Shanks算法指標(biāo)計(jì)算法Pohlig-Hellman算法主要內(nèi)容2023/9/18235.4.3有限域上離散對(duì)數(shù)的計(jì)算方法Shanks算5.5

橢圓曲線上的Menezes-Vanstone公鑰密碼橢圓曲線的定義實(shí)數(shù)域上橢圓曲線的圖像實(shí)數(shù)域上橢圓曲線點(diǎn)的加法運(yùn)算實(shí)數(shù)域上橢圓曲線點(diǎn)的加法運(yùn)算的性質(zhì)有限域上的橢圓曲線有限域上的橢圓曲線的性質(zhì)橢圓曲線上的離散對(duì)數(shù)問(wèn)題Menezes-Vanstone公鑰密碼體制2023/9/18245.5橢圓曲線上的Menezes-Vanstone公5.5.1

橢圓曲線的定義設(shè)F是一個(gè)域.域F上的橢圓曲線是指由Weierstrass方程確定的所有點(diǎn)(x,y)∈F×F以及一個(gè)特殊的無(wú)窮遠(yuǎn)點(diǎn)O所構(gòu)成的集合,其中2023/9/18255.5.1橢圓曲線的定義設(shè)F是一個(gè)域.域F上的橢5.5.2

實(shí)數(shù)域上橢圓曲線的圖像方程根的情況是Δ>0有一個(gè)實(shí)根和一對(duì)共軛復(fù)根Δ=0有三個(gè)實(shí)根，分別為Δ<

0有三個(gè)不同的實(shí)根實(shí)數(shù)域上的橢圓曲線方程關(guān)于x軸是對(duì)稱的。如果判別式Δ≠0，則稱其為非奇異橢圓曲線；否則稱其為奇異橢圓曲線。點(diǎn)擊查看圖例2023/9/18265.5.2實(shí)數(shù)域上橢圓曲線的圖像方程5.5.2

實(shí)數(shù)域上橢圓曲線的圖像定理5.18(代數(shù)基本定理)

設(shè)為實(shí)數(shù)域上的一個(gè)一元n次多項(xiàng)式,n為整數(shù),并且n≥1,則f(x)在復(fù)數(shù)域上有且僅有n個(gè)根。定理5.19(一元多項(xiàng)式根與系數(shù)的關(guān)系)

設(shè)為實(shí)數(shù)域上的一個(gè)一元n次多項(xiàng)式,n為整數(shù),并且n≥1。設(shè)為f(x)的n個(gè)根,則對(duì)于2023/9/18275.5.2實(shí)數(shù)域上橢圓曲線的圖像定理5.18(代數(shù)基5.5.3

實(shí)數(shù)域上橢圓曲線點(diǎn)的加法運(yùn)算設(shè)a和b為實(shí)數(shù)為實(shí)數(shù)域上的非奇異橢圓曲線,其中O為無(wú)窮遠(yuǎn)點(diǎn)。在橢圓曲線E上定義加法運(yùn)算如下：對(duì)任意定義其中另外,對(duì)任意定義P+O=O+P=P2023/9/18285.5.3實(shí)數(shù)域上橢圓曲線點(diǎn)的加法運(yùn)算設(shè)a和b為實(shí)5.5.4

實(shí)數(shù)域上橢圓曲線點(diǎn)加法運(yùn)算的性質(zhì)(封閉性)對(duì)任意P∈E和

Q∈E,P+Q∈E(結(jié)合律)對(duì)任意P∈E,Q∈E以及R∈E,(P+Q)+R=P+(Q+R)(單位元)對(duì)任意P∈E,P+O=O+P=P(負(fù)元素)對(duì)任意P∈E,存在Q∈

E,滿足P+Q=Q+P=O(交換律)對(duì)任意P∈E和Q∈E,P+Q=Q+P2023/9/18295.5.4實(shí)數(shù)域上橢圓曲線點(diǎn)加法運(yùn)算的性質(zhì)(封閉性)5.5.5

有限域上的橢圓曲線定義5.10

設(shè)p>3是一個(gè)素?cái)?shù).有限域上的橢圓曲線是由一個(gè)稱為無(wú)窮遠(yuǎn)點(diǎn)的特殊點(diǎn)O和滿足的所有點(diǎn)同余方程組成的集合E,其中對(duì)任意定義其中定義加法運(yùn)算2023/9/18305.5.5有限域上的橢圓曲線定義5.10設(shè)p>35.5.6

有限域上的橢圓曲線的性質(zhì)定理5.20(Hasse定理)

設(shè)E是有限域上的橢圓曲線,則定理5.21(Hasse定理)

設(shè)E是有限域上的橢圓曲線,則其中t的絕對(duì)值定理5.22(橢圓曲線的群結(jié)構(gòu))

設(shè)E是有限域

上的橢圓曲線,p>3為素?cái)?shù),則存在正整數(shù)和，使得E與同構(gòu),和

滿足并且2023/9/18315.5.6有限域上的橢圓曲線的性質(zhì)定理5.20(Ha5.5.7

橢圓曲線上的離散對(duì)數(shù)問(wèn)題定義5.11

設(shè)E是有限域上的橢圓曲線,的階是滿足的最小正整數(shù)n,記為ord(P),其中O是無(wú)窮遠(yuǎn)點(diǎn)。定義5.12

設(shè)p>3是一個(gè)素?cái)?shù),E是有限域上的橢圓曲線.設(shè)G是E的一個(gè)循環(huán)子群,P是G的一個(gè)生成元,Q∈

G.已知P和Q,求滿足nP=Q的唯一整數(shù)稱為橢圓曲線上的離散對(duì)數(shù)問(wèn)題。2023/9/18325.5.7橢圓曲線上的離散對(duì)數(shù)問(wèn)題定義5.11設(shè)E5.5.8

Menezes-Vanstone公鑰密碼體制隨機(jī)選取整數(shù)d，1≤d≤ord(α)?1。計(jì)算β=dα，

β是公開的加密密鑰，d是保密的解密密鑰Menezes-Vanstone公鑰密碼體制描述如下設(shè)p>3是一個(gè)大素?cái)?shù)，E是有限域Zp上的橢圓曲線。α∈E是橢圓曲線上的一個(gè)點(diǎn)，并且α的階足夠大，使得在由α生成的循環(huán)子群中離散對(duì)數(shù)問(wèn)題是難解的。p和E以及α都公開明文空間為密文空間為加密變