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

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

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

解密密鑰當然必須保密。

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

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

定理和Fermat小定理RSA

公鑰密碼體制RSA

的安全性討論模n

求逆的算法模n

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

中國剩余定理定義5.3

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

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

Euler

函數(shù)定義5.4

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

如果

和

互素,則定理5.3

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

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

Euler定理和Fermat小定理定理5.5

(Euler定理)

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

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

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

RSA公鑰密碼體制選取兩個大素數(shù)p和q，p和q保密計算，公開，保密隨機選取正整數(shù)1<e<，滿足

e

是公開的加密密鑰計算d，滿足

。d是保密的解密密鑰加密變換：對明文

密文為解密變換：對密文明文為RSA

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

RSA的安全性討論

RSA公鑰密碼體制的安全性是基于大整數(shù)的素分解問題的難解性。盡管尚未在理論上嚴格證明因子分解問題一定是難解的,但經(jīng)過長期的研究迄今沒有找到一個有效算法的事實,使得因子分解問題成為眾所周知的難題。這是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是一個正整數(shù)，對于存在使得的充分必要條件是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步計算的快速算法2023/9/18115.2.7模n的大數(shù)冪乘的快速算法如果b=0，則5.2.8

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

大素數(shù)的生成模奇素數(shù)的平方剩余Legendre符號Jacobi

符號Solovay-Strassen

素性測試法Miller-Rabin素性測試法素數(shù)的分布2023/9/18135.3大素數(shù)的生成模奇素數(shù)的平方剩余Legendre符號5.3.1素數(shù)的分布定理5.8

存在無窮多個素數(shù)。定理5.9(素數(shù)定理)

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

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

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

Legendre

符號定義5.6

設(shè)p>2是一個素數(shù).對任意整數(shù)a,若a≡

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

設(shè)p>2是一個素數(shù),則對任意整數(shù)a,定理5.12

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

設(shè)p>2是一個素數(shù),q>2也是一個素數(shù)，p≠

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

Jacobi

符號定義5.7

設(shè)n>2是一個奇整數(shù),n的素分解為其中是素數(shù),對任意整數(shù)a,稱為Jacobi符號定理5.14

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

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

Solovay-Strassen

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

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

Miller-Rabin

素性測試法定義5.8

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

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

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

EIGamal

公鑰密碼體制EIGamal

公鑰密碼體制描述如下：選取大素數(shù)

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

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

，密文空間為加密變換：對任意明文

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

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

EIGamal

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

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

n≤

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

設(shè)E是有限域

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

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

橢圓曲線上的離散對數(shù)問題定義5.11

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

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

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

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

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