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

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

Rivest,

Adi

Shamir

和Leonard

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

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

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

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

任意選取一個大整數(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可以容易地計算出d。4)

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

將明文P

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

=

Pe

modulo

r6)

將密文c解密為明文P，計算方法為：P

=

cd

modulo

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

p,

q

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

rm

==

1

mod

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

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

b

==

a^m

mod

pq,

c

==

b^r

mod

pq,則

c

==

a

mod

pq證明的過程,

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

敘述如下:m

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

n

是任一整數(shù),

則

n^m

==

n

mod

m(換另一句話說,

如果

n

和

m

互質(zhì),

則

n^(m-1)

==

1

mod

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

就可以很容易地證出費(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ù)時,則

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ù)時,則

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ù)時,

證明同上4.

如果

a

同時是

p

和

q

的倍數(shù)時,則

pq

|

a=>

c

==

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

==

0

mod

pq=>

pq

|

c

-

a=>

c

==

a

mod

pqQ.E.D.這個定理說明

a

經(jīng)過編碼為

b

再經(jīng)過解碼為

c

時,

a

==

c

mod

n

(n

=

pq)....但我們在做編碼解碼時,

限制

0

<=

a

<

n,

0

<=

c

<

n,所以這就是說

a

等於

c,

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

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

*

11

=

1

modulo

8，計算出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互逆，公開密鑰加密方法也允許采用這樣的方式對加密信息進(jìn)行"簽名"，以便接收方能確定簽名不是偽造的。兩個在不安全信道中通信的人，假設(shè)為Alice（收信者）和Bob（發(fā)信者），他們希望能夠安全的通信而不被他們的敵手Oscar破壞。Alice

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

Alice

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

Bob自己）除了擁有鑰匙的Alice，都不能再打開箱子，這樣即使Oscar能找到Alice的鎖，即使Oscar能在通信過程中截獲這個箱子，沒有

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

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

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

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

XM

)d

=

Xd

*Md

mod

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

Hash

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

的分組長度太大，為保證安全性，n

至少也要

600

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

Electronic

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