05-密码学(1)

前言

本篇开始，将给大家介绍密码学相关的知识点，这也是为后面学习安全攻防前做的准备，只有了解清楚了加密算法，你才能知道如何去防止破解，是吧！本篇文章首先会大致介绍密码学的发展史，接着会重点介绍RSA加密算法，包括这个算法推算过程。

一、密码学

什么是密码学？

密码学是指研究信息加密，破解密码的技术科学。

密码学的起源可追溯到2000年前，而当今的密码学则是以数学为基础的。

发展历史

相传古罗马名将凯撒大帝为了防止敌方截获情报，用密码传送情报。凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表👇

上图就好比一个密码本，如果不知道密码本，即使截获一段信息也看不懂。所以，密码本存在两个问题👇

1. 密码本泄漏
2. 如果截取足够多的密文可以看字母出现的频率，也可以破解，这就是所谓的暴力破解

从凯撒大帝时代到上世纪70年代这段很长的时间里，密码学的发展非常的缓慢，因为设计者基本上靠经验，没有运用数学原理。当今的密码学是以数学为基础的👇

• 在1976年以前，所有的加密方法都是同一种模式：加密、解密 使用同一种算法。在交互数据的时候，彼此通信的双方就必须将规则告诉对方，否则没法解密。那么加密和解密的规则（简称 密钥（同“月”发音） ），它的保护就显得尤其重要。传递密钥就成为了最大的隐患。这种加密方式被成为 对称加密算法 （symmetric encryption algorithm）
• 1976年，两位美国计算机学家 迪菲（W.Diffie）、赫尔曼（ M.Hellman ） 提出了一种崭新构思，可以在不直接传递密钥的情况下，完成密钥交换。这被称为 迪菲赫尔曼密钥交换 算法。开创了密码学研究的新方向。
• 1977年三位麻省理工学院的数学家 罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman） 一起设计了一种算法，可以实现非对称加密。这个算法用他们三个人的名字命名，叫做RSA算法。

二、RSA

上世纪70年代产生的一种加密算法。其加密方式比较特殊，需要两个密钥：公开密钥简称公钥（publickey）和 私有密钥 简称私钥（privatekey）。公钥加密，私钥解密；私钥加密，公钥解密。这个加密算法就是伟大的RSA。

2.1 RSA数学原理

2.1.1离散对数问题

为什么要提到离散对数这个概念呢？这个和加解密有什么关系？带着这样的问题，我们一步步来看，最理想的加解密情况应该是这样的 👉 加密简单，解密很难。怎样才能做到这点呢，首先我们来看看mod运算👇

mod运算就是求2个数x和y的余数。

例如：如果用质数17做模数（17就好比y），x是3的幂数，并且它们的余数是12，求x到底是3的几次方？👇

接着我们按顺序尝试写出来👇

最终求得是13次方。根据上图，我们可以发现一个规律👇

3的n次方mod17结果永远在1~16之间，就好比一个时钟👇

所以mod运算也称作时钟算法。

这里的3称作是17的原根，这里的结果是12，反推n的话，需要我们一条条的计算出来，根据穷举求n。假如模数变大，那么反推破解难度也会变的很大，这个就是离散对数问题。

2.1.2欧拉函数

欧拉函数概念👇

任意给定正整数n，在<= n的正整数之中，有多少个与n构成互质关系？

互质关系 👇

如果两个正整数，除了1以外，没有其他公因数，就称这两个数是互质关系（coprime）。

计算多少个这个值的方式就叫做欧拉函数，使用φ(n)(φ发音同fai三声)表示。例如👇

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

欧拉函数特点

1.当n是质数的时候φ(n)=n-1。

2. 如果n可以分解成两个互质的整数之积，如n=A*B则👇
   φ(A*B)=φ(A)* φ(B)

根据以上两点得到：

如果N是两个互质数P1和 P2的乘积，则 👉 φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)

欧拉定理

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

欧拉定理

费马小定理

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

验证：m = 6，n = 5（5是质数） --> 6^4%5 --> 24*24%5 -->24*24的结果看个位数是6，6%5 = 1。

公式转换

接着我们公式转换👇

1. 欧拉定理 👉 m^φ(n) % n ≡ 1 (m和n互质) ，并且 1^k % n ≡ 1，我们在m^φ(n) % n ≡ 1 两边各乘以1^k👇

2. 我们又知道1*m ≡ m，两边各乘以m，那么👇

⚠️注意：这种情况必须满足2个条件

1. m和n互质
2. m < n

模反元素

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

假设商为k则可以得到以下公式👇

当φ(n) == x 时，那么 e * d = k * φ(n) + 1，k * φ(n) + 1熟悉不？👇

是不是就等价于👇

验证：m：4 ， n：15， φ(15) = 8
通过模反元素，假设 e：3， d是多少？
8k + 1 = 3d --> d = (8k + 1)/3 --> k = 4 时 d = 11，k=7 时d = 19。

小结

整个推导过程如下图👇

2.1.3 迪菲赫尔曼密钥交换

上图是结合之前的例子，将数据的传递过程展示出来，基本分为以下几步👇

1. 服务端取随机数15（保密，不告诉任何人），3¹⁵%17得到的结果（6）发送给客户端。中间三方可能截获6
2. 客户端取随机数13（保密，不告诉任何人），3¹³%17得到12发送给服务端。中间三方可能截获12
3. 客户端拿到服务端发送的6进行6¹³%17得到数据10
4. 服务端拿到客户端发送的12进行12¹⁵%17也能得到10

在这个过程中客户端和服务端得到了相同的值10，单中间第三方截获的是6和12，这就是 迪菲赫尔曼密钥交换。客户端和服务端实际想交换的是数据10。

整个过程的原理如下图👇

找到了3和17的原根，这个时候就相当于进行了拆分。

2.1.4 RSA

RSA诞生

通过迪菲赫尔曼密钥交换拆分了m^e*d % n ≡ m，如下图👇

• 加密：m^e % n = c
• 解密：c^d % n = m
• 公钥：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因数分解才能算出。

这个时候就需要穷举了，很难破解。

2.2 RSA终端命令

由于Mac系统内置OpenSSL(开源加密库)，我们可以直接在终端上使用命令进行RSA操作。OpenSSL中RSA算法常用指令主要有三个👇

• genrsa 👉 生成并输入一个rsa密钥
• rsautl 👉 使用rsa密钥进行加密、解密、签名、验算等
• rsa 👉 处理rsa密钥格式转换问题

示例

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

openssl genrsa -out private.pem 1024

• 从私钥中提取公钥

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

• 将私钥转换成为明文

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

打开 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

上图中指令的过程👇

1. vi message.txt 新建message.txt文件，点击按键 i进入插入模式，输入密码:LGPerson，再点击Esc按键退出编辑模式，再输入":wq"保存退出
2. cat message.txt查看message.txt文件内容，确认密码:LGPerson写进去了
3. 使用公钥 public.pem 进行加密，生成加密文件enc.txt
4. 查看加密文件enc.txt
5. 使用私钥private.pem解密，生成解密文件dec.txt
6. 查看解密文件dec.txt

再看看文件enc.txt和文件dec.txt的大小👇

enc.txt文件128字节，dec.txt文件16字节。

• 反过来，通过私钥加密数据 & 公钥解密数据
  这个时候就变成了签名和验证了👇

签名:openssl rsautl -sign -in message.txt -inkey private.pem -out sign.txt
验证:openssl rsautl -verify -in sign.txt -inkey public.pem -pubin -out verify.txt

以上生成的所有文件的目录👇

总结

• 加密算法都是数学知识！
• 对称加密（传统加密算法，Key）
• RSA （三个人的名字）非对称加密！（现代加密算法）

  • 原根 👉 3^n^ %17 = 12，求n，此时3就是17的原根

  • 欧拉函数

    • 任意给定正整数n，在<= n的正整数之中，有多少个与n构成互质关系
    • 特点
      1. 当n是质数的时候φ(n)=n-1。
      2. 如果n可以分解成两个互质的整数之积，如n=A*B则 φ(A*B)=φ(A)* φ(B)

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

  • 费马小定理 👉 如果两个正整数m和n互质，而且n为质数！那么φ(n) = n-1 👉 m^n-1

  • 模反元素 👉 m^(e*d) mod n ≡ m

    

  • 迪菲赫尔曼密钥交换

• RSA算法
  • RSA：拆解两个（大）质数的乘积很难！所以RSA相对安全！
  • 加密 M^e mod N = C ，解密 C^d mod N = M
  • 密文 C， 明文 M， 公钥 N 和 E ， 私钥 N 和 D
  • 条件（总共有6个数字！）：
    • N 是由两个很大的质数（P1、P2）相乘得到！
    • 为了方便求出φ(N) 👉 φ(N) = (P1-1) * (P2-1)
    • D 是 E 相对于φ(N)的模反元素