6、密码学 -- 初识RSA

今天我们来了解一下什么事RSA。
再介绍RSA之前我们要先了解几个数学概念。

• 原根（离散对数问题）
  3^N mode 17 = 12
  我们来看一张表
  

  
  通过表我们知道：
  3¹³ % 17 = 12
  观察上表我们会发现，N 在1~16之间，%17之后的值也在1~16之间，这是因为3是17的原根
  

• 欧拉函数 Φ(fai)
  首先思考一个问题：
  任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成
  计算这个值的方式叫做，使用：Φ(n)表示。

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

ii: 欧拉函数的特点：
①：当n是质数的时候，Φ(n)=n-1
②：如果n可以分解成 两个互质的整数之积，如：n = A*B 则：Φ(A*B) = Φ(A) * Φ(B)
根据以上两点得到：
如果N是两个质数P1 和 P2 的乘积，则：
Φ(N) = Φ(P1) * Φ(P2) = (P1 - 1) * (p2 - 1)

比如：

///计算8的欧拉函数，
Φ(8) = 4
///计算7的欧拉函数，
Φ(7) = 6
///计算56的欧拉函数，
Φ(56) = Φ(8) * Φ(7) = 4 * 6 = 24

• 欧拉定理
  如果两个正整数m 和n互质，那么m的Φ(n)次方，减去1，可以被n整除。
  (m^Φ(n) - 1) % n = 0
  或者这样写
  m^Φ(n) % n = 1

⚠️ 注意，这里是取模，也就是取余数，不是除法。

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

• 公式转换

i：m^Φ(n) % n = 1
由于 1^k = 1，所以

ii：m^k*Φ(n) % n = 1
又因为1*m = m，所以

iii：m^k*Φ(n)+1 % n = m（注意：此步骤换算的过程中，m 要小于 n 才会成立）

• 模反元素
  如果两个正整数e和x互质，那么一定可以找到整数d，使得e*d -1被x整除。那么d就是e对于x的模反元素。
  i：e*d % x = 1
ii：e*d - 1 = k*x --->e*d = k*x + 1
  此时结合上面的公式转换，如果x = Φ(n)，则：m^e*d % n = m

• 迪菲赫尔曼密钥交换
  

  迪菲赫尔曼密钥交换

原理：

迪菲赫尔曼密钥交换原理

• RSA算法

加密 ：m^e % n = c
解密 ：c^d % n = m

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

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

• Mac终端使用
  Mac的终端可以直接使用OpenSSL 进行RSA的命令运行。
  OpenSSL中RSA算法常用指令主要有三个：

命令	含义
genrsa	生成并输入一个RSA私钥
rsautl	使用RSA密钥进行加密、解密、签名和验证等运算
rsa	处理RSA密钥的格式转换等问题

• OpenSSL使用RSA
  i：生成RSA私钥，密钥长度为1024bit

openssl genrsa -out private.pem 1024

生成私钥
ii：从私钥中提取公钥

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

提取公钥

生成的文件如下：

iii：通过公钥加密数据，私钥解密数据

///生成明文文件
vi message.txt
///查看文件内容
cat 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.tx

iiii：我们还可以将私钥转换成明文

openssl rsa -in private.pem -text -out private.txt

私钥转明文

总结：这里我们对RSA加密进行了简单的了解，之后我们会针对实际的应用作进一步的探讨。