第4章公鑰密碼技術(shù)2

第4章公鑰密碼技術(shù)本章主要內(nèi)容概述公鑰密碼提出的背景公鑰密碼的基本思想公鑰密碼的應(yīng)用 RSA公鑰密碼體制ElGamal公鑰密碼體制第4章公鑰密碼技術(shù)4.1概述

4.1.1公鑰密碼提出的背景

1．密鑰管理的困難性問題 傳統(tǒng)密鑰管理任何兩個(gè)用戶要進(jìn)行通信就需要一個(gè)密鑰，則n個(gè)用戶需要n(n-1)/2個(gè)密鑰，當(dāng)用戶量增大時(shí)密鑰空間急劇增大。

公鑰服務(wù)器傳統(tǒng)對(duì)稱加密法公鑰算法公鑰這一概念的真正貢獻(xiàn)是，它減少了網(wǎng)絡(luò)用戶必須管理的密鑰數(shù)。如果使用對(duì)稱加密法5個(gè)用戶的網(wǎng)絡(luò)需要10個(gè)保密密鑰，每個(gè)用戶都得記?。ú⒈Ｃ埽?個(gè)密鑰。但是在公鑰系統(tǒng)中，每個(gè)用戶只需記住他們自己的私鑰，從公共場所查找所需的公鑰即可第4章公鑰密碼技術(shù)2．系統(tǒng)的開放性問題

對(duì)稱密碼體制的密鑰分發(fā)方法要求密鑰共享各方互相信任，因此它不能解決陌生人間的密鑰傳遞問題

3．?dāng)?shù)字簽名問題 對(duì)稱加密算法難以實(shí)現(xiàn)抗抵賴的安全需求。第4章公鑰密碼技術(shù)公鑰密碼學(xué)的發(fā)展概述

1976年，WhitfieldDiffie和MartinHellman發(fā)表了的“Newdirectionsincryptography”。這篇?jiǎng)潟r(shí)代的文章奠定了公鑰密碼系統(tǒng)的基礎(chǔ)?？捎糜诒Ｃ芡ㄐ牛部捎糜跀?shù)字簽字。這一體制的出現(xiàn)在密碼學(xué)史上是劃時(shí)代的事件，它為解決計(jì)算機(jī)信息網(wǎng)中的安全提供了新的理論和技術(shù)基礎(chǔ)。自從公鑰密碼的概念被提出以來，相繼提出了許多公鑰密碼方案，如RSA、背包體制、McEliece、ElGamal體制等。在不斷的研究和實(shí)踐中，有些方案被攻破了，有些方案不太實(shí)用。關(guān)于最初十年的公鑰密碼技術(shù)的研究和發(fā)展，可參見文獻(xiàn)[W.Diffie.Thefirsttenyearsofpublic-keycryptography.ProceedingoftheIEEE,76(5),1988,560-577.]。公鑰密碼學(xué)的意義公鑰密碼學(xué)的發(fā)展是整個(gè)密碼學(xué)發(fā)展歷史中最偉大的一次革命公鑰密碼學(xué)和以前的傳統(tǒng)密碼學(xué)完全不同首先，公鑰算法是基于數(shù)學(xué)函數(shù)而不是基于替換和置換更重要的是，與只使用一個(gè)密鑰的對(duì)稱傳統(tǒng)密碼不同，公鑰密碼是非對(duì)稱的，它使用兩個(gè)獨(dú)立的密鑰。我們將會(huì)看到，使用兩個(gè)密鑰在消息的保密性，密鑰分配和認(rèn)證領(lǐng)域有著重要意義。第4章公鑰密碼技術(shù)關(guān)于公鑰密碼的常見的幾種誤區(qū)第一種誤解是從密鑰分析角度看，公鑰密碼比傳統(tǒng)密碼更安全。從抗密碼分析角度看，原則上不能說傳統(tǒng)密碼優(yōu)于公鑰密碼，也不能說公鑰密碼優(yōu)于傳統(tǒng)密碼第二種誤解是，公鑰密碼是一種通用的方法，所以傳統(tǒng)密碼已經(jīng)過時(shí)。其實(shí)不然，由于現(xiàn)有的公鑰密碼方法所需要的計(jì)算量大，所以取代傳統(tǒng)密碼似乎不太可能?！肮€密碼學(xué)僅限于用在密鑰管理和簽名這類應(yīng)用中，這幾乎是已被廣泛接受的事實(shí)”公鑰服務(wù)器傳統(tǒng)對(duì)稱加密法公鑰算法公鑰這一概念的真正貢獻(xiàn)是，它減少了網(wǎng)絡(luò)用戶必須管理的密鑰數(shù)。如果使用對(duì)稱加密法5個(gè)用戶的網(wǎng)絡(luò)需要10個(gè)保密密鑰，每個(gè)用戶都得記住（并保密）4個(gè)密鑰。但是在公鑰系統(tǒng)中，每個(gè)用戶只需記住他們自己的私鑰，從公共場所查找所需的公鑰即可第4章公鑰密碼技術(shù)4.1.2公鑰密碼的基本思想

公鑰密碼也稱為非對(duì)稱密碼。使用公鑰密碼的每一個(gè)用戶都分別擁有兩個(gè)密鑰：加密密鑰與解密密鑰，它們兩者并不相同，并且由加密密鑰得到解密密鑰在計(jì)算上是不可行的。每一個(gè)用戶的加密密鑰都是公開的。僅根據(jù)密碼算法和加密密鑰來確定解密密鑰在計(jì)算上是不可行的兩個(gè)密鑰中的任何一個(gè)都可用來加密，另一個(gè)用來解密基于公開密鑰的加密過程Joy明文輸入加密算法，如RSA等解密算法明文輸出Alice的私鑰Bob的公鑰環(huán)TedAliceMikeAlice的公鑰密文傳輸BobAlice加密基于公開密鑰的鑒別過程Bob的公鑰Joy明文輸入加密算法，如RSA等傳輸密文解密算法明文輸出Bob的私鑰Alice的公鑰環(huán)TedBobMikeBobAlice認(rèn)證對(duì)稱密碼公鑰密碼一般要求一般要求1.加密和解密使用相同的密鑰和相同的算法1.同一算法用于加密和解密，但加密和解密使用不同密鑰2.收發(fā)雙方必須共享密鑰2.發(fā)送方擁有加密或解密密鑰，而接收方擁有另一密鑰安全性安全安全性要求1.密鑰必須是保密1.兩個(gè)密鑰之一必須是保密的2.若沒有其他信息，則解密消息是不可能或至少是不可行的2.若沒有其他信息，則解密信息是不可能或至少是不可行的3.知道算法和若干密文不足以確定密鑰3.知道算法和其中一個(gè)密鑰以及若干密文不足以確定另一密鑰第4章公鑰密碼技術(shù)單向陷門函數(shù)

單向陷門函數(shù)可以被定義為如下函數(shù)f：（1）給出f的定義域中的任意元素x,f(x)的計(jì)算是容易的；（2）給出y=f(x)中的y要計(jì)算x時(shí)，若知道設(shè)計(jì)函數(shù)f時(shí)結(jié)合進(jìn)去的某種信息（該信息稱為陷門），則容易計(jì)算；若不知道該信息，則難以計(jì)算。 設(shè)計(jì)公鑰密碼體制可以轉(zhuǎn)換為尋找單向陷門函數(shù)。目前人們主要是基于如下的數(shù)學(xué)上的困難問題來設(shè)計(jì)單向函數(shù)和公鑰密碼體制：（1）大整數(shù)分解問題(如公鑰密碼體制RSA)；（2）有限域上的離散對(duì)數(shù)問題(如公鑰密碼體制ElGamal):（3）橢圓曲線上的離散對(duì)數(shù)問題(如公鑰密碼體制ECC)。第4章公鑰密碼技術(shù)4.1.3公鑰密碼的應(yīng)用

（1）機(jī)密性的實(shí)現(xiàn)發(fā)送方用接收方的公鑰加密消息，接收方用自己的私鑰來解密。（2）數(shù)字簽名發(fā)送方用自己的私鑰來簽名消息，接收方通過發(fā)送方對(duì)應(yīng)的公鑰來鑒別消息，并且發(fā)送方不能對(duì)自己的簽名進(jìn)行否認(rèn)。（3）密鑰分發(fā)和協(xié)商發(fā)送方和接收方基于公鑰密碼系統(tǒng)容易實(shí)現(xiàn)在公開信道上的大規(guī)模的密鑰分發(fā)和協(xié)商。費(fèi)馬定理和歐拉定理歐拉定理對(duì)任意互素的a和n有：aφ(n)=1modnφ(n)是小于n且與n互素的整數(shù)的個(gè)數(shù)費(fèi)馬定理費(fèi)馬定理可如下描述：若p是素?cái)?shù)，a是正整數(shù)且不能被p整除，則 ap-1≡1（modp）另一種有用的表示形式是：若p是素?cái)?shù)且a是任意正整數(shù)，則： ap≡a(modp)公鑰加密體制:

RSA密碼體制 1978年，MIT三位年青數(shù)學(xué)家R.L.Rivest，A.Shamir和L.Adleman發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰的方法，稱作MIT體制，后來被廣泛稱之為RSA體制。它既可用于加密、又可用于數(shù)字簽字，易懂且易于實(shí)現(xiàn)，是目前仍然安全并且逐步被廣泛應(yīng)用的一種體制。國際上一些標(biāo)準(zhǔn)化組織ISO、ITU、及SWIFT等均已接受RSA體制作為標(biāo)準(zhǔn)。在Internet中所采用的PGP(PrettyGoodPrivacy)中也將RSA作為傳送會(huì)話密鑰和數(shù)字簽字的標(biāo)準(zhǔn)算法。4.2.1RSA的算法描述（1）密鑰的生成

1.選擇兩個(gè)大素?cái)?shù)p，q，（p，q為互異素?cái)?shù)，需要保密），

2.計(jì)算n=p×q，

(n)=(p－1)×(q－1)3.選擇整數(shù)e使gcd(

(n)，e)=1,1<e<

(n)4.計(jì)算d，使d=e－1mod

(n),

得到：公鑰為{e,n}；私鑰為{d,n}（2）加密(用e，n)：明文：M<n，密文C=Me(modn).（3）

解密(用d，n)：密文C，明文M=Cd(modn)第4章公鑰密碼技術(shù)RSA密碼體制1.方案：獨(dú)立地選取兩大素?cái)?shù)p1和p2(各100～200位十進(jìn)制數(shù)字)，計(jì)算n=p×q，其歐拉函數(shù)值

(n)=(p－1)(q－1)。隨機(jī)選一整數(shù)e，1

e<

(n)，(

(n),e)=1。因而在模

(n)下，e有逆元d=e-1mod

(n)，取公鑰為n，e。秘密鑰為d。

(p,q不再需要，可以銷毀。)

加密：將明文分組，各組在modn下可惟一地表示。各組長達(dá)200位十進(jìn)數(shù)字。可用明文集Az={x：1

x<n,(x,n)=1}

密文y=xemodn解密：x=yd

modn證明：yd=(xe)d=xde，因?yàn)閐e

1mod

(n)而有de=q

(n)＋1。由歐拉定理，(x,n)=1意味x

(n)

1modn，故有yd=xde=xk

(n)+1

x

xk

(n)=x

1=xmodn陷門函數(shù)：Z=(p,q,d)

RSA密碼體制(續(xù)）RSA算法舉例(1)選擇兩個(gè)素?cái)?shù)p=7,q=17；(2)計(jì)算n=p*q=7*17=119;(3)計(jì)算φ(n)=(p-1)(q-1)=(7-1)(17-1)=96(4)選擇一個(gè)隨機(jī)整數(shù)e=5，且1<e<φ(n)=96，滿足gcd(e,φ(n))=1；則公鑰Pk=（5，119）；(5)計(jì)算d，(d*e)modφ(n)=1,即(d*5)mod96=1，d=77；則私鑰Sk=（77，119）；設(shè)明文P=19；加密：195mod119=66，傳送密文C=66；解密：6677mod119=19，獲得明文P=19。第4章公鑰密碼技術(shù)4.2.3RSA的安全性

RSA的安全性是基于分解大整數(shù)的困難性假定，之所以為假定是因?yàn)槠淅щy性至今還未能證明。

若能將n分解為兩個(gè)素?cái)?shù)因子p，q，則可計(jì)算

(n)=(p－1)(q

－1)，d=e－1mod

(n)

因此，不難得出結(jié)論：破譯RSA不會(huì)比大整數(shù)分解更加困難!

(1)對(duì)模n的長度必須足夠長，至少為1024比特

(2)p和q的長度應(yīng)該相差不多；(3)p

1和q

1都應(yīng)該包含大的素因子；(4)gcd(p

1,q

1)應(yīng)該很小；(5)d<n1/4。RSA的安全性（續(xù)）窮舉攻擊：這種方法試圖窮舉所有可能的私鑰。數(shù)學(xué)攻擊：有多種數(shù)學(xué)攻擊方法，他們的實(shí)質(zhì)都是試圖分解兩個(gè)素?cái)?shù)的乘積。計(jì)時(shí)攻擊：這類方法依賴于解密算法的運(yùn)行時(shí)間。選擇密文攻擊：這種攻擊利用了RSA算法的性質(zhì)第4章公鑰密碼技術(shù)（1）不同的用戶選用的素?cái)?shù)不能相同（2）一般不能直接應(yīng)用RSA進(jìn)行加解密

由于RSA算法是決定性算法（即對(duì)相同的明文始終會(huì)給出相同的密文）和具有特殊的代數(shù)結(jié)構(gòu)等原因，用RSA算法進(jìn)行直接加密在很多環(huán)境下是不安全的。故在使用RSA進(jìn)行加密前，需要對(duì)明文做某種預(yù)處理，一般是進(jìn)行隨機(jī)化的填充。4.3ElGamal公鑰密碼體制

4.3ElGamal公鑰密碼體制

ElGamal密碼體制是T.ElGamal于1985年提出，是最有名的公鑰密碼體制之一，它的安全性是基于離散對(duì)數(shù)問題.

1．密鑰的生成選取大素?cái)?shù)p，g∈Zp*是一個(gè)本原元（生成元）。

p、g

作為系統(tǒng)參數(shù)所有用戶共享。系統(tǒng)中每個(gè)用戶U都隨機(jī)挑選一個(gè)整數(shù)x，2≤x≤p－2，并計(jì)算：

y=gx(modp)，

y作為用戶U的公開密鑰，而x作為用戶U的秘密密鑰第4章公鑰密碼技術(shù)4.3ElGamal公鑰密碼體制（續(xù)）2.加密：(1)用戶A先把明文M編碼為一個(gè)在0到(p－1)之間的整數(shù)m

作為傳輸?shù)拿魑模?2)用戶A挑選一個(gè)秘密隨機(jī)數(shù)r(

2≤r≤p－2)，并計(jì)算：c1＝gr(modp)；(3)