RSA加密算法详解及Python实现 | Jimmy Huang’s Blog²

type

status

RSA 加密算法

一、前言

RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。

二、准备工作

1、找出两个质数 𝑝 和 𝑞

2、𝑛=𝑝×𝑞

3、𝜙(𝑛)=(𝑝−1)(𝑞−1)

4、公钥 𝑒 ：在 1<𝑒<𝜙(𝑛) 中找一个整数

* 𝑒 和 𝜙(𝑛) 互质

5、私钥 𝑑 ：通过 𝑒⋅𝑑≡1𝑚𝑜𝑑𝜙(𝑛)得到

三、加密函数

给定 𝑛 与公钥 𝑒

加密函数为：

四、解密函数

给定私钥 𝑑 及密文 𝑦 和 𝑛

解密函数为：

五、算法流程

Alice 想发送一个加密后的信息给 Bob，Alice 想发送的消息是（𝑥=4 ），Alice 对其加密后生成密文 𝑦 发送给 Bob，Bob 使用自己的私钥解密 y

六、代码实现

有一个小问题（大问题）如果加密的信息，或者算法选择到的\(e\) 的值过大时，可能会出现精度问题，导致结果错误= = 但至少按照算法的思路写出来的这个程序是能够按照算法的意思，解出答案来的主要问题就是当指数太大数，精度发生了丢失（应该）有时间再重新写一下这个程序8

运行截图