第四章公鑰加密

4．1概述

4．2RSA公鑰加密算法

4．3ElGamal公鑰加密算法

4．4橢圓曲線上公鑰加密算法公開鑰明文密文私鑰明文秘密鑰秘密鑰明文密文明文4．1概述公鑰密碼與對稱鑰密碼的比較：公鑰密碼：

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

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

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

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

公鑰密碼與對稱鑰密碼的應(yīng)用：公鑰密碼：產(chǎn)生有效的數(shù)字簽名，密鑰管理；

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

稱為混合密碼系統(tǒng)。大數(shù)分解問題——RSA公鑰密碼有限域上的離散對數(shù)問題——ElGamal公鑰密碼橢圓曲線上離散對數(shù)問題——MV公鑰密碼單向函數(shù)：計算F(m,Kp)＝c容易，但由c計算m不容易。陷門單向函數(shù)：如果已知Ks，則由c計算m是容易的。什么樣的函數(shù)是單向函數(shù)？如何利用單向函數(shù)、公開鑰進(jìn)行加密？如何嵌入陷門？計算難易——計算復(fù)雜性理論為基礎(chǔ)；數(shù)論困難問題(2)令n＝pq，用戶公布n。計算并保密。一、RSA算法：Rivest-Shamir-Adleman(1)選擇一對不同的大素數(shù)p和q，將p和q保密。(3)選取正整數(shù)e，使其滿足

e是公開鑰。

1.密鑰生成4．2

RSA公鑰加密算法2.加密過程3.解密過程解密過程的正確性：當(dāng)m與n不互素時，設(shè)m=kp，可得同樣結(jié)論。例題-1：（1）密鑰生成：p＝11,q=23,n=pq=11×23=253,

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

對于明文m=165，則密文（3）解密過程：二、RSA的安全性1、RSA的安全性建立在合數(shù)n的分解是困難的基礎(chǔ)上，如果分解已知，則就能求出密鑰d；

2、如果已知，則可得到n的分解p和q；所以p和q以上方程的解，此方程是容易解的。

3、p和q應(yīng)為安全素數(shù)或強(qiáng)素數(shù)。

p=2p1+1的素數(shù)為安全素數(shù)，其中p1為素數(shù)。強(qiáng)素數(shù)是p-1、p+1都有大素因子p1、p2，并且p11，p21還有大素因子。

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

6、單純的RSA不能抵抗選擇密文攻擊。泄漏一些信息，如明文奇偶性，還有：5、隨著計算能力的不斷增加和因子分解算法能力不斷提高，

p和q的選擇越來越大。目前較安全的RSA的n一般為1024bit或2048bit。三、模冪和模逆算法模冪算法：例題-2：147＝128＋16＋3

＝10010011

為下一步做準(zhǔn)備！x存放中間結(jié)果！再如：322mod12=9定理：gcd(a,b)=sa+tb,a和b為正整數(shù)。模逆算法：

可以寫出迭代算法：

i022010173301211-73例題-1中3-1mod220，可由下表得出：gcd(220,3)=1=220-73*3

3-1mod220=-73=147一、離散對數(shù)問題群元素的階：乘法群中滿足的最小正整數(shù)m。

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

g稱為G的生成元。

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

ElGamal公鑰加密算法是域，3和5是它的本原元。例題-3：有限域上的離散對數(shù)問題：給定一個素數(shù)p和Zp的一個本原元，對于找一個唯一整數(shù)使得通常記為例題-4：已知,求對于一般離散對數(shù)問題，沒有有效算法（多項式時間的）。只有指數(shù)時間的算法，所以是困難的…….明文空間為，密文空間為選擇大素數(shù)p，是一個本原元，p和是公開的；對于任意明文，秘密隨機(jī)選取一個整數(shù),密文為：隨機(jī)選擇整數(shù)，計算，是公鑰，d

是私鑰；二、ElGamal密碼體制

1.密鑰生成2.加密過程

3.解密過程

解密變換的正確性：對任意密文明文為（3）用戶A想秘密地發(fā)送明文M＝11給用戶B，A選擇一個隨機(jī)數(shù)，并計算（2）用戶B選擇整數(shù)d＝10，作為自己的私鑰，計算作為自己的公鑰；例題-5：（1）選取素數(shù)p＝19，生成元；A將（14，17）發(fā)送給B；

（4）B計算

三、ElGamal密碼體制的安全性

1、ElGamal是基于有限域上的離散對數(shù)困難性；2、素數(shù)p至少為300位十進(jìn)制數(shù)；3、p-1至少有一個大素因子。一、有限域上的橢圓曲線(ellipticcurve)

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

系數(shù)在實數(shù)域上的，稱為實數(shù)域上的橢圓曲線；系數(shù)在有限域上的，稱為有限域上的橢圓曲線。橢圓曲線上的點，關(guān)于定義的加法，構(gòu)成交換群。4．4橢圓曲線上公鑰加密算法實數(shù)域上的橢圓曲線有限域（p為大于3的素數(shù)）上的橢圓曲線的點再加上一個無窮遠(yuǎn)點所組成的集合E。是滿足同余方程，其中保證有三個根可以在橢圓曲線上定義加法運算：對于任意點

設(shè)PQ直線的方程為：將帶入當(dāng)P≠Q(mào)時：根據(jù)根和系數(shù)的關(guān)系：因為PQ和E的第三個交點為：當(dāng)P＝Q時：的導(dǎo)數(shù)為可以證明：橢圓曲線E關(guān)于加法構(gòu)成一個交換群。Euler準(zhǔn)則：如果p是一個奇素數(shù)，則z是模p的平方剩余當(dāng)且僅當(dāng)

如何求出橢圓曲線的加法群？對每個x，計算再求同余方程：例題-6：設(shè)p＝11，E是由下列方程確定的Z11上的橢圓曲線。試確定E的所有點。06681874258933974810454是否平方剩余06No18No25Yes4，733Yes5，648No54Yes2，968No74Yes2，989Yes3，897No104Yes2，900112439455363758994101或者：所以E的所有點為：

(2，4),(2，7),(3，5),(3，6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(10,2),(10,9),再加上無窮遠(yuǎn)點O，共13個點。或者根據(jù)：例如：設(shè)，計算：（5,2）同樣可計算：所以，的階是13，是循環(huán)群E的生成元。橢圓曲線上的離散對數(shù)問題：設(shè)p>3是一個素數(shù)，E是有限域上的橢圓曲線，

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

1.密鑰生成

設(shè)p>3是一個素數(shù)，E是有限域上的橢圓曲線，是橢圓曲線上的一個點，并且階足夠大，使得由生成的循環(huán)子群中離散對數(shù)問題是難解的。p和E以及都公開。M-V公鑰密碼體制:隨機(jī)選取整數(shù)d，，計算。是公開鑰，d是保密的私鑰。明文空間為密文空間為

加密時，對于任意明文

秘密隨機(jī)選取一個整數(shù)k，密文為:3.解密過程2.加密過程明文為:解密過程的正確性：

例題-7：前例的橢圓曲線，設(shè)，私鑰d=7,假設(shè)明文x=(9,1),隨機(jī)選取的k=6,求相應(yīng)的密文。

解：

計算見后頁三、橢圓曲線上公鑰密碼的特點

優(yōu)點：同樣安全強(qiáng)度下密鑰短；速度快?？梢詰?yīng)用于計算和存儲能力小的智能卡等場合。

1、在一個使用RSA的公開密鑰系統(tǒng)中，你截獲了一個發(fā)給公鑰是e＝5，n＝35的用戶的密文c＝10，明文是什么？

2、在一個ElGamal公鑰密碼體制服務(wù)系統(tǒng)中，密鑰簽發(fā)中心給用戶A建立的ElGamal體制如下：選取素數(shù)p=29及

Zp的一個本原元，若交給用戶A保存的秘密密

鑰d＝7，則在（網(wǎng)絡(luò)）公共服務(wù)器上公布的公開密鑰

為（，，）。

（接下頁