RSA算法是最重要算法之一，它是计算机通信安全的基石，保证了加密数据不会被破解。本文主要参考了参考资料中的文章，介绍一下RSA算法的内容，自己写一遍，算是学习了。
历史
1.对称加密算法
在1976年以前，所有的加密方法都是同一种模式"对称加密算法"（Symmetric-key algorithm）:
- （1）甲方选择某一种加密规则，对信息进行加密；
- （2）乙方使用同一种规则，对信息进行解密。
这种加密模式有一个最大弱点：甲方必须把加密规则告诉乙方，否则无法解密。
2.非对称加密算法
1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。
- （1）甲要传密信给乙，乙先根据某种算法得出本次与甲通信的公钥与私钥
- （2）乙将公钥传给甲（公钥可以让任何人知道，即使泄露也没有任何关系）
- （3）甲使用乙传给的公钥加密要发送的信息原文m，发送给乙密文c
- （4）乙使用自己的私钥解密密文c，得到信息原文m
如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
3.RSA算法的出现
1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。
这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。
数论知识
1.质数
一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为质数（素数）；否则称为合数。
2.互质数
互质，又称互素。若N个整数的最大公因子是1，则称这N个整数互质。
3.指数运算
指数运算又称乘方计算，计算结果称为幂。nm
指将n自乘m次。把nm
看作乘方的结果，叫做”n的m次幂”或”n的m次方”。其中，n称为“底数”，m称为“指数**”。
4.模运算
让m去被n整除，只取所得的余数作为结果，就叫做模运算。
例如，10 mod 3 = 1 、26 mod 6 = 2 、28 mod 2 = 0
5.同余
给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即(a-b)modm=0，那么就称整数a与b对模m同余，记作a≡b(modm)，同时可成立amodm=b。
6.欧拉函数
任意给定正整数n，计算在小于等于n的正整数之中，有多少个与n构成互质关系？计算这个值的方法就叫做欧拉函数，以φ(n)表示.
例如，在1到8之中，与8形成互质关系的是1、3、5、7，所以φ(n)=4
在RSA算法中，我们需要明白欧拉函数对以下定理成立
如果n可以分解成两个互质的整数之积，即n=p×q，则有：φ(n)=φ(pq)=φ(p)φ(q);
根据“大数是质数的两个数一定是互质数”可以知道：一个数如果是质数，则小于它的所有正整数与它都是互质数；所以如果一个数p是质数，则有：φ(p)=p-1
由上易得，若我们知道一个数n可以分解为两个质数p和q的乘积，则有
φ(n)=(p-1)(q-1)
7.欧拉定理
如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立：
image
比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。
8.模反元素
意即，如果两个正整数a和n互质，那么一定可以找到整数b
使得ab-1被n整除，或者说ab被n除的余数是1
比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {...,-18,-7,4,15,26,...}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。
算法基础
1.实例
先通过一个实例来理解RSA算法的过程：
甲要发给乙一个加密内容：m=65
乙发送甲公钥：(n,e)=(3233,17)
甲根据公式
加密出c
甲将使用公钥加密的密文c=2790发送给乙
乙收到c=2790的密文后使用私钥(n,d)=(3233,2753)
根据公式
解密出m
从始至终，用来解密的私钥(n,d)=(3233,2753)一直都在乙处，从未泄露。乙给甲的仅仅是用来加密的公钥(3233,17)，这个公钥并不能用来解密，即使被他人截获，也没有任何泄密的风险。
2.计算公私钥
- 1.随机选择两个不相等的质数p和q（乙选择了61和53）
- 2.计算p和q的乘积n=p×q=61×53=3233
- 3.根据本文“欧拉函数”介绍过的公式
φ(n)=(p-1)(q-1)
代入计算n的欧拉函数值
φ(3233)=(61-1)×(53-1)=60×52=3120 - 4.随机选择一个整数e，条件是1<e<φ(n)，且e与φ(n)互质
乙就在1到3120之间，随机选择了17 - 5.因为e与φ(n)互质，根据求模反元素的公式计算e，对于e的模反元素d有：
ed≡1(modφ(n))
这个式子等价于
(ed-1)/φ(n)=k（k为任意正整数）
即
ed-kφ(n)=1，
代入数据得：17d-3120k=1
实质上就是对以上这个二元一次方程求解得到一组解为：(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.安全性
在上面给出的例子中，一共出现了6个数字：
- 随机质数p 61
- 随机质数q 53
- n=p×q 3233
- φ(n)=(p-1)(q-1) 3120
- 随机e与φ(n)互质 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因数分解，才能算出p和q。
结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。
事实上，RSA的安全性就是源自你没办法轻易的对大整数“因式分解”。人类已经分解的最大整数（232个十进制位，768个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
算法实现
iOS中的实现与使用
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算法的例子，可以看一下。
总结
本文主要还是整理了网上各个文章，其中数学原理解释的最清楚的应该是阮一峰的RSA算法原理（一）与RSA算法原理（二）。数学原理上有不懂的可以再看一下这两篇文章。最后总结一下RSA算法加密方式。
| 密钥组成与加解密 | 公式 |
|---|---|
| 公钥KU | n：质数p和质数q的乘积（p和q必须保密）e：与(p-1)×(q-1)互质 |
| 私钥KR | n：同公钥nd： |
|
| 加密 |
|
| 解密 |
|
参考资料
本文CSDN地址
1.RSA算法原理（一）
2.RSA算法原理（二）
2.wiki-RSA加密算法
3.RSA算法基础详解
4.RSA加密
5.iOS 上的 RSA 加密方法
6.通过ios实现RSA加密和解密
