RSA算法学习

介绍：

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

RSA 算法的可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今，只有短的 RSA 密钥才可能被强力方式解破。到 2017 年为止，还没有任何可靠的攻击 RSA 算法的方式。

基本原理：

公钥与私钥的产生：

1.随机选择两个不同大质数 p 和 q，计算 N=p×q

2.根据欧拉函数，求得 φ(N)=φ(p)φ(q)=(p−1)(q−1)

3.选择一个小于 φ(N) 的整数 e，使 e 和 φ(N) 互质。并求得 e 关于 φ(N) 的模反元素，命名为 d，有 ed ≡ 1(modφ(N))

4.将 p 和 q 的记录销毁

此时，(N,e) 是公钥，(N,d) 是私钥。

消息加密：

首先需要将消息 以一个双方约定好的格式转化为一个小于 N，且与 N 互质的整数 m。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：
$$
m^e≡c(modN)
$$

消息解密：

利用密钥 d 进行解密。
$$
c^d≡m(modN)
$$