RSA算法是最重要算法之一讼溺，它是計(jì)算機(jī)通信安全的基石楣号，保證了加密數(shù)據(jù)不會(huì)被破解。本文主要參考了參考資料中的文章怒坯，介紹一下RSA算法的內(nèi)容炫狱，自己寫(xiě)一遍，算是學(xué)習(xí)了剔猿。
歷史
1.對(duì)稱加密算法
在1976年以前视译，所有的加密方法都是同一種模式"對(duì)稱加密算法"（Symmetric-key algorithm）:
- （1）甲方選擇某一種加密規(guī)則，對(duì)信息進(jìn)行加密归敬；
- （2）乙方使用同一種規(guī)則酷含，對(duì)信息進(jìn)行解密。
這種加密模式有一個(gè)最大弱點(diǎn)：甲方必須把加密規(guī)則告訴乙方弄慰，否則無(wú)法解密第美。
2.非對(duì)稱加密算法
1976年，兩位美國(guó)計(jì)算機(jī)學(xué)家Whitfield Diffie 和 Martin Hellman陆爽，提出了一種嶄新構(gòu)思什往，可以在不直接傳遞密鑰的情況下，完成解密慌闭。這被稱為"Diffie-Hellman密鑰交換算法"别威。
- （1）甲要傳密信給乙躯舔，乙先根據(jù)某種算法得出本次與甲通信的公鑰與私鑰
- （2）乙將公鑰傳給甲（公鑰可以讓任何人知道，即使泄露也沒(méi)有任何關(guān)系）
- （3）甲使用乙傳給的公鑰加密要發(fā)送的信息原文m省古，發(fā)送給乙密文c
- （4）乙使用自己的私鑰解密密文c粥庄，得到信息原文m
如果公鑰加密的信息只有私鑰解得開(kāi)，那么只要私鑰不泄漏豺妓，通信就是安全的惜互。
3.RSA算法的出現(xiàn)
1977年，三位數(shù)學(xué)家Rivest琳拭、Shamir 和 Adleman 設(shè)計(jì)了一種算法训堆，可以實(shí)現(xiàn)非對(duì)稱加密。這種算法用他們?nèi)齻€(gè)人的名字命名白嘁，叫做RSA算法坑鱼。
這種算法非常可靠，密鑰越長(zhǎng)絮缅，它就越難破解鲁沥。根據(jù)已經(jīng)披露的文獻(xiàn)，目前被破解的最長(zhǎng)RSA密鑰是768個(gè)二進(jìn)制位耕魄。也就是說(shuō)画恰，長(zhǎng)度超過(guò)768位的密鑰，還無(wú)法破解（至少?zèng)]人公開(kāi)宣布）屎开。因此可以認(rèn)為阐枣，1024位的RSA密鑰基本安全，2048位的密鑰極其安全奄抽。
數(shù)論知識(shí)
1.質(zhì)數(shù)
一個(gè)大于1的自然數(shù)蔼两，除了1和它本身外，不能被其他自然數(shù)整除（除0以外）的數(shù)稱之為質(zhì)數(shù)（素?cái)?shù)）逞度；否則稱為合數(shù)额划。
2.互質(zhì)數(shù)
互質(zhì)，又稱互素档泽。若N個(gè)整數(shù)的最大公因子是1俊戳，則稱這N個(gè)整數(shù)互質(zhì)。
3.指數(shù)運(yùn)算
指數(shù)運(yùn)算又稱乘方計(jì)算馆匿，計(jì)算結(jié)果稱為冪抑胎。nm
指將n自乘m次。把nm
看作乘方的結(jié)果渐北，叫做”n的m次冪”或”n的m次方”阿逃。其中，n稱為“底數(shù)”，m稱為“指數(shù)**”恃锉。
4.模運(yùn)算
讓m去被n整除搀菩，只取所得的余數(shù)作為結(jié)果，就叫做模運(yùn)算破托。
例如肪跋，10 mod 3 = 1 、26 mod 6 = 2 土砂、28 mod 2 = 0
5.同余
給定一個(gè)正整數(shù)m州既，如果兩個(gè)整數(shù)a和b滿足a-b能被m整除，即(a-b)modm=0萝映，那么就稱整數(shù)a與b對(duì)模m同余易桃，記作a≡b(modm)，同時(shí)可成立amodm=b锌俱。
6.歐拉函數(shù)
任意給定正整數(shù)n，計(jì)算在小于等于n的正整數(shù)之中敌呈，有多少個(gè)與n構(gòu)成互質(zhì)關(guān)系贸宏？計(jì)算這個(gè)值的方法就叫做歐拉函數(shù)，以φ(n)表示.
例如磕洪，在1到8之中吭练，與8形成互質(zhì)關(guān)系的是1、3析显、5鲫咽、7，所以φ(n)=4
在RSA算法中谷异，我們需要明白歐拉函數(shù)對(duì)以下定理成立
如果n可以分解成兩個(gè)互質(zhì)的整數(shù)之積分尸，即n=p×q，則有：φ(n)=φ(pq)=φ(p)φ(q);
根據(jù)“大數(shù)是質(zhì)數(shù)的兩個(gè)數(shù)一定是互質(zhì)數(shù)”可以知道：一個(gè)數(shù)如果是質(zhì)數(shù)歹嘹，則小于它的所有正整數(shù)與它都是互質(zhì)數(shù)箩绍；所以如果一個(gè)數(shù)p是質(zhì)數(shù)，則有：φ(p)=p-1
由上易得尺上，若我們知道一個(gè)數(shù)n可以分解為兩個(gè)質(zhì)數(shù)p和q的乘積材蛛，則有
φ(n)=(p-1)(q-1)
7.歐拉定理
如果兩個(gè)正整數(shù)a和n互質(zhì)，則n的歐拉函數(shù)φ(n)可以讓下面的等式成立：
image
比如怎抛，3和7互質(zhì)卑吭，而7的歐拉函數(shù)φ(7)等于6，所以3的6次方（729）減去1马绝，可以被7整除（728/7=104）豆赏。
8.模反元素
意即俩滥，如果兩個(gè)正整數(shù)a和n互質(zhì)，那么一定可以找到整數(shù)b
使得ab-1被n整除展父，或者說(shuō)ab被n除的余數(shù)是1
比如敢朱，3和11互質(zhì)，那么3的模反元素就是4耙饰，因?yàn)?(3 × 4)-1 可以被11整除纹笼。顯然，模反元素不止一個(gè)苟跪， 4加減11的整數(shù)倍都是3的模反元素 {...,-18,-7,4,15,26,...}廷痘，即如果b是a的模反元素，則 b+kn 都是a的模反元素件已。
算法基礎(chǔ)
1.實(shí)例
先通過(guò)一個(gè)實(shí)例來(lái)理解RSA算法的過(guò)程：
甲要發(fā)給乙一個(gè)加密內(nèi)容：m=65
乙發(fā)送甲公鑰：(n,e)=(3233,17)
甲根據(jù)公式
加密出c
甲將使用公鑰加密的密文c=2790發(fā)送給乙
乙收到c=2790的密文后使用私鑰(n,d)=(3233,2753)
根據(jù)公式
解密出m
從始至終笋额，用來(lái)解密的私鑰(n,d)=(3233,2753)一直都在乙處，從未泄露篷扩。乙給甲的僅僅是用來(lái)加密的公鑰(3233,17)兄猩，這個(gè)公鑰并不能用來(lái)解密，即使被他人截獲鉴未，也沒(méi)有任何泄密的風(fēng)險(xiǎn)枢冤。
2.計(jì)算公私鑰
- 1.隨機(jī)選擇兩個(gè)不相等的質(zhì)數(shù)p和q（乙選擇了61和53）
- 2.計(jì)算p和q的乘積n=p×q=61×53=3233
- 3.根據(jù)本文“歐拉函數(shù)”介紹過(guò)的公式
φ(n)=(p-1)(q-1)
代入計(jì)算n的歐拉函數(shù)值
φ(3233)=(61-1)×(53-1)=60×52=3120 - 4.隨機(jī)選擇一個(gè)整數(shù)e，條件是1<e<φ(n)铜秆，且e與φ(n)互質(zhì)
乙就在1到3120之間淹真，隨機(jī)選擇了17 - 5.因?yàn)閑與φ(n)互質(zhì)，根據(jù)求模反元素的公式計(jì)算e连茧，對(duì)于e的模反元素d有：
ed≡1(modφ(n))
這個(gè)式子等價(jià)于
(ed-1)/φ(n)=k（k為任意正整數(shù)）
即
ed-kφ(n)=1核蘸，
代入數(shù)據(jù)得：17d-3120k=1
實(shí)質(zhì)上就是對(duì)以上這個(gè)二元一次方程求解得到一組解為：(d,k)=(2753,-15) - 6.將n和e封裝成公鑰，n和d封裝成私鑰
n=3233啸驯，e=17客扎，d=2753
所以公鑰就是(3233,17)，私鑰就是(3233,2753)
至此坯汤，整個(gè)rsa公私鑰的算法就清楚了
3.推導(dǎo)
整個(gè)過(guò)程中虐唠，讓人困擾的可能是
與
事實(shí)上式子2就是從式子1推導(dǎo)出來(lái)，具體過(guò)程可以參考RSA算法原理（二）惰聂，這邊也做一個(gè)簡(jiǎn)單描述：
4.安全性
在上面給出的例子中疆偿，一共出現(xiàn)了6個(gè)數(shù)字：
- 隨機(jī)質(zhì)數(shù)p 61
- 隨機(jī)質(zhì)數(shù)q 53
- n=p×q 3233
- φ(n)=(p-1)(q-1) 3120
- 隨機(jī)e與φ(n)互質(zhì) 17
- e的模反元素d 2753
其中公鑰用到了(n,e)，剩下4個(gè)不知搓幌。關(guān)鍵私鑰(n,d)杆故，關(guān)鍵值是d，不能泄露d溉愁。
那么处铛，有無(wú)可能在已知n和e的情況下饲趋，推導(dǎo)出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。
結(jié)論：如果n可以被因數(shù)分解反镇，d就可以算出固蚤，也就意味著私鑰被破解。
事實(shí)上歹茶，RSA的安全性就是源自你沒(méi)辦法輕易的對(duì)大整數(shù)“因式分解”夕玩。人類已經(jīng)分解的最大整數(shù)（232個(gè)十進(jìn)制位，768個(gè)二進(jìn)制位）惊豺。比它更大的因數(shù)分解风秤，還沒(méi)有被報(bào)道過(guò)，因此目前被破解的最長(zhǎng)RSA密鑰就是768位扮叨。實(shí)際應(yīng)用中，RSA密鑰一般是1024位领迈，重要場(chǎng)合則為2048位彻磁。
算法實(shí)現(xiàn)
iOS中的實(shí)現(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);
但這個(gè)framework的api只支持從標(biāo)準(zhǔn)證書(shū)文件(cer,crt)中讀取公私鑰。
所以先要使用openssl生成公鑰證書(shū)public_key.der和私鑰證書(shū)private_key.p12狸捅。然后讀取公私鑰衷蜓，再用framework進(jìn)行加密。
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:@""]; // 這里尘喝，請(qǐng)換成你生成p12時(shí)的密碼
NSString* restrinBASE64STRING = [rsaEncryptor rsaEncryptString:@"I.O.S"];
NSLog(@"Encrypted: %@", restrinBASE64STRING); // 請(qǐng)把這段字符串Copy到JAVA這邊main()里做測(cè)試
NSString* decryptString = [rsaEncryptor rsaDecryptString: restrinBASE64STRING];
NSLog(@"Decrypted: %@", decryptString);
具體的RSAEncryptor代碼磁浇，這里就不貼了，可以從我的github上找相應(yīng)的iOS加解密的代碼朽褪。上面還有一個(gè)c++的RSA算法的例子置吓，可以看一下。
總結(jié)
本文主要還是整理了網(wǎng)上各個(gè)文章缔赠，其中數(shù)學(xué)原理解釋的最清楚的應(yīng)該是阮一峰的RSA算法原理（一）與RSA算法原理（二）衍锚。數(shù)學(xué)原理上有不懂的可以再看一下這兩篇文章。最后總結(jié)一下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算法基礎(chǔ)詳解
4.RSA加密
5.iOS 上的 RSA 加密方法
6.通過(guò)ios實(shí)現(xiàn)RSA加密和解密
