Can you summarize the following document?
        
  

  假設Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰:  formula_20是公鑰,formula_21是私鑰。Alice將她的公鑰formula_20傳給Bob,而將她的私鑰formula_21藏起來。

  首選取兩個互質數 p和q, 乘法計算p * q 得到 N。  然後計算出尤拉φ(N): φ函式φ(N)是小於或等於N的正整數中與N互質的數的數目。 根據尤拉公式,由於p和q都是質數,故 φ(N) = (p-1)*(q-1)  這時候我們隨機選擇一個整數e,條件是1< e < φ(n),且e與φ(n) 互質。 接著我們計算e對φ(n)的模逆元得到d: e*d ≡ 1 (mod φ(n)) 這個公式簡單的說就是 e*d除以φ(N)得到的餘數為1,這個公式可以轉換成 ed%((p-1)(q-1))=1 => ed=k(p-1)(q-1)+1  於是,RSA公鑰為(e,n),私鑰為(d,n)。  加密原文x得到密文m=x^e%n  解密公式為x=m^d%n  證明解密邏輯:  證明x=m^d%n,就是證明m^d%n-x=0 m^d%n-x //如何=0,往下分解:  =(x^e%n)^d%n-x //代入加密原文  =x^ed%n-x //根據模運算公式:a ^ b % p = ((a % p)^b) % p  =x^(k(p-1)(q-1)+1)%n-x //代入ed的值  =x*(x^(k(p-1)(q-1))-1)%n //x挪到括號外,條件x<n  根據費馬小定理公式:a^(p-1) - 1可以被p整除。 所以x^(k(q-1))^(p-1) - 1 可以被p整除,x^(k(p-1))^(q-1) - 1 可以被q整除。 所以x^(k(p-1)(q-1)) - 1 可以被pq整除,也就是可以被N整除。 就是x*(x^(k(p-1)(q-1))-1)%n=0,證明完成。

  假設Bob想給Alice送一個訊息formula_24,他知道Alice產生的formula_25和formula_8。他使用起先與Alice約好的格式將formula_24轉換為一個小於formula_25的非負整數formula_29,比如他可以將每一個字轉換為這個字的Unicode碼,然後將這些數字連在一起組成一個數字。假如他的資訊非常長的話,他可以將這個資訊分為幾段,然後將每一段轉換為formula_29。用下面這個公式他可以將formula_29加密為formula_32:  計算formula_32並不複雜。Bob算出formula_32後就可以將它傳遞給Alice。

  Alice得到Bob的訊息formula_32後就可以利用她的金鑰formula_13來解碼。她可以用以下這個公式來將formula_32轉換為formula_29:  得到formula_29後,她可以將原來的資訊formula_24重新復原。  解碼的原理是  已知formula_15,即 formula_45。 由尤拉定理得:

  RSA也可以用來為一個訊息署名。假如Alice想給Bob傳遞一個署名的訊息的話,那麼她可以為她的訊息計算一個雜湊值(Message digest),然後用她的私鑰“加密”(如同前面“加密訊息”的步驟)這個雜湊值並將這個“署名”加在訊息的後面。這個訊息只有用她的公鑰才能被解密。Bob獲得這個訊息後可以用Alice的公鑰“解密”(如同前面“解密訊息”的步驟)這個雜湊值,然後將這個資料與他自己為這個訊息計算的雜湊值相比較。假如兩者相符的話,那麼Bob就可以知道發信人持有Alice的私鑰,以及這個訊息在傳播路徑上沒有被篡改過。

  假設偷聽者Eve獲得了Alice的公鑰formula_25和formula_8以及Bob的加密訊息formula_32,但她無法直接獲得Alice的金鑰formula_13。要獲得formula_13,最簡單的方法是將formula_25分解為formula_1和formula_2,這樣她可以得到同餘方程formula_55並解出formula_13,然後代入解密公式 匯出"n"(破密)。但至今為止還沒有人找到一個多項式時間的演算法來分解一個大的整數的因子,同時也還沒有人能夠證明這種演算法不存在(見因數分解)。  至今為止也沒有人能夠證明對formula_25進行因數分解是唯一的從formula_32匯出formula_29的方法,直到今天也還沒有找到比它更簡單的方法。(至少沒有公開的方法。)  因此今天一般認為只要formula_25足夠大,那麼駭客就沒有辦法了。  假如formula_25的長度小於或等於256位,那麼用一臺個人電腦在幾個小時內就可以分解它的因子了。1999年,數百臺電腦合作分解了一個512位長的formula_25。一個由Shamir 和Tromer在2003年從理論上構建的硬體TWIRL,使人們開始質疑1024位長的N的安全性,目前推薦formula_25的長度至少為2048位。  1994年彼得·秀爾(Peter Shor)證明一臺量子計算機可以在多項式時間內進行因數分解。假如量子計算機有朝一日可以成為一種可行的技術的話,那麼秀爾的演算法可以淘汰RSA和相關的衍生演算法。(即依賴於分解大整數困難性的加密演算法)  假如有人能夠找到一種有效的分解大整數的演算法的話,或者假如量子計算機可行的話,那麼在解密和製造更長的鑰匙之間就會展開一場競爭。但從原理上來說RSA在這種情況下是不可靠的。

  

  首先要使用概率演算法來驗證隨機產生的大的整數是否質數,這樣的演算法比較快而且可以消除掉大多數非質數。假如有一個數通過了這個測試的話,那麼要使用一個精確的測試來保證它的確是一個質數。  除此之外這樣找到的formula_1和formula_2還要滿足一定的要求,首先它們不能太靠近,此外formula_67或formula_68的因子不能太小,否則的話formula_25也可以被很快地分解。  此外尋找質數的演算法不能給攻擊者任何資訊,這些質數是怎樣找到的,尤其產生隨機數的軟體必須非常好。要求是隨機和不可預測。這兩個要求並不相同。一個隨機過程可能可以產生一個不相關的數的系列,但假如有人能夠預測出(或部分地預測出)這個系列的話,那麼它就已經不可靠了。比如有一些非常好的隨機數演算法,但它們都已經被髮表,因此它們不能被使用,因為假如一個攻擊者可以猜出formula_1和formula_2一半的位的話,那麼他們就已經可以輕而易舉地推算出另一半。  此外金鑰formula_13必須足夠大,1990年有人證明假如formula_1大於formula_2而小於formula_75(這是一個很常見的情況)而formula_76,那麼從formula_25和formula_8可以很有效地推算出formula_13。此外formula_80永遠不應該被使用。

  比起AES、3DES和其它對稱演算法來說,RSA要慢得多。實際的運用(如TLS)一般結合了對稱加密(如AES)和非對稱加密(如RSA)兩者。

  和其它加密過程一樣,對RSA來說分配公鑰的過程是非常重要的。分配公鑰的過程必須能夠抵擋中間人攻擊。假設Eve交給Bob一個公鑰,並使Bob相信這是Alice的公鑰,並且她可以截下Alice和Bob之間的資訊傳遞,那麼她可以將她自己的公鑰傳給Bob,Bob以為這是Alice的公鑰。Eve可以將所有Bob傳遞給Alice的訊息截下來,將這個訊息用她自己的金鑰解密,讀這個訊息,然後將這個訊息再用Alice的公鑰加密後傳給Alice。理論上Alice和Bob都不會發現Eve在偷聽他們的訊息。今天人們一般用可靠的第三方機構簽發憑證來防止這樣的攻擊。

  NIST建議的RSA金鑰長度為至少2048位元。

  

  針對RSA最流行的攻擊一般是基於大數因數分解。1999年,RSA-155 (512 bits)被成功分解,花了五個月時間(約8000 MIPS年)和224 CPU hours在一臺有3.2G中央記憶體的Cray C916計算機上完成。  RSA-158表示如下:  2009年12月12日,編號為RSA-768(768 bits, 232 digits)數也被成功分解。這一事件威脅了現通行的1024-bit金鑰的安全性,普遍認為使用者應儘快升級到2048-bit或以上。  RSA-768表示如下:

  1995年有人提出了一種非常意想不到的攻擊方式:假如Eve(竊密者)對Alice的硬體有充分的瞭解,而且知道它對一些特定的訊息加密時所需要的時間的話,那麼她可以很快地推匯出"d"。這種攻擊方式之所以會成立,主要是因為在進行加密時所進行的模指數運算是一個位元一個位元進行的,而位元為1所花的運算比位元為0的運算要多很多,因此若能得到多組訊息與其加密時間,就會有機會可以反推出私鑰的內容。
RSA加密演算法是一種非對稱加密演算法,在公開金鑰加密和電子商業中被廣泛使用。RSA是由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)在1977年一起提出的。當時他們三人都在麻省理工學院工作。RSA 就是他們三人姓氏開頭字母拼在一起組成的。