RSA的起源
- 1976年以前所有的加密方法都是同一种模式：加解密双方使用同一种规则(简称“密钥”)。这种加密方式被称为对称加密算法。
- 1976年，两位美国计算机学家迪菲(W.Diffie)、赫尔曼(M.Hellman)提出了一种崭新构思，加密和解密使用不同的规则，但只要两种规则(密钥)之间存在某种对应关系即可实现在不直接传递密钥的情况下完成解密。这被称为Diffie-Hellman密钥交换算法。
- 1977年三位麻省理工学院的数学家罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起设计了一种算法，可以实现
非对称加密。image
这个算法用他们三个人的名字命名，叫做RSA算法。其加密方式比较特殊，需要两个密钥：公开密钥简称公钥(publickey)和私有密钥简称私钥(privatekey)。公钥加密，私钥解密；私钥加密，公钥解密。
RSA算法原理 -- 摘抄自网站
- 互质关系：如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系。关于互质关系有几个结论：
1.任意两个质数构成互质关系
2.一个数是质数，另一个数只要不是前者的倍数，两者互质
3.若较大的数为质数，则两者互质
4.任意自然数与1都互质
5.若p大于1，则p与p-1构成互质
6.若p为大于1的奇数，则p与p-2互质
-
欧拉函数：
φ(n)表示在小于等于n的正整数之中有多少个与n构成互质关系(除了1以外没有其他公因数)。
1.如果n=1，则φ(1)=1。因为1与任何数都构成互质关系。
2.如果n是质数，则φ(n)=n-1。因为质数与小于它的每一个数都构成互质关系。
3.如果n是质数p的k次方，k为正整数，则φ(n) = p^k - p^(k-1) = p^k(1 - 1/p)
4.如果n为两个互质的整数p1、p2之积，那么φ(n) =φ(p1) * φ(p2)
5.因为任意一个大于1的正整数都可以写成一系列质数p1,p2,p3...pn之积
φ(n) = φ(p1^k1 * p2^k2 *...pn^kn)
= φ(p1^k1) * φ(p2^k2) * ... * φ(pn^kn)
= p1^k1(1 - 1/p1) * p2^k2(1-1/p2)...* pn^kn(1-1/pn)
= n * (1-1/p1)(1-1/p2)...(1-1/pn)
φ(72) = φ(8*9) = φ(2^3 * 3^2) = 72*(1-1/2)(1-1/3) = 24
= φ(8) * φ(9) = 4 * 6 = 24
-
欧拉定理：如果两个正整数
a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立：a^φ(n) % n = 1，a的φ(n)次方除以n取余等于1；如果两个正整数a与质数p互质，a^φ(p) % p = a^(p-1) % p = 1，这就是著名的费马小定理，欧拉定理是RSA算法的核心。 -
模反元素：如果两个正整数
a和n互质，那么一定可以找到整数b，使用a * b - 1被n整除，这时b就叫做a的模反元素，比如7和9互质，7*4 % 9 = 1，那么此时4就是7的模反元素，另外13、22、31都是，即b + k * n都是a的模反元素。
了解上面的数论知识之后，再来理解RSA算法就比较容易了，假如A和B要进行加密通信，那么如何生成公钥和私钥？
- 第一步，随机选择两个不相等的质数
p和q。 - 第二步，计算
p和q的乘积n，n转化为二进制的长度就是密钥的长度，实际应用中一般RSA的密钥长度是1024位，重要场合则为2048位。 - 第三步，计算
n的欧拉函数φ(n)，根据公式φ(n) = (p-1)(q-1) - 第四步，随机选择一个整数
e - 第五步，计算
e对于φ(n)的模反元素d，即满足e * d - 1 = k*φ(n)，即对二元一次方程求解e*x - φ(n)*y = 1，其中e和φ(n)已知，使用扩欧几里得算法求解得出一组(x,y)，即得d = y - 第六步，将
n和e封装成公钥，n和d封装成私钥。在实际应用中公钥和私钥的数据都是采用ASN.1格式表达(感兴趣可以查看维基百科ASN.1，需要科学上网)
RSA算法的可靠性
由于n和e是公开的，d为推导出来的，如果d被算出来，那么就意味着私钥被破解，我们可以看一下d的推导过程：
-
e * d % φ(n) = 1，只要计算出φ(n)，那么d就能被算出来 - 如何计算
φ(n)，φ(n) = (p-1)(q-1)，计算p和q两个质数即可算出φ(n) -
n=p*q，将n进行因数分解，才能算出p和q
总结：如果n可以被因数分解，私钥才能被破解
维基百科对于RSA有这样一段描述：
对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被破解的。
目前已公布分解出的最大整数是232个十进制位，768个二进制位，因此1024位很安全，2048位非常安全。
- 公钥加密：消息
m使用公钥加密(n,e)，m * e % n = c，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n - 私钥解密：
c * d % n = m
在这个过程中依赖于迪菲赫尔曼密钥交换算法 等式m ^ (e * d) % n = m可拆分为m * e % n = c，c * d % n = m。不难看出我们也可以使用d加密，e解密。论证了上面所提到的公钥加密，私钥解密；私钥加密，公钥解密。
Mac系统内置OpenSSL(开源加密库)，所以我们可以使用终端尝试使用RSA
-
生成RSA私钥，指定长度1024bit，命令为
openssl genrsa -out private.pem 1024
终端截图示例 从私钥中提取公钥，命令为
openssl rsa -in xxx.pem -pubout -out public.pem随便创建一个txt文件，并写入一些内容，注意不能太长，比如message.txt
公钥加密私钥解密：
openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt
openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt私钥加密公钥解密：
openssl rsautl -sign -in message.txt -inkey private.pem -out enc.txt
openssl rsautl -verify -in enc.txt -inkey public.pem -pubin -out dec.txt
OC代码中使用RSA不能直接使用pem格式文件，需要将私钥转成p12文件，公钥转成der格式
- 首先需要请求一个csr的文件，因为证书是需要认证的，这个csr文件中包含一些信息如Country Name、Organization Name、Email等。随便填~
终端命令为：openssl req -new -key private.pem -out rsacert.csr，过程中需要填写一些信息以及密码(空即可)。 - 证书签名生成crt文件：
openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt，-days 3650有效期十年的自签名证书(https协议就需要这样的一个证书，想省钱可以使用这种自签名证书，将crt文件放在服务器上，让别人接受即可~) - crt生成p12文件：
openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt，需要输入密码 - 生成der文件：
openssl x509 -outform der -in rsacert.crt -out rsacert.der - 将
p.p12和rsacert.der文件添加到工程中使用。主要是使用动态库Security中的SecKey类中的方法
OSStatus SecKeyEncrypt(
SecKeyRef key,
SecPadding padding,
const uint8_t *plainText,
size_t plainTextLen,
uint8_t *cipherText,
size_t *cipherTextLen)
使用方法github有很多封装示例，这里就不再列举。
