密碼學(xué)公開(kāi)密鑰體系之RSA算法new

[密碼學(xué)]公開(kāi)密鑰體系之RSA算法當(dāng)前最著名、應(yīng)用最廣泛的公鑰系統(tǒng)RSA是在1978年，由美國(guó)麻省理工學(xué)院(MIT)的Ron

Rivest,

Adi

Shamir

和Leonard

Adleman在題為《獲得數(shù)字簽名和公開(kāi)鑰密碼系統(tǒng)的方法》的論文中提出的。它是一個(gè)基于數(shù)論的非對(duì)稱(公開(kāi)鑰)密碼體制，是一種分組密碼體制。其名稱來(lái)自于三個(gè)發(fā)明者的姓名首字母。

它的安全性是基于大整數(shù)素因子分解的困難性，而大整數(shù)因子分解問(wèn)題是數(shù)學(xué)上的著名難題，至今沒(méi)有有效的方法予以解決，因此可以確保RSA算法的安全性。RSA系統(tǒng)是公鑰系統(tǒng)的最具有典型意義的方法，大多數(shù)使用公鑰密碼進(jìn)行加密和數(shù)字簽名的產(chǎn)品和標(biāo)準(zhǔn)使用的都是RSA算法。RSA算法是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，因此它為公用網(wǎng)絡(luò)上信息的加密和鑒別提供了一種基本的方法。它通常是先生成一對(duì)RSA

密鑰，其中之一是保密密鑰，由用戶保存；另一個(gè)為公開(kāi)密鑰，可對(duì)外公開(kāi)，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊(cè)，人們用公鑰加密文件發(fā)送給個(gè)人，個(gè)人就可以用私鑰解密接受。為提高保密強(qiáng)度，RSA密鑰至少為500位長(zhǎng)，一般推薦使用1024位。該算法基于下面的兩個(gè)事實(shí),這些事實(shí)保證了RSA算法的安全有效性：1.已有確定一個(gè)數(shù)是不是質(zhì)數(shù)的快速算法；2.尚未找到確定一個(gè)合數(shù)的質(zhì)因子的快速算法。工作原理1)

任意選取兩個(gè)不同的大質(zhì)數(shù)p和q，計(jì)算乘積r=p*q；2)

任意選取一個(gè)大整數(shù)e，e與(p-1)*(q-1)互質(zhì)，整數(shù)e用做加密密鑰。注意：e的選取是很容易的，例如，所有大于p和q的質(zhì)數(shù)都可用。3)

確定解密密鑰d：

d

*

e

=

1

modulo（p

-

1）*（q

-

1）

根據(jù)e、p和q可以容易地計(jì)算出d。4)

公開(kāi)整數(shù)r和e，但是不公開(kāi)d；5)

將明文P

(假設(shè)P是一個(gè)小于r的整數(shù))加密為密文c，計(jì)算方法為：c

=

Pe

modulo

r6)

將密文c解密為明文P，計(jì)算方法為：P

=

cd

modulo

r然而只根據(jù)r和e（不是p和q）要計(jì)算出d是不可能的。因此，任何人都可對(duì)明文進(jìn)行加密，但只有授權(quán)用戶（知道d）才可對(duì)密文解密。數(shù)學(xué)原理定理若

p,

q

是相異質(zhì)數(shù),

rm

==

1

mod

(p-1)(q-1),a

是任意一個(gè)正整數(shù),

b

==

a^m

mod

pq,

c

==

b^r

mod

pq,則

c

==

a

mod

pq證明的過(guò)程,

會(huì)用到費(fèi)馬小定理,

敘述如下:m

是任一質(zhì)數(shù),

n

是任一整數(shù),

則

n^m

==

n

mod

m(換另一句話說(shuō),

如果

n

和

m

互質(zhì),

則

n^(m-1)

==

1

mod

m)運(yùn)用一些基本的群論的知識(shí),

就可以很容易地證出費(fèi)馬小定理的........證明因?yàn)?/p>

rm

==

1

mod

(p-1)(q-1),

所以

rm

=

k(p-1)(q-1)

+

1,

其中

k

是整數(shù)因?yàn)樵?/p>

modulo

中是

preserve

乘法的(x

==

y

mod

z

and

u

==

v

mod

z

=>

xu

==

yv

mod

z),所以,

c

==

b^r

==

(a^m)^r

==

a^(rm)

==

a^(k(p-1)(q-1)+1)

mod

pq1.

如果

a

不是

p

的倍數(shù),

也不是

q

的倍數(shù)時(shí),則

a^(p-1)

==

1

mod

p

(費(fèi)馬小定理)

=>

a^(k(p-1)(q-1))

==

1

mod

pa^(q-1)

==

1

mod

q

(費(fèi)馬小定理)

=>

a^(k(p-1)(q-1))

==

1

mod

q所以

p,

q

均能整除

a^(k(p-1)(q-1))

-

1

=>

pq

|

a^(k(p-1)(q-1))

-

1即

a^(k(p-1)(q-1))

==

1

mod

pq=>

c

==

a^(k(p-1)(q-1)+1)

==

a

mod

pq2.

如果

a

是

p

的倍數(shù),

但不是

q

的倍數(shù)時(shí),則

a^(q-1)

==

1

mod

q

(費(fèi)馬小定理)=>

a^(k(p-1)(q-1))

==

1

mod

q=>

c

==

a^(k(p-1)(q-1)+1)

==

a

mod

q=>

q

|

c

-

a因

p

|

a=>

c

==

a^(k(p-1)(q-1)+1)

==

0

mod

p=>

p

|

c

-

a所以,

pq

|

c

-

a

=>

c

==

a

mod

pq3.

如果

a

是

q

的倍數(shù),

但不是

p

的倍數(shù)時(shí),

證明同上4.

如果

a

同時(shí)是

p

和

q

的倍數(shù)時(shí),則

pq

|

a=>

c

==

a^(k(p-1)(q-1)+1)

==

0

mod

pq=>

pq

|

c

-

a=>

c

==

a

mod

pqQ.E.D.這個(gè)定理說(shuō)明

a

經(jīng)過(guò)編碼為

b

再經(jīng)過(guò)解碼為

c

時(shí),

a

==

c

mod

n

(n

=

pq)....但我們?cè)谧鼍幋a解碼時(shí),

限制

0

<=

a

<

n,

0

<=

c

<

n,所以這就是說(shuō)

a

等於

c,

所以這個(gè)過(guò)程確實(shí)能做到編碼解碼的功能.....為了說(shuō)明該算法的工作過(guò)程,我們下面給出一個(gè)簡(jiǎn)單例子,顯然我們?cè)谶@只能取很小的數(shù)字，但是如上所述，為了保證安全，在實(shí)際應(yīng)用上我們所用的數(shù)字要大的多得多。例：選取p=3,

q=5，則r=15，（p-1）*（q-1）=8。選取e=11（大于p和q的質(zhì)數(shù)），通過(guò)d

*

11

=

1

modulo

8，計(jì)算出d

=3。假定明文為整數(shù)13。則密文c為c

=

Pe

modulo

r=

1311

modulo

15=

1,792,160,394,037

modulo

15=

7復(fù)原明文P為：P

=

cd

modulo

r=

73

modulo

15=

343

modulo

15=

13因?yàn)閑和d互逆，公開(kāi)密鑰加密方法也允許采用這樣的方式對(duì)加密信息進(jìn)行"簽名"，以便接收方能確定簽名不是偽造的。兩個(gè)在不安全信道中通信的人，假設(shè)為Alice（收信者）和Bob（發(fā)信者），他們希望能夠安全的通信而不被他們的敵手Oscar破壞。Alice

想到了一種辦法，她使用了一種鎖（相當(dāng)于公鑰），這種鎖任何人只要輕輕一按就可以鎖上，但是只有Alice的鑰匙（相當(dāng)于私鑰）才能夠打開(kāi)。然后

Alice

對(duì)外發(fā)送無(wú)數(shù)把這樣的鎖，任何人比如Bob想給她寄信時(shí)，只需找到一個(gè)箱子，然后用一把Alice的鎖將其鎖上再寄給Alice，這時(shí)候任何人（包括

Bob自己）除了擁有鑰匙的Alice，都不能再打開(kāi)箱子，這樣即使Oscar能找到Alice的鎖，即使Oscar能在通信過(guò)程中截獲這個(gè)箱子，沒(méi)有

Alice的鑰匙他也不可能打開(kāi)箱子，而Alice的鑰匙并不需要分發(fā)，這樣

Oscar也就無(wú)法得到這把“私人密鑰”。優(yōu)點(diǎn)RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。該算法的加密密鑰和加密算法分開(kāi)，使得密鑰分配更為方便。它特別符合計(jì)算機(jī)網(wǎng)絡(luò)環(huán)境。對(duì)于

網(wǎng)上的大量用戶，可以將加密密鑰用電話簿的方式印出。如果某用戶想與另一用戶進(jìn)行保密通信，只需從公鑰簿上查出對(duì)方的加密密鑰，用它對(duì)所傳送的信息加密發(fā)出即可。對(duì)方收到信息后，用僅為自己所知的解密密鑰將信息脫密，了解報(bào)文的內(nèi)容。由此可看出，RSA算法解決了大量網(wǎng)絡(luò)用戶密鑰管理的難題，這是公鑰密碼系統(tǒng)相對(duì)于對(duì)稱密碼系統(tǒng)最突出的優(yōu)點(diǎn)。缺點(diǎn)1)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。2)安全性,

RSA的安全性依賴于大數(shù)的因子分解，但并沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)，而且密碼學(xué)界多數(shù)人士?jī)A向于因子分解不是NPc問(wèn)題。目前，人們已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)，這就要求使用更長(zhǎng)的密鑰，速度更慢；另外，目前人們正在積極尋找攻擊RSA的方法，如選擇密文攻擊，一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實(shí)體簽署。然后，經(jīng)過(guò)計(jì)算就可得到它所想要的信息。實(shí)際上，攻擊利用的都是同一個(gè)弱點(diǎn)，即存在這樣一個(gè)事實(shí)：乘冪保留了輸入的乘法結(jié)構(gòu)：(

XM

)d

=

Xd

*Md

mod

n前面已經(jīng)提到，這個(gè)固有的問(wèn)題來(lái)自于公鑰密碼系統(tǒng)的最有用的特征--每個(gè)人都能使用公鑰。但從算法上無(wú)法解決這一問(wèn)題，主要措施有兩條：一條是采用好的公鑰協(xié)議，保證工作過(guò)程中實(shí)體不對(duì)其他實(shí)體任意產(chǎn)生的信息解密，不對(duì)自己一無(wú)所知的信息簽名；另一條是決不對(duì)陌生人送來(lái)的隨機(jī)文檔簽名，簽名時(shí)首先使用One-Way

Hash

Function對(duì)文檔作HASH處理，或同時(shí)使用不同的簽名算法。除了利用公共模數(shù)，人們還嘗試一些利用解密指數(shù)或φ（n）等等攻擊.3)速度太慢,由于RSA

的分組長(zhǎng)度太大，為保證安全性，n

至少也要

600

bitx以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí)；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長(zhǎng)度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。目前，SET(Secure

Electronic

Transaction)協(xié)議中要求cA采用2048比特長(zhǎng)的密鑰，其他實(shí)體使用1024比特的密鑰。為了速度問(wèn)題,目前人們廣泛使用單,公鑰密碼結(jié)合使用的方法,優(yōu)缺點(diǎn)互補(bǔ):單鑰密碼加密速度快,人們用它來(lái)加密較長(zhǎng)的文件,然后用RSA來(lái)給文件密鑰加密,極好的解決了單鑰密碼的密鑰分發(fā)問(wèn)題。公鑰加密算法中使用最廣的是RSA。RSA算法研制的最初理