今天我們來學習下非對稱加密算法經典算法之一——RSA算法。
如果我們把密碼學分為兩個時代：經典密碼學和現代密碼學，而兩個時代的轉折點恰好是1977年，也就是RSA算法被首次提出的那一年。
RSA算法和DH算法（Diffie-Hellman密鑰交換協議/算法）具有劃時代的意義，他們第一次使基於數論的安全通訊密碼學方案成為可行的；
同時也是第一次使通訊雙方在不需要共享秘鑰的情況下能夠安全通訊。
過去密碼學需要雙方在世界範圍內傳輸對應的密碼本來進行通訊，以防有人竊聽到密鑰，而現在雙方都能夠進行已被證明安全的通訊。
RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。
當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。
之前我們講過，非對稱加密技術的核心是公私鑰分開，即用來加解密數據的密鑰分為公鑰和私鑰兩部分，公鑰可以被公開，私鑰則保持私有。
這種加解密方式被稱為公鑰密碼學系統。
公鑰密碼學的核心是單向函數。
單向函數怎麼解？
先舉例，對於函數f，已知x，計算f（x）很容易，但如果我們已知f（x），計算x變得很難。
向一個方向的計算很容易，但反方向計算很難的函數就叫做單向函數。
現在我們把它換成區塊鏈語言，我們用私鑰生成公鑰很容易，但從公鑰反推私鑰很難，這也是非對稱加密算法的基礎。
RSA算法的原理
為什麼公鑰反推私鑰很難？這就涉及了RSA算法的核心，基於一個簡單的數論事實：
將兩個大質數相乘十分容易，但反過來將它們的乘積進行因式分解則很難，因此通常把乘積作為公鑰。
現在我們明白了，因為我們把公鑰反推私鑰等價於因式分解。
那麼因式分解有多難呢？
我們來感受下，如果乘積是6的話，相信大家都能將它因式分解，2×3，這很容易；
我們換個數字3551，它怎麼因式分解，我相信需要大家算一算了，結果是53、67，有人算出來了嗎；
再換一個有挑戰的，2147483647 ，不用軟件的話我們都很難判斷它到底能不能因式分解（PS：2147483647是質數，不能因式分解）。
這只是一個10位數，如果我們真的面對一個幾十位數的因式分解，好像就只能呵呵了。
道理我們都懂了，我們來看看算法是如何實現。
筆者曾經給我們Astar小高講過RSA的加解密過程。結果就是下圖
我想，對於大部分讀者來說，如果只是想了解RSA的話，上面的內容就足矣了，如果真的對密碼學感興趣的話，可以參閱密碼學的書籍作為參考。下面我們開始。
RSA算法實現過程
1. 公鑰n、e和私鑰d的生成：
a）隨機選取兩個質數p和q;
b）定義n=pq（p乘q）;
c）定義r = φ(N)= φ(p)φ(q) = (p-1)(q-1);
d）定義e是與r互質的數，實際中通常選擇65537；
e）定義d為e關於r的模反元素，ed=1（mod r）（ed的乘積減1可以被r整除）
2. 加密過程：
m為加密前的信息，c為加密後生成的信息
(m^e) mod n=c（m的e次冪除以n的餘數為c）
3. 解密過程：
(c^d) mod n=m（c的d次冪除以n的餘數為m）
這就是RSA的加解密過程，如果Astar小高想破解加密信息c，他現在有這個幾個數：
公鑰n、e、加密信息c，沒有密碼，必須想辦法得到私鑰d，所以他必須知道p和q，那麼他需要對n作質因子分解，然後他需要面臨的是一個世界性難題。
如果說上述過程，看的比較吃力的話，那我們舉個例子讓大家實際體會下。
1. 設p=7，q=13，n=pq=91，r = φ(N) = φ(p)φ(q) = (p-1)(q-1)=72；設e=5，解方程ed=1（mod 72）得d=29
2. 現在我們加密一段信息，“Astar”，為了用數字表示這段信息，我們把字母轉化成信息，拉丁字母表通常用UTF-8來表示。每個字母都對應一個數字。
在這個編碼下，astar是65,83,84,65,82，每個數字都小於n=91（因為在加解密的時候，都要算除以91的餘數，所以選取比91小的數據會方便我們的計算）。開始我們的計算。
3. 首先來到加密過程
根據公式(m^e) mod n=c，已知原信息a為65，則加密信息c=65（真的是巧合）。
對每個字母重複這個過程，我們得到加密信息Astar變成：65,83,28,65,10
4. 再來看揭秘過程
根據公式(c^d) mod n=m，這裡我們看到d作為私鑰為29，所以要計算29次冪之高，可見在解密的時候，運算要高於加密時的運算。
這裡不在做過多的計算，只是想通過一個簡單的例子讓大家更好的理解加解密過程。
RSA真的安全嗎
RSA算法之所以安全又強大，是建立在公認數學難題的基礎上，也就是因式分解。
然而隨著時代的發展，因式分解已經並非最難解的問題了，像兩次篩法（Quadratic Sieve）和普通數域篩選法（General Number Field Sieve）這類專門加工過的算法在解決素數因子分解的問題上是比較成功的。
可以說，大數字因式分解的難度正在隨著數字的變大而縮小，隨著解碼資源的增加，密鑰的長度又不得不變得更長。
所以為了信息的安全，我們不得不消耗額外的計算資源。這將帶來兩個問題：1.RSA算法的安全性有多高；2是否有代替算法。
第一個問題，BlackHat曾經寫了一篇專欄《The Matasano Crypto Challenges - 64 Dirty Little SecretsCryptographers Don't Want You To Know》解析RSA的相關問題。
視頻原始YouTube鏈接：
https://www.youtube.com/watch?v=iZa_XKpj9X4；
總結了下，RSA算法並不是絕對的安全，在一些特定的情況下：
a）不要對不同的用戶重複使用相同的n（pq乘積），否則這兩個用戶可以分別互相算出對方的私鑰；
b）RSA中，e和d不要選的特別小；
c）兩個質數（p、q）如果選的很近，則n會比較好分解；
總結，RSA已經40歲出頭了，在這個計算能力飛速發展的今天，我們在使用RSA算法的時候，儘量選擇傑出的開發人員，避免踩到上面的那些坑，以免造成經濟損失。
第二個問題，有沒有一個比因式分解更難的算法，當然是有。
1985年，一種基於橢圓曲線的加密算法被提出來，如果說今天這節課有點遠離區塊鏈技術的話，那麼橢圓曲線算法和區塊鏈頗有淵源，它被應用在比特幣和以太坊的非對稱加密算法中。
下一節內容，我們將探究橢圓曲線的奧秘。
閱讀更多 AA加速器 的文章
