公開密鑰密碼課件

公開密鑰密碼51、山氣日夕佳，飛鳥相與還。52、木欣欣以向榮，泉涓涓而始流。53、富貴非吾愿，帝鄉(xiāng)不可期。54、雄發(fā)指危冠，猛氣沖長纓。55、土地平曠，屋舍儼然，有良田美池桑竹之屬，阡陌交通，雞犬相聞。公開密鑰密碼公開密鑰密碼51、山氣日夕佳，飛鳥相與還。52、木欣欣以向榮，泉涓涓而始流。53、富貴非吾愿，帝鄉(xiāng)不可期。54、雄發(fā)指危冠，猛氣沖長纓。55、土地平曠，屋舍儼然，有良田美池桑竹之屬，阡陌交通，雞犬相聞。密碼學公開密鑰密碼一、公開密鑰密碼體制的基本思想1、傳統(tǒng)密碼的缺點：①收發(fā)雙方持有相同密鑰，密鑰分配困難，網(wǎng)絡(luò)環(huán)境更突出。②不能方便地實現(xiàn)數(shù)字簽名，商業(yè)等應用不方便。Ke＝Kd公開密鑰密碼51、山氣日夕佳，飛鳥相與還。公開密鑰密碼公開密1密碼學公開密鑰密碼密碼學公開密鑰密碼2一、公開密鑰密碼體制的基本思想1、傳統(tǒng)密碼的缺點：①收發(fā)雙方持有相同密鑰，密鑰分配困難，網(wǎng)絡(luò)環(huán)境更突出。②不能方便地實現(xiàn)數(shù)字簽名，商業(yè)等應用不方便。Ke

＝Kd一、公開密鑰密碼體制的基本思想1、傳統(tǒng)密碼的缺點：Ke＝3一、公開密鑰密碼體制的基本思想2、公開密鑰密碼的基本思想：①將密鑰K一分為二，一個專門加密，一個專門解密：

Ke≠Kd

②且由Ke

不能計算出Kd

，于是可將Ke公開，使密鑰分配簡單。③由于Ke≠Kd且由Ke

不能計算出Kd

，所以

Kd

便成為用戶的指紋，于是可方便地實現(xiàn)數(shù)字簽名。

一、公開密鑰密碼體制的基本思想2、公開密鑰密碼的基本思想：4一、公開密鑰密碼體制的基本思想3、公開密鑰密碼的基本條件：①E和D互逆；基本條件，保密條件

D（E（M））＝M②Ke≠Kd且由Ke

不能計算出Kd

；安全條件③E和D都高效。實用條件④E（D（M））＝M保真條件

如果滿足①②③可保密，如果滿足②③④可保真，如果4個條件都滿足，可同時保密保真。

一、公開密鑰密碼體制的基本思想3、公開密鑰密碼的基本條件：5二、公開密鑰密碼的基本工作方式設(shè)

M為明文，C為密文，E為公開密鑰密碼的加密算法，D為解密算法，Ke為公開的加密鑰，Kd為保密的解密鑰，每個用戶都分配一對密鑰，而且將所有用戶的公開的加密鑰Ke存入共享的密鑰庫PKDB。二、公開密鑰密碼的基本工作方式6二、公開密鑰密碼的基本工作方式1、確保數(shù)據(jù)秘密性：AB發(fā)方：①A首先查PKDB，查到B的公開的加密鑰KeB

。②A用KeB加密M得到密文C：C=E（M，KeB）

③A發(fā)C給B。收方：①B接受C。②B用自己的KdB解密，得到明文M=D(C，KdB)。M二、公開密鑰密碼的基本工作方式1、確保數(shù)據(jù)秘密性：A7二、公開密鑰密碼的基本工作方式1、確保數(shù)據(jù)秘密性：安全性分析：①只有B才有KdB，因此只有B才能解密，所以確保了秘密性。②任何人都可查PKDB得到B的KeB，所以任何人都可冒充A給B發(fā)送數(shù)據(jù)。不能確保真實性。

二、公開密鑰密碼的基本工作方式1、確保數(shù)據(jù)秘密性：8二、公開密鑰密碼的基本工作方式2、確保數(shù)據(jù)真實性：AB發(fā)方：①A首先用自己的KdA對M解密，得到C=D(M，KdA)。②A發(fā)C給B。

收方：①B接受C。②B查PKDB查到A的公開的加密鑰KeA

。③B用KeA加密C，得到明文M=E（C，KeA）。M二、公開密鑰密碼的基本工作方式2、確保數(shù)據(jù)真實性：A9二、公開密鑰密碼的基本工作方式2、確保數(shù)據(jù)真實性：安全性分析：①只有A才有KdA，因此只有A才能解密產(chǎn)生C，所以確保了真實性。②任何人都可查PKDB得到A的KeA，所以任何人都可加密得到明文。不能確保秘密性。

二、公開密鑰密碼的基本工作方式2、確保數(shù)據(jù)真實性：10二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性：AB發(fā)方：①A首先用自己的KdA對M解密，得到S：S=D(M，KdA)②查PKDB，查到B的公開的加密鑰KeB。

③用KeB加密S得到C：C=E（S，KeB）④A發(fā)C給B。

M二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性11二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性：收方：①B接受C。②B用自己的KdB解密C，得到S：S=D（C，KdB）③B查PKDB查到A的公開的加密鑰KeA

。④B用A的公開的加密鑰KeA

加密S，得到M：M=E（S，KeA）二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性12二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性：安全性分析：①只有A才有KdA，因此只有A才能解密產(chǎn)生S，所以確保了真實性。②只有B才有KdB，因此只有B才能獲得明文，所以確保了秘密性。

二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性13三、RSA公開密鑰密碼1978年美國麻省理工學院的三名密碼學者R.L.Rivest,A.Shamir和L.Adleman提出了一種基于大合數(shù)因子分解困難性的公開密鑰密碼，簡稱為RSA密碼。RSA密碼被譽為是一種風格幽雅的公開密鑰密碼。既可用于加密，又可用于數(shù)字簽名，安全、易懂。RSA密碼已成為目前應用最廣泛的公開密鑰密碼。三、RSA公開密鑰密碼1978年美國麻省理工學院的三名密碼學14三、RSA公開密鑰密碼1、加解密算法①隨機地選擇兩個大素數(shù)p和q，而且保密；②計算n=pq，將

n公開；③計算φ(n)=(p-1)(q-1)，對φ(n)保密；④隨機地選取一個正整數(shù)e，1<e<φ(n)且（e，φ(n)）=1，將e公開；⑤根據(jù)ed＝1modφ(n)，求出d，并對d保密；⑥加密運算：C＝Memodn⑦解密運算：M＝Cdmodn

三、RSA公開密鑰密碼1、加解密算法15三、RSA公開密鑰密碼2、算法論證①E和D的可逆性要證明：D(E(M))=MM＝Cd＝(Me)d＝Medmodn因為ed＝1modφ(n)，這說明ed＝tφ(n)+1,其中t為某整數(shù)。所以，

Med＝Mtφ(n)+1modn。因此要證明Med＝Mmodn，只需證明

Mtφ(n)+1＝Mmodn。三、RSA公開密鑰密碼2、算法論證16三、RSA公開密鑰密碼2、算法論證①E和D的可逆性在（M，n）＝1的情況下，根據(jù)數(shù)論(Euler定理)，Mtφ(n)＝1modn，于是有，Mtφ(n)+1＝Mmodn。三、RSA公開密鑰密碼2、算法論證17三、RSA公開密鑰密碼2、算法論證①E和D的可逆性在（M，n）≠1的情況下，分兩種情況：第一種情況：M∈{1,2,3,…,n-1}因為n=pq，p和q為素數(shù)，M∈{1,2,3,…,n-1}，且（M，n）≠1。這說明M必含p或q之一為其因子，而且不能同時包含兩者，否則將有M≥n，與M∈{1,2,3,…,n-1}矛盾。三、RSA公開密鑰密碼2、算法論證18三、RSA公開密鑰密碼2、算法論證①E和D的可逆性不妨設(shè)M＝ap。又因q為素數(shù)，且M不包含q，故有（M，q）＝1，于是有，Mφ(q)＝1modq。進一步有，Mt(p-1)φ(q)＝1modq。因為q是素數(shù)，φ(q)＝（q-1），所以t(p-1)φ(q)＝tφ(n)，所以有Mtφ(n)＝1modq。三、RSA公開密鑰密碼2、算法論證19三、RSA公開密鑰密碼2、算法論證①E和D的可逆性于是，Mtφ(n)＝bq+1，其中b為某整數(shù)。兩邊同乘M，Mtφ(n)+1＝bqM+M。因為M＝ap，故Mtφ(n)+1＝bqap+M=abn+M。取模n得，Mφ(n)+1＝Mmodn。三、RSA公開密鑰密碼2、算法論證20三、RSA公開密鑰密碼2、算法論證①E和D的可逆性在（M，n）≠1的情況下，分兩種情況：第二種情況：M＝0當M＝0時，直接驗證，可知命題成立。

三、RSA公開密鑰密碼2、算法論證21三、RSA公開密鑰密碼2、算法論證②加密和解密運算的可交換性

D(E(M))=(Me)d=Med=(Md))e=E(D(M))modn所以，RSA密碼可同時確保數(shù)據(jù)的秘密性和數(shù)據(jù)的真實性。③加解密算法的有效性

RSA密碼的加解密運算是模冪運算，有比較有效的算法。三、RSA公開密鑰密碼2、算法論證22三、RSA公開密鑰密碼2、算法論證④在計算上由公開密鑰不能求出解密鑰

小合數(shù)的因子分解是容易的，然而大合數(shù)的因子分解卻是十分困難的。關(guān)于大合數(shù)的因子分解的時間復雜度下限目前尚沒有一般的結(jié)果，迄今為止的各種因子分解算法提示人們這一時間下限將不低于O（EXP（lnNlnlnN）1/2）。根據(jù)這一結(jié)論，只要合數(shù)足夠大，進行因子分解是相當困難的。三、RSA公開密鑰密碼2、算法論證23三、RSA公開密鑰密碼2、算法論證④在計算上由公開密鑰不能求出解密鑰假設(shè)截獲密文C，從中求出明文M。他知道M≡Cdmodn，因為n是公開的，要從C中求出明文M，必須先求出d，而d是保密的。但他知道，ed≡1modφ(n)，e是公開的，要從中求出d，必須先求出φ(n)，而φ(n)是保密的。三、RSA公開密鑰密碼2、算法論證24三、RSA公開密鑰密碼2、算法論證④在計算上由公開密鑰不能求出解密鑰但他又知道，φ(n)=(p-1)(q-1)，要從中求出φ(n)，必須先求出p和q，而p和q是保密的。但他知道，n=pq，要從n求出p和q，只有對n進行因子分解。而當n足夠大時，這是很困難的。三、RSA公開密鑰密碼2、算法論證25三、RSA公開密鑰密碼2、算法論證④在計算上由公開密鑰不能求出解密鑰

只要能對n進行因子分解，便可攻破RSA密碼。由此可以得出，破譯RSA密碼的困難性≤對n因子分解的困難性。目前尚不能證明兩者是否能確切相等，因為不能確知除了對n進行因子分解的方法外，是否還有別的更簡捷的破譯方法。目前只有Rabin密碼具有：破譯Rabin密碼的困難性=對n因子分解的困難性。三、RSA公開密鑰密碼2、算法論證263、RSA密碼的實現(xiàn)1）參數(shù)選擇為了確保RSA密碼的安全，必須認真選擇密碼參數(shù)：①p和q要足夠大；

一般應用：p和q應512b重要應用：p和q應1024b

②p和q應為強素數(shù)

文獻指出，只要(p-1)、(p+1)、(q-1)、(q+1)四個數(shù)之一只有小的素因子，n就容易分解。③p和q的差要大；

三、RSA公開密鑰密碼3、RSA密碼的實現(xiàn)三、RSA公開密鑰密碼27三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)1）參數(shù)選擇④（p-1）和（q-1）的最大公因子要小。

如果（p-1）和（q-1）的最大公因子太大，則易受迭代加密攻擊。⑤e的選擇

隨機且含1多就安全，但加密速度慢。于是，有的學者建議取e＝216+1＝65537⑥d的選擇

d不能太小，要足夠大⑦不要許多用戶共用一個模n；易受共模攻擊三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)28三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)2）大素數(shù)的產(chǎn)生①概率產(chǎn)生

目前最常用的概率性算法是Miller檢驗算法。Miller檢驗算法已經(jīng)成為美國的國家標準。②確定性產(chǎn)生確定性測試

確定性構(gòu)造三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)29三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)3）大素數(shù)的運算①快速乘方算法反復平方乘算法：設(shè)e的二進制表示為

e＝ek-12k-1+ek-22k-2+...,+e121+e0則Me=((…(Mek-1)2Mek-2)2…Me1)2Me0modn設(shè)e為k位二進制數(shù)，w(e)為e的二進制系數(shù)中為1的個數(shù)，則最多只需要計算w(e)-1次平方和w(e)次數(shù)的模乘。從而大大簡化了計算。三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)30三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)3）大素數(shù)的運算②快速模乘算法反復平方乘算法解決了快速乘方取模的問題，仍未解決快速模乘的問題；Montgomery算法是一種快速模乘的好算法；將以上兩種算法結(jié)合成為實現(xiàn)RSA密碼的有效方法。硬件協(xié)處理器是提高運算效率的有效方法。三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)31三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)3）大素數(shù)的運算Montgomery算法的思路：要計算Y=ABmodn,因為n很大，取模運算困難，采取一個小的模R，回避大模的計算。

利用空間換時間，多用存儲空間換取快速。

缺點：不能直接計算出Y=ABmodn，只能計算出中間值A(chǔ)BR-1modn，因此還需要預處理和調(diào)整運算。一次性計算Y=ABmodn并不劃算。適合：RSA等密碼中多次的模乘計算。三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)32三、RSA公開密鑰密碼4、對RSA公開密鑰密碼的主要攻擊窮舉攻擊：窮舉所有可能的私鑰數(shù)學攻擊：因式分解攻擊參數(shù)的選取不當造成的攻擊選擇密文攻擊共模攻擊小指數(shù)攻擊

計時攻擊三、RSA公開密鑰密碼4、對RSA公開密鑰密碼的主要攻擊33RSA公鑰加密的攻擊—因子分解因子分解攻擊RSA的途徑包括?分解n為p，q?直接確定φ(n),而不確定p，q?直接確定d，而不確定φ(n)?可以證明，從e和n確定φ(n)或者d的算法至少和因子分解一樣費時。因此，將因子分解的困難性作為評價RSA安全性的基準。RSA公鑰加密的攻擊—因子分解因子分解攻擊RSA的途徑包括34RSA公鑰加密的攻擊—選擇密文攻擊RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實體簽署。然后，經(jīng)過計算就可得到它所想要的信息。RSA公鑰加密的攻擊—選擇密文攻擊RSA在選擇密文攻擊面前很35RSA公鑰加密的攻擊—共模攻擊共模攻擊：指通信系統(tǒng)中使用相同的n，且存在兩個用戶的公鑰e1和e2是互質(zhì)的，則可以由這兩個用戶對同一條明文的不同加密結(jié)果，恢復出原始明文攻擊方法：設(shè)c1≡me1(modn)c2≡me2(modn)攻擊者知道e1,e2,n,c1,c2因為e1和e2互質(zhì)，故用Euclidean算法能找到r和s，使得t×e1+s×e2=1(注意是相等)則c1t×c2s=m(modn)不能用同一個n來生成密鑰RSA公鑰加密的攻擊—共模攻擊36RSA公鑰加密的攻擊—小指數(shù)攻擊Wiener在1990年指出，當d<n1/4時，從e和n可以很容易求出密鑰dRSA公鑰加密的攻擊—小指數(shù)攻擊37RSA公鑰加密的攻擊—計時攻擊思想：利用指數(shù)中某一位為0或者為1時，硬件加密速度不同RSA公鑰加密的攻擊—計時攻擊38四、ELGamal公鑰密碼1、基本情況：①ELGamal密碼是除了RSA密碼之外最有代表性的公開密鑰密碼。②RSA密碼建立在大合數(shù)分解的困難性之上。③ELGamal密碼建立在離散對數(shù)的困難性之上。所謂離散對數(shù)，就是給定正整數(shù)x，y，n，求出正整數(shù)k（如果存在的?話），使y≡xk(modn)。四、ELGamal公鑰密碼1、基本情況：所謂離散對數(shù)，就是給39四、ELGamal公鑰密碼2、離散對數(shù)問題：①設(shè)p為素數(shù)，則模p的剩余構(gòu)成有限域：

Fp={0,1,2,…,p-1}Fp的非零元構(gòu)成循環(huán)群Fp*

Fp*={1,2,…,p-1}={α，α2，α3，，αp-1}，則稱α為Fp*的生成元或模p的本原元。②求α的摸冪運算為: y=αxmodp，1≤x≤p-1,

四、ELGamal公鑰密碼2、離散對數(shù)問題：40四、ELGamal公鑰密碼2、離散對數(shù)問題：求對數(shù)X的運算為

x=logαy，1≤x≤p-1由于上述運算是定義在模p有限域上的，所以稱為離散對數(shù)運算。③從x計算y是容易的?？墒菑膟計算x就困難得多，利用目前最好的算法，對于小心選擇的p將至少需用O(p?)次以上的運算，只要p足夠大，求解離散對數(shù)問題是相當困難的。四、ELGamal公鑰密碼2、離散對數(shù)問題：41四、ELGamal公鑰密碼3、算法準備：隨機地選擇一個大素數(shù)p，且要求p-1有大素數(shù)因子。再選擇一個模p的本原元α。將p和α公開。⑴密鑰生成用戶隨機地選擇一個整數(shù)d作為自己的秘密的解密鑰，2≤d≤p-2。計算y=αd

modp，取y為自己的公開的加密鑰。由公開鑰y

計算秘密鑰d，必須求解離散對數(shù)，而這是極困難的。

四、ELGamal公鑰密碼3、算法42四、ELGamal公鑰密碼⑵加密將明文消息M（0≤M≤p-1)加密成密文的過程如下：①隨機地選取一個整數(shù)k，2≤k≤p-2。②計算：

U＝y(tǒng)kmodp；C1＝αkmodp；C2＝UMmodp；③取C＝（C1，C2）作為的密文。

四、ELGamal公鑰密碼⑵加密43四、ELGamal公鑰密碼⑶解密將密文（C1，C2）解密的過程如下：①計算V＝C1dmodp；②計算M＝C2

V-1modp。四、ELGamal公鑰密碼⑶解密44四、ELGamal公鑰密碼解密的可還原性可證明如下：

C2

V-1modp＝(UM)V-1modp＝UM（C1d）-1modp＝UM（（αk）d）-1modp＝UM（（αd）k）-1modp＝UM（（y）k）-1modp＝UM（U）-1modp＝Mmodp四、ELGamal公鑰密碼解密的可還原性可證明如下：45四、ELGamal公鑰密碼4、安全性由于ELGamal密碼的安全性建立在GF（p）離散對數(shù)的困難性之上，而目前尚無求解GF（p）離散對數(shù)的有效算法，所以在p足夠大時ELGamal密碼是安全的。為了安全p應為150位以上的十進制數(shù)，而且p-1應有大素因子。為了安全加密和簽名所使用的k必須是一次性的。d和k都不能太小。四、ELGamal公鑰密碼4、安全性46四、ELGamal公鑰密碼4、安全性如果k不是一次性的，時間長了就可能被攻擊著獲得。又因y是公開密鑰，攻擊者自然知道。于是攻擊者就可以根據(jù)U＝y(tǒng)kmodp計算出U，進而利用Euclid算法求出U－1。又因為攻擊者可以獲得密文C2，于是可根據(jù)式C2＝UMmodp通過計算U－1C2得到明文M。設(shè)用同一個k加密兩個不同的明文M和M’，相應的密文為（C1，C2）和（C1’，C2’）。因為C2∕C2’＝M∕M’，如果攻擊者知道M，則很容易求出M’。

四、ELGamal公鑰密碼4、安全性47四、ELGamal公鑰密碼5、ELGamal密碼的應用

由于ELGamal密碼的安全性得到世界公認，所以得到廣泛的應用。著名的美國數(shù)字簽名標準DSS，采用了ELGamal密碼的一種變形。為了適應不同的應用，人們在應用中總結(jié)出18種不同的ELGamal密碼的變形。四、ELGamal公鑰密碼5、ELGamal密碼的應用48四、ELGamal公鑰密碼5、ELGamal密碼的應用

①加解密速度快 由于實際應用時ELGamal密碼運算的素數(shù)p比RSA要小，所以ELGamal密碼的加解密速度比RSA稍快。②隨機數(shù)源 由ELGamal密碼的解密鑰d和隨機數(shù)k都應是高質(zhì)量的隨機數(shù)。因此，應用ELGamal密碼需要一個好的隨機數(shù)源，也就是說能夠快速地產(chǎn)生高質(zhì)量的隨機數(shù)。③大素數(shù)的選擇 為了ELGamal密碼的安全，p應為150位（十進制數(shù)）以上的大素數(shù)，而且p-1應有大素因子。

四、ELGamal公鑰密碼5、ELGamal密碼的應用49五、橢圓曲線密碼1、橢圓曲線密碼的一般情況受ELGamal密碼啟發(fā)，在其它離散對數(shù)問題難解的群中，同樣可以構(gòu)成ELGamal密碼。于是人們開始尋找其它離散問題難解的群。研究發(fā)現(xiàn)，有限域GF（p）上的橢圓曲線的解點構(gòu)成交換群，而且離散對數(shù)問題是難解的。于是可在此群上建立ELGamal密碼，并稱為橢圓曲線密碼。五、橢圓曲線密碼1、橢圓曲線密碼的一般情況50五、橢圓曲線密碼1、橢圓曲線密碼的一般情況橢圓曲線密碼已成為除RSA密碼之外呼聲最高的公鑰密碼之一。它密鑰短、簽名短，軟件實現(xiàn)規(guī)模小、硬件實現(xiàn)電路省電。普遍認為，160位長的橢圓曲線密碼的安全性相當于1024位的RSA密碼，而且運算速度也較快。五、橢圓曲線密碼1、橢圓曲線密碼的一般情況51五、橢圓曲線密碼1、橢圓曲線密碼的一般情況一些國際標準化組織已把橢圓曲線密碼作為新的信息安全標準。如，IEEEP1363/D4，ANSIF9.62，ANSIF9.63等標準，分別規(guī)范了橢圓曲線密碼在Internet協(xié)議安全、電子商務(wù)、Web服務(wù)器、空間通信、移動通信、智能卡等方面的應用。五、橢圓曲線密碼1、橢圓曲線密碼的一般情況52五、橢圓曲線密碼2、橢圓曲線設(shè)p是大于3的素數(shù)，且4a3+27b2≠0modp，稱y2=x3+ax+b，a,b∈GF(p)為GF（p）上的橢圓曲線。由橢圓曲線可得到一個同余方程：y2=x3+ax+bmodp其解為一個二元組<x,y>，x,y∈GF(p)，將此二元組描畫到橢圓曲線上便為一個點，于是又稱其為解點。五、橢圓曲線密碼2、橢圓曲線53五、橢圓曲線密碼2、橢圓曲線

為了利用解點構(gòu)成交換群，需要引進一個O元素，并定義如下的加法運算：①定義單位元引進一個無窮點O（∞，∞），簡記為0，作為0元素。O（∞，∞）＋O（∞，∞）＝0＋0＝0。并定義對于所有的解點P（x

，y），P（x

，y）+O＝O+P（x

，y）＝P（x

，y）。五、橢圓曲線密碼2、橢圓曲線54五、橢圓曲線密碼2、橢圓曲線②定義逆元素設(shè)P（x1，y1）和Q（x2，y2）是解點，如果x1=x2且y1=-y2，則P（x1，y1）＋Q（x2，y2）＝0。這說明任何解點R（x，y）的逆就是 R（x，-y）。注意：規(guī)定無窮遠點的逆就是其自己。 O（∞，∞）＝-O（∞，∞）五、橢圓曲線密碼2、橢圓曲線55五、橢圓曲線密碼2、橢圓曲線③定義加法設(shè)P(x1，y1)≠Q(mào)(x2，y2)，且P和Q不互逆，則P（x1，y1）＋Q（x2，y2）＝R（x3，y3）。其中x3=λ2-x1-x2，y3=λ(x1–x3)-y1，λ=（y2-y1）/(x2-x1）。五、橢圓曲線密碼2、橢圓曲線56五、橢圓曲線密碼2、橢圓曲線③定義加法當P（x1，y1）=Q(x2，y2)時P（x1，y1）＋Q(x2，y2)＝2P（x1，y1）＝R（x3，y3）。其中x3=λ2-2x1，y3=λ(x1–x3)-y1，λ=（3x12+a）/（2y1）。

五、橢圓曲線密碼2、橢圓曲線57五、橢圓曲線密碼2、橢圓曲線作集合E={全體解點，無窮點O}?？梢则炞C，如上定義的集合E和加法運算構(gòu)成加法交換群。復習：群的定義G是一個非空集，定義了一種運算，且運算是自封閉的；運算滿足結(jié)合律；G中有單位元；G中的元素都有逆元；五、橢圓曲線密碼2、橢圓曲線58五、橢圓曲線密碼3、橢圓曲線解點加法運算的幾何意義：

設(shè)P（x1，y1）和Q（x2，y2）是橢圓曲線的兩個點，則連接P（x1，y1）和Q（x2，y2）的直線與橢圓曲線的另一交點關(guān)于橫軸的對稱點即為P（x1，y1）+Q（x2，y2）點。五、橢圓曲線密碼3、橢圓曲線解點加法運算的幾何意義：59五、橢圓曲線密碼3、橢圓曲線解點加法運算的幾何意義：

xy0PQP+Q五、橢圓曲線密碼3、橢圓曲線解點加法運算的幾何意義：xy0P60五、橢圓曲線密碼4、舉例：取p=11，橢圓曲線y2=x3+x+6。由于p較小，使GF(p)也較小，故可以利用窮舉的方法根據(jù)y2=x3+x+6mod11求出所有解點。復習：平方剩余

設(shè)p為素數(shù)，如果存在一個正整數(shù)x，使得x2=amodp,則稱

a是模p的平方剩余。五、橢圓曲線密碼4、舉例：61五、橢圓曲線密碼

xx3+x+6mod11是否模11平方剩余y

06No18No25Yes 4,733Yes 5,648No54Yes 2,968No74Yes 2,989Yes 3,897No104Yes 2,9五、橢圓曲線密碼xx3+x+6mod1162五、橢圓曲線密碼根據(jù)表可知全部解點集為：(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的點構(gòu)成一個加法交換群。由于群的元素個數(shù)為13，而13為素數(shù)，所以此群是循環(huán)群，而且任何一個非O元素都是生成元。五、橢圓曲線密碼根據(jù)表可知全部解點集為：63五、橢圓曲線密碼由于是加法群，n個元素G相加，G+G+...+G＝nG。我們?nèi)＝（2，7）為生成元，具體計算加法表如下：

2G=（2，7）+（2，7）=（5，2）因為λ=（3×22+1）（2×7）-1mod11=2×3-1mod11=2×4mod11=8。于是，x3=82-2×2mod11=5，y3=8（2-5）-7mod11=2。五、橢圓曲線密碼由于是加法群，n個元素G相加，G+G+...64五、橢圓曲線密碼

G＝（2，7），2G＝（5，2），3G＝（8，3），4G＝（10，2），5G＝（3，6），6G＝（7，9），7G＝（7，2），8G＝（3，5），9G＝（10，9），10G＝（8，8），11G＝（5，9），12G＝（2，4），13G＝O（∞，∞）。五、橢圓曲線密碼G＝（2，7），2G＝（5，2）65五、橢圓曲線密碼除了GF(p)上的橢圓曲線，外還有定義在GF(2m)上的橢圓曲線。這兩種橢圓曲線都可以構(gòu)成安全的橢圓曲線密碼。在上例中，由于p較小，使GF(p)也較小，故可以利用窮舉的方法求出所有解點。但是，對于一般情況要確切計算橢圓曲線解點數(shù)N的準確值比較困難。N滿足以下不等式P+1-2P1/2≤N≤P+1+2P1/2。五、橢圓曲線密碼除了GF(p)上的橢圓曲線，外還有定義在GF66五、橢圓曲線密碼5、橢圓曲線密碼

ELGamal密碼建立在有限域GF（p）的乘法群的離散對數(shù)問題的困難性之上。而橢圓曲線密碼建立在橢圓曲線群的離散對數(shù)問題的困難性之上。兩者的主要區(qū)別是其離散對數(shù)問題所依賴的群不同。因此兩者有許多相似之處。五、橢圓曲線密碼5、橢圓曲線密碼67五、橢圓曲線密碼5、橢圓曲線密碼①

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

在上例中橢圓曲線上的解點所構(gòu)成的交換群恰好是循環(huán)群，但是一般并不一定。于是我們希望從中找出一個循環(huán)子群E1

?？梢宰C明當循環(huán)子群E1的階n是足夠大的素數(shù)時，這個循環(huán)子群中的離散對數(shù)問題是困難的。五、橢圓曲線密碼5、橢圓曲線密碼68五、橢圓曲線密碼5、橢圓曲線密碼①

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

設(shè)P和Q是橢圓曲線上的兩個解點，t為一正整數(shù)，且1≤t<n。對于給定的P和t，計算tP＝Q是容易的。但若已知P和Q點，要計算出t則是極困難的。這便是橢圓曲線群上的離散對數(shù)問題，簡記為ECDLP(EllipticCurveDiscreteLogarithmProblem)。五、橢圓曲線密碼5、橢圓曲線密碼69五、橢圓曲線密碼5、橢圓曲線密碼①

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

除了幾類特殊的橢圓曲線外，對于一般ECDLP目前尚沒有找到有效的求解方法。于是可以在這個循環(huán)子群E1中建立任何基于離散對數(shù)困難性的密碼，并稱這個密碼為橢圓曲線密碼。五、橢圓曲線密碼5、橢圓曲線密碼70五、橢圓曲線密碼②橢圓曲線密碼

T=<p,a,b,G,n,h>p為大于3素數(shù)，p確定了有限域GF（p）；元素a,b∈GF(p),a和b確定了橢圓曲線；G為循環(huán)子群E1的生成元點，n為素數(shù)且為生成元G的階，G和n確定了循環(huán)子群E1；h=|E|/n，并稱為余因子，h將交換群E和循環(huán)子群聯(lián)系起來。五、橢圓曲線密碼②橢圓曲線密碼71五、橢圓曲線密碼②橢圓曲線密碼

密鑰：用戶的私鑰定義為一個隨機數(shù)d，d∈{1,2,···,n-1}。用戶的公開鑰定義為Q點，Q=dG。五、橢圓曲線密碼②橢圓曲線密碼72五、橢圓曲線密碼②橢圓曲線密碼設(shè)d為用戶私鑰，Q為公鑰，將Q存入PKDB。設(shè)要加密的明文數(shù)據(jù)為M，將M劃分為一些較小的數(shù)據(jù)塊，M=[m1，m2，···，mt]，其中0≤mi<n。五、橢圓曲線密碼②橢圓曲線密碼73五、橢圓曲線密碼②橢圓曲線密碼加密過程：A把M加密發(fā)給B⑴A查PKDB，查到B的公開密鑰QB。⑵A選擇一個隨機數(shù)k，且k∈{1,2,···,n-1}。⑶A計算點X1（x1，y1）=kG。⑷A計算點X2（x2，y2）=kQB，如果分量x2=O，則轉(zhuǎn)⑵。⑸A計算密文C=mix2modn。⑹A發(fā)送加密數(shù)據(jù)（X1，C）給B。五、橢圓曲線密碼②橢圓曲線密碼74五、橢圓曲線密碼②橢圓曲線密碼解密過程：用戶B用自己的私鑰dB求出點X2：

dBX1=dB（kG）=k(dBG)=kQB

=X2（x2，y2）對C解密，得到明文mi=Cx2–1modn

。五、橢圓曲線密碼②橢圓曲線密碼75五、橢圓曲線密碼②橢圓曲線密碼橢圓曲線密碼的實現(xiàn)由于橢圓曲線密碼所依據(jù)的數(shù)學基礎(chǔ)比較復雜，從而使得其具體實現(xiàn)也比較困難。難點：安全橢圓曲線的產(chǎn)生；倍點運算。五、橢圓曲線密碼②橢圓曲線密碼76六、公鑰密碼的理論模型1、單向函數(shù)設(shè)函數(shù)y=f(x)，如果滿足以下兩個條件，則稱為單向函數(shù)：如果對于給定的x，要計算出y很容易；而對于給定的y，要計算出x很難。2、單向函數(shù)的應用安全HASH函數(shù)操作系統(tǒng)口令六、公鑰密碼的理論模型1、單向函數(shù)77六、公鑰密碼的理論模型3、利用單向函數(shù)構(gòu)造密碼用正變換作加密，加密效率高；用逆變換作解密，安全，敵手不可破譯；但是加密后不能還原。六、公鑰密碼的理論模型3、利用單向函數(shù)構(gòu)造密碼78六、公鑰密碼的理論模型4、單向陷門函數(shù)

設(shè)函數(shù)y=f(x)，且f具有陷門，如果滿足以下兩個條件，則稱為單向陷門函數(shù)：如果對于給定的x，要計算出y很容易；而對于給定的y，如果不掌握陷門要計算出x很難，而如果掌握陷門要計算出x就很容易。六、公鑰密碼的理論模型4、單向陷門函數(shù)79六、公鑰密碼的理論模型5、單向陷門函數(shù)的應用用正變換作加密，加密效率高；用逆變換作解密，安全；

把陷門信息作為密鑰，且只分配給合法用戶。確保合法用戶能夠方便地解密，而非法用戶不能破譯。六、公鑰密碼的理論模型5、單向陷門函數(shù)的應用80六、公鑰密碼的理論模型6、單向函數(shù)的研究現(xiàn)狀理論上：不能證明單向函數(shù)一定存在；實際上：只要函數(shù)的單向性足夠工程應用就行；

實際上已找到的單向性足夠的函數(shù)有：

①合數(shù)的因子分解問題

大素數(shù)的乘積容易計算（pqn），而大合數(shù)的因子分解困難(npq)。

②有限域上的離散對數(shù)問題

有限域上大素數(shù)的冪乘容易計算（ab

c），而對數(shù)計算困難(logacb)。六、公鑰密碼的理論模型6、單向函數(shù)的研究現(xiàn)狀81公鑰密碼方案的實際應用實現(xiàn)速度通常用于交換對稱算法的加密密鑰數(shù)字簽名算法公鑰密碼方案的實際應用實現(xiàn)速度82公鑰密碼安全性分析窮舉攻擊：可使用長密鑰來對抗由公鑰來計算私鑰：目前為止，雖然對特定公鑰算法，均未證明該方法不可行。但公鑰仍廣泛使用公鑰密碼安全性分析窮舉攻擊：可使用長密鑰來對抗83對稱加密VS公鑰加密對稱加密VS公鑰加密84公鑰加密VS公鑰簽名公鑰加密：可以提供保密性，但不能提供認證性。因為任何人都可以用A的公鑰對消息進行加密，并發(fā)送給A。公鑰簽名：可以提供認證性，但不能提供保密性。因為簽名的驗證過程中消息必須為明文的形式。要同時實現(xiàn)加密和認證，可以同時使用加密和簽名(一般為：先簽名，后加密)公鑰加密VS公鑰簽名公鑰加密：可以提供保密性，但不能提851、公開密鑰密碼體制的基本思想是什么？2、公開密鑰密碼體制的基本工作方式有哪些？并進行簡單的描述。1、公開密鑰密碼體制的基本思想是什么？8651、天下之事常成于困約，而敗于奢靡?！懹?/p>

52、生命不等于是呼吸，生命是活動?！R梭

53、偉大的事業(yè)，需要決心，能力，組織和責任感?！撞飞?/p>

54、唯書籍不朽?！獑烫?/p>

55、為中華之崛起而讀書?！芏鱽碇x謝！51、天下之事常成于困約，而敗于奢靡?！懹?/p>

52、87公開密鑰密碼51、山氣日夕佳，飛鳥相與還。52、木欣欣以向榮，泉涓涓而始流。53、富貴非吾愿，帝鄉(xiāng)不可期。54、雄發(fā)指危冠，猛氣沖長纓。55、土地平曠，屋舍儼然，有良田美池桑竹之屬，阡陌交通，雞犬相聞。公開密鑰密碼公開密鑰密碼51、山氣日夕佳，飛鳥相與還。52、木欣欣以向榮，泉涓涓而始流。53、富貴非吾愿，帝鄉(xiāng)不可期。54、雄發(fā)指危冠，猛氣沖長纓。55、土地平曠，屋舍儼然，有良田美池桑竹之屬，阡陌交通，雞犬相聞。密碼學公開密鑰密碼一、公開密鑰密碼體制的基本思想1、傳統(tǒng)密碼的缺點：①收發(fā)雙方持有相同密鑰，密鑰分配困難，網(wǎng)絡(luò)環(huán)境更突出。②不能方便地實現(xiàn)數(shù)字簽名，商業(yè)等應用不方便。Ke＝Kd公開密鑰密碼51、山氣日夕佳，飛鳥相與還。公開密鑰密碼公開密88密碼學公開密鑰密碼密碼學公開密鑰密碼89一、公開密鑰密碼體制的基本思想1、傳統(tǒng)密碼的缺點：①收發(fā)雙方持有相同密鑰，密鑰分配困難，網(wǎng)絡(luò)環(huán)境更突出。②不能方便地實現(xiàn)數(shù)字簽名，商業(yè)等應用不方便。Ke

＝Kd一、公開密鑰密碼體制的基本思想1、傳統(tǒng)密碼的缺點：Ke＝90一、公開密鑰密碼體制的基本思想2、公開密鑰密碼的基本思想：①將密鑰K一分為二，一個專門加密，一個專門解密：

Ke≠Kd

②且由Ke

不能計算出Kd

，于是可將Ke公開，使密鑰分配簡單。③由于Ke≠Kd且由Ke

不能計算出Kd

，所以

Kd

便成為用戶的指紋，于是可方便地實現(xiàn)數(shù)字簽名。

一、公開密鑰密碼體制的基本思想2、公開密鑰密碼的基本思想：91一、公開密鑰密碼體制的基本思想3、公開密鑰密碼的基本條件：①E和D互逆；基本條件，保密條件

D（E（M））＝M②Ke≠Kd且由Ke

不能計算出Kd

；安全條件③E和D都高效。實用條件④E（D（M））＝M保真條件

如果滿足①②③可保密，如果滿足②③④可保真，如果4個條件都滿足，可同時保密保真。

一、公開密鑰密碼體制的基本思想3、公開密鑰密碼的基本條件：92二、公開密鑰密碼的基本工作方式設(shè)

M為明文，C為密文，E為公開密鑰密碼的加密算法，D為解密算法，Ke為公開的加密鑰，Kd為保密的解密鑰，每個用戶都分配一對密鑰，而且將所有用戶的公開的加密鑰Ke存入共享的密鑰庫PKDB。二、公開密鑰密碼的基本工作方式93二、公開密鑰密碼的基本工作方式1、確保數(shù)據(jù)秘密性：AB發(fā)方：①A首先查PKDB，查到B的公開的加密鑰KeB

。②A用KeB加密M得到密文C：C=E（M，KeB）

③A發(fā)C給B。收方：①B接受C。②B用自己的KdB解密，得到明文M=D(C，KdB)。M二、公開密鑰密碼的基本工作方式1、確保數(shù)據(jù)秘密性：A94二、公開密鑰密碼的基本工作方式1、確保數(shù)據(jù)秘密性：安全性分析：①只有B才有KdB，因此只有B才能解密，所以確保了秘密性。②任何人都可查PKDB得到B的KeB，所以任何人都可冒充A給B發(fā)送數(shù)據(jù)。不能確保真實性。

二、公開密鑰密碼的基本工作方式1、確保數(shù)據(jù)秘密性：95二、公開密鑰密碼的基本工作方式2、確保數(shù)據(jù)真實性：AB發(fā)方：①A首先用自己的KdA對M解密，得到C=D(M，KdA)。②A發(fā)C給B。

收方：①B接受C。②B查PKDB查到A的公開的加密鑰KeA

。③B用KeA加密C，得到明文M=E（C，KeA）。M二、公開密鑰密碼的基本工作方式2、確保數(shù)據(jù)真實性：A96二、公開密鑰密碼的基本工作方式2、確保數(shù)據(jù)真實性：安全性分析：①只有A才有KdA，因此只有A才能解密產(chǎn)生C，所以確保了真實性。②任何人都可查PKDB得到A的KeA，所以任何人都可加密得到明文。不能確保秘密性。

二、公開密鑰密碼的基本工作方式2、確保數(shù)據(jù)真實性：97二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性：AB發(fā)方：①A首先用自己的KdA對M解密，得到S：S=D(M，KdA)②查PKDB，查到B的公開的加密鑰KeB。

③用KeB加密S得到C：C=E（S，KeB）④A發(fā)C給B。

M二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性98二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性：收方：①B接受C。②B用自己的KdB解密C，得到S：S=D（C，KdB）③B查PKDB查到A的公開的加密鑰KeA

。④B用A的公開的加密鑰KeA

加密S，得到M：M=E（S，KeA）二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性99二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性：安全性分析：①只有A才有KdA，因此只有A才能解密產(chǎn)生S，所以確保了真實性。②只有B才有KdB，因此只有B才能獲得明文，所以確保了秘密性。

二、公開密鑰密碼的基本工作方式3、同時確保數(shù)據(jù)秘密性和真實性100三、RSA公開密鑰密碼1978年美國麻省理工學院的三名密碼學者R.L.Rivest,A.Shamir和L.Adleman提出了一種基于大合數(shù)因子分解困難性的公開密鑰密碼，簡稱為RSA密碼。RSA密碼被譽為是一種風格幽雅的公開密鑰密碼。既可用于加密，又可用于數(shù)字簽名，安全、易懂。RSA密碼已成為目前應用最廣泛的公開密鑰密碼。三、RSA公開密鑰密碼1978年美國麻省理工學院的三名密碼學101三、RSA公開密鑰密碼1、加解密算法①隨機地選擇兩個大素數(shù)p和q，而且保密；②計算n=pq，將

n公開；③計算φ(n)=(p-1)(q-1)，對φ(n)保密；④隨機地選取一個正整數(shù)e，1<e<φ(n)且（e，φ(n)）=1，將e公開；⑤根據(jù)ed＝1modφ(n)，求出d，并對d保密；⑥加密運算：C＝Memodn⑦解密運算：M＝Cdmodn

三、RSA公開密鑰密碼1、加解密算法102三、RSA公開密鑰密碼2、算法論證①E和D的可逆性要證明：D(E(M))=MM＝Cd＝(Me)d＝Medmodn因為ed＝1modφ(n)，這說明ed＝tφ(n)+1,其中t為某整數(shù)。所以，

Med＝Mtφ(n)+1modn。因此要證明Med＝Mmodn，只需證明

Mtφ(n)+1＝Mmodn。三、RSA公開密鑰密碼2、算法論證103三、RSA公開密鑰密碼2、算法論證①E和D的可逆性在（M，n）＝1的情況下，根據(jù)數(shù)論(Euler定理)，Mtφ(n)＝1modn，于是有，Mtφ(n)+1＝Mmodn。三、RSA公開密鑰密碼2、算法論證104三、RSA公開密鑰密碼2、算法論證①E和D的可逆性在（M，n）≠1的情況下，分兩種情況：第一種情況：M∈{1,2,3,…,n-1}因為n=pq，p和q為素數(shù)，M∈{1,2,3,…,n-1}，且（M，n）≠1。這說明M必含p或q之一為其因子，而且不能同時包含兩者，否則將有M≥n，與M∈{1,2,3,…,n-1}矛盾。三、RSA公開密鑰密碼2、算法論證105三、RSA公開密鑰密碼2、算法論證①E和D的可逆性不妨設(shè)M＝ap。又因q為素數(shù)，且M不包含q，故有（M，q）＝1，于是有，Mφ(q)＝1modq。進一步有，Mt(p-1)φ(q)＝1modq。因為q是素數(shù)，φ(q)＝（q-1），所以t(p-1)φ(q)＝tφ(n)，所以有Mtφ(n)＝1modq。三、RSA公開密鑰密碼2、算法論證106三、RSA公開密鑰密碼2、算法論證①E和D的可逆性于是，Mtφ(n)＝bq+1，其中b為某整數(shù)。兩邊同乘M，Mtφ(n)+1＝bqM+M。因為M＝ap，故Mtφ(n)+1＝bqap+M=abn+M。取模n得，Mφ(n)+1＝Mmodn。三、RSA公開密鑰密碼2、算法論證107三、RSA公開密鑰密碼2、算法論證①E和D的可逆性在（M，n）≠1的情況下，分兩種情況：第二種情況：M＝0當M＝0時，直接驗證，可知命題成立。

三、RSA公開密鑰密碼2、算法論證108三、RSA公開密鑰密碼2、算法論證②加密和解密運算的可交換性

D(E(M))=(Me)d=Med=(Md))e=E(D(M))modn所以，RSA密碼可同時確保數(shù)據(jù)的秘密性和數(shù)據(jù)的真實性。③加解密算法的有效性

RSA密碼的加解密運算是模冪運算，有比較有效的算法。三、RSA公開密鑰密碼2、算法論證109三、RSA公開密鑰密碼2、算法論證④在計算上由公開密鑰不能求出解密鑰

小合數(shù)的因子分解是容易的，然而大合數(shù)的因子分解卻是十分困難的。關(guān)于大合數(shù)的因子分解的時間復雜度下限目前尚沒有一般的結(jié)果，迄今為止的各種因子分解算法提示人們這一時間下限將不低于O（EXP（lnNlnlnN）1/2）。根據(jù)這一結(jié)論，只要合數(shù)足夠大，進行因子分解是相當困難的。三、RSA公開密鑰密碼2、算法論證110三、RSA公開密鑰密碼2、算法論證④在計算上由公開密鑰不能求出解密鑰假設(shè)截獲密文C，從中求出明文M。他知道M≡Cdmodn，因為n是公開的，要從C中求出明文M，必須先求出d，而d是保密的。但他知道，ed≡1modφ(n)，e是公開的，要從中求出d，必須先求出φ(n)，而φ(n)是保密的。三、RSA公開密鑰密碼2、算法論證111三、RSA公開密鑰密碼2、算法論證④在計算上由公開密鑰不能求出解密鑰但他又知道，φ(n)=(p-1)(q-1)，要從中求出φ(n)，必須先求出p和q，而p和q是保密的。但他知道，n=pq，要從n求出p和q，只有對n進行因子分解。而當n足夠大時，這是很困難的。三、RSA公開密鑰密碼2、算法論證112三、RSA公開密鑰密碼2、算法論證④在計算上由公開密鑰不能求出解密鑰

只要能對n進行因子分解，便可攻破RSA密碼。由此可以得出，破譯RSA密碼的困難性≤對n因子分解的困難性。目前尚不能證明兩者是否能確切相等，因為不能確知除了對n進行因子分解的方法外，是否還有別的更簡捷的破譯方法。目前只有Rabin密碼具有：破譯Rabin密碼的困難性=對n因子分解的困難性。三、RSA公開密鑰密碼2、算法論證1133、RSA密碼的實現(xiàn)1）參數(shù)選擇為了確保RSA密碼的安全，必須認真選擇密碼參數(shù)：①p和q要足夠大；

一般應用：p和q應512b重要應用：p和q應1024b

②p和q應為強素數(shù)

文獻指出，只要(p-1)、(p+1)、(q-1)、(q+1)四個數(shù)之一只有小的素因子，n就容易分解。③p和q的差要大；

三、RSA公開密鑰密碼3、RSA密碼的實現(xiàn)三、RSA公開密鑰密碼114三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)1）參數(shù)選擇④（p-1）和（q-1）的最大公因子要小。

如果（p-1）和（q-1）的最大公因子太大，則易受迭代加密攻擊。⑤e的選擇

隨機且含1多就安全，但加密速度慢。于是，有的學者建議取e＝216+1＝65537⑥d的選擇

d不能太小，要足夠大⑦不要許多用戶共用一個模n；易受共模攻擊三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)115三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)2）大素數(shù)的產(chǎn)生①概率產(chǎn)生

目前最常用的概率性算法是Miller檢驗算法。Miller檢驗算法已經(jīng)成為美國的國家標準。②確定性產(chǎn)生確定性測試

確定性構(gòu)造三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)116三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)3）大素數(shù)的運算①快速乘方算法反復平方乘算法：設(shè)e的二進制表示為

e＝ek-12k-1+ek-22k-2+...,+e121+e0則Me=((…(Mek-1)2Mek-2)2…Me1)2Me0modn設(shè)e為k位二進制數(shù)，w(e)為e的二進制系數(shù)中為1的個數(shù)，則最多只需要計算w(e)-1次平方和w(e)次數(shù)的模乘。從而大大簡化了計算。三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)117三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)3）大素數(shù)的運算②快速模乘算法反復平方乘算法解決了快速乘方取模的問題，仍未解決快速模乘的問題；Montgomery算法是一種快速模乘的好算法；將以上兩種算法結(jié)合成為實現(xiàn)RSA密碼的有效方法。硬件協(xié)處理器是提高運算效率的有效方法。三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)118三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)3）大素數(shù)的運算Montgomery算法的思路：要計算Y=ABmodn,因為n很大，取模運算困難，采取一個小的模R，回避大模的計算。

利用空間換時間，多用存儲空間換取快速。

缺點：不能直接計算出Y=ABmodn，只能計算出中間值A(chǔ)BR-1modn，因此還需要預處理和調(diào)整運算。一次性計算Y=ABmodn并不劃算。適合：RSA等密碼中多次的模乘計算。三、RSA公開密鑰密碼

3、RSA密碼的實現(xiàn)119三、RSA公開密鑰密碼4、對RSA公開密鑰密碼的主要攻擊窮舉攻擊：窮舉所有可能的私鑰數(shù)學攻擊：因式分解攻擊參數(shù)的選取不當造成的攻擊選擇密文攻擊共模攻擊小指數(shù)攻擊

計時攻擊三、RSA公開密鑰密碼4、對RSA公開密鑰密碼的主要攻擊120RSA公鑰加密的攻擊—因子分解因子分解攻擊RSA的途徑包括?分解n為p，q?直接確定φ(n),而不確定p，q?直接確定d，而不確定φ(n)?可以證明，從e和n確定φ(n)或者d的算法至少和因子分解一樣費時。因此，將因子分解的困難性作為評價RSA安全性的基準。RSA公鑰加密的攻擊—因子分解因子分解攻擊RSA的途徑包括121RSA公鑰加密的攻擊—選擇密文攻擊RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實體簽署。然后，經(jīng)過計算就可得到它所想要的信息。RSA公鑰加密的攻擊—選擇密文攻擊RSA在選擇密文攻擊面前很122RSA公鑰加密的攻擊—共模攻擊共模攻擊：指通信系統(tǒng)中使用相同的n，且存在兩個用戶的公鑰e1和e2是互質(zhì)的，則可以由這兩個用戶對同一條明文的不同加密結(jié)果，恢復出原始明文攻擊方法：設(shè)c1≡me1(modn)c2≡me2(modn)攻擊者知道e1,e2,n,c1,c2因為e1和e2互質(zhì)，故用Euclidean算法能找到r和s，使得t×e1+s×e2=1(注意是相等)則c1t×c2s=m(modn)不能用同一個n來生成密鑰RSA公鑰加密的攻擊—共模攻擊123RSA公鑰加密的攻擊—小指數(shù)攻擊Wiener在1990年指出，當d<n1/4時，從e和n可以很容易求出密鑰dRSA公鑰加密的攻擊—小指數(shù)攻擊124RSA公鑰加密的攻擊—計時攻擊思想：利用指數(shù)中某一位為0或者為1時，硬件加密速度不同RSA公鑰加密的攻擊—計時攻擊125四、ELGamal公鑰密碼1、基本情況：①ELGamal密碼是除了RSA密碼之外最有代表性的公開密鑰密碼。②RSA密碼建立在大合數(shù)分解的困難性之上。③ELGamal密碼建立在離散對數(shù)的困難性之上。所謂離散對數(shù)，就是給定正整數(shù)x，y，n，求出正整數(shù)k（如果存在的?話），使y≡xk(modn)。四、ELGamal公鑰密碼1、基本情況：所謂離散對數(shù)，就是給126四、ELGamal公鑰密碼2、離散對數(shù)問題：①設(shè)p為素數(shù)，則模p的剩余構(gòu)成有限域：

Fp={0,1,2,…,p-1}Fp的非零元構(gòu)成循環(huán)群Fp*

Fp*={1,2,…,p-1}={α，α2，α3，，αp-1}，則稱α為Fp*的生成元或模p的本原元。②求α的摸冪運算為: y=αxmodp，1≤x≤p-1,

四、ELGamal公鑰密碼2、離散對數(shù)問題：127四、ELGamal公鑰密碼2、離散對數(shù)問題：求對數(shù)X的運算為

x=logαy，1≤x≤p-1由于上述運算是定義在模p有限域上的，所以稱為離散對數(shù)運算。③從x計算y是容易的。可是從y計算x就困難得多，利用目前最好的算法，對于小心選擇的p將至少需用O(p?)次以上的運算，只要p足夠大，求解離散對數(shù)問題是相當困難的。四、ELGamal公鑰密碼2、離散對數(shù)問題：128四、ELGamal公鑰密碼3、算法準備：隨機地選擇一個大素數(shù)p，且要求p-1有大素數(shù)因子。再選擇一個模p的本原元α。將p和α公開。⑴密鑰生成用戶隨機地選擇一個整數(shù)d作為自己的秘密的解密鑰，2≤d≤p-2。計算y=αd

modp，取y為自己的公開的加密鑰。由公開鑰y

計算秘密鑰d，必須求解離散對數(shù)，而這是極困難的。

四、ELGamal公鑰密碼3、算法129四、ELGamal公鑰密碼⑵加密將明文消息M（0≤M≤p-1)加密成密文的過程如下：①隨機地選取一個整數(shù)k，2≤k≤p-2。②計算：

U＝y(tǒng)kmodp；C1＝αkmodp；C2＝UMmodp；③取C＝（C1，C2）作為的密文。

四、ELGamal公鑰密碼⑵加密130四、ELGamal公鑰密碼⑶解密將密文（C1，C2）解密的過程如下：①計算V＝C1dmodp；②計算M＝C2

V-1modp。四、ELGamal公鑰密碼⑶解密131四、ELGamal公鑰密碼解密的可還原性可證明如下：

C2

V-1modp＝(UM)V-1modp＝UM（C1d）-1modp＝UM（（αk）d）-1modp＝UM（（αd）k）-1modp＝UM（（y）k）-1modp＝UM（U）-1modp＝Mmodp四、ELGamal公鑰密碼解密的可還原性可證明如下：132四、ELGamal公鑰密碼4、安全性由于ELGamal密碼的安全性建立在GF（p）離散對數(shù)的困難性之上，而目前尚無求解GF（p）離散對數(shù)的有效算法，所以在p足夠大時ELGamal密碼是安全的。為了安全p應為150位以上的十進制數(shù)，而且p-1應有大素因子。為了安全加密和簽名所使用的k必須是一次性的。d和k都不能太小。四、ELGamal公鑰密碼4、安全性133四、ELGamal公鑰密碼4、安全性如果k不是一次性的，時間長了就可能被攻擊著獲得。又因y是公開密鑰，攻擊者自然知道。于是攻擊者就可以根據(jù)U＝y(tǒng)kmodp計算出U，進而利用Euclid算法求出U－1。又因為攻擊者可以獲得密文C2，于是可根據(jù)式C2＝UMmodp通過計算U－1C2得到明文M。設(shè)用同一個k加密兩個不同的明文M和M’，相應的密文為（C1，C2）和（C1’，C2’）。因為C2∕C2’＝M∕M’，如果攻擊者知道M，則很容易求出M’。

四、ELGamal公鑰密碼4、安全性134四、ELGamal公鑰密碼5、ELGamal密碼的應用

由于ELGamal密碼的安全性得到世界公認，所以得到廣泛的應用。著名的美國數(shù)字簽名標準DSS，采用了ELGamal密碼的一種變形。為了適應不同的應用，人們在應用中總結(jié)出18種不同的ELGamal密碼的變形。四、ELGamal公鑰密碼5、ELGamal密碼的應用135四、ELGamal公鑰密碼5、ELGamal密碼的應用

①加解密速度快 由于實際應用時ELGamal密碼運算的素數(shù)p比RSA要小，所以ELGamal密碼的加解密速度比RSA稍快。②隨機數(shù)源 由ELGamal密碼的解密鑰d和隨機數(shù)k都應是高質(zhì)量的隨機數(shù)。因此，應用ELGamal密碼需要一個好的隨機數(shù)源，也就是說能夠快速地產(chǎn)生高質(zhì)量的隨機數(shù)。③大素數(shù)的選擇 為了ELGamal密碼的安全，p應為150位（十進制數(shù)）以上的大素數(shù)，而且p-1應有大素因子。

四、ELGamal公鑰密碼5、ELGamal密碼的應用136五、橢圓曲線密碼1、橢圓曲線密碼的一般情況受ELGamal密碼啟發(fā)，在其它離散對數(shù)問題難解的群中，同樣可以構(gòu)成ELGamal密碼。于是人們開始尋找其它離散問題難解的群。研究發(fā)現(xiàn)，有限域GF（p）上的橢圓曲線的解點構(gòu)成交換群，而且離散對數(shù)問題是難解的。于是可在此群上建立ELGamal密碼，并稱為橢圓曲線密碼。五、橢圓曲線密碼1、橢圓曲線密碼的一般情況137五、橢圓曲線密碼1、橢圓曲線密碼的一般情況橢圓曲線密碼已成為除RSA密碼之外呼聲最高的公鑰密碼之一。它密鑰短、簽名短，軟件實現(xiàn)規(guī)模小、硬件實現(xiàn)電路省電。普遍認為，160位長的橢圓曲線密碼的安全性相當于1024位的RSA密碼，而且運算速度也較快。五、橢圓曲線密碼1、橢圓曲線密碼的一般情況138五、橢圓曲線密碼1、橢圓曲線密碼的一般情況一些國際標準化組織已把橢圓曲線密碼作為新的信息安全標準。如，IEEEP1363/D4，ANSIF9.62