一、RSA
1、密钥生成
- 生成两个保密的大素数p, q
- n = pq;
- n的欧拉函数φ(n) = ( p – 1 )( q – 1 );
- 取一个数作为公钥e，直接取(1, φ(n) )之间的一个整数，而且gcd( e , φ(n) )=1；
- 我们由公钥e和欧拉函数值求出私钥d: d * e = 1 (mod φ(n) )
ed之间的关系：二者为欧拉函数下的乘法逆元，e和欧拉函数之所以互素是为了保证逆元存在。
乘法逆元的性质在于：
2、加解密算法
注意一下明文预处理：
将铭文比特串分组，每一组十进制数小于n，所以length（分组）<= log2(n)
加密：记分组为m，则密文c = m^d (mod n)
解密：m’ = c^e (mod n)
二、Rabin密码机制
rabin宏观上和RSA的区别在于：
1）RSA的攻击破解在于难度等同或不超过大整数分解困难问题，但是Rabin是和大整数破解直接等价的，所以一定是一样困难的。
2）同时Rabin也不是单项陷门，所以同一密文可能有好几个明文对应。
1、密码生成
- e = 2（其实就是算法的一部分，也可以不看成密钥）
- 也取两个大素数p, q，但是要满足p=q=3 (mod 4)。
- n = pq，并直接公开（p，q保密）
- 所以n是公钥，p,q为私钥
2、加解密
加密：c = m^2 ( mod n )
解密：求四个方程组，得到四个不同的解，m中依靠特定信息使接收方有效的确定明文。
