RSA加密原理
一、歐拉函數與歐拉定理
RSA加密算法和歐拉定理密切相關，歐拉定理又用到了歐拉函數，歐拉函數的定義如下：
對于正整數n，歐拉函數
是小于等于n的正整數中與 n 互質的數的個數。
互質指兩個整數的最大公約數為1，例如互質的有：
3、5
2、9
13、14
不互質的例如有：
2、4
256、32
999、666
明顯的，1與任何數互質，是以
大于等于1。
對于8來說，與它互質的有1、3、5、7，是以
。
對于7來說，與它互質的有1、2、3、4、5、6，是以
。
對于13來說，與它互質的有1到12，是以φ(13) = 12，不難得出n為質數的時候，
。
了解了歐拉函數
，咋們再來看歐拉定理：
對于互質的正整數p、q，則p的φ(q)次方與1同餘，模為q。
即
，因為1模q必為1，也等同于
。如果對同餘迷糊的話，
的意思就是a除以c的餘數和b除以c的餘數相等。
二、大質數乘積
RSA算法的可靠性在于大數分解質因數的困難，比如p、q均為很大的質數，僅僅知道p*q的結果，想求解p、q則特别困難。理論上的量子計算機上的Shor算法就是分解質因數的算法，如果得以實作，現有的加密體系就會失效。例如銀行、核武器等各種機密都需要重新尋找可靠的加密方式。
RSA算法首先尋找兩個大質數p與q，然後得出
。歐拉函數是積性函數，滿足
的性質，是以
。又因為n為質數的時候，
，而p、q均為質數，是以
。
三、模反元素
對于互質的正整數p、q，一定可以找到一個數d滿足
，d就叫做p對模數q的模反元素。
為何d一定存在？因為歐拉定理，
，d至少存在為
。
四、公鑰的計算
假設公鑰為
對，用于加密資訊。私鑰為
對，用于解密資訊。公鑰是所有人都知道的資訊，如果有人需要給我發送資訊，就需要用這個公鑰處理後再發送，即使第三者知道了處理後的資訊和公鑰也無法還原到加密前的資訊。
先來看公鑰是如何生成的，n為兩個質數p、q的乘積。e與
互質，且小于
。是以首先生成兩個大質數p與q，然後計算出n。因為p、q是質數，通過
不難計算出
的值，由于質數與其他數都互質，是以e最小可以是3，也有文章說實際應用一般選65537。
五、私鑰的計算
私鑰的d為，e對模數
的模反元素，即滿足
，其中e和
互質（上一節所求出的e值）。通俗的說就是e*d除以
餘數等于1，即
。
歐幾裡得算法簡稱gcd，也叫做輾轉相除法，用于計算兩個正整數的最大公約數。基本公式為
，是以可以編寫如下程式：
template <typename T>
T gcd(T a, T b)
{
return b ? gcd(b, a % b) : a;
}
而公鑰d的計算需要用到擴充歐幾裡得算法，原理基于：
對于兩個整數的最大公約數
，必然存在整數x和y滿足
。
是以可以編寫如下代碼：
template <typename T>
T exgcd(T a, T b, T& x, T& y)
{
if(!b)
{
x = 1;
y = 0;
return a;
}
T r = exgcd(b, a%b, x, y);
T t=x;
x = y;
y = t - a / b * y;
return r;
}
是以等式
可表示為 ，
，求出x的值即為d。
六、加密解密與安全性
設密文為C，明文為M，使
。則
，
。
發送方使用公鑰
使明文M變為密文C後，密文通過公有管道發送給接收方，在過程中即使其他人知道公鑰并竊取到了密文，也是無法知道明文的。因為明文隻能通過第二個公式中的密鑰的d計算得到，由于d不需要在網絡上傳輸，也就不太可能被别人知道。由于知道n，可以通過分解n得到p、q來破解。不過大數質因數分解需要特别長的時間，是以不太現實。也可以直接計算出
或者直接試出來d的值，不過一個圍棋的走法就比宇宙的原子數還多，對于幂次的數量增長是很誇張的。因為這個質數相乘的步驟很簡單，不過反過來就很難得出了，這就是非對稱加密的特點。假設利用M = C + 3，或者M = C ^ 2之類的算法加密解密，一旦破解者知道了算法原理，就不難得出 C = M - 3，C = sqrt(M) 的解密方法。而
這樣的式子就沒辦法寫成
這種能快速計算的式子，必須利用密鑰的d才能快速的計算出明文。
七、解密公式的證明
C是由加密公式得到的，不過怎麼得出
的呢？數學家們往往會通過直覺假設，然後再邏輯性的證明。如果假設與事實相當符合，就已經成功了，不過能夠邏輯上的證明才會用得心裡踏實。
一個數求模的餘數必然和它同餘，是以
，同餘具有乘方性質，又因為
是以
。由于M小于n，是以隻要
即可證明
，即等同于證明
。
當M與n互質時，代入歐拉定理得
，乘方性質得
，乘法性質得
，是以M與n互質時得證。
當M與n不互質時，因為n分解因式隻能等于p*q，是以M必須有p因子或者q因子，即M=hp，或M=hq。假設M=hq，又因為M小于n，是以p、q不能都是因子，是以M與p互質。代入歐拉定理得
，乘方性質得
，好吧，根據
和乘法性質得出
。是以
，由于其中餘數被抵消了，是以相減會是j倍的p。是以
，因為這個式子的左邊是q的整數倍，是以右邊也必須是q的整數倍，是以jp是q的整數倍，因為p與q互質，是以j必須是q的整數倍，是以令j = tq可得
，即
，是以
，這樣就證明了，同理M=hp的時候也一樣。
綜上所述就證明了
，至于利用到的歐拉定理、歐拉公式、同餘的計算性質、歐幾裡得算法等等，我就不再證明了，請站在巨人的肩膀上！
八、計算需求
首先我們需要表示一個較大的數字，程式設計語言自帶的類型最大一般隻有64位遠遠不夠。而RSA的要求是1024至更多，是以需要大數類，并且實作相關的計算，C#與JAVA都有BigInteger類，可惜是C++标準庫沒有。
其次我們需要尋找大素數，在n位置處随機選取
個數字來檢驗它是不是質數。素性檢驗先使用費馬檢驗，然後再使用Miller-Rabin測試，不過仍有極低的機率出錯。
素數分布函數
的意思是小于等于x的素數個數，之是以在n處挑選
個，是由于素數定理說明了随機選取一個整數n是質數的機率為
。素數定理：
至于公鑰的e一般直接使用65537，然後使用擴充歐幾裡得算法計算出私鑰d。加密和解密就需要的是幂模計算。由于隻有幂模運算在加密解密中使用，是以它的速度最重要。不過《算法導論》已經給出了有效的方法求
的值了。叫反複平方法，至于它的原理大概是
，我初步改寫後的代碼如下：
template <typename T>
T modular_exponentiation(T a, T b, T n)
{
T d = 1;
T k = sizeof(T) * 8 - 1;
for (T i = k; i >= 0; --i)
{
d = (d * d) % n;
if ((b & (1 << i)))
{
d = (d * a) % n;
}
}
return d;
}
用int型初步測試了下，在值比較小的時候沒有問題，稍微大一點就會有問題。
至于如何将這些算法應用到大數上，就需要更多特定的算法了。由于太過繁瑣，一兩天是肯定研究不透了，看來實踐的難度并不比理論低（學習理論，而不是發明理論，發明理論的難度更不可及了），是以我決定就此打住了，Java和C#都有大數類，不過C++标準庫沒有，是以我也不想再進一步造輪子了，知道原理即可。