初识RSA

前言

这篇文章将从RSA理论、RSA终端操作、RSA代码操作三个方面去了解和使用RSA加密。一到四节是理论部分，觉得看的无趣的小伙伴们可以直接跳到第五节

数学小课堂

质数：又叫素数，在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数，如2，3，5，7
因数：又叫约数，整数a除以整数b(b≠0) 的商正好是整数，则b是a的因数，如2是4的约数
互质：如果两个正整数，没有除1以外的公因数，则称它们为互质关系，如7和9互质
取模运算：又叫时钟运算，与我们平时所说的取余运算略有不同（两者区别可自行百度，在RSA运算中两者的运算结果是一致的），取模符号为 mod，取余符号为 %
同余定理：
幂运算性质：如果 $a≡b mod m$ ，那么 $a^{n}≡b^{n}modm$

一、密码学发展历史

早期：使用密码本（罗马字母与数字对应的一张表）
1976年以前：对称加密算法，加密解密使用同一种规则（密钥），这种规则的保护就显得极为重要，一旦泄露或破解，所有的信息都能被解密出来
1976年：”迪费赫尔曼密钥交换“算法是由美国两个计算机学家迪费（W.Diffie）、赫尔曼（M.Hellman）共同提出的构思，可以在不直接传递密钥的情况下进行密钥交换
1977年：RSA加密问世。RSA是由美国麻省理工学院的数学家罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出并用他们的名字命名的

二、RSA中的数学原理

原根： $g^{i} mod p ≠ g^{j} mod p$ （p为质数），其中i≠j且i, j介于1至(p-1)之间，则g为p的原根
如：因为3^1 mod 17 = 3，3^2 mod 17 = 9...3^16 mod 17 = 1，3的1~16次方mod17的值都不相同，所以3为17的原根
欧拉函数：在小于正整数n的数中，与n互质的数的个数
特点：
- 如果 $n = A * B$ ，且A、B互质，则 $Φ(n) = Φ(A) * Φ(B)$
- n为质数时，Φ(n) = n - 1，如Φ(17) = 16
欧拉定理：如果两个正整数m和n互质，那么m的Φ(n)次方减1可以被n整除
条件：m与n互质
公式： $m^{Φ(n)} mod n ≡ 1$
费马小定理：是欧拉定理的一种特殊情况，n自身为质数时，Φ(n) = n - 1
条件：m与n互质，且n为质数
公式： $m^{n-1}mod n ≡ 1$
模反元素：如果两个正整数e和x互质，那么一定可以找到整数d，使得ed-1被x整除，而d被称作e对于x的模反元素
条件：e与x互质
公式： $e * d mod x ≡ 1$
欧拉函数和模反元素的公式推演

接下来我们利用已知的数学公式来推演公式：
① 在欧拉定理公式中， $m^{Φ(n)} mod n ≡ 1$ 等式两边同k次方，根据同余定理的幂运算性质就可以得到 $m^{k*Φ(n)} mod n ≡ 1$
② 然后在等式两边同乘m，即可得出 $m^{k*Φ(n)+1} mod n ≡ m$
③ 在模反元素公式中， $e * d mod x ≡ 1$ 去掉mod运算符。既然ed-1可以被x整除，那么ed必然是x的k倍数+1
④ 在x=φ(n)的情况下， $m^{ed} mod n ≡ n$

总结：欧拉函数和模反元素可以推出RSA加密的前身，而且根据多次计算，发现所满足的必要条件与欧拉函数并不一致
条件：

m < n；
d是e对于φ(n)的模反元素；

公式： $m^{ed} mod n ≡ n$

数学家们花了许多时间和精力都没有想到继续拆分这个公式的方法，知道迪费、赫尔曼两个大佬的出现才解决了这个难题，同时迪费赫尔曼密钥交换也开创了密码学的新方向

三、迪费赫尔曼密钥交换

这里拿了一张Hank老师的思维导图来进行说明：

服务器生成一个随机数15，然后根据固定的算法 $3^{15}mod17$ 得到加密后的信息6发送给客户端
客户端同时生成一个随机数13，根据同样的算法 $3^{13}mod17$ 得到信息12发给服务器
服务器和客户端根据得到的信息照着原来的算法再次运算，就能得到对方发的真实信息，信息交换中也不会涉及到密钥的交换

注意：

信息在传输过程中，第三方只能截取到信息6和信息12，并不能截取到真实信息
算法规律是彼此都知道的，就算算法泄露出去了，根据离散对数中的原根概念，已知3^n mod 17=12，想求出n也绝非易事

其实迪费赫尔曼当时的目的只是为了在密钥交换的时候更加安全，而之后RSA三兄弟站了出来

四、RSA的诞生

迪费赫尔曼已经成功将 $m^{ed} mod n ≡ n$ 拆分成 $m^{e} mod n= c$ 和 $c^{d} mod n = n$ ，只是没有提出这一理念

RSA算法
加密算法： $m^{e} mod n= c$
解密算法： $c^{d} mod n = n$
其中m是明文，c是密文，n和e是公钥，n和d是私钥
条件：① m < n；② d是e对于φ(n)的模反元素
RSA说明
1. n会非常大，长度一般为1024位
2. 由于需要求出φ(n)，所以根据欧函数特点，最简单的方式n由两个质数相乘得到: 质数p1、p2
3. 最终由φ(n)得到e 和 d，总共生成6个数字：p1、p2、n、φ(n)、e、d
4. 除了公钥用到的n和e，其余4个数字是不公开的
RSA的安全性
1. 想要破解RSA得到d，由于 $e * d = φ(n) * k + 1$ ，就要先知道e和φ（n）
2. 要得到φ(n)必须知道质数p1、p2
3. 由于 $n = p1 * p2$ ，只有将n因数分解才能算出
RSA的特点
1. 相对安全
2. 加密效率低
3. 加密数据小（一般用来加密Hash值做对称加密）

五、RSA终端使用

生成私钥
openssl genrsa -out private.pem 1024
私钥中提取公钥
openssl rsa -in private.pem -pubout -out public.pem
查看公钥
cat public.pem
将私钥转成文本文件
openssl rsa -in private.pem -text -out private.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.bin
用公钥验证
openssl rsautl -verify -in enc.bin -inkey public.pem -pubin -out dec.txt
查看二进制文件
xxd enc.bin

六、证书生成

生成请求证书文件，需要填写国家、省市、组织名
钥匙串也可以从证书颁发机构请求证书
openssl req -new -key private.pem -out rsacert.csr
证书签名
openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt
生成公钥
openssl x509 -outform der -in rsacert.crt -out rsacert.der
生成私钥
openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt
┭┮﹏┭┮终于不用在生成p12文件时百度代码了

七、Base64编码

base64可以将任意的二进制数据进行编码，编码成为由65个字符组成的文本文件，是二进制数据的一种表现
base64编码是由（A-Z，a-z，0-9，+ / =）组成的，最少为24个字符位，从左至右6个为一组，不足6个则补零，用等号来填补最后的空白
如A的二进制是01000001，补到24位是010000 010000 000000 000000，转换成base64码就是QQ==

终端编码
base64 xxx.jpeg -o xxx.text
终端解码
base64 xxx.text -o xxx.jpeg -D
代码编码

// 对一个字符编码
- (NSString *)base64Endcode:(NSString *)str {
    NSData *data = [str dataUsingEncoding:NSUTF8StringEncoding];
    return [data base64EncodedStringWithOptions:0];
}

代码解码

// 对一个编码解密
- (NSString *)base64Decode:(NSString *)str {
    NSData *data = [[NSData alloc] initWithBase64EncodedString:str options:0];
    return [[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding];
}