㈠ 公鑰密碼系統及RSA公鑰演算法
公鑰密碼系統及RSA公鑰演算法
本文簡單介紹了公開密鑰密碼系統的思想和特點，並具體介紹了RSA演算法的理論基礎，工作原理和具體實現過程，並通過一個簡單例子說明了該演算法是如何實現。在本文的最後，概括說明了RSA演算法目前存在的一些缺點和解決方法。
關鍵詞：公鑰密碼體制 ， 公鑰 ，私鑰 ，RSA
§1引言
隨著計算機聯網的逐步實現，Internet前景越來越美好，全球經濟發展正在進入信息經濟時代，知識經濟初見端倪。計算機信息的保密問題顯得越來越重要，無論是個人信息通信還是電子商務發展，都迫切需要保證Internet網上信息傳輸的安全，需要保證信息安全。信息安全技術是一門綜合學科，它涉及資訊理論、計算機科學和密碼學等多方面知識，它的主要任務是研究計算機系統和通信網路內信息的保護方法以實現系統內信息的安全、保密、真實和完整。其中，信息安全的核心是密碼技術。密碼技術是集數學、計算機科學、電子與通信等諸多學科於一身的交叉學科。它不僅能夠保證機密性信息的加密，而且能夠實現數字簽名、身份驗證、系統安全等功能。是現代化發展的重要科學之一。本文將對公鑰密碼系統及該系統中目前最廣泛流行的RSA演算法做一些簡單介紹。
§2公鑰密碼系統
要說明公鑰密碼系統，首先來了解一下不同的加密演算法：目前的加密演算法按密鑰方式可分為單鑰密碼演算法和公鑰密碼演算法。
2.1.單鑰密碼
又稱對稱式密碼，是一種比較傳統的加密方式，其加密運算、解密運算使用的是同樣的密鑰，信息的發送者和信息的接收者在進行信息的傳輸與處理時，必須共同持有該密碼（稱為對稱密碼）。因此，通信雙方都必須獲得這把鑰匙，並保持鑰匙的秘密。
單鑰密碼系統的安全性依賴於以下兩個因素：第一，加密演算法必須是足夠強的，僅僅基於密文本身去解密信息在實踐上是不可能的；第二，加密方法的安全性依賴於密鑰的秘密性，而不是演算法的秘密性，因此，我們沒有必要確保演算法的秘密性（事實上，現實中使用的很多單鑰密碼系統的演算法都是公開的），但是我們一定要保證密鑰的秘密性。
從單鑰密碼的這些特點我們容易看出它的主要問題有兩點：第一，密鑰量問題。在單鑰密碼系統中，每一對通信者就需要一對密鑰，當用戶增加時，必然會帶來密鑰量的成倍增長，因此在網路通信中，大量密鑰的產生﹑存放和分配將是一個難以解決的問題。第二，密鑰分發問題。單鑰密碼系統中，加密的安全性完全依賴於對密鑰的保護，但是由於通信雙方使用的是相同的密鑰，人們又不得不相互交流密鑰，所以為了保證安全，人們必須使用一些另外的安全信道來分發密鑰，例如用專門的信使來傳送密鑰，這種做法的代價是相當大的，甚至可以說是非常不現實的，尤其在計算機網路環境下，人們使用網路傳送加密的文件，卻需要另外的安全信道來分發密鑰，顯而易見，這是非常不智是甚至是荒謬可笑的。
2.2公鑰密碼
正因為單鑰密碼系統存在如此難以解決的缺點，發展一種新的﹑更有效﹑更先進的密碼體制顯得更為迫切和必要。在這種情況下，出現了一種新的公鑰密碼體制，它突破性地解決了困擾著無數科學家的密鑰分發問題，事實上，在這種體制中，人們甚至不用分發需要嚴格保密的密鑰，這次突破同時也被認為是密碼史上兩千年來自單碼替代密碼發明以後最偉大的成就。
這一全新的思想是本世紀70年代，美國斯坦福大學的兩名學者Diffie和Hellman提出的，該體制與單鑰密碼最大的不同是：
在公鑰密碼系統中，加密和解密使用的是不同的密鑰（相對於對稱密鑰，人們把它叫做非對稱密鑰），這兩個密鑰之間存在著相互依存關系：即用其中任一個密鑰加密的信息只能用另一個密鑰進行解密。這使得通信雙方無需事先交換密鑰就可進行保密通信。其中加密密鑰和演算法是對外公開的，人人都可以通過這個密鑰加密文件然後發給收信者，這個加密密鑰又稱為公鑰；而收信者收到加密文件後,它可以使用他的解密密鑰解密，這個密鑰是由他自己私人掌管的，並不需要分發，因此又成稱為私鑰，這就解決了密鑰分發的問題。
為了說明這一思想,我們可以考慮如下的類比：
兩個在不安全信道中通信的人，假設為Alice（收信者）和Bob（發信者），他們希望能夠安全的通信而不被他們的敵手Oscar破壞。Alice想到了一種辦法，她使用了一種鎖（相當於公鑰），這種鎖任何人只要輕輕一按就可以鎖上，但是只有Alice的鑰匙（相當於私鑰）才能夠打開。然後Alice對外發送無數把這樣的鎖，任何人比如Bob想給她寄信時，只需找到一個箱子，然後用一把Alice的鎖將其鎖上再寄給Alice，這時候任何人（包括Bob自己）除了擁有鑰匙的Alice，都不能再打開箱子，這樣即使Oscar能找到Alice的鎖，即使Oscar能在通信過程中截獲這個箱子，沒有Alice的鑰匙他也不可能打開箱子，而Alice的鑰匙並不需要分發，這樣Oscar也就無法得到這把「私人密鑰」。
從以上的介紹可以看出，公鑰密碼體制的思想並不復雜，而實現它的關鍵問題是如何確定公鑰和私鑰及加/解密的演算法，也就是說如何找到「Alice的鎖和鑰匙」的問題。我們假設在這種體制中, PK是公開信息，用作加密密鑰，而SK需要由用戶自己保密，用作解密密鑰。加密演算法E和解密演算法D也都是公開的。雖然SK與PK是成對出現，但卻不能根據PK計算出SK。它們須滿足條件：
①加密密鑰PK對明文X加密後，再用解密密鑰SK解密，即可恢復出明文，或寫為：DSK（EPK（X））=X
②加密密鑰不能用來解密，即DPK（EPK（X））≠X
③在計算機上可以容易地產生成對的PK和SK。
④從已知的PK實際上不可能推導出SK。
⑤加密和解密的運算可以對調，即：EPK（DSK（X））=X
從上述條件可看出，公開密鑰密碼體制下，加密密鑰不等於解密密鑰。加密密鑰可對外公開，使任何用戶都可將傳送給此用戶的信息用公開密鑰加密發送，而該用戶唯一保存的私人密鑰是保密的，也只有它能將密文復原、解密。雖然解密密鑰理論上可由加密密鑰推算出來，但這種演算法設計在實際上是不可能的，或者雖然能夠推算出，但要花費很長的時間而成為不可行的。所以將加密密鑰公開也不會危害密鑰的安全。
這種體制思想是簡單的，但是，如何找到一個適合的演算法來實現這個系統卻是一個真正困擾密碼學家們的難題，因為既然Pk和SK是一對存在著相互關系的密鑰，那麼從其中一個推導出另一個就是很有可能的，如果敵手Oscar能夠從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是單向的，因為它需要用有效的方式解密所收到的信息。因此，Alice應該擁有一個陷門，其中包含容易求出E的你函數的秘密信息。也就是說，Alice可以有效解密，因為它有額外的秘密知識，即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是在1978年，由美國麻省理工學院(MIT)的Rivest、Shamir和Adleman在題為《獲得數字簽名和公開鑰密碼系統的方法》的論文中提出的。它是一個基於數論的非對稱(公開鑰)密碼體制，是一種分組密碼體制。其名稱來自於三個發明者的姓名首字母。它的安全性是基於大整數素因子分解的困難性，而大整數因子分解問題是數學上的著名難題，至今沒有有效的方法予以解決，因此可以確保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 molo（p - 1）*（q - 1） 根據e、p和q可以容易地計算出d。
4)公開整數r和e，但是不公開d；
5)將明文P (假設P是一個小於r的整數)加密為密文C，計算方法為：
C = Pe molo r
6)將密文C解密為明文P，計算方法為：
P = Cd molo 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 = 1 molo 8，計算出d =3。
假定明文為整數13。則密文C為
C = Pe molo r
= 1311 molo 15
= 1,792,160,394,037 molo 15
= 7
復原明文P為：
P = Cd molo r
= 73 molo 15
= 343 molo 15
= 13
因為e和d互逆，公開密鑰加密方法也允許採用這樣的方式對加密信息進行"簽名"，以便接收方能確定簽名不是偽造的。
假設A和B希望通過公開密鑰加密方法進行數據傳輸，A和B分別公開加密演算法和相應的密鑰，但不公開解密演算法和相應的密鑰。A和B的加密演算法分別是ECA和ECB，解密演算法分別是DCA和DCB，ECA和DCA互逆，ECB和DCB互逆。 若A要向B發送明文P，不是簡單地發送ECB（P），而是先對P施以其解密演算法DCA，再用加密演算法ECB對結果加密後發送出去。
密文C為：
C = ECB（DCA（P））
B收到C後，先後施以其解密演算法DCB和加密演算法ECA，得到明文P：
ECA（DCB（C））
= ECA（DCB（ECB（DCA（P））））
= ECA（DCA（P））/*DCB和ECB相互抵消*/
=
P /*DCB和ECB相互抵消*/
這樣B就確定報文確實是從A發出的，因為只有當加密過程利用了DCA演算法，用ECA才能獲得P，只有A才知道DCA演算法，沒 有人，即使是B也不能偽造A的簽名。
3.4優缺點
3.4.1優點
RSA演算法是第一個能同時用於加密和數字簽名的演算法，也易於理解和操作。RSA是被研究得最廣泛的公鑰演算法，從提出到現在已近二十年，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。該演算法的加密密鑰和加密演算法分開，使得密鑰分配更為方便。它特別符合計算機網路環境。對於網上的大量用戶，可以將加密密鑰用電話簿的方式印出。如果某用戶想與另一用戶進行保密通信，只需從公鑰簿上查出對方的加密密鑰，用它對所傳送的信息加密發出即可。對方收到信息後，用僅為自己所知的解密密鑰將信息脫密，了解報文的內容。由此可看出，RSA演算法解決了大量網路用戶密鑰管理的難題，這是公鑰密碼系統相對於對稱密碼系統最突出的優點。
3.4.2缺點
1)產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。
2)安全性, RSA的安全性依賴於大數的因子分解，但並沒有從理論上證明破譯RSA的難度與大數分解難度等價，而且密碼學界多數人士傾向於因子分解不是NPC問題。目前，人們已能分解140多個十進制位的大素數，這就要求使用更長的密鑰，速度更慢；另外，目前人們正在積極尋找攻擊RSA的方法，如選擇密文攻擊，一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實體簽署。然後，經過計算就可得到它所想要的信息。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結構：
( XM )d = Xd *Md mod n
前面已經提到，這個固有的問題來自於公鑰密碼系統的最有用的特徵--每個人都能使用公鑰。但從演算法上無法解決這一問題，主要措施有兩條：一條是採用好的公鑰協議，保證工作過程中實體不對其他實體任意產生的信息解密，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用One-Way Hash Function對文檔作HASH處理，或同時使用不同的簽名演算法。除了利用公共模數，人們還嘗試一些利用解密指數或φ（n）等等攻擊.
3)速度太慢,由於RSA的分組長度太大，為保證安全性，n至少也要600 bitx以上，使運算代價很高，尤其是速度較慢，較對稱密碼演算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利於數據格式的標准化。目前，SET(Secure Electronic Transaction)協議中要求CA採用2048比特長的密鑰，其他實體使用1024比特的密鑰。為了速度問題,目前人們廣泛使用單,公鑰密碼結合使用的方法,優缺點互補:單鑰密碼加密速度快,人們用它來加密較長的文件,然後用RSA來給文件密鑰加密,極好的解決了單鑰密碼的密鑰分發問題。
§4結束語
目前，日益激增的電子商務和其它網際網路應用需求使公鑰體系得以普及，這些需求量主要包括對伺服器資源的訪問控制和對電子商務交易的保護，以及權利保護、個人隱私、無線交易和內容完整性（如保證新聞報道或股票行情的真實性）等方面。公鑰技術發展到今天，在市場上明顯的發展趨勢就是PKI與操作系統的集成，PKI是「Public
Key Infrastructure」的縮寫，意為「公鑰基礎設施」。公鑰體制廣泛地用於CA認證、數字簽名和密鑰交換等領域。
公鑰加密演算法中使用最廣的是RSA。RSA演算法研製的最初理念與目標是努力使互聯網安全可靠，旨在解決DES演算法秘密密鑰的利用公開信道傳輸分發的難題。而實際結果不但很好地解決了這個難題；還可利用RSA來完成對電文的數字簽名以抗對電文的否認與抵賴；同時還可以利用數字簽名較容易地發現攻擊者對電文的非法篡改，以保護數據信息的完整性。目前為止，很多種加密技術採用了RSA演算法，該演算法也已經在互聯網的許多方面得以廣泛應用，包括在安全介面層（SSL）標准（該標準是網路瀏覽器建立安全的互聯網連接時必須用到的）方面的應用。此外，RSA加密系統還可應用於智能IC卡和網路安全產品。
但目前RSA演算法的專利期限即將結束，取而代之的是基於橢圓曲線的密碼方案（ECC演算法）。較之於RSA演算法，ECC有其相對優點，這使得ECC的特性更適合當今電子商務需要快速反應的發展潮流。此外，一種全新的量子密碼也正在發展中。
至於在實際應用中應該採用何種加密演算法則要結合具體應用環境和系統，不能簡單地根據其加密強度來做出判斷。因為除了加密演算法本身之外，密鑰合理分配、加密效率與現有系統的結合性以及投入產出分析都應在實際環境中具體考慮。加密技術隨著網路的發展更新，將有更安全更易於實現的演算法不斷產生，為信息安全提供更有力的保障。今後，加密技術會何去何從，我們將拭目以待。
參考文獻：
[1] Douglas R.Stinson.《密碼學原理與實踐》.北京:電子工業出版社,2003,2:131-132
[2]西蒙.辛格.《密碼故事》.海口:海南出版社,2001,1:271-272
[3]嬴政天下.加密演算法之RSA演算法.http://soft.winzheng.com/infoView/Article_296.htm，2003
[4]加密與數字簽名.http://www.njt.cn/yumdq/dzsw/a2.htm
[5]黑客中級教程系列之十.http://www.qqorg.i-p.com/jiaocheng/10.html
㈡ RAS加密的數學原理
RSA演算法是現今使用最廣泛的公鑰密碼演算法，也是號稱地球上最安全的加密演算法。在了解RSA演算法之前，先熟悉下幾個術語根據密鑰的使用方法，可以將密碼分為對稱密碼和公鑰密碼
對稱加密：加密和解密使用同一種密鑰的方式
非對稱加密：加密和解密使用不同的密碼的方式，因此公鑰密碼通常也稱為非對稱密碼。
好多人都知道RSA加密的數學公式，但是不知道其的內部運作，那麼我們以下就詳細分析一波！
圖1，mod就是取余的意思，上面公式的意思是3的多少次方除以17餘數為12。由圖2可知道3的13次方的時候就滿足圖1的公式。由圖2的可知，公式後面的余數都是不一樣的，而且是1-16。當我們好奇試試3^17%17時候，結果就是3，好明顯等於了3^1%17的結果，那麼我們稱 3為17的原根 。
思考：任意給定正整數n，請問在小於等於n的正整數之中，有多少個與n構成互質關系？
計算這個值的方式叫做歐拉函數，使用：Φ(n)表示
計算8的歐拉函數，和8互質的 1 、2、 3 、4、 5 、6、 7 、8 所以 φ(8) = 4
計算7的歐拉函數，和7互質的 1、2、3、4、5、6 、7 所以 φ(7) = 6
計算56的歐拉函數：φ(56) = φ(8)* φ(7) = 4 * 6 = 24
如果兩個正整數，除了1以外，沒有其他公因數，我們就稱這兩個數是 互質關系 （coprime）。
一、當n是質數的時候，φ(n)=n-1。
二、如果n可以分解成兩個互質的整數之積，如n=A*B則： φ(A*B)=φ(A)*φ(B)
根據以上兩點得到：如果N是兩個質數P1 和 P2的乘積則：φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)
如果兩個正整數m和n互質，那麼m的φ(n)次方減去1，可以被n整除。如圖3所示：
我們可以設置互質的數如m=5和n=3，那麼φ(3) = 3-1=2，5^2%3=1。所以上面的公式是成立的。（有興趣的可以試多一點數字，注意是互質的兩個數）
歐拉定理的特殊情況：如果兩個正整數m和n互質，而且n為質數！那麼φ(n)結果就是n-1。如圖4所示：
注意：滿足第3步的時候，m必須要小於n。
如果兩個正整數e和x互質，那麼一定可以找到整數d，使得 ed-1 被x整除。那麼d就是e對於x的「模反元素」。如圖6所示：
公鑰： n和e
私鑰： n和d
明文: m
密文: c
1、n會非常大，長度一般為1024個二進制位。（目前人類已經分解的最大整數，232個十進制位，768個二進制位）
2、由於需要求出φ(n)，所以根據歐函數特點，最簡單的方式n ，由兩個質數相乘得到:
質數：p1、p2 Φ(n) = (p1 -1) * (p2 - 1)
3、最終由φ(n)得到e 和 d 。
總共生成6個數字：p1、p2、n、φ(n)、e、d
除了公鑰用到了n和e其餘的4個數字是不公開的。目前破解RSA得到d的方式如下：
1、要想求出私鑰 d 。由於e*d = φ(n)*k + 1。要知道e和φ(n);
2、e是知道的，但是要得到 φ(n)，必須知道p1和 p2。
3、由於 n=p1*p2。只有將n因數分解才能算出。
㈢ 加密技術有哪幾種
採用密碼技術對信息加密，是最常用的安全交易手段。在電子商務中獲得廣泛應用的加密技術有以下兩種：
（1）公共密鑰和私用密鑰（public key and private key）
這一加密方法亦稱為RSA編碼法，是由Rivest、Shamir和Adlernan三人所研究發明的。它利用兩個很大的質數相乘所產生的乘積來加密。這兩個質數無論哪一個先與原文件編碼相乘，對文件加密，均可由另一個質數再相乘來解密。但要用一個質數來求出另一個質數，則是十分困難的。因此將這一對質數稱為密鑰對(Key Pair)。在加密應用時，某個用戶總是將一個密鑰公開，讓需發信的人員將信息用其公共密鑰加密後發給該用戶，而一旦信息加密後，只有用該用戶一個人知道的私用密鑰才能解密。具有數字憑證身份的人員的公共密鑰可在網上查到，亦可在請對方發信息時主動將公共密鑰傳給對方，這樣保證在Internet上傳輸信息的保密和安全。
（2）數字摘要(digital digest)
這一加密方法亦稱安全Hash編碼法（SHA:Secure Hash Algorithm）或MD5(MD Standards for Message Digest)，由Ron Rivest所設計。該編碼法採用單向Hash函數將需加密的明文「摘要」成一串128bit的密文，這一串密文亦稱為數字指紋(Finger Print)，它有固定的長度，且不同的明文摘要成密文，其結果總是不同的，而同樣的明文其摘要必定一致。這樣這摘要便可成為驗證明文是否是「真身」的「指紋」了。
上述兩種方法可結合起來使用，數字簽名就是上述兩法結合使用的實例。
3.2數字簽名(digital signature)
在書面文件上簽名是確認文件的一種手段，簽名的作用有兩點，一是因為自己的簽名難以否認，從而確認了文件已簽署這一事實；二是因為簽名不易仿冒，從而確定了文件是真的這一事實。數字簽名與書面文件簽名有相同之處，採用數字簽名，也能確認以下兩點：
a. 信息是由簽名者發送的。
b. 信息在傳輸過程中未曾作過任何修改。
這樣數字簽名就可用來防止電子信息因易被修改而有人作偽；或冒用別人名義發送信息；或發出（收到）信件後又加以否認等情況發生。
數字簽名採用了雙重加密的方法來實現防偽、防賴。其原理為：
（1） 被發送文件用SHA編碼加密產生128bit的數字摘要（見上節）。
（2） 發送方用自己的私用密鑰對摘要再加密，這就形成了數字簽名。
（3） 將原文和加密的摘要同時傳給對方。
（4） 對方用發送方的公共密鑰對摘要解密，同時對收到的文件用SHA編碼加密產生又一摘要。
（5） 將解密後的摘要和收到的文件在接收方重新加密產生的摘要相互對比。如兩者一致，則說明傳送過程中信息沒有被破壞或篡改過。否則不然。
3.3數字時間戳(digital time-stamp)
交易文件中，時間是十分重要的信息。在書面合同中，文件簽署的日期和簽名一樣均是十分重要的防止文件被偽造和篡改的關鍵性內容。
在電子交易中，同樣需對交易文件的日期和時間信息採取安全措施，而數字時間戳服務(DTS：digital time-stamp service)就能提供電子文件發表時間的安全保護。
數字時間戳服務（DTS）是網上安全服務項目，由專門的機構提供。時間戳（time-stamp）是一個經加密後形成的憑證文檔，它包括三個部分：1）需加時間戳的文件的摘要(digest)，2）DTS收到文件的日期和時間，3）DTS的數字簽名。
時間戳產生的過程為：用戶首先將需要加時間戳的文件用HASH編碼加密形成摘要，然後將該摘要發送到DTS，DTS在加入了收到文件摘要的日期和時間信息後再對該文件加密（數字簽名），然後送回用戶。由Bellcore創造的DTS採用如下的過程：加密時將摘要信息歸並到二叉樹的數據結構；再將二叉樹的根值發表在報紙上，這樣更有效地為文件發表時間提供了佐證。注意，書面簽署文件的時間是由簽署人自己寫上的，而數字時間戳則不然，它是由認證單位DTS來加的，以DTS收到文件的時間為依據。因此，時間戳也可作為科學家的科學發明文獻的時間認證。
3.4數字憑證(digital certificate, digital ID)
數字憑證又稱為數字證書，是用電子手段來證實一個用戶的身份和對網路資源的訪問的許可權。在網上的電子交易中，如雙方出示了各自的數字憑證，並用它來進行交易操作，那麼雙方都可不必為對方身份的真偽擔心。數字憑證可用於電子郵件、電子商務、群件、電子基金轉移等各種用途。
數字憑證的內部格式是由CCITT X.509國際標准所規定的，它包含了以下幾點：
(1) 憑證擁有者的姓名，
(2) 憑證擁有者的公共密鑰，
(3) 公共密鑰的有效期，
(4) 頒發數字憑證的單位，
(5) 數字憑證的序列號（Serial number），
(6) 頒發數字憑證單位的數字簽名。
數字憑證有三種類型：
(1) 個人憑證(Personal Digital ID)：它僅僅為某一個用戶提供憑證，以幫助其個人在網上進行安全交易操作。個人身份的數字憑證通常是安裝在客戶端的瀏覽器內的。並通過安全的電子郵件（S/MIME）來進行交易操作。
(2) 企業（伺服器）憑證（Server ID）：它通常為網上的某個Web伺服器提供憑證，擁有Web伺服器的企業就可以用具有憑證的萬維網站點(Web Site)來進行安全電子交易。有憑證的Web伺服器會自動地將其與客戶端Web瀏覽器通信的信息加密。
(3) 軟體（開發者）憑證（Developer ID）：它通常為Internet中被下載的軟體提供憑證，該憑證用於和微軟公司Authenticode技術（合法化軟體）結合的軟體，以使用戶在下載軟體時能獲得所需的信息。
上述三類憑證中前二類是常用的憑證，第三類則用於較特殊的場合，大部分認證中心提供前兩類憑證，能提供各類憑證的認證中心並不普遍
㈣ 常見密碼技術簡介
##
密碼技術在網路傳輸安全上的應用
隨著互聯網電子商務和網路支付的飛速發展，互聯網安全已經是當前最重要的因素之一。作為一名合格的軟體開發工程師，有必要了解整個互聯網是如何來保證數據的安全傳輸的，本篇文章對網路傳輸安全體系以及涉及到的演算法知識做了一個簡要的介紹，希望大家能夠有一個初步的了解。
###密碼技術定義
簡單的理解，密碼技術就是編制密碼和破譯密碼的一門技術，也即是我們常說的加密和解密。常見的結構如圖：
其中涉及到的專業術語：
1.秘鑰：分為加密秘鑰和解密秘鑰，兩者相同的加密演算法稱為對稱加密，不同的稱為非對稱加密；
2.明文：未加密過的原文信息，不可以被泄露；
3.密文：經過加密處理後的信息，無法從中獲取有效的明文信息；
4.加密：明文轉成密文的過程，密文的長度根據不同的加密演算法也會有不同的增量；
5.解密：密文轉成明文的過程；
6.加密/解密演算法：密碼系統使用的加密方法和解密方法；
7.攻擊：通過截獲數據流、釣魚、木馬、窮舉等方式最終獲取秘鑰和明文的手段。
###密碼技術和我們的工作生活息息相關
在我們的日常生活和工作中，密碼技術的應用隨處可見，尤其是在互聯網系統上。下面列舉幾張比較有代表性的圖片，所涉及到的知識點後面都會一一講解到。
1.12306舊版網站每次訪問時，瀏覽器一般會提示一個警告，是什麼原因導致的？ 這樣有什麼風險呢？
2.360瀏覽器瀏覽HTTPS網站時，點開地址欄的小鎖圖標會顯示加密的詳細信息，比如網路的話會顯示```AES_128_GCM、ECDHE_RSA```，這些是什麼意思？
3.在Mac系統的鑰匙串里有很多的系統根證書，展開後有非常多的信息，這些是做什麼用的？
4.去銀行開通網上支付都會附贈一個U盾，那U盾有什麼用呢？
##如何確保網路數據的傳輸安全
接下來我們從實際場景出發，以最常見的客戶端Client和服務端Server傳輸文件為例來一步步了解整個安全體系。
####1. 保密性
首先客戶端要把文件送到服務端，不能以明文形式發送，否則被黑客截獲了數據流很容易就獲取到了整個文件。也就是文件必須要確保保密性，這就需要用到對稱加密演算法。
** 對稱加密： **加密和解密所使用的秘鑰相同稱為對稱加密。其特點是速度快、效率高，適用於對較大量的數據進行加密。常見的對稱加密演算法有DES、3DES、AES、TDEA、RC5等，讓我們了解下最常見的3DES和AES演算法：
** DES(Data Encryption Standard)： **1972年由美國IBM研製，數學原理是將明文以8位元組分組（不足8位可以有不同模式的填充補位），通過數學置換和逆置換得到加密結果，密文和明文長度基本相同。秘鑰長度為8個位元組，後有了更安全的一個變形，使用3條秘鑰進行三次加密，也就是3DES加密。
**3DES：**可以理解為對明文進行了三次DES加密，增強了安全程度。
** AES(Advanced Encryption Standard)： **2001年由美國發布，2002年成為有效標准，2006年成為最流行的對稱加密演算法之一。由於安全程度更高，正在逐步替代3DES演算法。其明文分組長度為16位元組，秘鑰長度可以為16、24、32(128、192、256位)位元組，根據秘鑰長度，演算法被稱為AES-128、AES-192和AES-256。
對稱加密演算法的入參基本類似，都是明文、秘鑰和模式三個參數。可以通過網站進行模擬測試：[http://tool.chacuo.net/crypt3des]()。其中的模式我們主要了解下ECB和CBC兩種簡單模式，其它有興趣可自行查閱。
** ECB模式(Electronic Codebook Book)： **這種模式是將明文分成若干小段，然後對每一段進行單獨的加密，每一段之間不受影響，可以單獨的對某幾段密文進行解密。
** CBC模式(Cipher Block Chaining)： **這種模式是將明文分成若干小段，然後每一段都會和初始向量(上圖的iv偏移量)或者上一段的密文進行異或運算後再進行加密，不可以單獨解密某一斷密文。
** 填充補位： **常用為PKCS5Padding，規則為缺幾位就在後面補幾位的所缺位數。，比如明文數據為```/x01/x01/x01/x01/x01/x01```6個位元組，缺2位補```/x02```，補完位```/x01/x01/x01/x01/x01/x01/x02/x02```。解密後也會按照這個規則進行逆處理。需要注意的是：明文為8位時也需要在後面補充8個```/x08```。
####2. 真實性
客戶端有了對稱秘鑰，就需要考慮如何將秘鑰送到服務端，問題跟上面一樣：不能以明文形式直接傳輸，否則還是會被黑客截獲到。這里就需要用到非對稱加密演算法。
** 非對稱加密： **加密和解密秘鑰不同，分別稱為公開秘鑰(publicKey)和私有秘鑰(privateKey)。兩者成對出現，公鑰加密只能用私鑰解密，而私鑰加密也只能用公鑰加密。兩者不同的是：公鑰是公開的，可以隨意提供給任何人，而私鑰必須保密。特點是保密性好，但是加密速度慢。常見的非對稱加密演算法有RSA、ECC等；我們了解下常見的RSA演算法：
** RSA(Ron Rivest、Adi Shamir、Leonard Adleman)： **1977年由麻省理工學院三人提出，RSA就是他們三個人的姓氏開頭字母拼在一起組成的。數學原理是基於大數分解。類似於```100=20x5```，如果只知道100的話，需要多次計算才可以試出20和5兩個因子。如果100改為極大的一個數，就非常難去試出真正的結果了。下面是隨機生成的一對公私鑰:
這是使用公鑰加密後結果：
RSA的這種特性就可以保證私鑰持有者的真實性，客戶端使用公鑰加密文件後，黑客就算截獲到數據因為沒有私鑰也是無法解密的。
** Tips： **
+** 不使用對稱加密，直接用RSA公私鑰進行加密和解密可以嗎？ **
答案：不可以，第一是因為RSA加密速度比對稱加密要慢幾十倍甚至幾百倍以上，第二是因為RSA加密後的數據量會變大很多。
+** 由服務端生成對稱秘鑰，然後用私鑰加密，客戶端用公鑰解密這樣來保證對稱秘鑰安全可行嗎？ **
答案：不可行，因為公鑰是公開的，任何一個人都可以拿到公鑰解密獲取對稱秘鑰。
####3. 完整性
當客戶端向服務端發送對稱秘鑰加密後的文件時，如果被黑客截獲，雖然無法解密得到對稱秘鑰。但是黑客可以用服務端公鑰加密一個假的對稱秘鑰，並用假的對稱秘鑰加密一份假文件發給服務端，這樣服務端會仍然認為是真的客戶端發送來的，而並不知道閱讀的文件都已經是掉包的了。
這個問題就需要用到散列演算法，也可以譯為Hash。常見的比如MD4、MD5、SHA-1、SHA-2等。
** 散列演算法(哈希演算法)： **簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。而且該過程是不可逆的，無法通過摘要獲得原文。
** SHA-1(Secure Hash Algorithm 1)： **由美國提出，可以生成一個20位元組長度的消息摘要。05年被發現了針對SHA-1的有效攻擊方法，已經不再安全。2010年以後建議使用SHA-2和SHA-3替代SHA-1。
** SHA-2(Secure Hash Algorithm 2)： **其下又分為六個不同演算法標准：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA512/256。其後面數字為摘要結果的長度，越長的話碰撞幾率越小。SHA-224的使用如下圖：
客戶端通過上面的散列演算法可以獲取文件的摘要消息，然後用客戶端私鑰加密後連同加密的文件發給服務端。黑客截獲到數據後，他沒有服務端私鑰無法獲取到對稱秘鑰，也沒有客戶端私鑰無法偽造摘要消息。如果再像上面一樣去掉包文件，服務端收到解密得到摘要消息一對比就可以知道文件已經被掉包篡改過了。
這種用私鑰對摘要消息進行加密的過程稱之為數字簽名，它就解決了文件是否被篡改問題，也同時可以確定發送者身份。通常這么定義：
** 加密： **用公鑰加密數據時稱為加密。
** 簽名： **用私鑰加密數據時稱為簽名。
####4. 信任性
我們通過對稱加密演算法加密文件，通過非對稱加密傳輸對稱秘鑰，再通過散列演算法保證文件沒被篡改過和發送者身份。這樣就安全了嗎？
答案是否定的，因為公鑰是要通過網路送到對方的。在這期間如果出現問題會導致客戶端收到的公鑰並不一定是服務端的真實公鑰。常見的** 中間人攻擊 **就是例子：
** 中間人攻擊MITM(Man-in-the-MiddleAttack)： **攻擊者偽裝成代理伺服器，在服務端發送公鑰證書時，篡改成攻擊者的。然後收到客戶端數據後使用攻擊者私鑰解密，再篡改後使用攻擊者私鑰簽名並且將攻擊者的公鑰證書發送給伺服器。這樣攻擊者就可以同時欺騙雙方獲取到明文。
這個風險就需要通過CA機構對公鑰證書進行數字簽名綁定公鑰和公鑰所屬人，也就是PKI體系。
** PKI(Privilege Management Infrastructure)： **支持公鑰管理並能支持認證、加密、完整性和可追究性的基礎設施。可以說整個互聯網數據傳輸都是通過PKI體系進行安全保證的。
** CA(Certificate Authority)： **CA機構就是負責頒發證書的，是一個比較公認的權威的證書發布機構。CA有一個管理標准：WebTrust。只有通過WebTrust國際安全審計認證，根證書才能預裝到主流的瀏覽器而成為一個全球可信的認證機構。比如美國的GlobalSign、VeriSign、DigiCert，加拿大的Entrust。我國的CA金融方面由中國人民銀行管理CFCA，非金融CA方面最初由中國電信負責建設。
CA證書申請流程：公司提交相應材料後，CA機構會提供給公司一張證書和其私鑰。會把Issuer,Public key,Subject,Valid from,Valid to等信息以明文的形式寫到證書裡面，然後用一個指紋演算法計算出這些數字證書內容的一個指紋，並把指紋和指紋演算法用自己的私鑰進行加密。由於瀏覽器基本都內置了CA機構的根證書，所以可以正確的驗證公司證書指紋（驗簽），就不會有安全警告了。
但是：所有的公司其實都可以發布證書，甚至我們個人都可以隨意的去發布證書。但是由於瀏覽器沒有內置我們的根證書，當客戶端瀏覽器收到我們個人發布的證書後，找不到根證書進行驗簽，瀏覽器就會直接警告提示，這就是之前12306打開會有警告的原因。這種個人發布的證書，其實可以通過系統設置為受信任的證書去消除這個警告。但是由於這種證書機構的權威性和安全性難以信任，大家最好不要這么做。
我們看一下網路HTTPS的證書信息：
其中比較重要的信息：
簽發機構：GlobalSign Root CA；
有效日期：2018-04-03到2019-05-26之間可用；
公鑰信息：RSA加密，2048位；
數字簽名：帶 RSA 加密的 SHA-256 ( 1.2.840.113549.1.1.11 )
綁定域名：再進行HTTPS驗證時，如果當前域名和證書綁定域名不一致，也會出現警告；
URI：在線管理地址。如果當前私鑰出現了風險，CA機構可以在線吊銷該證書。
####5. 不可抵賴性
看起來整個過程都很安全了，但是仍存在一種風險：服務端簽名後拒不承認，歸咎於故障不履行合同怎麼辦。
解決方法是採用數字時間戳服務：DTS。
** DTS(digital time-stamp)： **作用就是對於成功的電子商務應用，要求參與交易各方不能否認其行為。一般來說，數字時間戳產生的過程為：用戶首先將需要加時間戳的文件用Hash演算法運算形成摘要，然後將該摘要發送到DTS。DTS在加入了收到文件摘要的日期和事件信息後再對該文件進行數字簽名，然後送達用戶。
####6. 再次認證
我們有了數字證書保證了身份的真實性，又有了DTS提供的不可抵賴性。但是還是不能百分百確定使用私鑰的就是合法持有者。有可能出現被別人盜用私鑰進行交易的風險。
解決這個就需要用到強口令、認證令牌OTP、智能卡、U盾或生物特徵等技術對使用私鑰的當前用戶進行認證，已確定其合法性。我們簡單了解下很常見的U盾。
** USB Key(U盾)： **剛出現時外形比較像U盤，安全性能像一面盾牌，取名U盾。其內部有一個只可寫不可讀的區域存儲著用戶的私鑰(也有公鑰證書)，銀行同樣也擁有一份。當進行交易時，所有涉及到私鑰的運算都在U盾內部進行，私鑰不會泄露。當交易確認時，交易的詳細數據會顯示到U盾屏幕上，確認無誤後通過物理按鍵確認就可以成功交易了。就算出現問題黑客也是無法控制U盾的物理按鍵的，用戶可以及時取消避免損失。有的U盾裡面還有多份證書，來支持國密演算法。
** 國密演算法： **國家密碼局針對各種演算法制定了一些列國產密碼演算法。具體包括：SM1對稱加密演算法、SM2公鑰演算法、SM3摘要演算法、SM4對稱加密演算法、ZUC祖沖之演算法等。這樣可以對國產固件安全和數據安全進行進一步的安全控制。
## HTTPS分析
有了上面的知識，我們可以嘗試去分析下HTTPS的整個過程，用Wireshark截取一次HTTPS報文：
Client Hello: 客戶端發送Hello到服務端443埠，裡麵包含了隨機數、客戶端支持的加密演算法、客戶端的TLS版本號等；
Server Hello: 服務端回應Hello到客戶端，裡麵包含了服務端選擇的加密套件、隨機數等；
Certificate： 服務端向客戶端發送證書
服務端計算對稱秘鑰：通過ECDH演算法得到對稱秘鑰
客戶端計算對稱秘鑰：通過ECDH演算法得到對稱秘鑰
開始用對稱秘鑰進行加密傳輸數據
其中我們又遇到了新的演算法：DH演算法
** DH(Diffie-Hellman)： **1976年由Whitefield與Martin Hellman提出的一個奇妙的秘鑰交換協議。這個機制的巧妙在於可以通過安全的方式使雙方獲得一個相同的秘鑰。數學原理是基於原根的性質，如圖：
*** DH演算法的用處不是為了加密或解密消息，而是用於通信雙方安全的交換一個相同的秘鑰。 ***
** ECDH： **基於ECC(橢圓曲線密碼體制)的DH秘鑰交換演算法，數學原理是基於橢圓曲線上的離散對數問題。
** ECDHE： **字面少了一個E，E代表了臨時。在握手流程中，作為伺服器端，ECDH使用證書公鑰代替Pb，使用自身私鑰代替Xb。這個演算法時伺服器不發送server key exchange報文，因為發送certificate報文時，證書本身就包含了Pb信息。
##總結
| 演算法名稱 | 特點 | 用處 | 常用演算法名 |
| --- | :--- | :---: | ---: |
| 對稱加密 | 速度快，效率高| 用於直接加密文件 | 3DES、AES、RC4 |
| 非對稱加密 | 速度相對慢，但是確保安全 | 構建CA體系 | RSA、ECC |
| 散列演算法 | 算出的摘要長度固定，不可逆 | 防止文件篡改 | SHA-1、SHA-2 |
| DH演算法 | 安全的推導出對稱秘鑰 | 交換對稱秘鑰 | ECDH |
----
㈤ RSA 加密演算法（原理篇）
前幾天看到一句話，「我們中的很多人把一生中最燦爛的笑容大部分都獻給了手機和電腦屏幕」。心中一驚，這說明了什麼？手機和電腦已經成為了我們生活中的一部分，所以才會有最懂你的不是你，也不是你男朋友，而是大數據。
如此重要的個人數據，怎樣才能保證其在互聯網上的安全傳輸呢？當然要靠各種加密演算法。說起加密演算法，大家都知道有哈希、對稱加密和非對稱加密了。哈希是一個散列函數，具有不可逆操作；對稱加密即加密和解密使用同一個密鑰，而非對稱加密加密和解密自然就是兩個密鑰了。稍微深入一些的，還要說出非對稱加密演算法有DES、3DES、RC4等，非對稱加密演算法自然就是RSA了。那麼當我們聊起RSA時，我們又在聊些什麼呢？今天筆者和大家一起探討一下，有不足的地方，還望各位朋友多多提意見，共同進步。
RSA簡介：1976年由麻省理工學院三位數學家共同提出的，為了紀念這一里程碑式的成就，就用他們三個人的名字首字母作為演算法的命名。即 羅納德·李維斯特 （Ron Rivest）、 阿迪·薩莫爾 （Adi Shamir）和 倫納德·阿德曼 （Leonard Adleman）。
公鑰：用於加密，驗簽。
私鑰：解密，加簽。
通常知道了公鑰和私鑰的用途以後，即可滿足基本的聊天需求了。但是我們今天的主要任務是來探究一下RSA加解密的原理。
說起加密演算法的原理部分，肯定與數學知識脫不了關系。
我們先來回憶幾個數學知識：
φn = φ(A*B)=φ(A)*φ(B)=(A-1)*(B-1)。
這個公式主要是用來計算給定一個任意的正整數n，在小於等於n的正整數中，有多少個與n構成互質的關系。
其中n=A*B，A與B互為質數，但A與B本身並不要求為質數，可以繼續展開，直至都為質數。
在最終分解完成後，即 φ(N) = φ(p1)*φ(p2)*φ(p3)... 之後，p1，p2，p3都是質數。又用到了歐拉函數的另一個特點，即當p是質數的時候，φp = p - 1。所以有了上面給出的歐拉定理公式。
舉例看一下：
計算15的歐拉函數，因為15比較小，我們可以直接看一下，小於15的正整數有 1、2、3、4、5、6、7、8、9、10、11、12、13、14。和15互質的數有1、2、4、7、8、11、13、14一共四個。
對照我們剛才的歐拉定理： 。
其他感興趣的，大家可以自己驗證。
之所以要在這里介紹歐拉函數，我們在計算公鑰和私鑰時候，會用到。
如果兩個正整數m 和 n 互質，那麼m 的 φn 次方減1，可以被n整除。
其中 .
其中當n為質數時，那麼 上面看到的公式就變成了
mod n 1.
這個公式也就是著名的 費馬小定理 了。
如果兩個正整數e和x互為質數，那麼一定存在一個整數d，不止一個，使得 e*d - 1 可以被x整除，即 e * d mode x 1。則稱 d 是 e 相對於 x的模反元素。
了解了上面所講的歐拉函數、歐拉定理和模反元素後，就要來一些化學反應了，請看圖：
上面這幅圖的公式變化有沒有沒看明白的，沒看明白的咱們評論區見哈。
最終我們得到了最重要的第5個公式的變形，即紅色箭頭後面的：
mod n m。
其中有幾個關系，需要搞明白，m 與 n 互為質數，φn = x，d 是e相對於x的模反元素。
有沒有看到一些加解密的雛形。
從 m 到 m。 這中間涵蓋了從加密到解密的整個過程，但是缺少了我們想要的密文整個過程。
OK，下面引入本文的第四個數學公式：
我們來看一下整個交換流程：
1、客戶端有一個數字13，服務端有一個數字15;
2、客戶端通過計算 3的13次方 對 17 取余，得到數字12; 將12發送給服務端；同時服務端通過計算3的15次方，對17取余，得到數字6，將6發送給客戶端。至此，整個交換過程完成。
3、服務端收到數字12以後，繼續計算，12的15次方 對 17取余，得到 數字10。
4、客戶端收到數字 6以後，繼續計算，6的13次方 對 17 取余，得到數字 10。
有沒有發現雙方，最終得到了相同的內容10。但是這個數字10從來沒有在網路過程中出現過。
好，講到這里，可能有些人已經恍然大悟，這就是加密過程了，但是也有人會產生疑問，為什麼要取數字3 和 17 呢，這里還牽涉到另一個數學知識，原根的問題。即3是17的原根。看圖
有沒有發現規律，3的1~16次方，對17取余，得到的整數是從1~16。這時我們稱3為17的原根。也就是說上面的計算過程中有一組原根的關系。這是最早的迪菲赫爾曼秘鑰交換演算法。
解決了為什麼取3和17的問題後，下面繼續來看最終的RSA是如何產生的：
還記得我們上面提到的歐拉定理嗎，其中 m 與 n 互為質數，n為質數，d 是 e 相對於 φn的模反元素。
當迪菲赫爾曼密鑰交換演算法碰上歐拉定理會產生什麼呢？
我們得到下面的推論：
好，到這里我們是不是已經看到了整個的加密和解密過程了。
其中 m 是明文；c 是密文； n 和 e 為公鑰；d 和 n 為私鑰 。
其中幾組數字的關系一定要明確：
1、d是e 相對於 φn 的模反元素，φn = n-1，即 e * d mod n = 1.
2、m 小於 n，上面在講迪菲赫爾曼密鑰交換演算法時，提到原根的問題，在RSA加密演算法中，對m和n並沒有原根條件的約束。只要滿足m與n互為質數，n為質數，且m < n就可以了。
OK，上面就是RSA加密演算法的原理了，經過上面幾個數學公式的狂轟亂炸，是不是有點迷亂了，給大家一些時間理一下，後面會和大家一起來驗證RSA演算法以及RSA為什麼安全。
㈥ 密碼學基礎（三）：非對稱加密（RSA演算法原理）
加密和解密使用的是兩個不同的秘鑰，這種演算法叫做非對稱加密。非對稱加密又稱為公鑰加密，RSA只是公鑰加密的一種。
現實生活中有簽名，互聯網中也存在簽名。簽名的作用有兩個，一個是身份驗證，一個是數據完整性驗證。數字簽名通過摘要演算法來確保接收到的數據沒有被篡改，再通過簽名者的私鑰加密，只能使用對應的公鑰解密，以此來保證身份的一致性。
數字證書是將個人信息和數字簽名放到一起，經由CA機構的私鑰加密之後生成。當然，不經過CA機構，由自己完成簽名的證書稱為自簽名證書。CA機構作為互聯網密碼體系中的基礎機構，擁有相當高級的安全防範能力，所有的證書體系中的基本假設或者前提就是CA機構的私鑰不被竊取，一旦 CA J機構出事，整個信息鏈將不再安全。
CA證書的生成過程如下：
證書參與信息傳遞完成加密和解密的過程如下：
互質關系：互質是公約數只有1的兩個整數，1和1互質，13和13就不互質了。
歐拉函數：表示任意給定正整數 n，在小於等於n的正整數之中，有多少個與 n 構成互質關系，其表達式為：
其中，若P為質數，則其表達式可以簡寫為：
情況一：φ(1)=1
1和任何數都互質，所以φ(1)=1；
情況二：n 是質數， φ(n)=n-1
因為 n 是質數，所以和小於自己的所有數都是互質關系，所以φ(n)=n-1；
情況三：如果 n 是質數的某一個次方，即 n = p^k ( p 為質數，k 為大於等於1的整數)，則φ(n)=(p-1)p^(k-1)
因為 p 為質數，所以除了 p 的倍數之外，小於 n 的所有數都是 n 的質數；
情況四：如果 n 可以分解成兩個互質的整數之積，n = p1 × p2，則φ(n) = φ(p1p2) = φ(p1)φ(p2)
情況五：基於情況四，如果 p1 和 p2 都是質數，且 n=p1 × p2，則φ(n) = φ(p1p2) = φ(p1)φ(p2)=(p1-1)(p2-1)
而 RSA 演算法的基本原理就是歐拉函數中的第五種情況，即： φ(n)=(p1-1)(p2-1);
如果兩個正整數 a 和 n 互質，那麼一定可以找到整數 b，使得 ab-1 被 n 整除，或者說ab被n除的余數是1。這時，b就叫做a的「模反元素」。歐拉定理可以用來證明模反元素必然存在。
可以看到，a的 φ(n)-1 次方，就是a對模數n的模反元素。
n=p x q = 3233，3233寫成二進制是110010100001，一共有12位，所以這個密鑰就是12位。
在實際使用中，一般場景下選擇1024位長度的數字，更高安全要求的場景下，選擇2048位的數字，這里作為演示，選取p=61和q=53；
因為n、p、q都為質數，所以φ(n) = (p-1)(q-1)=60×52= 3120
注意，這里是和φ(n) 互互質而不是n！假設選擇的值是17，即 e=17；
模反元素就是指有一個整數 d，可以使得 ed 被 φ(n) 除的余數為1。表示為：(ed-1)=φ(n) y --> 17d=3120y+1，算出一組解為(2753,15)，即 d=2753，y=-15，也就是(17 2753-1)/3120=15。
注意，這里不能選擇3119，否則公私鑰相同？？
公鑰：(n,e)=(3233,2753)
私鑰：(n,d)=(3233,17)
公鑰是公開的，也就是說m=p*q=3233是公開的，那麼怎麼求e被？e是通過模反函數求得，17d=3120y+1，e是公開的等於17，這時候想要求d就要知道3120，也就是φ(n)，也就是φ(3233)，說白了，3233是公開的，你能對3233進行因數分解，你就能知道d，也就能破解私鑰。
正常情況下，3233我們可以因數分解為61*53，但是對於很大的數字，人類只能通過枚舉的方法來因數分解，所以RSA安全性的本質就是：對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA演算法愈可靠。
人類已經分解的最大整數是：
這個人類已經分解的最大整數為232個十進制位，768個二進制位，比它更大的因數分解，還沒有被報道過，因此目前被破解的最長RSA密鑰就是768位。所以實際使用中的1024位秘鑰基本安全，2048位秘鑰絕對安全。
網上有個段子：
已經得出公私鑰的組成：
公鑰：(n,e)=(3233,2753)
私鑰：(n,d)=(3233,17)
加密的過程就是
解密過程如下：
其中 m 是要被加密的數字，c 是加密之後輸出的結果，且 m < n ，其中解密過程一定成立可以證明的，這里省略證明過程。
總而言之，RSA的加密就是使用模反函數對數字進行加密和求解過程，在實際使用中因為 m < n必須成立，所以就有兩種加密方法：
對稱加密存在雖然快速，但是存在致命的缺點就是秘鑰需要傳遞。非對稱加密雖然不需要傳遞秘鑰就可以完成加密和解密，但是其致命缺點是速度不夠快，不能用於高頻率，高容量的加密場景。所以才有了兩者的互補關系，在傳遞對稱加密的秘鑰時採用非對稱加密，完成秘鑰傳送之後採用對稱加密，如此就可以完美互補。
㈦ RSA加密原理
RSA加密是一種非對稱加密。可以在不直接傳遞密鑰的情況下，完成解密。這能夠確保信息的安全性，避免了直接傳遞密鑰所造成的被破解的風險。是由一對密鑰來進行加解密的過程，分別稱為公鑰和私鑰。公鑰加密--私鑰解密，私鑰加密--公鑰解密
在 整數 中， 離散對數 是一種基於 同餘 運算和 原根 的一種 對數 運算。而在實數中對數的定義 log b a 是指對於給定的 a 和 b ，有一個數 x ，使得 b x = a 。相同地在任何群 G 中可為所有整數 k 定義一個冪數為 b K ，而 離散對數 log b a 是指使得 b K = a 的整數 k 。
當3為17的 原根 時，我們會發現一個規律
對 正整數 n，歐拉函數是小於或等於n的正整數中與n 互質 的數的數目（因此φ(1)=1）。有以下幾個特點
服務端根據生成一個隨機數15，根據 3 15 mod 17 計算出6，服務端將6傳遞給客戶端，客戶端生成一個隨機數13，根據 3 13 mod 17 計算出12後，將12再傳回給服務端，客戶端收到服務端傳遞的6後，根據 6 13 mod 17 計算出 10 ，服務端收到客戶端傳遞的12後，根據 12 15 mod 17 計算出 10 ，我們會發現我們通過 迪菲赫爾曼密鑰交換 將 10 進行了加密傳遞
說明：
安全性：
除了 公鑰 用到 n 和 e ，其餘的4個數字是 不公開 的（p1、p2、φ(n)、d）
目前破解RSA得到的方式如下：
缺點
RSA加密 效率不高 ，因為是純粹的數學演算法，大數據不適合RSA加密，所以我們在加密大數據的時候，我們先用 對稱加密 演算法加密大數據得到 KEY ，然後再用 RSA 加密 KEY ，再把大數據和KEY一起進行傳遞
因為Mac系統內置了OpenSSL（開源加密庫），所以我們開源直接在終端進行RSA加密解密
生成RSA私鑰，密鑰名為private.pem,密鑰長度為1024bit
因為在iOS中是無法使用 .pem 文件進行加密和解密的，需要進行下面幾個步驟
生成一個10年期限的crt證書
crt證書格式轉換成der證書