201108031353RSA非對稱加密演算法 + 公開密鑰加密 + 加密 + 數位簽章

RSA加密演算法是一種非對稱加密演算法。在公鑰加密標準電子商業中RSA被廣泛使用。RSA是1977年羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的

1973年,在英國政府通訊總部工作的數學家克利福德·柯克斯(Clifford Cocks)在一個內部文件中提出了一個相應的演算法,但他的發現被列入機密,一直到1997年才被發表。

對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之,對一極大整數做因數分解愈困難,RSA演算法愈可靠。假如有人找到一種快速因數分解的演算法的話,那麼用RSA加密的信息的可靠性就肯定會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的RSA鑰匙才可能被強力方式解破。到2008年為止,世界上還沒有任何可靠的攻擊RSA演算法的方式。只要其鑰匙的長度足夠長,用RSA加密的信息實際上是不能被解破的。但在分布式計算技術量子計算機理論日趨成熟的今天,RSA加密安全性受到了挑戰。

1983年麻省理工學院在美國為RSA演算法申請了專利。這個專利2000年9月21日失效。由於該演算法在申請專利前就已經被發表了,在世界上大多數其它地區這個專利權不被承認。

目錄

[操作]


[公鑰和私鑰的產生]

假設Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰

  1. 隨意選擇兩個大的質數pqp不等於q,計算N=pq
  2. 根據歐拉函數,不大於N且與N互質的整數個數為(p-1)(q-1)
  3. 選擇一個整數e與(p-1)(q-1)互質,並且e小於(p-1)(q-1)
  4. 用以下這個公式計算dd× e ≡ 1 (mod (p-1)(q-1))
  5. pq的記錄銷毀。

(N,e)是公鑰,(N,d)是私鑰。(N,d)是秘密的。Alice將她的公鑰(N,e)傳給Bob,而將她的私鑰(N,d)藏起來。

[加密消息]

假設Bob想給Alice送一個消息m,他知道Alice產生的Ne。他使用起先與Alice約好的格式將m轉換為一個小於N的整數n,比如他可以將每一個字轉換為這個字的Unicode碼,然後將這些數字連在一起組成一個數字。假如他的信息非常長的話,他可以將這個信息分為幾段,然後將每一段轉換為n。用下面這個公式他可以將n加密為c

 n^e \equiv c\ (\mathrm{mod}\ N)

計算c並不複雜。Bob算出c後就可以將它傳遞給Alice。

[解密消息]

Alice得到Bob的消息c後就可以利用她的密鑰d來解碼。她可以用以下這個公式來將c轉換為n

 c^d \equiv n\ (\mathrm{mod}\ N)

得到n後,她可以將原來的信息m重新復原。

解碼的原理是

 c^d \equiv n^{e \cdot d}\ (\mathrm{mod}\ N)

以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。由費馬小定理可證明(因為pq是質數)

 n^{e \cdot d} \equiv n\ (\mathrm{mod}\ p)      和      n^{e \cdot d} \equiv n\ (\mathrm{mod}\ q)

這說明(因為pq不同的質數,所以pq互質)

 n^{e \cdot d} \equiv n\ (\mathrm{mod}\ pq)

[簽名消息]

RSA也可以用來為一個消息署名。假如甲想給乙傳遞一個署名的消息的話,那麼她可以為她的消息計算一個散列值(Message digest),然後用她的密鑰(private key)加密這個散列值並將這個「署名」加在消息的後面。這個消息只有用她的公鑰才能被解密。乙獲得這個消息後可以用甲的公鑰解密這個散列值,然後將這個數據與他自己為這個消息計算的散列值相比較。假如兩者相符的話,那麼他就可以知道發信人持有甲的密鑰,以及這個消息在傳播路徑上沒有被篡改過。


[安全]

假設偷聽者乙獲得了甲的公鑰Ne以及丙的加密消息c,但她無法直接獲得甲的密鑰d。要獲得d,最簡單的方法是將N分解為pq,這樣她可以得到同餘方程d× e ≡ 1 (mod (p-1)(q-1))並解出d,然後代入解密公式

 c^d \equiv n\ (\mathrm{mod}\ N)

導出n(破密)。但至今為止還沒有人找到一個多項式時間的演算法來分解一個大的整數的因子,同時也還沒有人能夠證明這種演算法不存在(見因數分解)。

至今為止也沒有人能夠證明對N進行因數分解是唯一的從c導出n的方法,但今天還沒有找到比它更簡單的方法。(至少沒有公開的方法。)

因此今天一般認為只要N足夠大,那麼駭客就沒有辦法了。

假如N的長度小於或等於256,那麼用一台個人電腦在幾個小時內就可以分解它的因子了。1999年,數百台電腦合作分解了一個512位長的N。今天對N的要求是它至少要1024位長。

1994年彼得·秀爾(Peter Shor)證明一台量子計算機可以在多項式時間內進行因數分解。假如量子計算機有朝一日可以成為一種可行的技術的話,那麼秀爾的演算法可以淘汰RSA和相關的衍生演算法。(即依賴於分解大整數困難性的加密演算法)

假如有人能夠找到一種有效的分解大整數的演算法的話,或者假如量子計算機可行的話,那麼在解密和製造更長的鑰匙之間就會展開一場競爭。但從原理上來說RSA在這種情況下是不可靠的。


[實現細節]


[密鑰生成]

首先要使用機率演算法來驗證隨機產生的大的整數是否質數,這樣的演算法比較快而且可以消除掉大多數非質數。假如有一個數通過了這個測試的話,那麼要使用一個精確的測試來保證它的確是一個質數。

除此之外這樣找到的pq還要滿足一定的要求,首先它們不能太靠近,此外p-1或q-1的因子不能太小,否則的話N也可以被很快地分解。

此外尋找質數的演算法不能給攻擊者任何信息,這些質數是怎樣找到的,尤其產生隨機數的軟體必須非常好。要求是隨機不可預測。這兩個要求並不相同。一個隨機過程可能可以產生一個不相關的數的系列,但假如有人能夠預測出(或部分地預測出)這個系列的話,那麼它就已經不可靠了。比如有一些非常好的隨機數演算法,但它們都已經被發表,因此它們不能被使用,因為假如一個攻擊者可以猜出pq一半的位的話,那麼他們就已經可以輕而易舉地推算出另一半。

此外密鑰d必須足夠大,1990年有人證明假如p大於q而小於2q(這是一個很經常的情況)而d < N1/4/3,那麼從Ne可以很有效地推算出d。此外e = 2永遠不應該被使用。

[速度]

比起DES和其它對稱演算法來說,RSA要慢得多。實際上Bob一般使用一種對稱演算法來加密他的信息,然後RSA來加密他的比較短的對稱密碼,然後將用RSA加密的對稱密碼和用對稱演算法加密的消息送給Alice。

這樣一來對隨機數的要求就更高了,尤其對產生對稱密碼的要求非常高,因為否則的話可以越過RSA來直接攻擊對稱密碼。

[密鑰分配]

和其它加密過程一樣,對RSA來說分配公鑰的過程是非常重要的。分配公鑰的過程必須能夠抵擋一個從中取代的攻擊。假設蛋蛋交給阿慶一個公鑰,並使阿慶相信這是小Q的公鑰,並且她可以截下小Q和阿慶之間的信息傳遞,那麼她可以將她自己的公鑰傳給阿慶,阿慶以為這是小Q的公鑰。可以將所有阿慶傳遞給小Q的消息截下來,將這個消息用她自己的密鑰解密,讀這個消息,然後將這個消息再用小Q的公鑰加密後傳給小Q。理論上小Q和阿慶都不會發現蛋蛋在偷聽他們的消息。今天人們一般用數字認證來防止這樣的攻擊。

[時間攻擊]

1995年有人提出了一種非常意想不到的攻擊方式:假如娥妹對阿黃的硬體有充分的了解,而且知道它對一些特定的消息加密時所需要的時間的話,那麼她可以很快地推導出d。這種攻擊方式之所以會成立,主要是因為在進行加密時所進行的模指數運算是一個位元一個位元進行的,而位元為1所花的運算比位元為0的運算要多很多,因此若能得到多組訊息與其加密時間,就會有機會可以反推出私鑰的內容。


[典型密鑰長度]

1997年後開發的系統,用戶應使用1024位密鑰,證書認證機構應用2048位或以上。


[已公開的或已知的攻擊方法]

針對RSA最流行的攻擊一般是基於大數因數分解。1999年,RSA-155(512 bits)被成功分解,花了五個月時間(約8000 MIPS 年)和224 CPU hours 在一台有3.2G中央內存的Cray C916計算機上完成 。

2002年,RSA-158也被成功因數分解。

RSA-158表示如下:

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609
727842468219535093544305870490251995655335710209799226484977949442955603

= 3388495837466721394368393204672181522815830368604993048084925840555281177

×

  11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

2009年12月12日,編號為 RSA-768 (768 bits, 232 digits)數也被成功分解[1]。這一事件威脅了現通行的1024-bit密鑰的安全性,普遍認為用戶應儘快升級到2048-bit或以上。

RSA-768表示如下:

123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413

= 3347807169895689878604416984821269081770479498371376856891
  2431388982883793878002287614711652531743087737814467999489

×

  3674604366679959042824463379962795263227915816434308764267
  6032283815739666511279233373417143396810270092798736308917


[相關條目]


公開密鑰加密


公開金鑰加密英語Public-key cryptography,也稱為非對稱金鑰加密),該思想最早由雷夫·莫寇(Ralph C. Merkle)在1974年提出[1],之後在1976年。狄菲(Whitfield Diffie)與赫爾曼(Martin Hellman)兩位學者以單向函數單向暗門函數為基礎,為發訊與收訊的兩方建立金鑰。

該加密演算法使用兩個不同的金鑰,各名為加密金鑰解密金鑰。前者公開,又稱公開金鑰,簡稱公鑰。後者保密,又稱私有金鑰,簡稱私鑰。這兩個金鑰是數學相關,用某用戶加密金鑰加密後所得的信息,只能用該用戶的解密金鑰才能解密。RSA演算法(由發明者Rivest、Shmir和Adleman姓氏首字母縮寫而來)是著名的公開金鑰加密演算法,相關公鑰密碼系統還有El GammaRSA橢圓曲線密碼學等。公鑰加密的另一用途是身份驗證:用私鑰加密的信息,可以用公鑰對其解密。接收者由此可知:這條信息確實來自於擁有私鑰的某人,公鑰的形式就是數字證書

目錄


[優點]

對稱密鑰加密相比,優點在於無需共享的通用密鑰,解密的私鑰不發往任何用戶。即使公鑰在網上被截獲,如果沒有與其匹配的私鑰,也無法解密,所截獲的公鑰是沒有任何用處的。


[過程]

假設兩個用戶A,B進行通信,公鑰為c,私鑰為d,明文為x.

  1. A用公鑰對明文進行加密形成密文c(x),然後傳輸密文;
  2. B收到密文,用私鑰對密文進行解密d(c(x)),得到要通信的明文x。


[公鑰密碼學]

密碼學中,公開鑰匙密碼學,簡稱公鑰密碼學,又稱非對稱密碼學,是使用一對公鑰和私鑰的密碼學,與只用一個鑰匙密鑰密碼學相對應。通常,我們所說的公鑰密碼學包括公鑰加密演算法數字簽名演算法。有些公鑰加密演算法可以很容易被改造成一個數字簽名演算法(如RSA),而有些則需要經過較大改動。


加密

 

密碼學中,加密是將明文信息隱匿起來,使之在缺少特殊信息時不可讀。雖然加密作為通信保密的手段已經存在了幾個世紀,但是只有那些對安全要求特別高的組織和個人才會使用它。在20世紀70年代中期,強加密(Strong Encryption)的使用開始從政府保密機構延伸至公共領域,並且目前已經成為保護許多廣泛使用系統的方法,比如網際網路電子商務手機網路和銀行自動取款機 等。

加密可以用於保證安全性,但是其它一些技術在保障通信安全方面仍然是必須的,尤其是關於數據完整性和信息驗證;例如,信息驗證碼(MAC)或者數字簽名。另一方面的考慮是為了應付流量分析

加密或軟體編碼隱匿(Code Obfuscation)同時也在軟體版權保護中,用於對付反向工程,未授權的程序分析,破解和軟體盜版及數位內容數位版權管理DRM)等。


數位簽章


Gnome-mime-text-x-copying.svg數位簽章
(又稱公鑰數位簽章電子簽章)是一種類似寫在上的普通的物理簽名,但是使用了公鑰加密領域的技術實現,用於鑒別數位信息的方法一套數位簽章通常定義兩種互補的運算,一個用於簽名,另一個用於驗證。

數位簽章不是指將你的簽名掃描成數位圖像,或者用觸摸板獲取的簽名,更不是你的落款

數位簽章了的文件的完整性是很容易驗證的(不需要騎縫章,騎縫簽名,也不需要筆跡專家),而且數位簽章具有不可抵賴性(不需要筆跡專家來驗證)。

目錄

[使用]

你可以對你發出的每一封電子郵件進行數位簽章。(詳見電子郵件一文。)這不是指落款,普遍把落款訛誤成簽名

中國大陸,數位簽章是具法律效力的,正在被普遍使用。2000年中華人民共和國的新《合同法》首次確認了電子合同、電子簽名的法律效力。2005年4月1日起,中華人民共和國首部《電子簽名法》正式實施。


[原理及特點]

每個人都有一對「鑰匙」(數位身份),其中一個只有她/他本人知道(私鑰),另一個公開的(公鑰)簽名的時候用私鑰,驗證簽名的時候用公鑰。又因為任何人都可以落款申稱她/他就是你,因此公鑰必須向接受者信任的人(身份認證機構)來註冊。註冊後身份認證機構給你發一數位證書對文件簽名後,你把此數位證書連同文件簽名一起發給接受者,接受者向身份認證機構求證是否真地是用你的密鑰簽發的文件。

在通訊中使用數位簽章一般基於以下原因:

[鑒權]

公鑰加密系統允許任何人在發送信息時使用私鑰進行加密,數位簽章能夠讓信息接收者利用發送者的公鑰確認發送者的身份。當然,接收者不可能百分之百確信發送者的真實身份,而只能在密碼系統未被破譯的情況下才有理由確信

鑒權的重要性在財務數據上表現得尤為突出。舉個例子,假設一家銀行將指令由它的分行傳輸到它的中央管理系統,指令的格式是(a,b),其中a是賬戶的賬號,而b是賬戶的現有金額。這時一位遠程客戶可以先存入100元,觀察傳輸的結果,然後接二連三的發送格式為(a,b)的指令。這種方法被稱作b

[完整性]

傳輸數據的雙方都總希望確認消息未在傳輸的過程中被修改。加密使得第三方想要讀取數據十分困難,然而第三方仍然能採取可行的方法在傳輸的過程中修改數據。一個通俗的例子就是同形攻擊:回想一下,還是上面的那家銀行從它的分行向它的中央管理系統發送格式為(a,b)的指令,其中a是賬號,而b是賬戶中的金額。一個遠程客戶可以先存100元,然後攔截傳輸結果,再傳輸(a,b3),這樣他就立刻變成百萬富翁了。

[不可否認]

在密文背景下,抵賴這個詞指的是不承認與消息有關的舉動(即聲稱消息來自第三方)消息的接收方可以通過數位簽章來防止所有後續的抵賴行為,因為接收方可以出示簽名給別人看來證明信息的來源。


[實現]

數位簽章演算法依靠公鑰加密技術來實現的。在公鑰加密技術里,每一個使用者有一對密鑰:一把公鑰和一把私鑰。公鑰可以自由發布,但私鑰則秘密保存;還有一個要求就是要讓通過公鑰推算出私鑰的做法不可能實現。

普通的數位簽章演算法包括三種演算法:

  • 一種密碼生成演算法
  • 標記演算法
  • 驗證演算法

 

回應
關鍵字





Powered by Xuite
TODAY IS TODAY.
Regator widget
防救災