算法——RSA

RSA算法

公钥加密系统
通过公钥加密系统，可以对传输于两个通信单位之间的消息进行加密，使窃听者即使得到被加密的信息也无法进行破译。公钥加密系统还能让通信的一方，在电子消息的末尾附加一个无法伪造的数字签名，这种签名是纸质文件上的手写签名的电子版本。任何人都可以轻松核对却不能伪造。数字签名可以为签名者身份和其签署的信息内容提供证明。

在公钥加密系统中，每个参与者都有一把公钥和一把私钥，在RSA加密系统中，每个私钥由一对整数组成。每个参与者都有自己的公钥和私钥

假设S为私钥，P为公钥，M为属于允许信息集合的一组信息
则有：M=S（P（M））
相应的，也有：M=P（S（M））
同样的，数字签名也可以通过S（）函数加密，与所传信息放在一起，便于接收方确认身份。

RSA加密系统

RSA公钥加密系统基于：寻找大素数是容易的，但要把一个数分解成两个大素数的积却是相当困难的。

• 随机选取两个大素数p，q（p！=q）
• 计算n=pq
• 选取一个与φ(n)=(p-1)(q-1)互质的小奇数e
• 对模m，计算出e的乘法逆元d的值

例如，求3关于模14的乘法逆元：
1=3-2=3-(14-34)=35-14
因此，3关于模14的乘法逆元为5。

• 相关算法：

密文=（明文^e）%n
明文=（密文^d）%n

• P=（e,n）公开，作为参与者的RSA公钥
• S=（d,n）保密，作为参与者的RSA私钥

RSA在HTTPS中的应用

• HTTP：超文本传输协议HTTP协议用于在Web浏览器和网站服务器之间传递信息，以明文方式发送内容，不提供任何形式的加密。因此不适宜传输敏感信息

• HTTPS=HTTP+SSL：在HTTP的基础上加入SSL协议。他并不是绝对安全，只是大幅增加了中间人攻击的成本。

  
  客户端与服务器交互流程.png

SSH远程登录

• 口令登录
  输入远程主机的密码，正确就可以成功登录了
  客户端首先发出登录请求，服务器返回一个公钥，客户端使用公钥对登录密码进行加密，传输给服务器后，服务器使用私钥对登录密码解密然后核对。
• 公钥登录
  在本机生成密钥对并将公钥复制到远程主机
  客户端发出登录请求之后，服务器随机发送一段字符串，客户端使用自己的私钥加密之后返回给服务器，服务器使用存储的客户端的公钥进行解密，解密成功则登录成功。

参考资料：
[1] 算法导论
[2] RSA与SSL浅析

附加材料：（留几篇好文）
[1]跨越千年的RSA算法
[2]浅谈HTTPS以及Fiddler抓取HTTPS协议