簡述RSA加密算法
cc 之前的文章中我們聊了聊AES加密算法，今天我們來聊聊另一種歷史悠久且應用廣泛的算法——RSA。
它是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）共同提出的一種加密算法，RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的。
RSA算法是一種非對稱加密算法，這一算法主要依靠分解大素數(shù)的復雜性來實現(xiàn)其安全性，由于大素數(shù)之積難被分解，因此該密碼就難被破解。
幾十年來，RSA算法經(jīng)歷了各種攻擊的挑戰(zhàn)，根據(jù)相關顯示，目前被破解的最長RSA密鑰是768個二進制位。也就是說，長度超過768位的密鑰，還未被破解，至少目前尚未有人公開宣布。
RSA原理
RSA基于一個十分簡單的數(shù)論事實：將兩個大素數(shù)相乘十分容易，但想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰，即公鑰，而兩個大素數(shù)組合成私鑰。公鑰是可發(fā)布的供任何人使用，私鑰則為自己所有，供解密之用。
RSA公私鑰生成流程
- 隨機找兩個質(zhì)數(shù)P和Q，P與Q越大，越安全。（例如：61和53）
- 計算p和q的乘積n。（n=61×53=3233，n的長度就是密鑰長度。3233寫成二進制是110010100001，一共有12位，所以這個密鑰就是12位。）
- 計算 n 的歐拉函數(shù)φ(n)。（根據(jù)公式φ(n)=(p-1)(q-1)算出φ(3233)等于60×52，即3120）
- 隨機選擇一個整數(shù)e，條件是1<e<φ(n)，且e與φ(n) 互質(zhì)。（條件是1<e<φ(n)，且e與φ(n) 互質(zhì)。1到3120之間，隨機選擇了17。）
- 有一個整數(shù)d，可以使得ed 除以φ(n) 的余數(shù)為 1。（ed ≡ 1 (mod φ(n))，即17*2753 mode 3120=1）
- 將n和e封裝成公鑰，n和d封裝成私鑰。（n=3233，e=17，d=2753，所以公鑰就是：3233,17，私鑰就是：3233, 2753。）
RSA加密
首先對明文進行比特串分組，使得每個分組對應的十進制數(shù)小于n，然后依次對每個分組m做一次加密，所有分組的密文構(gòu)成的序列就是原始消息的加密結(jié)果，即m滿足0<=m<n，則加密算法為：c=m^e mod n; c為密文，且0<=c<n。
RSA解密
對于密文0<=c<n，解密算法為：m=c^d mod n。
RSA加密算法的優(yōu)缺點
優(yōu)點：RSA算法是國際標準算法，屬于主流算法之一，應用廣泛，兼容性比較廣，能夠適用于各種不同的系統(tǒng)之中，不容易出現(xiàn)限制問題。
缺點：RSA算法加密長度為2048位，對于服務器的消耗是比較大的，計算速度也比較慢，效率偏低，一般只適用于處理小量數(shù)據(jù)。
盡管RSA加密算法運行消耗大，效率低，但是由于其優(yōu)秀兼容性和安全性，它依舊是使用最廣泛的非對稱加密算法。
免責聲明：素材源于網(wǎng)絡，如有侵權(quán)，請聯(lián)系刪稿。
