背景
最近读到了阮一峰介绍的的RSA算法原理，本文作为对这篇文章的简单批注。
一、非对称加密算法
对称加密算法的加密与解密过程采用相同的密钥，在这种情况下，往往需要传输密钥，一旦密钥被拦截，就会暴露所传递的信息。
非对称加密算法包含一对密钥，称为公钥和私钥，私钥由密钥所有者保存，不必公开，公钥可以公开。非对称加密算法既可以用于加密也可用于签名。
当用于加密时，消息发送者使用接收者的公钥对消息进行加密，然后将密文传输给接收者，接收者使用对应的私钥对密文进行解密即可得到原始消息。由于经公钥加密的密文只能由对应的私钥进行解密，只要不暴露私钥，就可以安全地传输消息。而非对称加密算法都采用了十分安全的算法保证攻击者难以通过公钥推算私钥，因此可以安全地公开公钥。
当用于签名时，私钥持有者使用自己的私钥对消息的摘要进行签名，然后将消息和摘要的签名一并发送给接收者，接收者可以利用对应的公钥对签名进行解密，并将解密结果与消息摘要进行比对，以确定消息是否被篡改。
二、互质关系
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。
关于互质关系，不难得到以下结论：
1. 任意两个质数构成互质关系，比如13和61。
2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
4. 1和任意一个自然数是都是互质关系，比如1和99。
5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。
6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。
上述结论中1-4均显而易见，下面对第5点进行证明：
假设p和p-1存在公因子k，k为正整数，则：
(1) p = mk，m为正整数
(2) p-1 = nk，n为正整数
由(1)(2)可得：(3) (m-n)k = 1
由于m，n均为正整数，则m-n也为整数，记为a=m-n
则 ak=1，由于a和k均为整数，且k>0，可得a=k=1
上述结论说明，p与p-1的公因子k只能为1，即p与p-1互质
下面对第6点进行证明：
假设p和p-1存在公因子k，k为正整数，则：
(1) p = mk，m为正整数
(2) p-2 = nk，n为正整数
由(1)(2)可得：(3) (m-n)k = 2
由于m，n均为正整数，则m-n也为整数，且k>0
则可得两组解：
解(1): m-n=1,k=2
解(2): m-n=2,k=1
由于p为奇数，则因子k不能为偶数，第一组解不成立
故只能使用第二组解，可得p和p-2的公因子k为1，p和p-2互质
不写了
需要学的东西还很多，有一些阮一峰未介绍的转换细节，参考RSA算法的数学原理与证明吧，写不动了，太菜了，总是RSA算法很NB，需要用到大量数论知识