前言：之前在做密碼學題的時候了解了一下RSA，但總感覺那時總結的過少，而且也了解的不到位，這次就再來詳細的了解一下，并通過做題來鞏固一下。
一、對稱加密與非對稱加密
對稱加密：
加密和解密用的是同一密鑰，也是最簡單、最快速的加密方式，通常使用的密匙相對較小，容易被破解，如果密鑰過大，安全性确實可以得到保證，但同樣加密和解密的效率将會很低。
因為雙方都需要密鑰進行加密解密，如果有一方的密鑰洩露出去，整個安全性将不複存在，是以這也是對稱加密的缺點。
非對稱加密：
相較于對稱加密，非對稱加密使用兩個密匙，即公開密鑰和私鑰密鑰。
非對稱加密很有趣，公鑰是任何人都可以請求得到的，但私鑰隻有一個人持有，而且用公鑰加密的密文隻能通過私鑰來解開，解密者無需像對稱加密一樣接收加密者的密鑰，而是自己儲存一個密鑰，這樣就不在網上傳送密匙，不會被攔截，會更加安全，但是相對于對稱加密，非對稱加密加密和解密的效率會低一些
下面就來學習屬于非對稱加密中的RSA算法
RSA概述：
1977年，三位數學家Rivest、Shamir 和 Adleman 設計出RSA算法，可以實作非對稱加密。而在此之前，使用的都是對稱加密。
RSA算法涉及的數學知識
了解RSA之前，需要了解一些數學知識
一、互質關系
兩個正整數，除1以外，沒有其他公因子，那麼這兩個數就是互質關系。
例如：30與7就是互質關系，但是30不是質數，這就是說明不是質數也能構成互質關系
由互質關系能得出以下結論：
- 任意兩個質數構成互質關系，比如7和61。
- 一個數是質數，另一個數隻要不是前者的倍數，兩者就構成互質關系，比如3和10。
- 如果兩個數之中，較大的那個數是質數，則兩者構成互質關系，比如97和57。
- 1和任意一個自然數是都是互質關系，比如1和99。
- p是大于1的整數，則p和p-1構成互質關系，比如57和56。
- p是大于1的奇數，則p和p-2構成互質關系，比如17和15。
二、歐拉函數
在數論，對正整數n，歐拉函數是小于n的正整數中與n互質的數的數目，以φ(n)表示
其實歐拉函數就是用來計算這樣一個問題
任意給定正整數n，在小于等于n的正整數之中，有多少個與n構成互質關系？
舉個列子：
在
1—10
中，與10互質的有
1、3、7、9
，即
φ(n)=4
通過歐拉函數又衍生出幾種情況：
第一種情況： 如果n=1，則 φ(1) = 1
。因為1與任何數（包括自身）都構成互質關系。
第二種情況： 如果n是質數，則
。因為質數與小于它的每一個數，都構成互質關系。比如7與1、2、3、4、5、6都構成互質關系。φ(n)=n-1
其中對RSA最重要的一種情況就是：
如果n可以分解成兩個互質的整數之積
n = p1 × p2
則
φ(n) = φ(p1p2) = φ(p1)φ(p2)
通過這個公式可以看出積的歐拉函數等于各個因子的歐拉函數之積
n=21
n=3*7
φ(n) = φ(p1p2) = φ(3)φ(7)=2*6=12
三、歐拉定理
歐拉定理表明，若,n
為正整數，且a
，則以下公式成立：n,a互質
換句話就是a的φ(n)次方被n除的餘數為1或者是a的φ(n)次方減去1，可以被n整除。
例如：2和5互質，φ(5)=4，則2的4次方(16)減1,15恰好被n(5)整除
歐拉定理還有一個特殊情況：
如果與正整數a
互質，因為質數p的φ§等于p-1，則歐拉定理可以寫成：質數p
四、模反元素
如果兩個正整數a和n互質，那麼一定可以找到整數b，使得 ab-1 被n整除，或者說ab被n除的餘數是1。這時，b就叫做a的“模反元素”。
a=3,n=4
(3*b-1)%4=0
故b=7或b=3
顯然模反元素不止一個，即如果b是a的模反元素，則 b+kn 都是a的模反元素（k為正整數）
可以看出，a的 φ(n)-1 次方，就是a對模數n的模反元素
五、模運算
讓m去被n整除，隻取所得的餘數作為結果，就叫做模運算。
舉個例子：
10 mod 4=2、8 mod 3=2
六、同餘
給定一個正整數m，如果兩個整數a和b滿足a-b能被m整除，即(a-b) mod m=0，
那麼就稱整數a與b對模m同餘，記作a≡b (mod m)，同時可成立a mod m=b
而且同餘與模運算是不同的
a≡b (mod m)僅可推出b=a mod m
七、歐幾裡德算法
歐幾裡德算法是用來求兩個正整數最大公約數的算法
計算公式gcd(a,b) = gcd(b,a mod b)
計算方法：
用較大數除以較小數，再用出現的餘數（第一餘數）去除除數，再用出現的餘數（第二餘數）去除第一餘數，如此反複，直到最後餘數是0為止
計算流程圖為：
需要的數學知識已經了解完了，接下來就來學習RSA
RSA算法
（一）、生成密鑰過程：
一、随機選擇兩個不相等的質數p和q
二、計算p和q的乘積n
三、計算n的歐拉函數φ(n)
四、随機選擇一個整數e，條件是1< e < φ(n)，且e與φ(n) 互質
五、計算e對于φ(n)的模反元素d
六、将n和e封裝成公鑰，n和d封裝成私鑰
下面就通過一個列子來執行一遍
一、選取兩個不相等的質數p=11 q=13
二、n=p*q=143
三、φ(n)=(p-1)(q-1)=10*12=120
四、從1<e<60, 随機選取一個e,這裡選取7
五、根據歐拉定理 e*d ≡ 1 (mod φ(n))，該公式又可轉化為e*d - 1 = kφ(n)
是以7*d+120*k=1,這個方程可以由擴充歐幾裡得算法（輾轉相除法）來得出結果：
六、120 = 7 * 17 + 1
17 = 17 * 1
//餘數放前面
1 = 120 * 1 + 7 * (-17)
1 = 120 * 1 + 7 *(-17)
故d = -17 k = 1
在RSA中d必須是正整數，是以将它翻轉
d=120 + （-17）=103
故公鑰為（n,e）=(143,7)
私鑰為（n,d）=(143,103)
（二）、加密解密過程
求出公鑰和私鑰，就可以對資訊進行加密和解密
一、通過公鑰進行加密（n,e）
設明文為M，密文為C，則加密公式為：
假設明文為13，則
M^e ≡ c (mod n)
13^7 = 117 (mod 143)
二、通過私鑰進行解密（n,d）
密文為C，明文為M，則解密公式為：
C^d ≡ M (mod n)
117^103 = 13 (mod 143)
換句通俗的話說
C的d次方除以n的餘數為M
(三)、RSA安全性
在已知n和e的情況下即（公鑰），能否推導出d？
（1）ed≡1 (mod φ(n))。隻有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。隻有知道p和q，才能算出φ(n)。
（3）n=pq。隻有将n因數分解，才能算出p和q。
但現實生活中，不可能跟我們舉例子一樣那麼小，而且大整數的因數分解，是一件非常困難的事情，例如：
12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413
沒法對這個整數進行因數分解，過于大了，而且目前破解的隻有暴力破解，是以RSA才号稱是地球上最安全的算法。
總結：這次總結更加詳細的了解了RSA的原理以及涉及的數學原理，接下來就通過做題來進行鞏固。
參考部落格：
RSA算法基礎詳解
RSA算法原理（二）