RSA加密/解密

RSA数学原理

原根

• 3 ^ x mod 17 = y
• 1 <= x < 17
• 1 <= y < 17

如果3的x次方除17的余数都小于17且x大于等于1小于17，则 3 是 17 的原根，

欧拉函数、欧拉定理

• 欧拉函数：对正整数n，欧拉函数是小于或等于n的正整数中与n[互质]的数的个数，记做φ(n) ，例如φ(1)=1,φ(8) = 4,φ(7)=6。

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

• 欧拉定理：如果两个正整数n和m互质，m ^ φ(n) % n = 1。

• 1. m ^ φ(n) % n = [ m ^ φ(n)] ^ k % n = 1;
• 2. m ^ [k * φ(n)] % n = 1 ;
• 3. m ^ [k * φ(n) + 1] % n = m

模反元素

e * d % x = 1 如果e和x互质，一定能找到一个数d使得e*d 除 x 等于1，则d称为e相对于x的模反元素（x是模）
推导出：e * d = kx + 1

公式

• 1. m ^ [k * φ(n) + 1] % n = m
• 2. 令x = φ(n)，则： k * φ(n) + 1 = kx + 1
• 3. 找到一个和x互质的数e，一个e相对于x的模反元素d，则： kx + 1 = e *d
• 4. 根据以上可以推导出公式： m ^(e * d) % n = m ；（d 是 e相对于φ(n)的模反元素）

迪菲赫尔曼密钥交换

• 1. m ^(e * d) %n = m ；分解为2步
• 2. m ^(e * d) %n = (m ^ e ) ^ d % n = m

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

明文：m
密文：c
公钥：e 和 n
私钥：d 和 n
条件：

• m < n
• (p1和p2都是质数)
• n = p1 * p2
• fai(n) = fai(p1 * p2) = fai(p1) * fai(p2) = (p1 -1) * (p2 -2)
• d 是e（65537/0x10001）相对于fai(n)的模反元素
  注意： 先生成私钥，所有数据就都有了，在从私钥里面提取出来公钥

Tip

• 客户端只要有e和n就可以解密服务器发送的密文了，e一般是公开的65537
• 客户端加密的内容只有用服务器的d才能解密出来
  • 所以客户端输入的密码在经过RSA加密后只有服务器才能解密
  • 在未加密的时候并没有向网络传输
• 网络传输的所有数据可以截取到，就像是大马路，但是截取的是内容是加密的那就是一堆乱码
• 假设客户端被破解了，可以接收到服务器发送的信息，但是一般服务器发送的信息都是公开的内容，保密性不强
• 权限验证都在服务器，你是vip才给你推送特定的内容，怎么验证你是vip是需要你提供密码发送到服务器
• 私钥有个唯一性，这个可以反向使用，让客户端生成私钥，把公钥给到服务器可以来验证设备的唯一性，常用作ssh登陆，如果你的私钥变了需要从新给到服务器一份公钥

RSA相关命令

• 生成私钥

openssl genras -out private.pem 1024

• 提取公钥，需要从私钥里面提取

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

• 公钥加密，私钥解密 参数数-encrypt / 私钥加密公钥解密是-sign/-verify 签名和炎症
• 加密

//公钥加密
openssl rsautl -encrypt -in file.txt -inkey public.pem -pubin -out enc.txt
//私钥加密
openssl rsautl -sign -in file.txt -inkey private.pem -out enc.txt

• 解密

//私钥解密
openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
//公钥解密
openssl rsautl -verify -in enc.txt -inkey public.pem -pubin -out dec.txt