前言
RSA(算法的名字以發明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman), 是第一個既能用于資料加密也能用于數字簽名的算法，易于了解和操作，應用廣泛。RSA的安全性依賴于大整數因子分解。目前來看，攻擊RSA算法最有效的方法便是分解模n。一般認為RSA需要1024位或更長的密鑰才有安全保障。
一、RSA算法簡介
RSA公開密鑰密碼體制的原理是：根據數論，尋求兩個大素數比較簡單，而将它們的乘積進行因式分解卻極其困難，是以可以将乘積公開作為加密密鑰。
RSA絕對是當今應用最為廣泛的加密算法，像數字簽名，數字證書，SSH，HTTPS加密連接配接全部都是他的典型應用。
二、數學基礎
1.互質
互質又稱為互素，如果兩個或兩個以上的整數的最大公約數是 1，則稱它們為互質。
2.歐拉函數
歐拉函數指的是對正整數n，求小于或等于n的正整數中與n互質的數的數目，記作φ(n)。
3.歐拉定理
歐拉定理也稱費馬-歐拉定理，指的是：如果兩個正整數m和n互質，則n的歐拉函數 φ(n) 可以讓下面的等式成立。
三、RSA 算法原理
1.解密解密選擇單向函數标準
對于解密和解密來講，實際上就是要找一個單向函數，函數的正向運算要很容易，但是函數的逆向運算要很難。
對于RSA這種情況，把公玥和資訊轉遞給函數進行運算得到密文的過程要很容易，但是反過來，如果有人看到了密文，知道了密鑰，要想得到原文這個過程要非常困難。
而且這個函數還要有一個特點，如果擁有特定的提示資訊，那麼逆向操作也會由很難變得很容易，也就是說，如果知道私鑰，那麼解密過程也會變得很容易。
2.RSA單向函數的選擇
RSA加密算法選擇的就是正向運算很容易，但是逆向運算很難的模函數作為單向函數。
RSA構造的加密函數是這樣的：
首先将資訊轉化成整數（計算機中，資訊都可以轉化成二進制的形式，自然轉化為整數也不難），根據RSA的計算規則，要選取一個整數e，對整數m進行e次方運算，然後選取一個整數N，對m的e次方進行求模運算，這樣就得到了密文c。
舉個很簡單的例子，大家先感受以下：
熟悉了RSA算法的加密規則之後，我們就可以把（e，N）公布作為算法的公鑰；根據模函數的運算規則，如果知道密文c，并且知道公鑰（e，N），求原文m是一個很難的問題。但是根據RSA的運算規則，隻要恰當選取了e和N，就一定會存在一個d，使得下面這個式子成立：
我們就可以把（d，N）作為私玥，進行解密。
到這裡，問題就很清晰了，第一個問題就是公玥e和N的選取，第二個問題就是知道公玥之後，如何快速的求出私鑰d。
3.RSA原了解析
根據上面介紹，我們可以得到RSA的加解密公式：
我們把它寫到一起：
然後對數學原理中介紹的歐拉定理公式做一下變形：
一眼便知，這裡的指數是一樣的，很容易便可以得到私鑰d的運算公式：
這樣就可以通過選取k、n、e來計算私玥d，這個式子看起來很簡單，但是真正困難的地方是φ(n)（前面數學基礎章節有介紹）的計算，計算φ(n)的唯一方法就是對n進行質因數分解，而大數的質因分解本身就是一件非常困難的事情。
但是如果n本身是一個質數的話，情況就大不相同了，我們通過兩個例子：
φ(7)很明顯等于6。
φ(13)很明顯等于12。
于是得到一條規律：如果p本身就是一個質數的話
φ§=p-1
然後歐拉函數還有一個特性，φ(pq)可以拆分為φ§和φ(q)單獨的乘積。
看到這裡，一個很明顯的靈感湧上心頭，那就是我們完全可以選擇兩個較大的質數p和q，讓n=pq，這樣就可以得到一個很大的數字n，如果不知道這兩個質數p和q的話，對n進行質因數分解是非常困難的，但是如果知道p和q的話，使用上面的公式：
φ(n) = φ(p*q) = (p-1)(q-1)可以輕松求得φ(n)。
得到φ(n) 之後，恰當選取e和k，便可對d求解。
到這裡，核心的問題就都解釋通了，最後我們總結以下算法流程：
總結
公鑰加密就是利用資訊不對等，讓加密者可以快速的構造出φ(n)，而其他人卻無法在有限的時間内去破解它。
由于公鑰加密的計算量大，速度慢，通常會與對稱加密算法一同使用。公鑰加密算法常被用做最初連接配接的建立，而真正資料傳輸的過程交由對稱加密算法來處理。