最近在研究比特币，比特币的交易签名算法就是使用了类似与RSA的非对称加密算法。毫不夸张地说有，有互联网的地方就有RSA的身影。非对称加密的原理比较好理解，生成一对密钥，公开出去的叫公钥，自己保留的叫私钥。你要给我发送信息，为了不让别人拦截你的信息后能知道消息的内容，你需要将你的信息用我给你的公钥加密。我收到消息后，用私钥解密之后就能得到你的消息原文了。
RSA的原理比较复杂，我花了好几天才勉强理解了个大概(数论学得太差)。
首先要理解几个数学概念：
- 互质关系：这个估计不用多说，两个数除了1没有其他的公约数就算互质关系。
- 欧拉函数：欧拉函数是求有多少个数与n满足互质关系的一个方程式的通解公式。
- 中国剩余定理：用于求解同余方程。
- 欧拉定理：这个太难解释，下次有图片了再解释。
- 费马小定理：欧拉定理的特殊形式。(其中一个模数为质数)
- 模反元素：对于abn三个数满足 ab ≡1 (mod n) ，我们称b为a对n的模反元素。
公钥和私钥怎么来？
- 寻找两个质数 p 和 q。
- 求乘积 n = p * q。
- 求解n的欧拉函数：φ(n) = (p-1)(q-1)
- 随机挑选一个整数，满足 1 < e < φ(n)，且e与φ(n)是互质关系
- 求 e 对于 φ(n) 的模反元素为d。
- 其中(n, e)是公钥，(n, d)就是私钥
加密的过程：
求出 c 的值，使其满足 m^e ≡ c (mod n) {其中m是密码原文，c就是传输用的密文}
解密的过程:
求出m的值，使其满足c^d ≡ m (mod n) {其中m就是密码的原文，c是等待被解密的密文}
RSA还是听常用的，最近在工作上老是碰到加密相关的事情。