分組密碼-電子科技大學(xué)課件

第4章公鑰密碼4.1數(shù)論基礎(chǔ)知識(shí)4.2公鑰密碼的基本概念4.3RSA公鑰密碼4.4ElGamal公鑰密碼4.5Rabin公鑰密碼4.6橢圓曲線公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)第4章公鑰密碼4.1數(shù)論基礎(chǔ)知識(shí)現(xiàn)代密碼學(xué)電子科技大14.1數(shù)論基礎(chǔ)知識(shí)現(xiàn)代密碼學(xué)電子科技大學(xué)4.1數(shù)論基礎(chǔ)知識(shí)現(xiàn)代密碼學(xué)電子科技大學(xué)2素?cái)?shù)與互素定義1

對(duì)于整數(shù)a,b（b0），若存在整數(shù)x使得b=ax，則稱a整除b，或a是b的因子，記作a|b。定義2

若a,b,c都是整數(shù)，a和b不全為0且c|a,c|b，則稱c是a和b的公因子。如果整數(shù)d滿足：①d是a和b的公因子；②a和b的任一公因子，也是d的因子。則稱d是a和b的最大公因子，記作d=gcd(a,b)。如果gcd(a,b)=1，則稱a和b互素。素?cái)?shù)與互素定義1對(duì)于整數(shù)a,b（b0），若存在整3定義3

若a,b,c都是整數(shù)，a和b都不為0且a|c,b|c，則稱c是a和b的公倍數(shù)。如果整數(shù)d滿足：①d是a和b的公倍數(shù)；②d整除a和b的任一公倍數(shù)。則稱d是a和b的最小公倍數(shù)，記作d=lcm(a,b)?，F(xiàn)代密碼學(xué)電子科技大學(xué)素?cái)?shù)與互素定義3若a,b,c都是整數(shù)，a和b都不為0且a|4定義4

對(duì)于任一整數(shù)p(p＞1)，若p的因子只有±1和±p，則稱p為素?cái)?shù)，否則稱為合數(shù)。對(duì)于任一整數(shù)a(a＞1)，都可以唯一的分解為素?cái)?shù)的乘積，即：a=p1×p2×…×pt其中，p1＜p2＜…＜pt都是素?cái)?shù)，pi＞0(i=1,2,…,t)。素?cái)?shù)與互素定義4對(duì)于任一整數(shù)p(p＞1)，若p的因子只有±15定義5

設(shè)n是一正整數(shù)，小于n且與n互素的正整數(shù)的個(gè)數(shù)稱為歐拉（Euler）函數(shù)，記作。歐拉函數(shù)有如下性質(zhì)：①若n是素?cái)?shù)，則。②若m和n互素，則。③如果：其中，p1<p2<…<pt都是素?cái)?shù)，pi＞0(i=1,2,…,t)，則：

現(xiàn)代密碼學(xué)電子科技大學(xué)歐拉函數(shù)定義5設(shè)n是一正整數(shù)，小于n且與n互素的正整數(shù)的個(gè)數(shù)稱為6定義6

設(shè)n是一正整數(shù)，a是整數(shù)，如果用n除a，得商為q，余數(shù)為r，即：其中表示小于或等于的最大整數(shù)。定義r為amodn，記作r

amodn。如果兩個(gè)整數(shù)a和b滿足：則稱a和b模n同余，記作a

bmodn。稱與a模n同余的數(shù)的全體為a的同余類(lèi)。現(xiàn)代密碼學(xué)電子科技大學(xué)表示向下取整同余及其性質(zhì)定義6設(shè)n是一正整數(shù)，a是整數(shù)，如果用n除a，得商為q，7同余有如下性質(zhì)：①若n|（ab），則abmodn。②若amodn

bmodn，則a

bmodn。③a

amodn。④若a

bmodn，則b

amodn。⑤若a

bmodn，b

cmodn，則a

cmodn。⑥若a

bmodn，c

dmodn，則a+c

b+d(modn),ac

bd(modn)。

現(xiàn)代密碼學(xué)電子科技大學(xué)同余及其性質(zhì)同余有如下性質(zhì)：現(xiàn)代密碼學(xué)電子科技大學(xué)同余及其性質(zhì)8一般的，定義Zn為小于n的所有非負(fù)整數(shù)集合，即Zn={0,1,…,n1}，稱Zn為模n的同余類(lèi)集合。Zn中的加法（+）和乘法（）都為模n運(yùn)算，具有如下性質(zhì)：①交換律

(w+x)modn=(x+w)modn(wx)modn=(xw)modn

現(xiàn)代密碼學(xué)電子科技大學(xué)模運(yùn)算一般的，定義Zn為小于n的所有非負(fù)整數(shù)集合，即Zn={0,9②結(jié)合律

[(w+x)+y]modn=[w+(x+y)]modn[(wx)y]modn=[w(xy)]modn③分配律

[w(x+y)]modn=[(wx)+(wy)]modn④單位元

(0+w)modn=wmodn(1w)modn=wmodn

模運(yùn)算②結(jié)合律[(w+x)+y]modn=[w10⑤加法逆元對(duì)w∈Zn，存在x∈Zn，使得w+x0modn，稱x為w的加法逆元，記作x=w。⑥乘法逆元設(shè)w∈Zn，如果存在x∈Zn，使得wx1modn，就說(shuō)w是可逆的，稱x為w的乘法逆元，記作x=w1。

并不是每個(gè)元素都有乘法逆元，可以證明w∈Zn是可逆的，當(dāng)且僅當(dāng)gcd(w,n)=1。如果w是可逆的，則可以定義除法：模運(yùn)算⑤加法逆元對(duì)w∈Zn，存在x∈Zn，使得w+x011定理1[費(fèi)馬（Fermat）定理]設(shè)p為素?cái)?shù)，a是正整數(shù)且gcd(a,p)=1，則ap1

1modp。如果a是任一正整數(shù)，則ap

1modp。定理2[歐拉定理]若gcd(a,n)=1，則：其中是歐拉函數(shù).現(xiàn)代密碼學(xué)電子科技大學(xué)費(fèi)馬定理及歐拉定理定理1[費(fèi)馬（Fermat）定理]設(shè)p為素?cái)?shù)，a是12定理3[中國(guó)剩余定理]設(shè)m1,m2,…,mk是兩兩互素的正整數(shù)，a1,a2,…,ak是任意k個(gè)整數(shù)，則同余方程組：

模M=m1m2…mk有唯一解：其中，Mi=M/mi，yi=Mi-1

modmi,i=1,2,…,k。中國(guó)剩余定理定理3[中國(guó)剩余定理]設(shè)m1,m2,…,mk是兩兩13離散對(duì)數(shù)求模下的整數(shù)冪根據(jù)歐拉定理，若gcd(a,n)=1,則af(n)≡1modn。考慮一般am≡1modn,如果a,n互素，至少有一個(gè)整數(shù)m滿足這一方程。稱滿足這一方程的最小正整數(shù)m為模n下a的階。例：a=7,n=19.71≡7mod19,72≡11mod19,73≡1mod19,所以7模19的階為3。從冪次為4開(kāi)始出現(xiàn)循環(huán)，循環(huán)周期與元素的階相同離散對(duì)數(shù)求模下的整數(shù)冪14離散對(duì)數(shù)定理：設(shè)a的階為m，則ak≡1modn的充分必要條件是k是m的倍數(shù)。推論：a的階整除j(n)。本原根：a的階m等于j(n)，a為n的本原根。如果a是n的本原根，a1,a2,...,aj(n)在模n下互不相同且與n互素。本原根不唯一。并非所有元素都有本原根，僅有以下形式的整數(shù)才有本原根：2，4，pa,2pa,p是奇素?cái)?shù)離散對(duì)數(shù)定理：設(shè)a的階為m，則ak≡1modn的充分必要條15離散對(duì)數(shù)指標(biāo)y=ax(a>0,a≠1)的逆函數(shù)稱為以a為底的對(duì)數(shù)，記為x=logay設(shè)p為素?cái)?shù)，a是p的本原根，則a0,a1,...,ap-1產(chǎn)生1到p-1中所有值，且每個(gè)值只出現(xiàn)一次。對(duì)任一b∈{1,…,p-1}，都存在唯一的i(1≤i≤p)，使b≡aimodp。i稱為模p下以a為底b的指標(biāo)，記為i=inda,p(d)離散對(duì)數(shù)指標(biāo)16離散對(duì)數(shù)指標(biāo)的性質(zhì)inda,p(1)=0inda,p(a)=1inda,p(xy)=[inda,p(x)+inda,p(y)]modj(p)inda,p(yr)=[r×inda,p(y)]modj(p)

后兩個(gè)性質(zhì)基于下列結(jié)論

若az≡aqmodp,a和p互素，則z≡qmodj(p)離散對(duì)數(shù)指標(biāo)的性質(zhì)17定義7

設(shè)，若存在一個(gè)，使得x2

amodn，則稱a是一個(gè)模n的二次剩余（quadraticresiduemodulon），并稱x是a的模n平方根；否則稱a是一個(gè)模n的二次非剩余（quadraticnonresiduemodulon）?，F(xiàn)代密碼學(xué)電子科技大學(xué)二次剩余定義7設(shè)，若存在一個(gè)184.2公鑰密碼的基本概念現(xiàn)代密碼學(xué)電子科技大學(xué)4.2公鑰密碼的基本概念現(xiàn)代密碼學(xué)電子科技大學(xué)191976年，Diffie和Hellman在“密碼學(xué)的新方向（NewDirectioninCryptography）”一文中首次提出了公鑰密碼體制（publickeycryptosystem）的思想。公鑰密碼體制的概念是為了解決傳統(tǒng)密碼系統(tǒng)中最困難的兩個(gè)問(wèn)題而提出的，這兩個(gè)問(wèn)題是密鑰分配和數(shù)字簽名。

4.2公鑰密碼的基本概念現(xiàn)代密碼學(xué)電子科技大學(xué)1976年，Diffie和Hellman在“密碼學(xué)的新方向（204.2.1公鑰密碼體制的原理公鑰密碼體制在加密和解密時(shí)使用不同的密鑰，加密密鑰簡(jiǎn)稱公鑰（publickey），解密密鑰簡(jiǎn)稱私鑰（privatekey）。公鑰是公開(kāi)信息，不需要保密，私鑰必須保密。給定公鑰，要計(jì)算出私鑰在計(jì)算上是不可行的。公鑰密碼體制有兩種基本模型，一種是加密模型，另一種是認(rèn)證模型?，F(xiàn)代密碼學(xué)電子科技大學(xué)4.2.1公鑰密碼體制的原理公鑰密碼體制在加密和解密時(shí)21（1）加密模型。如圖所示，接收者B產(chǎn)生一對(duì)密鑰PKB和SKB，其中PKB是公鑰，將其公開(kāi)，SKB是私鑰，將其保密。如果A要向B發(fā)送消息m，A首先用B的公鑰PKB加密m，表示為c=E(PKB,m)，其中c是密文，E是加密算法，然后發(fā)送密文c給B。B收到密文c后，利用自己的私鑰SKB解密，表示為m=D(SKB,c)，其中D是解密算法?，F(xiàn)代密碼學(xué)電子科技大學(xué)加密模型發(fā)送者A加密算法PKB密鑰源SKB解密算法接收者B密碼分析員mcmm’SK’B（1）加密模型。如圖所示，接收者B產(chǎn)生一對(duì)密鑰PKB和SKB22認(rèn)證模型（2）認(rèn)證模型。如圖所示，A首先用自己的私鑰SKA對(duì)消息m加密，表示為c=E(SKA,m)，然后發(fā)送c給B。B收到密文c后，利用A的公鑰PKA對(duì)c解密，表示為m=D(PKA,c)。由于是用A的私鑰對(duì)消息加密，只有A才能做到，c就可以看做是A對(duì)m的數(shù)字簽名。此外，沒(méi)有A的私鑰，任何人都不能篡改m，所以上述過(guò)程獲得了對(duì)消息來(lái)源和數(shù)據(jù)完整性的認(rèn)證。認(rèn)證模型（2）認(rèn)證模型。如圖所示，A首先用自己的私鑰SKA對(duì)23發(fā)送者A加密算法（簽名）SKA密鑰源PKA解密算法（驗(yàn)證）接收者B密碼分析員mcmSK’A發(fā)送者A加密算法SKA密鑰源PKA解密算法接收者B密碼分析員244.2.2公鑰密碼體制的要求公鑰體制的基本原理是陷門(mén)單向函數(shù)。定義8

陷門(mén)單向函數(shù)是滿足下列條件的可逆函數(shù)f：①對(duì)于任意的x，計(jì)算y=f(x)是容易的。②對(duì)于任意的y，計(jì)算x使得y=f(x)是困難的。③存在陷門(mén)t，已知t時(shí)，對(duì)于任意的y，計(jì)算x使得y=f(x)則是容易的?，F(xiàn)代密碼學(xué)電子科技大學(xué)4.2.2公鑰密碼體制的要求公鑰體制的基本原理是陷門(mén)單25（1）大整數(shù)分解問(wèn)題（factorizationproblem）

若已知兩個(gè)大素?cái)?shù)p和q，求n=pq是容易的，只需一次乘法運(yùn)算，而由n，求p和q則是困難的，這就是大整數(shù)分解問(wèn)題?，F(xiàn)代密碼學(xué)電子科技大學(xué)（1）大整數(shù)分解問(wèn)題（factorizationprobl26（2）離散對(duì)數(shù)問(wèn)題（discretelogarithmproblem）給定一個(gè)大素?cái)?shù)p，p1含另一大素?cái)?shù)因子q，則可構(gòu)造一個(gè)乘法群，它是一個(gè)p1階循環(huán)群。設(shè)g是的一個(gè)生成元，1＜g＜p1。已知x，求y=gx

modp是容易的，而已知y、g、p，求x使得y=gx

modp成立則是困難的，這就是離散對(duì)數(shù)問(wèn)題。（2）離散對(duì)數(shù)問(wèn)題（discretelogarithmp27（3）多項(xiàng)式求根問(wèn)題

有限域GF（p）上的一個(gè)多項(xiàng)式：

已知,p和x，求y是容易的，而已知y,，求x則是困難的，這就是多項(xiàng)式求根問(wèn)題。（3）多項(xiàng)式求根問(wèn)題28（5）判斷Diffie-Hellman問(wèn)題（decisionDiffie-Hellmanproblem,DDHP）給定素?cái)?shù)p，令g是的一個(gè)生成元。已知,,判斷等式：z=xymodp是否成立，這就是判斷性Diffie-Hellman問(wèn)題?，F(xiàn)代密碼學(xué)電子科技大學(xué)（5）判斷Diffie-Hellman問(wèn)題（decision29（6）二次剩余問(wèn)題（quadraticresidueproblem）

給定一個(gè)合數(shù)n和整數(shù)a，判斷a是否為modn的二次剩余，這就是二次剩余問(wèn)題。在n的分解未知時(shí)，求

amodn的解也是一個(gè)困難問(wèn)題。分組密碼-電子科技大學(xué)課件30（7）背包問(wèn)題（knapsackproblem）

給定向量A=()(為正整數(shù))和x=()(∈{0,1})，求和式：

是容易的，而由A和S，求x則是困難的，這就是背包問(wèn)題，又稱子集和問(wèn)題。（7）背包問(wèn)題（knapsackproblem）314.3RSA公鑰密碼4.3RSA公鑰密碼321．密鑰生成①選取兩個(gè)保密的大素?cái)?shù)p和q。②計(jì)算n=pq,，其中是n的歐拉函數(shù)值。③隨機(jī)選取整數(shù)e，滿足1＜e＜，且。④計(jì)算d，滿足。⑤公鑰為(e,n)，私鑰為（d,n）。4.3.1RSA算法描述現(xiàn)代密碼學(xué)電子科技大學(xué)1．密鑰生成4.3.1RSA算法描述現(xiàn)代密碼學(xué)電子科技332．加密首先對(duì)明文進(jìn)行比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，然后依次對(duì)每個(gè)分組m做一次加密，所有分組的密文構(gòu)成的序列即是原始消息的加密結(jié)果。即m滿足0≤m＜n，則加密算法為：c為密文，且0≤c＜n?，F(xiàn)代密碼學(xué)電子科技大學(xué)4.3.1RSA算法描述2．加密現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.1RSA算法描述343．解密對(duì)于密文0≤c＜n，解密算法為：現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.1RSA算法描述3．解密現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.1RSA算法描述354.3.2RSA的安全性1．?dāng)?shù)學(xué)攻擊用數(shù)學(xué)方法攻擊RSA的途徑有三種：①分解n為兩個(gè)素因子。這樣就可以計(jì)算從而計(jì)算出私鑰。②直接確定而不先確定p和q。這同樣可以確定.③直接確定d而不先確定。

現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.2RSA的安全性現(xiàn)代密碼學(xué)電子科技大學(xué)362．窮舉攻擊

像其他密碼體制一樣，RSA抗窮舉攻擊的方法也是使用大的密鑰空間，這樣看來(lái)是e和d的位數(shù)越大越好。但是由于在密鑰生成和加密/解密過(guò)程都包含了復(fù)雜的計(jì)算，故密鑰越大，系統(tǒng)運(yùn)行速度越慢。3．計(jì)時(shí)攻擊

計(jì)時(shí)攻擊是通過(guò)記錄計(jì)算機(jī)解密消息所用的時(shí)間來(lái)確定私鑰。這種攻擊不僅可以用于攻擊RSA，還可以用于攻擊其他的公鑰密碼系統(tǒng)。現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.2RSA的安全性2．窮舉攻擊現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.2RSA的安374.選擇密文攻擊

RSA易受選擇密文攻擊（chosenciphertextattack）4.3.2RSA的安全性4.選擇密文攻擊4.3.2RSA的安全性384.4ElGamal公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)4.4ElGamal公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)391．密鑰生成①選取大素?cái)?shù)p，且要求p1有大素?cái)?shù)因子。是一個(gè)本原元。②隨機(jī)選取整數(shù)x,1≤x≤p2，計(jì)算。③公鑰為y，私鑰為x。4.4.1ElGamal算法描述現(xiàn)代密碼學(xué)電子科技大學(xué)1．密鑰生成4.4.1ElGamal算法描述現(xiàn)代密碼學(xué)40p和g是公共參數(shù)，被所有用戶所共享，這一點(diǎn)與RSA算法是不同的。另外，在RSA算法中，每個(gè)用戶都需要生成兩個(gè)大素?cái)?shù)來(lái)建立自己的密鑰對(duì)（這是很費(fèi)時(shí)的工作），而ElGamal算法只需要生成一個(gè)隨機(jī)數(shù)和執(zhí)行一次模指數(shù)運(yùn)算就可以建立密鑰對(duì)。

p和g是公共參數(shù)，被所有用戶所共享，這一點(diǎn)與RSA算412．加密對(duì)于明文，首先隨機(jī)選取一個(gè)整數(shù)k,1≤k≤p2，然后計(jì)算：,則密文c=（

c1,c2）。3．解密為了解密一個(gè)密文c=（c1,c2），計(jì)算：現(xiàn)代密碼學(xué)電子科技大學(xué)2．加密現(xiàn)代密碼學(xué)電子科技大學(xué)424.4.2ElGamal的安全性在ElGamal公鑰密碼體制中，y=modp。從公開(kāi)參數(shù)g和y求解私鑰x需要求解離散對(duì)數(shù)問(wèn)題。目前還沒(méi)有找到一個(gè)有效算法來(lái)求解有限域上的離散對(duì)數(shù)問(wèn)題。因此，ElGamal公鑰密碼體制的安全性是基于有限域上離散對(duì)數(shù)問(wèn)題的困難性。為了抵抗已知的攻擊，p應(yīng)該選取至少160位以上的十進(jìn)制數(shù)，并且p1至少應(yīng)該有一個(gè)大的素因子。現(xiàn)代密碼學(xué)電子科技大學(xué)4.4.2ElGamal的安全性現(xiàn)代密碼學(xué)電子科技大學(xué)434.5Rabin公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)4.5Rabin公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)441．密鑰生成選取兩個(gè)大素?cái)?shù)p和q，滿足pq3mod4，計(jì)算n=pq，則公鑰為n，私鑰為（p,q）。2．加密對(duì)于明文m（0≤m＜n），計(jì)算密文:c=modn4.5.1Rabin算法描述現(xiàn)代密碼學(xué)電子科技大學(xué)1．密鑰生成4.5.1Rabin算法描述現(xiàn)代密碼學(xué)電子453．解密為了解密一個(gè)密文c，利用中國(guó)剩余定理求解同余方程組，計(jì)算：,,然后選擇整數(shù)a=q(q1modp)和b=p(p1modq)，四個(gè)可能的解為：,

，現(xiàn)代密碼學(xué)電子科技大學(xué)4.5.1Rabin算法描述3．解密現(xiàn)代密碼學(xué)電子科技大學(xué)4.5.1Rabin算法463．解密由中國(guó)剩余定理知解x2≡cmodn,等價(jià)于解方程組由于p≡q≡3mod4，下面將看到，方程組的解可容易地求出，其中每個(gè)方程都有兩個(gè)解，即4.5.1Rabin算法描述3．解密4.5.1Rabin算法描述47 經(jīng)過(guò)組合可得4個(gè)同余方程組 由中國(guó)剩余定理可解出每一方程組的解，共有4個(gè)，即每一密文對(duì)應(yīng)的明文不惟一。為了有效地確定明文,可在m中加入某些信息,如發(fā)送者的身份號(hào)、接收者的身份號(hào)、日期、時(shí)間等。 經(jīng)過(guò)組合可得4個(gè)同余方程組48下面證明，當(dāng)p≡q≡3mod4，兩個(gè)方程x2≡cmodp,x2≡cmodq的平方根都可容易地求出。下面證明，當(dāng)p≡q≡3mod4，兩個(gè)方程49雅克比符號(hào)？雅克比符號(hào)？50

所以和

是方程x2≡cmodp的兩個(gè)根。同理

和

是方程x2≡cmodq的兩個(gè)根。 由4.1.8節(jié)知，求解方程x2≡amodn與分解n是等價(jià)的，所以破譯Rabin密碼體制的困難程度等價(jià)于大整數(shù)n的分解。 所以和是方514.6橢圓曲線公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)4.6橢圓曲線公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)52橢圓曲線并非橢圓，之所以稱為橢圓曲線是因?yàn)樗那€方程與計(jì)算橢圓周長(zhǎng)的方程相似。一般的，橢圓曲線指的是由維爾斯特拉斯（Weierstrass）方程：4.5.1實(shí)數(shù)域上的橢圓曲線現(xiàn)代密碼學(xué)電子科技大學(xué)橢圓曲線并非橢圓，之所以稱為橢圓曲線是因?yàn)樗那€方程與計(jì)算53所確定的曲線，它是由方程的全體解（x,y）再加上一個(gè)無(wú)窮遠(yuǎn)點(diǎn)O構(gòu)成的集合，其中a、b、c、d、e是滿足一些簡(jiǎn)單條件的實(shí)數(shù)，x和y也在實(shí)數(shù)集上取值。上述曲線方程可以通過(guò)坐標(biāo)變換轉(zhuǎn)化為下述形式：4.5.1實(shí)數(shù)域上的橢圓曲線所確定的曲線，它是由方程的全體解（x,y）再加上一個(gè)無(wú)窮遠(yuǎn)54由它確定的橢圓曲線常記為E（a,b），簡(jiǎn)記為E。當(dāng)

時(shí)，稱E（a,b）是一條非奇異橢圓曲線。對(duì)于非奇異橢圓曲線，我們可以基于集合E（a,b）定義一個(gè)群。這是一個(gè)Abel群，具有重要的“加法規(guī)則”屬性。

4.5.1實(shí)數(shù)域上的橢圓曲線由它確定的橢圓曲線常記為E（a,b），簡(jiǎn)記為E。當(dāng)551．加法的幾何描述橢圓曲線上的加法運(yùn)算定義如下：如果橢圓曲線上的3個(gè)點(diǎn)位于同一直線上，那么它們的和為O。從這個(gè)定義出發(fā)，我們可以定義橢圓曲線的加法規(guī)則：①O為加法的單位元，對(duì)于橢圓曲線上的任何一點(diǎn)P，有P+O=P。②對(duì)于橢圓曲線上的一點(diǎn)P=（x,y），它的逆元為P=（x,y）。注意到這里有P+（P）=PP=O。現(xiàn)代密碼學(xué)電子科技大學(xué)1．加法的幾何描述現(xiàn)代密碼學(xué)電子科技大學(xué)56③設(shè)P和Q是橢圓曲線上x(chóng)坐標(biāo)不同的兩點(diǎn)，P+Q的定義如下：作一條通過(guò)P和Q的直線l與橢圓曲線相交于R（這一點(diǎn)是唯一的，除非這條直線在P點(diǎn)或Q點(diǎn)與該橢圓曲線相切，此時(shí)我們分別取R=P或R=Q），然后過(guò)R點(diǎn)作y軸的平行線l′，l′與橢圓曲線相交的另一點(diǎn)S就是P+Q。如圖4-2所示。

分組密碼-電子科技大學(xué)課件57圖4-2橢圓曲線上點(diǎn)的加法的幾何解釋現(xiàn)代密碼學(xué)電子科技大學(xué)圖4-2橢圓曲線上點(diǎn)的加法的幾何解釋現(xiàn)代密碼學(xué)電子科技58

④上述幾何解釋也適用于具有相同x坐標(biāo)的兩個(gè)點(diǎn)P和P的情形。用一條垂直的線連接這兩個(gè)，可看做是在無(wú)窮遠(yuǎn)點(diǎn)與橢圓曲線相交，因此有P+（P）=O。這與上述的第②條敘述是一致的。⑤為計(jì)算點(diǎn)Q的兩倍，在Q點(diǎn)作一條切線并找到與橢圓曲線的另一個(gè)交點(diǎn)T，則Q+Q=2Q=T。

以上定義的加法具有加法運(yùn)算的一般性質(zhì)，如交換律、結(jié)合律等?，F(xiàn)代密碼學(xué)電子科技大學(xué)④上述幾何解釋也適用于具有相同x坐標(biāo)的兩個(gè)點(diǎn)P和P的情592．加法的代數(shù)描述對(duì)于橢圓曲線上不互為逆元的兩點(diǎn)P=(x1,y1)和Q=(x2,y2)，S=P+Q=(x3,y3)由以下規(guī)則確定：其中現(xiàn)代密碼學(xué)電子科技大學(xué)2．加法的代數(shù)描述現(xiàn)代密碼學(xué)電子科技大學(xué)604.6.2有限域上的橢圓曲線橢圓曲線密碼體制使用的是有限域上的橢圓曲線，即變量和系數(shù)均為有限域中的元素。有限域GF(p)上的橢圓曲線是指滿足方程：的所有點(diǎn)(x,y)再加上一個(gè)無(wú)窮遠(yuǎn)點(diǎn)O構(gòu)成的集合，其中，a、b、x和y均在有限域GF(p)上取值，p是素?cái)?shù)。我們把該橢圓曲線記為

(a,b)。該橢圓曲線只有有限個(gè)點(diǎn)，其個(gè)數(shù)N由Hasse定理確定?，F(xiàn)代密碼學(xué)電子科技大學(xué)4.6.2有限域上的橢圓曲線橢圓曲線密碼體制使用的是有限61定理4（Hasse定理）設(shè)E是有限域GF(p)上的橢圓曲線，N是E上點(diǎn)的個(gè)數(shù)，則定理4（Hasse定理）設(shè)E是有限域GF(p)上的橢圓624.6.3橢圓曲線的密碼體制現(xiàn)代密碼學(xué)電子科技大學(xué)4.6.3橢圓曲線的密碼體制現(xiàn)代密碼學(xué)電子科技大學(xué)634.6.3橢圓曲線的密碼體制定義9

橢圓曲線

(a,b)上點(diǎn)P的階是指滿足：的最小正整數(shù)，記為ord(P)，其中O是無(wú)窮遠(yuǎn)點(diǎn)?，F(xiàn)代密碼學(xué)電子科技大學(xué)4.6.3橢圓曲線的密碼體制現(xiàn)代密碼學(xué)電子科技大學(xué)64橢圓曲線上的離散對(duì)數(shù)定義10設(shè)G是橢圓曲線

(a,b)上的一個(gè)循環(huán)子群，P是G的一個(gè)生成元，Q∈G。已知P和Q，求滿足：mP=Q的整數(shù)m,0≤m≤ord(P)1，稱為橢圓曲線上的離散對(duì)數(shù)問(wèn)題（EllipticCurveDiscretelogarithmproblem）。橢圓曲線上的離散對(duì)數(shù)定義10設(shè)G是橢圓曲線(65

1．橢圓曲線上的ElGamal密碼體制在使用一個(gè)橢圓曲線密碼體制時(shí)，我們首先需要將發(fā)送的明文m編碼為橢圓曲線上的點(diǎn)，然后再對(duì)點(diǎn)做加密變換，在解密后還得將逆向譯碼才能獲得明文。下面對(duì)橢圓曲線上的ElGamal密碼體制進(jìn)行介紹。密鑰生成在橢圓曲線

(a,b)上選取一個(gè)階為n（n為一個(gè)大素?cái)?shù)）的生成元P。隨機(jī)選取整數(shù)x(1＜x＜n)，計(jì)算Q=xP。公鑰為Q，私鑰為x?，F(xiàn)代密碼學(xué)電子科技大學(xué)1．橢圓曲線上的ElGamal密碼體制現(xiàn)代密碼學(xué)電子科技大66加密為了加密，隨機(jī)選取一個(gè)整數(shù)k,1＜k＜n，計(jì)算：

,則密文c=()。解密為了解密一個(gè)密文c=()，計(jì)算：攻擊者要想從c=()計(jì)算出，就必須知道k。而要從P和kP中計(jì)算出k將面臨求解橢圓曲線上的離散對(duì)數(shù)問(wèn)題。加密為了加密，隨機(jī)選取一個(gè)整數(shù)k,1＜k＜n，672．橢圓曲線密碼體制的優(yōu)點(diǎn)與基于有限域上的離散對(duì)數(shù)問(wèn)題的公鑰密碼體制相比，橢圓曲線密碼體制有如下優(yōu)點(diǎn)：①安全性高②密鑰長(zhǎng)度?、鬯惴`活性好現(xiàn)代密碼學(xué)電子科技大學(xué)2．橢圓曲線密碼體制的優(yōu)點(diǎn)現(xiàn)代密碼學(xué)電子科技大學(xué)68習(xí)題1．為什么對(duì)于長(zhǎng)消息來(lái)說(shuō)，最好是先采用公鑰密碼算法來(lái)傳輸一個(gè)對(duì)稱密鑰，然后再用該對(duì)稱密鑰來(lái)傳遞消息？2．RSA公鑰密碼體制、ElGamal公鑰密碼體制、Rabin公鑰密碼體制和橢圓曲線公鑰密碼體制的安全性依據(jù)是什么？3．在RSA密碼體制中，已知素?cái)?shù)p=3，q=11，公鑰e=7，試計(jì)算私鑰d并給出對(duì)明文m=5的加密和解密過(guò)程?，F(xiàn)代密碼學(xué)電子科技大學(xué)習(xí)題1．為什么對(duì)于長(zhǎng)消息來(lái)說(shuō)，最好是先采用公鑰密碼算法來(lái)傳輸694．在ElGamal密碼體制中，設(shè)素?cái)?shù)p=71，本原元g=7：①如果接收者B的公鑰為yB=3，發(fā)送者A隨機(jī)選擇整數(shù)k=2，求明文m=30所對(duì)應(yīng)的密文。②如果發(fā)送者A選擇另一個(gè)隨機(jī)整數(shù)k，使得明文m=30加密后的密文為c=（59,c2），求c2。4．在ElGamal密碼體制中，設(shè)素?cái)?shù)p=71，本原元g=705．在Rabin密碼體制中，p=127,q=131，試給出對(duì)明文m=4410的加密和解密過(guò)程。6．在橢圓曲線上的ElGamal密碼體制中，設(shè)橢圓曲線為(1,6)，生成元P=(2,7)，接收者的私鑰x=7。①求接收者的公鑰Q。②發(fā)送者欲發(fā)送消息=(10,9)，選擇隨機(jī)數(shù)k=3，求密文c。③給出接收者從密文c恢復(fù)消息的過(guò)程。

現(xiàn)代密碼學(xué)電子科技大學(xué)5．在Rabin密碼體制中，p=127,q=131，試71第4章公鑰密碼4.1數(shù)論基礎(chǔ)知識(shí)4.2公鑰密碼的基本概念4.3RSA公鑰密碼4.4ElGamal公鑰密碼4.5Rabin公鑰密碼4.6橢圓曲線公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)第4章公鑰密碼4.1數(shù)論基礎(chǔ)知識(shí)現(xiàn)代密碼學(xué)電子科技大724.1數(shù)論基礎(chǔ)知識(shí)現(xiàn)代密碼學(xué)電子科技大學(xué)4.1數(shù)論基礎(chǔ)知識(shí)現(xiàn)代密碼學(xué)電子科技大學(xué)73素?cái)?shù)與互素定義1

對(duì)于整數(shù)a,b（b0），若存在整數(shù)x使得b=ax，則稱a整除b，或a是b的因子，記作a|b。定義2

若a,b,c都是整數(shù)，a和b不全為0且c|a,c|b，則稱c是a和b的公因子。如果整數(shù)d滿足：①d是a和b的公因子；②a和b的任一公因子，也是d的因子。則稱d是a和b的最大公因子，記作d=gcd(a,b)。如果gcd(a,b)=1，則稱a和b互素。素?cái)?shù)與互素定義1對(duì)于整數(shù)a,b（b0），若存在整74定義3

若a,b,c都是整數(shù)，a和b都不為0且a|c,b|c，則稱c是a和b的公倍數(shù)。如果整數(shù)d滿足：①d是a和b的公倍數(shù)；②d整除a和b的任一公倍數(shù)。則稱d是a和b的最小公倍數(shù)，記作d=lcm(a,b)?，F(xiàn)代密碼學(xué)電子科技大學(xué)素?cái)?shù)與互素定義3若a,b,c都是整數(shù)，a和b都不為0且a|75定義4

對(duì)于任一整數(shù)p(p＞1)，若p的因子只有±1和±p，則稱p為素?cái)?shù)，否則稱為合數(shù)。對(duì)于任一整數(shù)a(a＞1)，都可以唯一的分解為素?cái)?shù)的乘積，即：a=p1×p2×…×pt其中，p1＜p2＜…＜pt都是素?cái)?shù)，pi＞0(i=1,2,…,t)。素?cái)?shù)與互素定義4對(duì)于任一整數(shù)p(p＞1)，若p的因子只有±176定義5

設(shè)n是一正整數(shù)，小于n且與n互素的正整數(shù)的個(gè)數(shù)稱為歐拉（Euler）函數(shù)，記作。歐拉函數(shù)有如下性質(zhì)：①若n是素?cái)?shù)，則。②若m和n互素，則。③如果：其中，p1<p2<…<pt都是素?cái)?shù)，pi＞0(i=1,2,…,t)，則：

現(xiàn)代密碼學(xué)電子科技大學(xué)歐拉函數(shù)定義5設(shè)n是一正整數(shù)，小于n且與n互素的正整數(shù)的個(gè)數(shù)稱為77定義6

設(shè)n是一正整數(shù)，a是整數(shù)，如果用n除a，得商為q，余數(shù)為r，即：其中表示小于或等于的最大整數(shù)。定義r為amodn，記作r

amodn。如果兩個(gè)整數(shù)a和b滿足：則稱a和b模n同余，記作a

bmodn。稱與a模n同余的數(shù)的全體為a的同余類(lèi)?，F(xiàn)代密碼學(xué)電子科技大學(xué)表示向下取整同余及其性質(zhì)定義6設(shè)n是一正整數(shù)，a是整數(shù)，如果用n除a，得商為q，78同余有如下性質(zhì)：①若n|（ab），則abmodn。②若amodn

bmodn，則a

bmodn。③a

amodn。④若a

bmodn，則b

amodn。⑤若a

bmodn，b

cmodn，則a

cmodn。⑥若a

bmodn，c

dmodn，則a+c

b+d(modn),ac

bd(modn)。

現(xiàn)代密碼學(xué)電子科技大學(xué)同余及其性質(zhì)同余有如下性質(zhì)：現(xiàn)代密碼學(xué)電子科技大學(xué)同余及其性質(zhì)79一般的，定義Zn為小于n的所有非負(fù)整數(shù)集合，即Zn={0,1,…,n1}，稱Zn為模n的同余類(lèi)集合。Zn中的加法（+）和乘法（）都為模n運(yùn)算，具有如下性質(zhì)：①交換律

(w+x)modn=(x+w)modn(wx)modn=(xw)modn

現(xiàn)代密碼學(xué)電子科技大學(xué)模運(yùn)算一般的，定義Zn為小于n的所有非負(fù)整數(shù)集合，即Zn={0,80②結(jié)合律

[(w+x)+y]modn=[w+(x+y)]modn[(wx)y]modn=[w(xy)]modn③分配律

[w(x+y)]modn=[(wx)+(wy)]modn④單位元

(0+w)modn=wmodn(1w)modn=wmodn

模運(yùn)算②結(jié)合律[(w+x)+y]modn=[w81⑤加法逆元對(duì)w∈Zn，存在x∈Zn，使得w+x0modn，稱x為w的加法逆元，記作x=w。⑥乘法逆元設(shè)w∈Zn，如果存在x∈Zn，使得wx1modn，就說(shuō)w是可逆的，稱x為w的乘法逆元，記作x=w1。

并不是每個(gè)元素都有乘法逆元，可以證明w∈Zn是可逆的，當(dāng)且僅當(dāng)gcd(w,n)=1。如果w是可逆的，則可以定義除法：模運(yùn)算⑤加法逆元對(duì)w∈Zn，存在x∈Zn，使得w+x082定理1[費(fèi)馬（Fermat）定理]設(shè)p為素?cái)?shù)，a是正整數(shù)且gcd(a,p)=1，則ap1

1modp。如果a是任一正整數(shù)，則ap

1modp。定理2[歐拉定理]若gcd(a,n)=1，則：其中是歐拉函數(shù).現(xiàn)代密碼學(xué)電子科技大學(xué)費(fèi)馬定理及歐拉定理定理1[費(fèi)馬（Fermat）定理]設(shè)p為素?cái)?shù)，a是83定理3[中國(guó)剩余定理]設(shè)m1,m2,…,mk是兩兩互素的正整數(shù)，a1,a2,…,ak是任意k個(gè)整數(shù)，則同余方程組：

模M=m1m2…mk有唯一解：其中，Mi=M/mi，yi=Mi-1

modmi,i=1,2,…,k。中國(guó)剩余定理定理3[中國(guó)剩余定理]設(shè)m1,m2,…,mk是兩兩84離散對(duì)數(shù)求模下的整數(shù)冪根據(jù)歐拉定理，若gcd(a,n)=1,則af(n)≡1modn?？紤]一般am≡1modn,如果a,n互素，至少有一個(gè)整數(shù)m滿足這一方程。稱滿足這一方程的最小正整數(shù)m為模n下a的階。例：a=7,n=19.71≡7mod19,72≡11mod19,73≡1mod19,所以7模19的階為3。從冪次為4開(kāi)始出現(xiàn)循環(huán)，循環(huán)周期與元素的階相同離散對(duì)數(shù)求模下的整數(shù)冪85離散對(duì)數(shù)定理：設(shè)a的階為m，則ak≡1modn的充分必要條件是k是m的倍數(shù)。推論：a的階整除j(n)。本原根：a的階m等于j(n)，a為n的本原根。如果a是n的本原根，a1,a2,...,aj(n)在模n下互不相同且與n互素。本原根不唯一。并非所有元素都有本原根，僅有以下形式的整數(shù)才有本原根：2，4，pa,2pa,p是奇素?cái)?shù)離散對(duì)數(shù)定理：設(shè)a的階為m，則ak≡1modn的充分必要條86離散對(duì)數(shù)指標(biāo)y=ax(a>0,a≠1)的逆函數(shù)稱為以a為底的對(duì)數(shù)，記為x=logay設(shè)p為素?cái)?shù)，a是p的本原根，則a0,a1,...,ap-1產(chǎn)生1到p-1中所有值，且每個(gè)值只出現(xiàn)一次。對(duì)任一b∈{1,…,p-1}，都存在唯一的i(1≤i≤p)，使b≡aimodp。i稱為模p下以a為底b的指標(biāo)，記為i=inda,p(d)離散對(duì)數(shù)指標(biāo)87離散對(duì)數(shù)指標(biāo)的性質(zhì)inda,p(1)=0inda,p(a)=1inda,p(xy)=[inda,p(x)+inda,p(y)]modj(p)inda,p(yr)=[r×inda,p(y)]modj(p)

后兩個(gè)性質(zhì)基于下列結(jié)論

若az≡aqmodp,a和p互素，則z≡qmodj(p)離散對(duì)數(shù)指標(biāo)的性質(zhì)88定義7

設(shè)，若存在一個(gè)，使得x2

amodn，則稱a是一個(gè)模n的二次剩余（quadraticresiduemodulon），并稱x是a的模n平方根；否則稱a是一個(gè)模n的二次非剩余（quadraticnonresiduemodulon）?，F(xiàn)代密碼學(xué)電子科技大學(xué)二次剩余定義7設(shè)，若存在一個(gè)894.2公鑰密碼的基本概念現(xiàn)代密碼學(xué)電子科技大學(xué)4.2公鑰密碼的基本概念現(xiàn)代密碼學(xué)電子科技大學(xué)901976年，Diffie和Hellman在“密碼學(xué)的新方向（NewDirectioninCryptography）”一文中首次提出了公鑰密碼體制（publickeycryptosystem）的思想。公鑰密碼體制的概念是為了解決傳統(tǒng)密碼系統(tǒng)中最困難的兩個(gè)問(wèn)題而提出的，這兩個(gè)問(wèn)題是密鑰分配和數(shù)字簽名。

4.2公鑰密碼的基本概念現(xiàn)代密碼學(xué)電子科技大學(xué)1976年，Diffie和Hellman在“密碼學(xué)的新方向（914.2.1公鑰密碼體制的原理公鑰密碼體制在加密和解密時(shí)使用不同的密鑰，加密密鑰簡(jiǎn)稱公鑰（publickey），解密密鑰簡(jiǎn)稱私鑰（privatekey）。公鑰是公開(kāi)信息，不需要保密，私鑰必須保密。給定公鑰，要計(jì)算出私鑰在計(jì)算上是不可行的。公鑰密碼體制有兩種基本模型，一種是加密模型，另一種是認(rèn)證模型?，F(xiàn)代密碼學(xué)電子科技大學(xué)4.2.1公鑰密碼體制的原理公鑰密碼體制在加密和解密時(shí)92（1）加密模型。如圖所示，接收者B產(chǎn)生一對(duì)密鑰PKB和SKB，其中PKB是公鑰，將其公開(kāi)，SKB是私鑰，將其保密。如果A要向B發(fā)送消息m，A首先用B的公鑰PKB加密m，表示為c=E(PKB,m)，其中c是密文，E是加密算法，然后發(fā)送密文c給B。B收到密文c后，利用自己的私鑰SKB解密，表示為m=D(SKB,c)，其中D是解密算法?，F(xiàn)代密碼學(xué)電子科技大學(xué)加密模型發(fā)送者A加密算法PKB密鑰源SKB解密算法接收者B密碼分析員mcmm’SK’B（1）加密模型。如圖所示，接收者B產(chǎn)生一對(duì)密鑰PKB和SKB93認(rèn)證模型（2）認(rèn)證模型。如圖所示，A首先用自己的私鑰SKA對(duì)消息m加密，表示為c=E(SKA,m)，然后發(fā)送c給B。B收到密文c后，利用A的公鑰PKA對(duì)c解密，表示為m=D(PKA,c)。由于是用A的私鑰對(duì)消息加密，只有A才能做到，c就可以看做是A對(duì)m的數(shù)字簽名。此外，沒(méi)有A的私鑰，任何人都不能篡改m，所以上述過(guò)程獲得了對(duì)消息來(lái)源和數(shù)據(jù)完整性的認(rèn)證。認(rèn)證模型（2）認(rèn)證模型。如圖所示，A首先用自己的私鑰SKA對(duì)94發(fā)送者A加密算法（簽名）SKA密鑰源PKA解密算法（驗(yàn)證）接收者B密碼分析員mcmSK’A發(fā)送者A加密算法SKA密鑰源PKA解密算法接收者B密碼分析員954.2.2公鑰密碼體制的要求公鑰體制的基本原理是陷門(mén)單向函數(shù)。定義8

陷門(mén)單向函數(shù)是滿足下列條件的可逆函數(shù)f：①對(duì)于任意的x，計(jì)算y=f(x)是容易的。②對(duì)于任意的y，計(jì)算x使得y=f(x)是困難的。③存在陷門(mén)t，已知t時(shí)，對(duì)于任意的y，計(jì)算x使得y=f(x)則是容易的?，F(xiàn)代密碼學(xué)電子科技大學(xué)4.2.2公鑰密碼體制的要求公鑰體制的基本原理是陷門(mén)單96（1）大整數(shù)分解問(wèn)題（factorizationproblem）

若已知兩個(gè)大素?cái)?shù)p和q，求n=pq是容易的，只需一次乘法運(yùn)算，而由n，求p和q則是困難的，這就是大整數(shù)分解問(wèn)題。現(xiàn)代密碼學(xué)電子科技大學(xué)（1）大整數(shù)分解問(wèn)題（factorizationprobl97（2）離散對(duì)數(shù)問(wèn)題（discretelogarithmproblem）給定一個(gè)大素?cái)?shù)p，p1含另一大素?cái)?shù)因子q，則可構(gòu)造一個(gè)乘法群，它是一個(gè)p1階循環(huán)群。設(shè)g是的一個(gè)生成元，1＜g＜p1。已知x，求y=gx

modp是容易的，而已知y、g、p，求x使得y=gx

modp成立則是困難的，這就是離散對(duì)數(shù)問(wèn)題。（2）離散對(duì)數(shù)問(wèn)題（discretelogarithmp98（3）多項(xiàng)式求根問(wèn)題

有限域GF（p）上的一個(gè)多項(xiàng)式：

已知,p和x，求y是容易的，而已知y,，求x則是困難的，這就是多項(xiàng)式求根問(wèn)題。（3）多項(xiàng)式求根問(wèn)題99（5）判斷Diffie-Hellman問(wèn)題（decisionDiffie-Hellmanproblem,DDHP）給定素?cái)?shù)p，令g是的一個(gè)生成元。已知,,判斷等式：z=xymodp是否成立，這就是判斷性Diffie-Hellman問(wèn)題?，F(xiàn)代密碼學(xué)電子科技大學(xué)（5）判斷Diffie-Hellman問(wèn)題（decision100（6）二次剩余問(wèn)題（quadraticresidueproblem）

給定一個(gè)合數(shù)n和整數(shù)a，判斷a是否為modn的二次剩余，這就是二次剩余問(wèn)題。在n的分解未知時(shí)，求

amodn的解也是一個(gè)困難問(wèn)題。分組密碼-電子科技大學(xué)課件101（7）背包問(wèn)題（knapsackproblem）

給定向量A=()(為正整數(shù))和x=()(∈{0,1})，求和式：

是容易的，而由A和S，求x則是困難的，這就是背包問(wèn)題，又稱子集和問(wèn)題。（7）背包問(wèn)題（knapsackproblem）1024.3RSA公鑰密碼4.3RSA公鑰密碼1031．密鑰生成①選取兩個(gè)保密的大素?cái)?shù)p和q。②計(jì)算n=pq,，其中是n的歐拉函數(shù)值。③隨機(jī)選取整數(shù)e，滿足1＜e＜，且。④計(jì)算d，滿足。⑤公鑰為(e,n)，私鑰為（d,n）。4.3.1RSA算法描述現(xiàn)代密碼學(xué)電子科技大學(xué)1．密鑰生成4.3.1RSA算法描述現(xiàn)代密碼學(xué)電子科技1042．加密首先對(duì)明文進(jìn)行比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，然后依次對(duì)每個(gè)分組m做一次加密，所有分組的密文構(gòu)成的序列即是原始消息的加密結(jié)果。即m滿足0≤m＜n，則加密算法為：c為密文，且0≤c＜n?，F(xiàn)代密碼學(xué)電子科技大學(xué)4.3.1RSA算法描述2．加密現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.1RSA算法描述1053．解密對(duì)于密文0≤c＜n，解密算法為：現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.1RSA算法描述3．解密現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.1RSA算法描述1064.3.2RSA的安全性1．?dāng)?shù)學(xué)攻擊用數(shù)學(xué)方法攻擊RSA的途徑有三種：①分解n為兩個(gè)素因子。這樣就可以計(jì)算從而計(jì)算出私鑰。②直接確定而不先確定p和q。這同樣可以確定.③直接確定d而不先確定。

現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.2RSA的安全性現(xiàn)代密碼學(xué)電子科技大學(xué)1072．窮舉攻擊

像其他密碼體制一樣，RSA抗窮舉攻擊的方法也是使用大的密鑰空間，這樣看來(lái)是e和d的位數(shù)越大越好。但是由于在密鑰生成和加密/解密過(guò)程都包含了復(fù)雜的計(jì)算，故密鑰越大，系統(tǒng)運(yùn)行速度越慢。3．計(jì)時(shí)攻擊

計(jì)時(shí)攻擊是通過(guò)記錄計(jì)算機(jī)解密消息所用的時(shí)間來(lái)確定私鑰。這種攻擊不僅可以用于攻擊RSA，還可以用于攻擊其他的公鑰密碼系統(tǒng)。現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.2RSA的安全性2．窮舉攻擊現(xiàn)代密碼學(xué)電子科技大學(xué)4.3.2RSA的安1084.選擇密文攻擊

RSA易受選擇密文攻擊（chosenciphertextattack）4.3.2RSA的安全性4.選擇密文攻擊4.3.2RSA的安全性1094.4ElGamal公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)4.4ElGamal公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)1101．密鑰生成①選取大素?cái)?shù)p，且要求p1有大素?cái)?shù)因子。是一個(gè)本原元。②隨機(jī)選取整數(shù)x,1≤x≤p2，計(jì)算。③公鑰為y，私鑰為x。4.4.1ElGamal算法描述現(xiàn)代密碼學(xué)電子科技大學(xué)1．密鑰生成4.4.1ElGamal算法描述現(xiàn)代密碼學(xué)111p和g是公共參數(shù)，被所有用戶所共享，這一點(diǎn)與RSA算法是不同的。另外，在RSA算法中，每個(gè)用戶都需要生成兩個(gè)大素?cái)?shù)來(lái)建立自己的密鑰對(duì)（這是很費(fèi)時(shí)的工作），而ElGamal算法只需要生成一個(gè)隨機(jī)數(shù)和執(zhí)行一次模指數(shù)運(yùn)算就可以建立密鑰對(duì)。

p和g是公共參數(shù)，被所有用戶所共享，這一點(diǎn)與RSA算1122．加密對(duì)于明文，首先隨機(jī)選取一個(gè)整數(shù)k,1≤k≤p2，然后計(jì)算：,則密文c=（

c1,c2）。3．解密為了解密一個(gè)密文c=（c1,c2），計(jì)算：現(xiàn)代密碼學(xué)電子科技大學(xué)2．加密現(xiàn)代密碼學(xué)電子科技大學(xué)1134.4.2ElGamal的安全性在ElGamal公鑰密碼體制中，y=modp。從公開(kāi)參數(shù)g和y求解私鑰x需要求解離散對(duì)數(shù)問(wèn)題。目前還沒(méi)有找到一個(gè)有效算法來(lái)求解有限域上的離散對(duì)數(shù)問(wèn)題。因此，ElGamal公鑰密碼體制的安全性是基于有限域上離散對(duì)數(shù)問(wèn)題的困難性。為了抵抗已知的攻擊，p應(yīng)該選取至少160位以上的十進(jìn)制數(shù)，并且p1至少應(yīng)該有一個(gè)大的素因子。現(xiàn)代密碼學(xué)電子科技大學(xué)4.4.2ElGamal的安全性現(xiàn)代密碼學(xué)電子科技大學(xué)1144.5Rabin公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)4.5Rabin公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)1151．密鑰生成選取兩個(gè)大素?cái)?shù)p和q，滿足pq3mod4，計(jì)算n=pq，則公鑰為n，私鑰為（p,q）。2．加密對(duì)于明文m（0≤m＜n），計(jì)算密文:c=modn4.5.1Rabin算法描述現(xiàn)代密碼學(xué)電子科技大學(xué)1．密鑰生成4.5.1Rabin算法描述現(xiàn)代密碼學(xué)電子1163．解密為了解密一個(gè)密文c，利用中國(guó)剩余定理求解同余方程組，計(jì)算：,,然后選擇整數(shù)a=q(q1modp)和b=p(p1modq)，四個(gè)可能的解為：,

，現(xiàn)代密碼學(xué)電子科技大學(xué)4.5.1Rabin算法描述3．解密現(xiàn)代密碼學(xué)電子科技大學(xué)4.5.1Rabin算法1173．解密由中國(guó)剩余定理知解x2≡cmodn,等價(jià)于解方程組由于p≡q≡3mod4，下面將看到，方程組的解可容易地求出，其中每個(gè)方程都有兩個(gè)解，即4.5.1Rabin算法描述3．解密4.5.1Rabin算法描述118 經(jīng)過(guò)組合可得4個(gè)同余方程組 由中國(guó)剩余定理可解出每一方程組的解，共有4個(gè)，即每一密文對(duì)應(yīng)的明文不惟一。為了有效地確定明文,可在m中加入某些信息,如發(fā)送者的身份號(hào)、接收者的身份號(hào)、日期、時(shí)間等。 經(jīng)過(guò)組合可得4個(gè)同余方程組119下面證明，當(dāng)p≡q≡3mod4，兩個(gè)方程x2≡cmodp,x2≡cmodq的平方根都可容易地求出。下面證明，當(dāng)p≡q≡3mod4，兩個(gè)方程120雅克比符號(hào)？雅克比符號(hào)？121

所以和

是方程x2≡cmodp的兩個(gè)根。同理

和

是方程x2≡cmodq的兩個(gè)根。 由4.1.8節(jié)知，求解方程x2≡amodn與分解n是等價(jià)的，所以破譯Rabin密碼體制的困難程度等價(jià)于大整數(shù)n的分解。 所以和是方1224.6橢圓曲線公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)4.6橢圓曲線公鑰密碼現(xiàn)代密碼學(xué)電子科技大學(xué)123橢圓曲線并非橢圓，之所以稱為橢圓曲線是因?yàn)樗那€方程與計(jì)算橢圓周長(zhǎng)的方程相似。一般的，橢圓曲線指的是由維爾斯特拉斯（Weierstrass）方程：4.5.1實(shí)數(shù)域上的橢圓曲線現(xiàn)代密碼學(xué)電子科技大學(xué)橢圓曲線并非橢圓，之所以稱為橢圓曲線是因?yàn)樗那€方程與計(jì)算124所確定的曲線，它是由方程的全體解（x,y）再加上一個(gè)無(wú)窮遠(yuǎn)點(diǎn)O構(gòu)成的集合，其中a、b、c、d、e是滿足一些簡(jiǎn)單條件的實(shí)數(shù)，x和y也在實(shí)數(shù)集上取值。上述曲線方程可以通過(guò)坐標(biāo)變換轉(zhuǎn)化為下述形式：4.5.1實(shí)數(shù)域上的橢圓曲線所確定的曲線，它是由方程的全體解（x,y）再加上一個(gè)無(wú)窮遠(yuǎn)125由它確定的橢圓曲線常記為E（a,b），簡(jiǎn)記為E。當(dāng)

時(shí)，稱E（a,b）是一條非奇異橢圓曲線。對(duì)于非奇異橢圓曲線，我們可以基于集合E（a,b）定義一個(gè)群。這是一個(gè)Abel群，具有重要的“加法規(guī)則”屬性。

4.5.1實(shí)數(shù)域上的橢圓曲線由它確定的橢圓曲線常記為E（a,b），簡(jiǎn)記為E。當(dāng)1261．加法的幾何描述橢圓曲線上的加法運(yùn)算定義如下：如果橢圓曲線上的3個(gè)點(diǎn)位于同一直線上，那么它們的和為O。從這個(gè)定義出發(fā)，我們可以定義橢圓曲線的加法規(guī)則：①O為加法的單位元，對(duì)于橢圓曲線上的任何一點(diǎn)P，有P+O=P。②對(duì)于橢圓曲線上的一點(diǎn)P=（x,y），它的逆元為P=（x,y）。注意到這里有P+（P）=PP=O?，F(xiàn)代密碼學(xué)電子科技大學(xué)1．加法的幾何描述現(xiàn)代密碼學(xué)電子科技大學(xué)127③設(shè)P和Q是橢圓曲線上x(chóng)坐標(biāo)不同的兩點(diǎn)，P+Q的定義如下：作一條通