RSA详解
1.RSA思想
RSA公开密钥密码体制是一种使用不同的加密密钥和解密密钥，由“已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。
在这种体制中，加密秘钥（公钥）PK是公开信息，而解密密钥（私钥）SK是需要保密的，加密算法E和解密算法D也都是公开的，这样的话虽然SK是由PK决定的，但是不能通过PK计算出SK。
基于这种思想，在1978年出现了著名的RSA算法。
- 通常是先生成一对RSA密钥
- 其中的一个是私钥，用户保存，另一个是公钥，可对外公开，甚至可以在网络服务器中注册
- 为了提高保密强度，密钥至少为500位，一般推荐1024位
- 为了减少计算量，传送信息的时候通常采用传统加密与公开密钥加密结合的方式
算法原理：根据数论的理论，找两个大素数比较简单，对他们的乘积进行因式分解却很困难，因此可以将乘积公开作为加密秘钥
2.算法描述
- 任意选两个不同的大素数p和q计算乘积n=pq，欧拉函数n=p-1 * q-1
- 任意选一个大整数e，满足 gcd (e,欧拉n)=1，整数e用作加密钥
- 确定的解密要d 满足(de) mod 欧拉n =1 很容易计算出d
- 公开n和e 保存d
- 将明文m(m<n)加密成c 加密算法为 c=m^e mod n
- 将密文c解密为明文m 解密算法为 m=c^d mod n
通俗易懂的解释：
1.第一步 随机选择两个不相同的质数 p 和 q 比如61和53，在实际应用中，这两个质数越大，就越难破解
2.第二步 计算p和q的乘积n 上面的栗子 n=61*53=3233
这个n就是密钥，写成二进制位110010100001，一共12位，那么这个密钥长度就是12位，在实际应用中,RSA密钥长度要到1024位，才具有足够的保密性
3.第三步，计算n的φ(n)
欧拉n=p-1* q-1 上面的栗子为3120
4.第四步 随机选择一个整数e 条件为1<e<φ(n)，且e与欧拉n互质，实际应用中常用65537，我们这边随便选个17
5.计算e对于φ(n)的模反元素d
所谓模反元素就是指有一个整数d 可以让ed 被 φ(n) 除的余数为1
可以通过扩展欧几里得算法求解
6.将n和e封装成公钥，n和d封装成私钥
可靠性：能不能在已知n和e的情况下，推出d，也就是能不能在已知公钥的情况下，推出私钥？
结论：不行，需要对大整数进行因式分解，这个过程很困难，目前被破解的最长RSA密钥为768位
7.加密过程：
通过公钥(n,e)对m进行加密，m必须为整数，且m必须小于n
加密过程
m ^ e ≡ c (mod n)
8.解密过程
c ^ d ≡ m (mod n)
3.安全性描述
- 保密强度随着密钥的长度增加而增强，但是密钥越长，加解密的时间也就夜场
- RSA安全性依赖于大数分解
- 因为进行的都是大数计算，使得RSA的速度比DES慢上好几倍甚至好几十倍，因为AES这类算法通常厂商会在硬件方面进行优化，RSA一般只用于少量的数据加密，RSA的速度比对应同样安全级别的对称密码算法要慢1000倍左右