簡要介紹了公鑰密碼體制的思想和特點，具體介紹了RSA算法的理論基礎、工作原理和具體實現過程，並通過壹個簡單的例子說明了算法是如何實現的。本文最後總結了RSA算法的壹些不足和解決方法。
關鍵詞:公鑰密碼系統，公鑰，私鑰，RSA
1簡介
隨著計算機網絡化的逐步實現，互聯網的前景越來越好，全球經濟發展正在進入信息經濟時代，知識經濟初具規模。計算機信息的安全變得越來越重要。無論是個人信息交流，還是電子商務的發展，都迫切需要保證互聯網上信息傳輸的安全。信息安全技術是壹門綜合學科，涉及信息論、計算機科學和密碼學。其主要任務是研究計算機系統和通信網絡中信息的保護方法，以實現系統中信息的安全、保密、真實和完整。其中，信息安全的核心是密碼技術。密碼學是壹門集數學、計算機科學、電子學和通信於壹體的交叉學科。它不僅能保證機密信息的加密，還能實現數字簽名、身份驗證、系統安全等功能。它是現代化的重要科學之壹。本文將簡要介紹公鑰密碼體制和目前該系統中最流行的RSA算法。
2公鑰密碼系統
要解釋公鑰密碼體制，首先我們來了解壹下加密算法的不同:目前的加密算法按照密鑰方式可以分為單密鑰密碼體制和公鑰密碼體制。
2.1.壹鍵密碼
也稱對稱密碼，是壹種比較傳統的加密方法，其加密操作和解密操作使用同壹個密鑰。在傳輸和處理信息時，信息的發送者和接收者都必須持有密碼(稱為對稱密碼)。因此，雙方都必須獲得該密鑰，並對其保密。
單密鑰密碼系統的安全性取決於以下兩個因素:壹是加密算法必須足夠強，實際中不可能基於密文本身來解密信息；第二，加密方法的安全性取決於密鑰的保密性，而不是算法的保密性。因此，我們沒有必要保證算法的保密性(實際上現實中使用的單密鑰密碼系統的很多算法都是公開的)，但必須保證密鑰的保密性。
從單密鑰密碼的這些特點，我們很容易看出主要有兩個問題:壹是密鑰的數量。在單密鑰密碼系統中，每對通信者都需要壹對密鑰。當用戶數量增加時，鑰匙的數量必然會成倍增加。因此，在網絡通信中，大量密鑰的生成、存儲和分發將是壹個難題。第二，密鑰分發問題。在單密鑰密碼系統中，加密的安全性完全取決於密鑰的保護。然而，由於雙方使用相同的密鑰，人們不得不相互交換密鑰。因此，為了確保安全，人們必須使用壹些其他的安全通道來分發密鑰，例如使用特殊的信使來傳輸密鑰。這是相當昂貴的，甚至是非常不現實的，尤其是在計算機網絡環境下，人們利用網絡傳輸加密文件，卻需要另壹個安全通道。
2.2公鑰加密
正是由於單密鑰密碼體制的缺點，才使得它如此難以解決，因此開發壹種新的、更有效、更先進的密碼體制就顯得更加迫切和必要。在這種情況下，壹種新的公鑰密碼體制應運而生，它解決了困擾無數科學家的密鑰分發問題。事實上，在這個系統中，人們甚至不必分發需要嚴格保密的密鑰。這壹突破也被認為是兩千年來單碼代替密碼發明以來，密碼學史上最偉大的成就。
這個全新的想法是由斯坦福大學的兩位學者Diffie和Hellman在本世紀70年代提出的。該系統與單密鑰加密的最大區別在於:
在公鑰密碼系統中，加密和解密使用不同的密鑰(與對稱密鑰相比，人們稱之為非對稱密鑰)，這兩種密鑰之間存在相互依賴關系:即用任壹種密鑰加密的信息只能用另壹種密鑰解密。這使得雙方能夠安全地通信，而無需事先交換密鑰。其中，加密密鑰和算法是公開的，每個人都可以用這個密鑰加密文件並發送給收件人。這個加密密鑰也稱為公鑰。接收方收到加密文件後，可以用他的解密密鑰解密，解密密鑰由他個人負責，不需要分發，所以也叫私鑰，解決了密鑰分發的問題。
為了說明這壹觀點，我們可以考慮以下類比:
在不安全的信道中進行通信的兩個人，假設愛麗絲(接收者)和鮑勃(發送者)，想要安全地通信而不被對手奧斯卡破壞。愛麗絲想到了壹個辦法。她用的是鎖(相當於公鑰)。這種鎖任何人輕輕壹按就能鎖上，但只有愛麗絲的鑰匙(相當於私人鑰匙)才能打開。然後愛麗絲發出無數這樣的鎖。當任何人，比如鮑勃，想給她寄信時，他只需要找到壹個盒子，然後用愛麗絲的鎖鎖上，寄給愛麗絲。此時，除了擁有鑰匙的愛麗絲之外，任何人(包括鮑勃本人)都無法打開箱子，所以即使奧斯卡能找到愛麗絲的鎖，即使奧斯卡能在通信過程中截獲箱子，但沒有愛麗絲的鑰匙，他也無法打開箱子，愛麗絲的鑰匙也不需要分發，所以奧斯卡無法獲得這個“私人鑰匙”。
從上面的介紹可以看出，公鑰密碼體制的思想並不復雜，實現它的關鍵問題是如何確定公鑰和私鑰以及加/解密算法，也就是如何找到愛麗絲的鎖和鑰匙。我們假設在這個系統中，PK是公開信息，作為加密密鑰使用，而SK需要用戶自己保密，作為解密密鑰使用。還公開了加密算法e和解密算法d。雖然SK和PK是成對出現的，但是SK是不能從PK計算出來的。他們必須滿足以下條件:
①用加密密鑰PK加密明文X後，用解密密鑰SK解密恢復明文，或者寫成:dsk (epk (x)) = X。
②加密密鑰不能用於解密，即DPK (EPK (x)) ≠ X
③在計算機上可以很容易地生成PK和SK對。
④實際上不可能從已知的PK推導出SK。
⑤加密和解密的運算可以反過來，即EPK (DSK (x)) = X
從以上條件可以看出，在公鑰密碼體制下，加密密鑰不等於解密密鑰。加密密鑰可以公開，這樣任何用戶都可以用公鑰加密發送給這個用戶的信息，而這個用戶保存的唯壹私鑰是保密的，只有它才能恢復和解密密文。雖然理論上可以從加密密鑰推導出解密密鑰，但這種算法設計實際上是不可能的，或者說雖然可以推導出來，但耗時較長，變得不可行。因此，公開加密密鑰不會危及密鑰的安全。
這個系統的想法很簡單，但是如何找到壹個合適的算法來實現這個系統對於密碼學家來說是壹個真正的難題，因為由於Pk和SK是壹對相互關聯的密鑰，因此很有可能從其中的壹個推導出另壹個。如果對手奧斯卡能從PK推導出SK，那麽這個系統就不再安全了。因此，如何找到合適的算法生成合適的PK和SK，並使Pk無法推導出SK，是密碼學家迫切需要解決的難題。這個問題甚至讓公鑰密碼體制的發展停滯了很長壹段時間。
為了解決這個問題，密碼學家考慮了數學上的陷門單向函數。下面，我們可以給它非正式的定義:
Alice的公開加密函數應該很容易計算，而它的反函數(即解密函數)應該很難計算(針對Alice以外的人)。很多Y=f(x)形式的函數，對於給定的自變量x的值，很容易計算出函數Y的值；但是，從y的壹個給定值，很多情況下很難根據函數關系f (x)計算出x的值。這樣壹個很容易計算但很難求逆的函數通常被稱為單向函數。在加密過程中，我們希望加密函數e是壹個單項式內射函數，這樣它就可以被解密。雖然沒有壹個函數可以被證明是單向的，但是許多內射函數被認為是單向的。
例如，有壹個函數被認為是單向的，假設n是兩個大素數p和q的乘積，b是正整數，那麽F被定義為:
f (x )= x b mod n
(如果gcd(b，φ(n))=1，那麽實際上這就是我們下面要講的RSA加密函數。)
如果要構造壹個公鑰密碼系統，僅僅給出壹個單向內射函數是不夠的。從Alice的角度來看，e沒有必要是單向的，因為它需要以有效的方式解密接收到的信息。所以愛麗絲應該有壹個陷門，裏面包含了妳的函數容易找到的秘密信息e，換句話說，愛麗絲之所以能有效解密，是因為它有額外的秘密知識，即SK，可以為妳提供解密函數d，所以我們稱壹個函數為陷門單向函數。如果它是壹個單向函數，在知道了壹個特定的陷門之後，很容易找到它的逆函數。
考慮上面的函數f (x) =？xb mod n .我們可以知道它的反函數f -1有壹個類似的形式f (x) = xa？Mod n，用於a的適當值。陷印是使用n的因式分解來有效地計算正確的指數a(對於給定的b)。
為了方便起見，我們把某種陷門單向函數作為？。所以隨機選壹個函數f屬於？作為公共加密函數；它的反函數f-1是壹個秘密解密函數。然後就可以實現公鑰密碼系統了。
根據上述關於陷門單向函數的思想，學者們提出了許多公鑰加密方法，其安全性基於復雜的數學問題。根據數學問題，至少有以下三種系統被認為是安全有效的:大整數因式分解系統(RSA)、橢圓曲線離散對數系統(ECC)和離散對數系統(DSA)。
3 RSA算法
3.1簡介
目前最著名、應用最廣泛的公鑰體制RSA是由麻省理工學院(MIT)的Rivest、Shamir和Adleman在1978中發表的題為“獲取數字簽名和公鑰密碼體制的方法”的論文中提出的。它是壹種基於數論和分組密碼系統的非對稱(公鑰)密碼系統。它的名字來自三個發明家的首字母。它的安全性是基於大整數素數分解的困難性，而大整數的分解是數學中著名的問題，沒有有效的方法解決，所以RSA算法的安全性是可以保證的。RSA系統是公開密鑰系統中最典型的方法。大多數使用公鑰密碼進行加密和數字簽名的產品和標準都使用RSA算法。
RSA算法是第壹個可以同時用於數據加密和數字簽名的算法，因此它為公共網絡上的信息加密和認證提供了壹個基本的方法。通常是壹對RSA密鑰，其中壹個是秘鑰，由用戶保管；另壹種是公鑰，可以公開，甚至可以在網絡服務器中註冊。人們使用公鑰加密文件，並將其發送給個人，個人可以用私鑰解密文件。為了提高安全強度，RSA密鑰至少要有500位長，壹般建議使用1024位。
該算法基於以下兩個事實，這兩個事實保證了RSA算法的安全性和有效性:
1)判斷壹個數是否為素數有壹個快速算法；
2)確定壹個合數的素因子的快速算法還沒有找到。
3.2工作原理
1)任意選擇兩個不同的大素數p和q並計算乘積r = p * q；
2)任意選擇壹個大整數e，e與(p-1)*(q-1)互質，整數e作為加密密鑰。註意:e的選取很容易，比如所有大於p和q的素數都有。
3)確定解密密鑰D :D * E = 1 moduo(P-1)*(Q-1)根據E，P和Q，可以很容易地計算出D。
4)公開整數r和e，但不公開d；
5)將明文p(假設p是小於r的整數)加密成密文c，計算方法如下:
C = Pe模r
6)將密文c解密成明文p，計算方法如下:
P = Cd模r
但是，只從R和E(而不是P和Q)計算D是不可能的。因此，任何人都可以加密明文，但只有授權用戶(知道D)才能解密密文。
3.3簡單示例
為了說明算法的工作過程，下面我們舉壹個簡單的例子。顯然這裏只能取很小的壹個數，但是如上所述，為了保證安全，我們在實際應用中使用的數要大得多。
例:若p = 3，q = 5，則r=15，(p-1)*(q-1)=8。選擇e=11(大於P和Q的素數)，由D * 11 = 1moduo8計算出d =3。
假設明文是13的整數。那麽密文c就是
C = Pe模r
= 1311模15
= 1，792，160，394，037模15
= 7
恢復的明文p是:
P = Cd模r
= 73模15
= 343模15
= 13
因為E和D是互易的，所以公鑰加密方法也允許加密的信息以這種方式被“簽名”,從而接收方可以確信簽名不是偽造的。
假設A和B想通過公鑰加密傳輸數據，A和B分別公開了加密算法和對應的密鑰，但沒有公開解密算法和對應的密鑰。A和B的加密算法是ECA和ECB，解密算法是DCA和DCB，ECA和DCA互逆，ECB和DCB互逆。如果A要發送明文P給B，不是簡單的發送ECB(P)，而是先將其解密算法DCA應用於P，然後用加密算法ECB將結果加密後發送出去。
密文c是:
C =歐洲中央銀行
B收到C後，依次應用其解密算法DCB和加密算法ECA，得到明文P:
非洲經委會
= ECA(DCB(ECB(DCA(P)))
= ECA(DCA(P))/*DCB和ECB相互抵消*/
=
p？/*DCB和ECB相互抵消*/
這樣B就可以確認消息確實是從A發出的，因為只有加密過程使用DCA算法，P才能被ECA得到。只有A知道DCA算法，任何人，甚至B，都無法偽造A的簽名。
3.4優點和缺點
3.4.1的優點
RSA算法是第壹個既能用於加密又能用於數字簽名的算法，也很容易理解和操作。RSA是研究最廣泛的公鑰算法。從提出到現在已經將近二十年了，經過各種攻擊的考驗，逐漸被人們所接受。它被普遍認為是目前最好的公鑰方案之壹。該算法的加密密鑰與加密算法分離，使得密鑰分發更加方便。特別適用於計算機網絡環境。對於互聯網上的大量用戶來說，加密密鑰可以在電話簿中打印出來。如果壹個用戶想與另壹個用戶進行秘密通信，他只需要從公鑰本中找出對方的加密密鑰，並用它來加密傳輸的信息。對方收到消息後，用只有自己知道的解密密鑰對消息進行解密，從而知道消息的內容。可以看出，RSA算法解決了大量網絡用戶的密鑰管理問題，這是公鑰密碼體制相比對稱密碼體制最突出的優勢。
缺點
1)生成密鑰很麻煩，受限於素數生成技術，很難做到壹次壹密。
2)安全性，RSA的安全性依賴於大數的因式分解，但並沒有從理論上證明破譯RSA的難度與大數因式分解的難度是等價的，密碼學中的大多數人傾向於認為因式分解不是NPC問題。目前人們已經能夠分解140以上的十進制素數，這需要使用更長的密鑰，速度較慢；另外，目前人們也在積極尋找攻擊RSA的方法，比如選擇密文攻擊。壹般來說，攻擊者會對某個信息進行盲復制，讓有私鑰的實體簽名。然後，它可以通過計算得到它想要的信息。事實上，所有的攻擊都利用了同壹個弱點，即存在這樣壹個事實，即冪保持輸入的乘法結構:
(XM )d = Xd *Md mod n
如前所述，這個固有的問題來自於公鑰密碼系統最有用的特性——每個人都可以使用公鑰。但這個問題無法從算法上解決，主要有兩種措施:壹種是采用良好的公鑰協議，保證實體不解密其他實體任意生成的信息，不簽署自己壹無所知的信息；另壹個就是千萬不要隨便簽署陌生人發來的文件。簽名時，首先使用單向哈希函數對文檔進行哈希，或者同時使用不同的簽名算法。除了使用模數，人們還嘗試了壹些使用解密指數或φ(n)的攻擊。
3)速度太慢。由於RSA的包長太大，為了保證安全性，n至少要600 bitx，使得運算成本非常高，特別是速度慢，比對稱密碼算法慢幾個數量級；而且隨著大數分解技術的發展，這個長度還在增加，不利於數據格式的標準化。目前Set(安全電子交易)協議要求CA使用2048位密鑰，其他實體使用1024位密鑰。為了解決速度問題，目前人們廣泛采用單密鑰和公鑰密碼相結合的方法，兩者優缺點互補:單密鑰密碼速度快，人們用它來加密長文件，再用RSA來加密文件密鑰，很好地解決了單密鑰密碼的密鑰分發問題。
4結論
目前，日益增長的電子商務和其他互聯網應用的需求普及了公鑰系統，公鑰系統主要包括服務器資源的訪問控制和電子商務交易的保護，以及權利、個人隱私、無線交易和內容完整性的保護(如確保新聞報道或股票報價的真實性)。公鑰技術發展到今天，市場上明顯的發展趨勢是PKI與操作系統的融合。PKI是“公共的”
Key Infrastructure的縮寫意為“公鑰基礎設施”。公鑰系統廣泛應用於CA認證、數字簽名和密鑰交換。
RSA是使用最廣泛的公鑰加密算法。RSA算法開發的最初思想和目標是讓互聯網安全可靠，旨在解決DES算法密鑰通過開放信道傳輸和分發的難題。實際結果不僅很好地解決了這個問題；RSA還可以用來完成對消息的數字簽名，以抵抗對消息的否認和否定；同時，利用數字簽名可以很容易地發現攻擊者對消息的非法篡改，從而保護數據信息的完整性。到目前為止，RSA算法已經被應用在很多加密技術中，在互聯網的很多方面都得到了廣泛的應用，包括安全接口層(SSL)標準的應用，這是web瀏覽器建立安全互聯網連接所必需的。此外，RSA加密系統還可以應用於智能IC卡和網絡安全產品。
但目前RSA算法的專利期即將結束，取而代之的是橢圓曲線密碼體制(ECC算法)。與RSA算法相比，ECC有其相對優勢，這使得ECC的特性更適合需要快速響應的電子商務的發展趨勢。此外，壹種全新的量子密碼也正在研發中。
至於實際應用中應該采用哪種加密算法，要結合具體的應用環境和系統，不能簡單的根據其加密強度來判斷。因為除了加密算法本身，密鑰的合理分配、加密效率與現有系統的結合、投入產出分析等都要在實際環境中考慮。隨著網絡的發展和更新，加密技術將產生更加安全和易於實現的算法，為信息安全提供更強有力的保障。未來，加密技術何去何從，我們拭目以待。
參考資料:
[1] Douglas R.Stinson,《密碼學原理與實踐》。北京:電子工業出版社，2003，2: 131-132。
[2]西蒙·辛格。密碼的故事。海口:海南出版社，2001，1: 271-272。
[3]嬴政天下。加密算法的RSA算法。/yum dq/dzsw/a2.htm。
[5]黑客中級教程系列10。/jiaocheng/10.html