前言
本文的RSA例子代碼更新在我的github上岂却。
RSA算法是最重要算法之一，它是計算機通信安全的基石弦追，保證了加密數(shù)據(jù)不會被破解岳链。本文主要參考了參考資料中的文章，介紹一下RSA算法的內(nèi)容骗卜，自己寫一遍宠页，算是學習了。
歷史
1.對稱加密算法
在1976年以前寇仓，所有的加密方法都是同一種模式"對稱加密算法"（Symmetric-key algorithm）:
- （1）甲方選擇某一種加密規(guī)則举户，對信息進行加密；
- （2）乙方使用同一種規(guī)則遍烦，對信息進行解密俭嘁。
這種加密模式有一個最大弱點：甲方必須把加密規(guī)則告訴乙方，否則無法解密服猪。
2.非對稱加密算法
1976年供填，兩位美國計算機學家Whitfield Diffie 和 Martin Hellman拐云，提出了一種嶄新構思，可以在不直接傳遞密鑰的情況下近她，完成解密叉瘩。這被稱為"Diffie-Hellman密鑰交換算法"。
- （1）甲要傳密信給乙粘捎，乙先根據(jù)某種算法得出本次與甲通信的公鑰與私鑰
- （2）乙將公鑰傳給甲（公鑰可以讓任何人知道薇缅，即使泄露也沒有任何關系）
- （3）甲使用乙傳給的公鑰加密要發(fā)送的信息原文m，發(fā)送給乙密文c
- （4）乙使用自己的私鑰解密密文c攒磨，得到信息原文m
如果公鑰加密的信息只有私鑰解得開泳桦，那么只要私鑰不泄漏，通信就是安全的娩缰。
3.RSA算法的出現(xiàn)
1977年灸撰，三位數(shù)學家Rivest、Shamir 和 Adleman 設計了一種算法拼坎，可以實現(xiàn)非對稱加密浮毯。這種算法用他們?nèi)齻€人的名字命名，叫做RSA算法泰鸡。
這種算法非常可靠亲轨，密鑰越長，它就越難破解鸟顺。根據(jù)已經(jīng)披露的文獻，目前被破解的最長RSA密鑰是768個二進制位器虾。也就是說讯嫂，長度超過768位的密鑰，還無法破解（至少沒人公開宣布）兆沙。因此可以認為欧芽，1024位的RSA密鑰基本安全，2048位的密鑰極其安全葛圃。
數(shù)論知識
1.質(zhì)數(shù)
一個大于1的自然數(shù)千扔，除了1和它本身外，不能被其他自然數(shù)整除（除0以外）的數(shù)稱之為質(zhì)數(shù)（素數(shù)）库正；否則稱為合數(shù)曲楚。
2.互質(zhì)數(shù)
互質(zhì)，又稱互素产园。若N個整數(shù)的最大公因子是1哄陶，則稱這N個整數(shù)互質(zhì)背零。
3.指數(shù)運算
指數(shù)運算又稱乘方計算荆隘，計算結果稱為冪趟大。nm
指將n自乘m次鹤树。把nm
看作乘方的結果，叫做”n的m次冪”或”n的m次方”逊朽。其中罕伯，n稱為“底數(shù)”，m稱為“指數(shù)**”叽讳。
4.模運算
讓m去被n整除追他，只取所得的余數(shù)作為結果，就叫做模運算绽榛。
例如湿酸，10 mod 3 = 1 、26 mod 6 = 2 灭美、28 mod 2 = 0
5.同余
給定一個正整數(shù)m推溃，如果兩個整數(shù)a和b滿足a-b能被m整除，即(a-b)modm=0届腐，那么就稱整數(shù)a與b對模m同余铁坎，記作a≡b(modm)，同時可成立amodm=b犁苏。
6.歐拉函數(shù)
任意給定正整數(shù)n硬萍，計算在小于等于n的正整數(shù)之中，有多少個與n構成互質(zhì)關系围详？計算這個值的方法就叫做歐拉函數(shù)朴乖，以φ(n)表示.
例如，在1到8之中助赞，與8形成互質(zhì)關系的是1买羞、3、5雹食、7畜普，所以φ(n)=4
在RSA算法中，我們需要明白歐拉函數(shù)對以下定理成立
如果n可以分解成兩個互質(zhì)的整數(shù)之積群叶，即n=p×q吃挑，則有：φ(n)=φ(pq)=φ(p)φ(q);
根據(jù)“大數(shù)是質(zhì)數(shù)的兩個數(shù)一定是互質(zhì)數(shù)”可以知道：一個數(shù)如果是質(zhì)數(shù)，則小于它的所有正整數(shù)與它都是互質(zhì)數(shù)街立；所以如果一個數(shù)p是質(zhì)數(shù)舶衬，則有：φ(p)=p-1
由上易得，若我們知道一個數(shù)n可以分解為兩個質(zhì)數(shù)p和q的乘積赎离，則有
φ(n)=(p-1)(q-1)
7.歐拉定理
如果兩個正整數(shù)a和n互質(zhì)约炎，則n的歐拉函數(shù)φ(n)可以讓下面的等式成立：
比如，3和7互質(zhì)，而7的歐拉函數(shù)φ(7)等于6圾浅，所以3的6次方（729）減去1掠手，可以被7整除（728/7=104）。
8.模反元素
意即狸捕，如果兩個正整數(shù)a和n互質(zhì)喷鸽，那么一定可以找到整數(shù)b
使得ab-1被n整除，或者說ab被n除的余數(shù)是1
比如灸拍，3和11互質(zhì)做祝，那么3的模反元素就是4，因為 (3 × 4)-1 可以被11整除鸡岗。顯然混槐，模反元素不止一個， 4加減11的整數(shù)倍都是3的模反元素 {...,-18,-7,4,15,26,...}轩性，即如果b是a的模反元素声登，則 b+kn 都是a的模反元素。
算法基礎
1.實例
先通過一個實例來理解RSA算法的過程：
甲要發(fā)給乙一個加密內(nèi)容：m=65
乙發(fā)送甲公鑰：(n,e)=(3233,17)
甲根據(jù)公式
加密出c
甲將使用公鑰加密的密文c=2790發(fā)送給乙
乙收到c=2790的密文后使用私鑰(n,d)=(3233,2753)
根據(jù)公式
解密出m
從始至終揣苏，用來解密的私鑰(n,d)=(3233,2753)一直都在乙處悯嗓，從未泄露。乙給甲的僅僅是用來加密的公鑰(3233,17)卸察，這個公鑰并不能用來解密脯厨，即使被他人截獲，也沒有任何泄密的風險坑质。
2.計算公私鑰
- 1.隨機選擇兩個不相等的質(zhì)數(shù)p和q（乙選擇了61和53）
- 2.計算p和q的乘積n=p×q=61×53=3233
- 3.根據(jù)本文“歐拉函數(shù)”介紹過的公式
φ(n)=(p-1)(q-1)
代入計算n的歐拉函數(shù)值
φ(3233)=(61-1)×(53-1)=60×52=3120 - 4.隨機選擇一個整數(shù)e合武，條件是1<e<φ(n)，且e與φ(n)互質(zhì)
乙就在1到3120之間涡扼，隨機選擇了17 - 5.因為e與φ(n)互質(zhì)眯杏，根據(jù)求模反元素的公式計算e，對于e的模反元素d有：
ed≡1(modφ(n))
這個式子等價于
(ed-1)/φ(n)=k（k為任意正整數(shù)）
即
ed-kφ(n)=1壳澳，
代入數(shù)據(jù)得：17d-3120k=1
實質(zhì)上就是對以上這個二元一次方程求解得到一組解為：(d,k)=(2753,-15) - 6.將n和e封裝成公鑰，n和d封裝成私鑰
n=3233茫经，e=17巷波，d=2753
所以公鑰就是(3233,17)，私鑰就是(3233,2753)
至此卸伞，整個rsa公私鑰的算法就清楚了
3.推導
整個過程中抹镊，讓人困擾的可能是
與
事實上式子2就是從式子1推導出來，具體過程可以參考RSA算法原理（二）荤傲，這邊也做一個簡單描述：
4.安全性
在上面給出的例子中垮耳，一共出現(xiàn)了6個數(shù)字：
- 隨機質(zhì)數(shù)p 61
- 隨機質(zhì)數(shù)q 53
- n=p×q 3233
- φ(n)=(p-1)(q-1) 3120
- 隨機e與φ(n)互質(zhì) 17
- e的模反元素d 2753
其中公鑰用到了(n,e)，剩下4個不知。關鍵私鑰(n,d)终佛，關鍵值是d俊嗽，不能泄露d。
那么铃彰，有無可能在已知n和e的情況下绍豁，推導出d？
- （1）ed≡1 (mod φ(n))牙捉。只有知道e和φ(n)竹揍，才能算出d。
- （2）φ(n)=(p-1)(q-1)邪铲。只有知道p和q芬位，才能算出φ(n)。
- （3）n=pq带到。只有將n因數(shù)分解昧碉，才能算出p和q。
結論：如果n可以被因數(shù)分解阴孟，d就可以算出晌纫，也就意味著私鑰被破解。
事實上永丝，RSA的安全性就是源自你沒辦法輕易的對大整數(shù)“因式分解”锹漱。人類已經(jīng)分解的最大整數(shù)（232個十進制位，768個二進制位）慕嚷。比它更大的因數(shù)分解哥牍，還沒有被報道過，因此目前被破解的最長RSA密鑰就是768位喝检。實際應用中嗅辣，RSA密鑰一般是1024位，重要場合則為2048位挠说。
算法實現(xiàn)
iOS中的實現(xiàn)與使用
iOS的 <sercurity.framework>框架中包含可以使用RSA加密與解密的方法：
//加密方法
OSStatus SecKeyEncrypt(
SecKeyRef key,
SecPadding padding,
const uint8_t *plainText,
size_t plainTextLen,
uint8_t *cipherText,
size_t *cipherTextLen)
__OSX_AVAILABLE_STARTING(__MAC_10_7, __IPHONE_2_0);
//解密方法
OSStatus SecKeyDecrypt(
SecKeyRef key, /* Private key */
SecPadding padding, /* kSecPaddingNone,
kSecPaddingPKCS1,
kSecPaddingOAEP */
const uint8_t *cipherText,
size_t cipherTextLen, /* length of cipherText */
uint8_t *plainText,
size_t *plainTextLen) /* IN/OUT */
__OSX_AVAILABLE_STARTING(__MAC_10_7, __IPHONE_2_0);
但這個framework的api只支持從標準證書文件(cer,crt)中讀取公私鑰澡谭。
所以先要使用openssl生成公鑰證書public_key.der和私鑰證書private_key.p12。然后讀取公私鑰损俭，再用framework進行加密蛙奖。
RSAEncryptor* rsaEncryptor = [[RSAEncryptor alloc] init];
NSString* publicKeyPath = [[NSBundle mainBundle] pathForResource:@"public_key" ofType:@"der"];
NSString* privateKeyPath = [[NSBundle mainBundle] pathForResource:@"private_key" ofType:@"p12"];
[rsaEncryptor loadPublicKeyFromFile: publicKeyPath];
[rsaEncryptor loadPrivateKeyFromFile: privateKeyPath password:@""]; // 這里，請換成你生成p12時的密碼
NSString* restrinBASE64STRING = [rsaEncryptor rsaEncryptString:@"I.O.S"];
NSLog(@"Encrypted: %@", restrinBASE64STRING); // 請把這段字符串Copy到JAVA這邊main()里做測試
NSString* decryptString = [rsaEncryptor rsaDecryptString: restrinBASE64STRING];
NSLog(@"Decrypted: %@", decryptString);
具體的RSAEncryptor代碼杆兵，這里就不貼了雁仲，可以從我的github上找相應的iOS加解密的代碼。上面還有一個c++的RSA算法的例子琐脏，可以看一下攒砖。
總結
本文主要還是整理了網(wǎng)上各個文章缸兔，其中數(shù)學原理解釋的最清楚的應該是阮一峰的RSA算法原理（一）與RSA算法原理（二）。數(shù)學原理上有不懂的可以再看一下這兩篇文章吹艇。最后總結一下RSA算法加密方式惰蜜。
| 密鑰組成與加解密 | 公式 |
|---|---|
| 公鑰KU | n：質(zhì)數(shù)p和質(zhì)數(shù)q的乘積（p和q必須保密）e：與(p-1)×(q-1)互質(zhì) |
| 私鑰KR | n：同公鑰nd： |
| 加密 |  |
| 解密 |  |
參考資料
本文CSDN地址
1.RSA算法原理（一）
2.RSA算法原理（二）
2.wiki-RSA加密算法
3.RSA算法基礎詳解
4.RSA加密
5.iOS 上的 RSA 加密方法
6.通過ios實現(xiàn)RSA加密和解密
