最近做 secure boot 涉及到 image 的 簽名和加密谈宛，用到最重要的算法之一就是RSA算法吆录。今天就簡單聊一下RSA算法。
炸裂的RSA葛假！
RSA算法在密碼界擁有絕對的地位聊训，原因很簡單：
- 歷史悠久： RSA算法是1977年由麻省理工的Ron Rivest恢氯，Adi Shamir，Leonard Adleman 共同提出勋磕，RSA來自于三個人的姓氏首字母挂滓，歷經(jīng)三十多年經(jīng)久不衰啸胧。
- 原理簡單： 基本上密碼學都脫胎于數(shù)學纺念，RSA算法雖然難以破解，但在數(shù)學上可以算得上十分簡潔優(yōu)美烙博。它的原理十分簡單：計算兩個大素數(shù)的乘積很容易渣窜，但是將這個乘積重新分解為兩個大素數(shù)非常難。
- 有效：RSA算法雖然很有歷史夷都，原理也十分簡單囤官，卻經(jīng)住了時間的考驗蛤虐，至今沒有有效的攻擊方式，屬于ISO加密標準的一部分刑顺。
- 應(yīng)用廣泛： RSA算法是第一種既可以用于加密也可以用于簽名的算法蹲堂，簡單的說就是既可以用來保護我的信息內(nèi)容不被別人看見贝淤，又可以用來證明這個東西確實是我寫的播聪，不同場合都可以靈活使用。
所以說不管你從哪個方向入門密碼學稼虎，RSA算法都是當之無愧的經(jīng)典必學招刨。
介紹RSA算法之前，先來介紹兩組常用的概念打却。
對稱與非對稱
介紹任何一種加密算法学密，都會首先說明該算法是屬于對稱加密淘衙，還是屬于非對稱加密，RSA算法就是一種非對稱加密算法哭靖。對稱與非對稱是密碼算法中的一種分類方式侈离，最直白的解釋就是對稱加密算法的密鑰只有一個，這個密鑰必須得到很好的保護铺坞，不能泄露洲胖；而非對稱加密算法的密鑰有兩個绿映，一個叫公鑰，公開可見叉弦，用于加密淹冰，一個叫私鑰，需要保密凝颇，用于解密疹鳄。
最簡單的對稱加密的例子就是密碼本瘪弓，發(fā)送方按照密碼本先把明文翻譯成密文，接收方再對著密碼本翻譯一遍就知道內(nèi)容了袱饭。壞處就是一旦密碼本被偷虑乖，整個加密過程就沒意義了。
非對稱加密的簡單例子就是鑰匙和鎖疹味，接收方有一把鎖和一把鑰匙，把鎖給發(fā)送方诫咱，鑰匙自己留著坎缭，發(fā)送方拿鎖把東西鎖上签钩，路上誰拿走都沒用，只有接收方的鑰匙才能打開鎖拿東西哄尔。這里的鎖就是密碼學意義上的公鑰岭接，鑰匙就是密碼學意義上的私鑰鸣戴。既然RSA算法是非對稱加密算法，那么也就意味著RSA算法需要生成一公一私兩個密鑰窄锅。
對稱加密算法雖然在安全性上沒有非對稱加密算法高入偷，但是這兩種算法之間并沒有絕對的好壞之分械哟。對稱加密的效率遠高于非對稱加密，在實際應(yīng)用場景中锋爪，會根據(jù)使用環(huán)境和數(shù)據(jù)的特點將兩種算法結(jié)合使用其骄，達到安全和效率的統(tǒng)一扯旷。
加密與簽名
加密和簽名本身的概念很好理解，加密是為了防止信息被別人看到毯炮，而簽名則是為了證明信息確實為本人所發(fā)。通常來說我們發(fā)送各種數(shù)據(jù)否副，一般會有以下要求：
- 保密性：發(fā)送的內(nèi)容不會被無關(guān)的人看到备禀；
- 完整性：發(fā)送的內(nèi)容不會被無關(guān)的人篡改曲尸；
- 合法性：發(fā)送內(nèi)容的來源是合法有效的男翰。
要做到保密性蛾绎，就是對傳遞的數(shù)據(jù)進行加密租冠，使用非對稱加密算法加密的一般流程是：
- 接收數(shù)據(jù)方首先準備生成一對RSA密鑰，將公鑰發(fā)布纤泵，保留私鑰捏题；
- 發(fā)送數(shù)據(jù)方拿接收方的公鑰對數(shù)據(jù)加密公荧，然后發(fā)給接收方；
- 接收方拿自己的私鑰進行解密稚矿，查看數(shù)據(jù)內(nèi)容晤揣。
而簽名則可以用來驗證數(shù)據(jù)的合法性和完整性昧识。以軟件安裝升級包為例跪楞，采用非對稱加密算法做校驗的簡化流程是：
- 軟件發(fā)布方準備好package，首先計算package的 hash甸祭，將 hash 和 package 一起用軟件發(fā)布方的私鑰簽名池户，發(fā)布加密后的 package 和發(fā)布方的公鑰；
- 用戶接收到發(fā)布方的更新后赊抖，首先拿發(fā)布方的公鑰對 package 進行解密氛雪，如果成功解密證明該 package 確實來自合法的發(fā)布方，然后對 package 也進行一次 hash 計算报亩，與發(fā)布方的 hash 做對比捆昏，驗證 package 是否被篡改毙沾。
簡而言之骗卜，公鑰加密私鑰解密的過程稱之為加密解密，私鑰加密公鑰解密的過程稱之為簽名驗證左胞。而在一套方案中同時考慮保密性寇仓，完整性和合法性，就需要設(shè)計更為復(fù)雜的簽密方案烤宙，對RSA算法來說遍烦，一般就需要兩個密鑰對共同完成了。
一個思考：如果 hacker 劫持發(fā)布方的 package 和 公鑰躺枕，解密并修改了 packet 的內(nèi)容植入病毒或者木馬服猪，然后用自己的私鑰加密數(shù)據(jù)，發(fā)布自己的公鑰和 packet 給用戶拐云，用戶要如何才能識別呢罢猪？
其實這就是所謂的中間人攻擊，也就是數(shù)字證書的存在意義了叉瘩，簡單說就是用數(shù)字證書證明發(fā)布方公鑰的有效性膳帕，而能夠頒布數(shù)字證書的通常就是官方認可的證書授權(quán)中心攒磨，簡稱CA機構(gòu)，類似于能夠頒發(fā)身份證的公安機關(guān)。
可見加密和簽名本身的概念雖然并不復(fù)雜演痒，但為了抵抗各類攻擊設(shè)計出的安全策略實在可以寫出厚厚一本書惦蚊。
公鑰和私鑰的區(qū)別
在簽名和加密的過程中，一會使用公鑰加密數(shù)據(jù)葛圃，一會使用私鑰加密數(shù)據(jù)库正，那么公鑰和私鑰的區(qū)別到底是什么呢。
事實上喷楣，從數(shù)學的角度來說罕伯，公鑰和私鑰的地位是同等的绽榛，用其中任意一個加密，另外一個都可以拿來解密。公私之分，完全取決于選擇公開哪一個围详。雖然在數(shù)學上兩者沒有嚴格的區(qū)分，但是在實際應(yīng)用中，選擇公開哪一個卻并不是隨便選的。在生成密鑰的過程中街立，我們既要保證密鑰的長度，也要考慮到計算的復(fù)雜性，所以我們一般會選擇長度較短的作為公鑰，長度較長的保留為私鑰众雷。在RSA算法生成密鑰的過程中编兄，選取65537作為公鑰幾乎是一個慣例，所以說公鑰和私鑰并不是隨便選一個公開或保留就可以的。
RSA算法邏輯
很多安全相關(guān)的開源庫，例如openssl眯杏，boringssl，libtomcrypt 等等卸伞，都有完善的 RSA算法實現(xiàn)遂黍，一般來說都分為密鑰的生成雾家，加密绍豁，解密三個部分霜浴，下面簡單介紹一下這三個部分的數(shù)學邏輯，這樣能更好的理解代碼。
密鑰的生成
參考代碼：https://github.com/libtom/libtomcrypt/blob/develop/src/pk/rsa/rsa_make_key.c
這部分代碼其實非常好懂挠说，首先通過偽隨機數(shù)計算出兩個大素數(shù) p 和 q，計算 p 和 q 的乘積 N，然后計算 （p-1）和 （q-1）的最小公倍數(shù) L阅签。在 1 和 L 之間選一個數(shù) E（約定俗成 E = 65537）精算，（N, E）就是公鑰。
最后計算私鑰 D杜跷，D 滿足如下條件：E＊D mod L ＝ 1，那么（N赤嚼，D）就是私鑰了。
用公鑰加密
參考代碼：https://github.com/libtom/libtomcrypt/blob/develop/src/pk/rsa/rsa_encrypt_key.c
加密過程只需要計算以下公式即可：
用私鑰解密
參考代碼：https://github.com/libtom/libtomcrypt/blob/develop/src/pk/rsa/rsa_decrypt_key.c
解密過程只需要計算以下公式即可：
以上可以看出RSA算法真的是具有簡潔的數(shù)學美感。
只是軟件實現(xiàn)上，RSA算法的運算代價很高肴熏，在長密鑰大數(shù)據(jù)的情況下，計算真的是非常的緩慢 ：）
以上就是RSA算法的簡單介紹了治筒，其實也真的蠻簡單的~
