RSA加密(上)
2021-05-15 本文已影响0人
浅墨入画
一. 密码学概述
密码学
密码学是指研究信息加密，破解密码的技术科学。密码学的起源可追溯到2000年前。而当今的密码学是以数学为基础的。
密码学发展史
- 在1976年以前，所有的加密方法都是同一种模式：加密、解密使用同一种算法。在交互数据的时候，彼此通信的双方就必须将规则告诉对方，否则没法解密。那么加密和解密的规则（简称密钥），它保护就显得尤其重要。传递密钥就成为了最大的隐患。这种加密方式被成为对
称加密算法（symmetric encryption algorithm） - 1976年，两位美国计算机学家 迪菲（W.Diffie）、赫尔曼（ M.Hellman ） 提出了一种崭新构思，可以在不直接传递密钥的情况下，完成密钥交换。这被称为
“迪菲赫尔曼密钥交换”算法。开创了密码学研究的新方向 - 1977年三位麻省理工学院的数学家 罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起设计了一种算法，可以实现非对称加密。这个算法用他们三个人的名字命名，叫做RSA算法。
二. 离散对数问题
上世纪70年代产生的一种加密算法。其加密方式比较特殊，需要两个密钥：公开密钥简称公钥（publickey）和私有密钥简称私钥（privatekey）。公钥加密，私钥解密；私钥加密，公钥解密。这个加密算法被称为的RSA
加密算法的核心思想：加密容易，破解很难，我们可以利用数学运算，如mod取模(西方被称为时钟算数)
- 用质数做模数，例如17
- 找一个比17小的数作为n次方的基数，例如3
- 找出基数的n次方 mod 质数 = 固定的数，求n
3^? mod 17 = 12，此时的？是多少呢？
从下图可以看出，3的1次方~16次方 mod 17 得到的结果不同，且结果分布在 [1,17)上，我们将 3 称为 17 的原根
image.png
// 终端进入python环境进行取模计算
$ python
>>> 3**17 % 17
3
>>> 3**18 % 17
9
通过上面计算，我们发现3^17 mod 17 = 3，由此可知3^? mod 17 = 12?有无数种结果，可能是13，也可能是29等。结论：通过 12 去反推3的?次方是很难的。如果质数加大，反推的难度也会加大，这就是离散对数问题
三. 欧拉函数&欧拉定理
思考一
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？
计算这个值的方式叫做欧拉函数，使用：Φ(n)表示(读 fai n)
计算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 = A * B，则
Φ(A * B) = Φ(A) * Φ(B)
根据欧拉函数的以上两个特点，得到如下结论： - 如果N是两个互质数P1和P2的乘积，则
Φ(N) = Φ(P1 * P2) = Φ(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
举例 m=6，n=5，那么6^(5-1) mod 5 = 1
公式转换
- 例如：
m=6，n=7，则6^(7-1) mod 7 = 1->6^(6*2) mod 7 = 1 - 例如：
m=6,n=7,则6^(6*3+1) mod 7 = 6
四. 模反元素
如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除，即(ed - 1)/x = 1。那么d就是e对于x的模反元素
模反元素推导公式
m ：4
n ：15
Φ(n)：8
e：(和Φ(n)互质) 3 也可以是5，这里使用3
d：3d-1=8k -> d=(8k+1)/3 -> d=11 19
$ python
>>> 4**(3*11)%15
4
>>> 4**(3*19)%15
4
五. RSA最终原理
迪菲赫尔曼密钥交换
image.png
- 服务端先取一个随机数15，通过 3^15 mod 17 = 6，将6传给客户端（第三方可以窃取这个6）
- 客户端通用的取一个随机数13，通过3^13 mod 17 = 12，将12传给服务器（第三方同样可以窃取这个12）
- 客户端拿到服务器传过来的6，通过6^13 mod 17 = 10，得到10
- 服务端拿到客户端传过来的12，通过12^15 mod 17 = 10，得到10
综上所述，服务端和客户端实际想交换的数字是 10
迪菲赫尔曼密钥交换
经过两次计算，客户端和服务端得到一个相同的数字，用于数据传输
- 客户端：
3 ^ 15 mod 17 = 6+6^13 mod 17 = 10->3 ^ (15 * 13) mod 17 = 10 - 服务端：
3 ^ 13 mod 17 = 12+12^15 mod 17 = 10->3 ^ (13 * 15) mod 17 = 10
RSA的诞生
RSA诞生原理
由上面的迪菲赫尔曼密钥交换原理以及模反元素公式可得到RSA加解密原理
需要注意的是：d是 e 相对于 φ(n)的模反元素，m和 n既为互质，m也是n的原根。
RSA算法
RSA算法的加解密公式为：
- 加密：
m^e mod n = c - 解密：
c^d mod n = m - 公钥：
n和e - 私钥：
n和d - 明文：
m - 密文：
c
其中涉及的公钥、私钥、密文、明文有如下说明
- n会非常大，长度一般为1024个二进制位（目前人类已经分解的最大整数，232个十进制位，768个二进制位）
- 由于需要求出φ(n)，所以根据欧拉函数特点，最简单的求解φ(n)方式：n由两个质数相乘得到 质数：
p1、p2
Φ(n) = (p1 -1) * (p2 - 1) - 最终由 Φ(n) 得到 e 和 d
总共生成6个数字：p1、p2、n、Φ(n)、e、d
RSA加密算法演示
m：取值 3 或 12
n：3*5=15（两个质数相乘）
φ(n) = （3-1）*（5-1）= 8
e：3（e和Φ(n)互质）
d：3d-1=8k -> d = 11 / 19（由公式 e * d mod x = 1 求解）
加密：`m^e mod n = c` -> 3^3 mod 15 = 12
解密：`c^d mod n = m` -> 12^11 mod 15 = 3
关于RSA的安全说明
除了公钥用到了n和e其余的4个数字是不公开的。目前破解RSA得到d的方式如下：
- 要想求出私钥
d。由于e*d = φ(n)*k + 1。要知道e和φ(n); - e是知道的，但是要得到 φ(n)，必须知道
p1和p2。 - 由于
n=p1*p2。只有将n因数分解才能算出。
RSA效率不高，因为是数学运算，且m不能大于n，大数据不适合用RSA加密，一般用对称加密（对称加密需要用到key）
- 对称加密的
key使用RSA加密，大数据使用对称加密算法 - 接收到传递过来的大数据时，需要先使用
RSA解密拿到key，在使用key解密大数据
六. RSA终端演示
由于Mac系统内置OpenSSL(开源加密库),所以我们可以直接在终端上使用命令来玩 RSA。OpenSSL中RSA算法常用指令主要有三个：
| 命令 | 含义 |
|---|---|
| genrsa | 生成并输入一个RSA私钥 |
| rsautl | 使用RSA密钥进行加密、解密、签名和验证等运算 |
| rsa | 处理RSA密钥的格式转换等问题 |
终端演示RSA加密算法
$ cd /Users/wn/Documents/资料/密码学-RSA/加密
// 生成RSA私钥，密钥长度为1024bit
$ openssl genrsa -out private.pem 1024
Generating RSA private key, 1024 bit long modulus
......++++++
.......++++++
e is 65537 (0x10001)
// 查看私钥，发现是base64编码
$ cat private.pem
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQDmay8wCseKDSO1XmJ+792IUrNXkAeLtzuwlJDTyEJCbKAUWtBb
RLvzJaygTBflBCPku8XrJY2ZeB/8nDSBIDmkgKiYeMMaGn/GRMKZtuVc9oJkCcaB
s76P4qpD0DRm4+GZzY9LOSwhsnXFtVRbbIlXT2BJ2BPc3LTbZ3i4cKiv9QIDAQAB
AoGAX2gCIeJUvNSz9GUgY27uS4Pyvk7k0PUNwg/B5+8DgH15yvPPUfsj14nB8J2R
R0JvmkYlrTffaaxTkkUbeFvfgXRncmhoQ3HdTjws0jXYR/8JT6ZBl2Nzq7XUPLdv
E3NQFoiicnjTYBclhTnZWw7FttukvshUzw2d+J8GFZAhwAECQQD+3y+6LKHKeTGA
giBJT9ODFE9/vz9pLd+wZBBAORziTc7DH8gnXRZ86hLxlW3aRwMeP4IzeyeG4+Jo
qBOhMiktAkEA53BJzW41DBgW8PpNBoqweeiB+irnYDJbRs2S2TqVJ0ef8Iofyxyy
DaTKBA+i7bk4GocsDELAe23lGWStDbvO6QJADqtR1+lRtpGbI8ZZjV6m0diNatDb
GXamdUSNGuUuoGfSCrD9mCZncPEX/geXtwR3TXpiSAxCjiT3lwZ1esWkUQJBAMl4
k5a0uJMlqVrv2fu24ffN8tAvZynzzEevj4VxHQSLsmy4IQM0oL+F06KDZich1Pgq
8apetab9PLHFVWyeMHkCQER10jqwB/ttSpALyKUAp5jYAsscSEmosgY+k2ghuMJK
rsTLRKAtcvPg7HCsUpZRXUyBX7PfPlHJYeArCij4qeY=
-----END RSA PRIVATE KEY-----
// 从私钥中提取公钥（即 n和e）
$ openssl rsa -in private.pem -pubout -out public.pem
writing RSA key
// 查看公钥，公钥要比私钥小很多
$ cat public.pem
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDmay8wCseKDSO1XmJ+792IUrNX
kAeLtzuwlJDTyEJCbKAUWtBbRLvzJaygTBflBCPku8XrJY2ZeB/8nDSBIDmkgKiY
eMMaGn/GRMKZtuVc9oJkCcaBs76P4qpD0DRm4+GZzY9LOSwhsnXFtVRbbIlXT2BJ
2BPc3LTbZ3i4cKiv9QIDAQAB
-----END PUBLIC KEY-----
// 将私钥转换为明文
$ openssl rsa -in private.pem -text -out private.txt
writing RSA key
// 查看私钥明文信息
$ cat private.txt
Private-Key: (1024 bit)
modulus:
...
公钥和私钥
// 通过公钥加密数据，私钥解密数据
$ vi message.txt
$ cat message.txt
密码：123456
// 使用公钥对message.txt文件进行加密，密文放入enc.txt文件
$ openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt
// 可以发现加密之后的enc.txt文件打不开，是一个二进制文件
$ cat enc.txt
v���Z�H�W��K?͑Y�jm]Ԃ|wn�����P�Km`����&���Z�G�`�@}-��r[�iK�t'��\$�ⴾK;NU{��}���
�-z6��p`a�P��B�%���Ҷ�-OG��"hello-world:加密
// 使用私钥对enc.txt文件进行解密
$ openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.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.txt - 公钥解密（验证）：
openssl rsautl -verify -in enc.txt -inkey public.pem -pubin -out dec.txt
总结
- 对称加密（传统加密算法）：公钥、私钥采用同一个key
- RSA非对称加密（现代加密算法）：加解密原理来源迪菲赫尔曼密钥交换
- RSA原理：拆解两个（大）质数的乘积很难，所以RSA相对安全
