密码学：RSA（一）
密码学是指研究信息加密，破解密码的技术科学。 密码学 的起源可追溯到2000年前。相传古罗马名将凯撒大帝为了防止敌方截获情报，用密码传送情报。凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表。这样，如果不知道 密码本 ，即使截获一段信息也看不懂。
从凯撒大帝时代到上世纪70年代这段很长的时间里，密码学的发展非常的缓慢，因为设计者基本上靠经验。没有运用 数学原理 。当今的密码学是以数学为基础的。
上世纪70年代产生的一种加密算法。其加密方式比较特殊，需要两个密钥： 公开密钥 简称 公钥 （ publickey ）和 私有密钥 简称 私钥 （ privatekey ）。 公钥加密，私钥解密；私钥加密，公钥解密 。这个加密算法就是伟大的 RSA 。
要实现加密和解密，那么就应该用一种 加密容易，破解很难 的数学运算。这个时候就用到了 mod 运算（时钟算法）。
如果用质数做模数（ 17 ），找一个比这个模数小的数 3 ，那么有如下算法：
3 的 x 次方模以 17 结果永远在 1~16 之间，在这里 3 为 17 的 原根 。由于知道结果反推 x 需要一个一个实验并且不唯一，所以很难反推出原来的值。这里 模数 变大反推破解难度就很大。这就是离散对数问题。
任意给定正整数 n ，在 <= n 的正整数之中，有多少个与 n 构成互质关系？
计算这个值的方式叫做 欧拉函数 ，使用： φ(n) 表示
根据以上两点得到： 如果 N 是两个互质数 P1 和 P2 的乘积则:
φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)
如果两个正整数 m 和 n 互质，那么 m 的 φ(n) 次方减去 1 ，可以被 n 整除。
欧拉定理的特殊情况：如果两个正整数 m 和 n 互质，而且 n 为质数！那么 φ(n) 结果就是 n-1 。
欧拉定律 m φ(n) % n ≡ 1 (m和n互质)
由于 1 k % n ≡ 1 ，可以得到：
由于 1*m ≡ m ，可以得到：
验证：
⚠️ 注意：换算的过程中， m 要小于 n 才会成立 。大于则相当于多饶了一圈。
如果两个正整数 e 和 x 互质，那么一定可以找到整数 d ，使得 ed-1 被 x 整除。
那么: d 就是 e 对于 x 的 模反元素
则可以得到以下公式：
假设商为 k 则可以得到以下公式：
当 φ(n) 为 x 时，则：
验证：M：4 ， N：15， φ(n): 8 。
通过模反元素假设 E：3， D？
3d -1 = 8k 则 d = (8k + 1)/3 k = 4 则 D = 11，k=7 则 d = 19
整个推导过程如下：
解决密钥传递的保密性问题
原理：
通过 迪菲赫尔曼密钥交换 拆分了m e*d % n ≡ m。
总共生成 6 个数字： p1、p2、n、φ(n)、e、d
验证
M ：3 、12 ，N： 3 * 5 = 15，φ(n)：8，
假设E：3，则通过模反元素计算得到 D：11，19
除了公钥用到了 n 和 e 其余的 4 个数字是不公开的。
目前破解 RSA 得到 d 的方式如下：
1、要想求出私钥 d 。由于 e*d = φ(n)*k + 1 。要知道 e 和 φ(n) ;
2、 e 是知道的，但是要得到 φ(n) ，必须知道 p1 和 p2 。
3、由于 n = p1*p2 。只有将 n 因数分解才能算出。
这个时候就需要穷举了，很难破解。
RSA 由于 m 要小于 n ，所以每次加密数据小，需要分段加密，效率不高。一般情况下用来加密大数据对称加密的 key 。
由于 Mac 系统内置 OpenSSL (开源加密库)，我们可以直接在终端上使用命令进行 RSA 操作。 OpenSSL 中 RSA 算法常用指令主要有三个：
生成RSA私钥,密钥长度为1024bit
e:65337(publicExponent)
通过公钥加密数据,私钥解密数据
加密：
解密：
完整命令:
enc.txt 文件 128 字节， dec.txt 文件 20 字节。
通过公钥加密数据,私钥解密数据
这个时候就变成了签名和验证了。
签名:
验证:
整个文件目录如下：
