非對稱加密及RSA算法

最近在學習區塊鍊相關的知識，發現其保證去中心化的一個重要的手段就是基于密碼學中的非對稱加密。

何為非對稱加密？

在回答這個問題之前，我覺得有比說一下對稱加密。所謂對稱加密，就是加密和解密都使用同一個密鑰。那麼很顯然，非對稱加密就是加密和解密使用不同的密鑰。

非對稱加密有兩個密鑰：公鑰和私鑰，公鑰是公開的，私鑰是私密的，公鑰加密的可以用私鑰解開，私鑰加密的東西可以用公鑰解開，即加密和解密的密鑰是不同的。舉個例子，甲要發資訊給乙，那麼甲可以使用乙方的公鑰對機密資訊進行加密簽名後發送給乙方，乙方收到資料後用自己的私鑰對資料進行解密。

好了，非對稱加密的概念我們很好了解，那麼具體如何實作非對稱加密呢？

常用的加密算法有​​RSA​​​、​​Elgamal​​​、背包算法、Rabin、D-H、​​ECC​​（橢圓曲線加密算法）。其中，使用最廣泛的是RSA算法。下面我們就具體介紹一下RSA算法，主要參考部落格​安全體系（二）——RSA算法詳解。​​

RSA

算法來源

RSA​​公鑰​​​​加密算法​​​是1977年由​​羅納德·李維斯特​​​（Ron Rivest）、​​阿迪·薩莫爾​​​（Adi Shamir）和​​倫納德·阿德曼​​（Leonard Adleman）一起提出的。1987年7月首次在美國公布，當時他們三人都在麻省理工學院工作實習。RSA就是他們三人姓氏開頭字母拼在一起組成的。

數學基礎

質數：除了1和它自己不能被别的數整除，這個數就是質數。

互質：兩個正整數，除了1以外，沒有其他公因子，那麼這兩個數就是互質的。

歐拉函數：對于任意一個正整數n，如果n=p1k1p2k2…prkr，其中，p1,p2,…,pk為質數，那麼在小于n的正整數中，可以用下面的公式求解與n互質的數的個數：   

φ(n)=n(1-1/p1)(1-1/p2)…(1-1/pr)

歐拉定理：如果a和n互為質數，則aφ(n)≡1(mod n)，其中φ(n)為n的歐拉函數。

模反元素：如果兩個正整數a和n互質，那麼一定可以找到整數b，使得ab-1被n整除，或者說ab被n除的餘數是1。這時b被稱為a的模反元素。用公式表示為：ab≡1(mod n)。

算法過程

密鑰生成

1、選擇兩個不同的質數p和q；

2、計算兩者的乘積為n，将n轉換成二進制後，二進制的長度即為密鑰的長度；

3、計算n的歐拉函數φ(n)；

4、選擇整個e，其中φ(n)>e>1，且e與φ(n)互質；

5、計算e對φ(n)的模範元素d；

6、将n和e封裝成公鑰，将n和d封裝成私鑰。

加密

me=c(mod n)，其中m為需要加密的資訊，c為加密後的資訊。

解密

me=c(mod n)，其中c為解密前的資訊，m為解密後的資訊。