RSA是第一個比較完善的公開密鑰算法，它既能用于加密，也能用于數字簽名。RSA以它的三個發明者
Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名，這個算法經受住了多年深入的密碼分析，
雖然密碼分析者既不能證明也不能否定RSA的安全性，但這恰恰說明該算法有一定的可信性，目前它已
經成為最流行的公開密鑰算法。
RSA密碼生成規則：
1、随意選擇兩個大的質數p和q，p不等于q，計算N=pq。
2、根據歐拉函數，不大于N且與N互質的整數個數為(p-1)(q-1)
3、選擇一個整數e與(p-1)(q-1)互質，并且e小于(p-1)(q-1)
4、用以下這個公式計算d：d× e ≡ 1 (mod (p-1)(q-1))，即d和e的乘積除（p-1）與（q-1）的乘積，餘數為1。
5、将p和q的記錄銷毀。
6、N,e,d組合構成公鑰和私鑰，(e,N)是公鑰，(d,N)是私鑰。
7、加密得到密文c：
8、解密得到明文n：
RSA的安全基于大數分解的難度。其公鑰和私鑰是一對大素數（100到200位十進制數或更大）的函數。
從一個公鑰和密文恢複出明文的難度，等價于分解兩個大素數之積（這是公認的數學難題）。當密碼位數足夠大時，以現有計算機的計算能力無法破解。
這裡涉及到質數，如何求質數，質數的定義是隻能被自身和1整除的數。根據定義，很容易判斷一個自然數是否為質數，python代碼如下：
def is_prime_number(x):
'''
判斷是否質數
'''
result = True
for i in xrange(x):
if i < 2:
continue
if x % i == 0:
result = False
break
return result
算法第三步中涉及到一個數學定義互質，互質數的定義是公約數隻有1的兩個數，叫做互質數。如何求公約數呢？這裡使用輾轉相除法求解。輾轉相除法又稱歐幾裡得算法，首次出現在歐幾裡得的《幾何原本》，中國最早出現于東漢時的《九章算術》。
輾轉相除法的原理是：兩個整數的最大公約數等于其中較小的數和兩數的相除餘數的最大公約數。
基于此原理，代碼實作如下：
def greatest_common_divisor(x,y):
'''
求x和y的最大公因數
'''
if x < y:
temp = y
y = x
x = temp
while x % y != 0:
temp = y
y = x % y
x = temp
return y
那麼開始構造自己的RSA吧，使用is_prime_number得到兩個質數。這裡讓p=59,q=601，那麼N=p*q=35459，T = (p-1)*(q-1) = 34800。
接下來通過第三四步求出d和e，代碼如下：
if __name__ == '__main__':
e_list = []
for i in xrange(34800):
if i < 2:
continue
if greatest_common_divisor(i,34800) == 1:
e_list.append(i)
for e in e_list:
for d in xrange(34800):
if d < 2:
continue
if (e*d) % 34800 == 1:
print e,d
從密碼對中選取一對即可，這裡選取d=163,e=427。那麼 公鑰是 (35459,163)，密鑰是(35459,427)
假如明文c=10，加密後為n=26352。
随着計算機計算能力的提升，RSA的要求越來越高，1997年後開發的系統，使用者應使用1024位密鑰，證書認證機構應用2048位或以上。
吐槽一下編輯器太挫了，一行文字太長還自動隐藏了。。