五、RSA的数学原理

• 问题:有没有加密容易.破解很难数学运算？,如下：
  3^? mod 17 = 12
  你是不是算了很久呢？答案是：3¹³ mod 17 = 12，如果3比17小，那么一定会存在一个值，这个值的范围在1~16之间，使得3ⁿ mod17=12,那么我们可以称3是17的原根
  

  image.png

• 疑问：n大于16呢？不在1～16的范围之内，会是怎么样的结果呢？
  

  image.png
  可以看到，结果和n在1～16的范围是一模一样的
  结论：当17是一个很大的数时，要算出n的值，难度是非常大的

• 欧拉函数
  任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？计算这个值的方式叫做欧拉函数，使用：Φ(n)表示

互质关系：如果两个正整数，除了1以外，没有其他公因数，我们就称这两个数是互质关系

例如:
计算8的欧拉函数，和8互质的 1、2、3、4、5、6、7、8
φ(8) = 4
计算7的欧拉函数，和7互质的 1、2、3、4、5、6、7
φ(7) = 6
计算56的欧拉函数
φ(56) = φ(8) * φ(7) = 4 * 6 = 24

欧拉函数特点
一、当n是质数的时候，φ(n)=n-1。
二、如果n可以分解成两个互质的整数之积，如n=AB则：
φ(AB)=φ(A)* φ(B)
根据以上两点得到：
如果N是两个质数P1 和 P2的乘积则
φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)

• 欧拉定理
  如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。

m^Φ(n) mod n ≡ 1

演变：

• 费马小定理
  欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1

m^(n-1) mod n ≡ 1

公式转换：
假设：1^k ≡ 1 => (m^Φ(n) mod n)^k ≡ 1 => m^Φ(n)*k mod n ≡ 1

m^Φ(n)*k mod n ==1这是一个定理，任何被称作定理的，都是从很多复杂的公式演变过来的，记住有这样的定理就行，不要尝试去验证，不然头顶的毛毛就不保了，这是数学家通过多年的研究验算得到的

又假设：1*m ≡ m => m^Φ(n)k+1 mod n ≡ m

模反元素
如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除。那么d就是e相对于x的“模反元素”

e*d mod x ≡ 1

e*d ≡ k*x+1
这里的k*x+1 有没有很眼熟，跟上面的m^Φ(n)k+1是不是很像，所以当e与Φ(n)互质时，公式可以演变成

m^e*d mod n ≡ m

结论:
e必须要与Φ(n)互质，m要小于n，以上等式成立

• 迪菲赫尔曼密钥交换算法
  image.png

结论
在迪菲赫尔曼密钥交换算法的前提，当m小于n，并且e与Φ(n)互质时，RSA的算法就诞生了

image.png
公钥： n和e
私钥： n和d
明文: m
密文: c

说明：
1、n会非常大，长度一般为1024个二进制位。（目前人类已经分解的最大整数，232个十进制位，768个二进制位）
2、由于需要求出φ(n)，所以根据欧拉函数特点，最简单的方式n 由两个质数相乘得到: 质数：p1、p2
Φ(n) = (p1 -1) * (p2 - 1)
3、最终由φ(n)得到e 和 d 。
总共生成6个数字：p1、p2、n、φ(n)、e、d

关于RSA的安全
除了公钥用到了n和e 其余的4个数字是不公开的。
目前破解RSA得到d的方式如下：
1、要想求出私钥 d 。由于e*d = φ(n)*k + 1。要知道e和φ(n);
2、e是知道的，但是要得到 φ(n)，必须知道p1 和 p2。
3、由于 n=p1*p2。只有将n因数分解才能算出。

• 由于Mac系统内置OpenSSL(开源加密库),所以我们可以直接在终端上使用命令来玩RSA

•生成RSA私钥,密钥长度为1024bit

 openssl genrsa -out private.pem 1024

•从私钥中提取公钥

openssl rsa -in private.pem -pubout -out public.pem

•生成文件如下

image.png

•通过公钥加密数据,私钥解密数据

//通过公钥进行加密
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.txtt

• Xcode项目内使用RSA

1. 根据私钥pem向证书颁发机构获取请求文件csr

 openssl req -new -key private.pem -out rsacert.csr

2.根据获取到的请求文件csr，去专门的证书签名机构请求签名，证明我们这个证书是合法的，这里，我们自己签名，但是自己签名的证书是没有认证的

//自己签名，证书有效期3650天，即10年，获取到rsacert.crt签名文件
openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt

3.通过crt转成内容为der格式的der证书

//公钥
openssl x509 -outform der -in rsacert.crt -out rsacert.der

4.绑定密钥p12

openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt

5.拿到der和p12就可以在Xcode中我们的项目中使用RSA了