密码学

密码学是指研究信息加密，破解密码的技术科学。密码学的起源可以追溯到2000年以前。而当今的密码学是以数学为基础的。

密码学的历史大致可以追溯到两千年前，相传古罗马名将凯撒大帝为了防止敌方窃取情报，用密码传送情报。凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表。这样，如果不知道密码本，即使解惑一段信息也看不懂。从凯撒大帝时代到上世纪七十年代这段很长的时间里，密码学的发展非常缓慢，因为设计者基本上靠经验。没有运用数学原理。

• 在1976年以前，所有的加密方式都是同一种模式：加密、解密使用同一种算法。在交互数据的时候，彼此通信的双方就必须将规则告诉对方，否则没法解密。那么对加密解密规则（密钥）的保护就尤为重要。传递密钥就成了最大的隐患。这种加密方式被称为对称加密算法（symmetric encryption algorithm）
• 1976年，两位美国科学家迪菲（W.Diffie）、赫尔曼（ M.Hellman ） 提出了一种崭新构思，可以在不直接传递密钥的情况下，完成密钥交换。这被称为迪菲赫尔曼密钥交换 算法，开创了密码学研究的新方向。

• 1977年三位麻省理工学院的数学家罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir） 和 伦纳德·阿德曼（Leonard Adleman） 一起设计了一种算法，可以实现非对称加密。这个算法用他们三个人的名字命名，叫做RSA算法 。

RSA数学原理

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

互质关系

如果两个数除了1之外没有其它公约数，我们就称两个数是互质关系。比如3和17，又比如15和32，不是质数也可以形成互质关系。

欧拉函数

思考以下问题🤔

给定任意正整数n，请问在小于等于n的正整数中，有多少个构成互质关系？（比如1到8之中，有多少个数与8构成互质关系）

计算这个值得方法叫做欧拉函数，用φ(n) 表示，在1到8之中，与8形成互质关系的是1、3、5、7共4个，所以

φ(8) = 4
复制代码

欧拉定理

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

费马小定理

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

模反元素

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

// 认为k是ed/x的商
e*d  mod  x ≡  1
e*d ≡  k*x + 1 
复制代码

比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果b是a的模反元素，则 b+kn 都是a的模反元素

公式转换

RSA实现步骤

以上理论理解起来很费劲，我们通过一个例子来走一遍流程，然后再回头去看上面的公式们或许理解起来会容易一些

1. 寻找两个不相等的质数p和q

我们可以选择61和53，实际应用中，这两个质数越大，就越难破解。

2. 计算p和q的乘积n

61 * 53 = 3233
复制代码

3. 计算n的欧拉函数φ(n)

φ(n) = (p-1)(q-1)
复制代码
φ(3233) = (61-1)(53-1) = 3120
复制代码

4. 随机选择一个整数e，条件是1 < e < φ(n)且 e和φ(n)互质

我们可以在1到3120中随机选择17，实际应用中通常选择比较大的数

5. 计算e和φ(n)的模反元素

所谓模反元素就是值一个整数d，可以使得ed被φ(n)除的余数为1

ed mod φ(n) ≡ 1 
复制代码
17d mod 3120 ≡ 1 
复制代码

d=2753满足条件

6. 将n和e封装成公钥，n和d封装成私钥

所以公钥就是(3233,17)，私钥就是(3233,2753)

7. 加密和解密

公钥加密公式为

m的e次方 mod n ≡ c 
复制代码

私钥解密公式为

c的d次方 mod n ≡ m
复制代码

假如我想将65发送给服务器，那么加密流程为

65的17次方 mod 3233 = 2790
复制代码

将2790发送给服务器，相当于c，然后服务器利用私钥解密

2790的2753次方 mod 3233 = 65
复制代码

神不知鬼不觉的就将值65传递给了服务器

对于浏览器来说公钥是公开的，服务器私钥加密没有意义，谁都可以拿到公钥来解密，RSA只解决了客户端利用公钥加密之后安全传递给服务器的问题，这就足够客户端和服务器制定新的加密规则，后续使用他们新制定的规则继续通讯，也就是对称加密算法
对于app来说公钥也可以是不公开的，那么app使用公钥加密传递给服务器、服务器使用私钥加密将数据传递给客户端都是相对安全的

8. RSA算法的可靠性

回顾以上流程我们共生成了6个数字 p、q、n、φ(n)、e、d，其中公钥用到了e、n，私钥用到了d、n，其余四个是不公开的，其中关键的是d，一旦d泄露那么黑客就可以完成解密，那么在已知公钥n、d的情况下有没有可能推导出d呢？

1. ed mod φ(n) ≡ 1
2. φ(n) = (p-1)(q-1)
3. n=pq

只有将n因式分解，才能计算出p和q，但是因式分解是一件非常困难的事儿，目前除了暴力破解还没有发现别的有效方法，所以RSA算法目前来说是相对安全的，秘钥长度越长因式分解难度就越大，也就越安全

终端演示

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

• 新建文件夹命名为rsaTest终端进入目录

• 生成RSA私钥，秘钥长度为1024bit

openssl genrsa -out private.pem 1024
复制代码

• 从私钥中提取公钥

openssl rsa -in private.pem -pubout -out public.pem
复制代码

• 将私钥转化为明文信息并查看

openssl rsa -in private.pem -text -out private.txt
复制代码

• 查看private.txt信息

cat private.txt
复制代码

• 新建文本文件message.txt

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.txt
复制代码

• 通过私钥进行加密

openssl rsautl -sign -in message.txt -inkey private.pem -out enc.txt
复制代码

• 通过公钥进行解密

openssl rsautl -verify -in enc.txt -inkey public.pem -pubin -out dec1.txt
复制代码

###

作者：理查德森 链接：https://juejin.cn/post/6950239582092787748 来源：掘金 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。