非对称加密算法

　　如果要给世界上所有算法按重要程度排个序，那我觉得公钥加密算法一定是排在最前边的，因为它是现代计算机通信安全的基石，保证了加密数据的安全。
　　01对称加密算法
　　在非对称加密出现以前，普遍使用的是对称加密算法。所谓对称加密，就是加密和解密是相反的操作，对数据进行解密，只要按加密的方式反向操作一遍就可以获得对应的原始数据了，举一个简单的例子，如果要对字符串abc进行加密，先获取它们的ANSCII码为：979899；密钥为2，加密后的数据就是：99100101，将密文数据发送出去。接收方收到数据后对数据进行解密，每个数据减2，就得到了原文。当然这只是一个非常简单的例子，真实的对称加密算法会做得非常复杂，但这已经能够说明问题了。
　　这样的加密方法有什么缺点呢？首先缺点一：密钥传递困难；想想看如果两个人，分别是Bob和Alice，Bob要给Alice发消息，那Bob就要把密钥通过某种方式告诉Alice，有什么可靠的途径呢？打电话、发邮件、写信。。。等等方式好像都不靠谱，都有被窃取的风险，也只有两人见面后当面交流这一种方式了；缺点二：密钥数量会随着通信人数的增加而急剧增加，密钥管理将会是一个非常困难的事情。
　　02非对称加密算法
　　1976年，两位美国计算机学家，提出了DiffieHellman密钥交换算法。这个算法的提出了一种崭新的构思，可以在不直接传递密钥的情况下，完成解密。这个算法启发了其他科学家，让人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应的关系即可，这样就避免了直接传递密钥。这种新的加密模式就是非对称加密算法。
　　算法大致过程是这样的：
　　（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
　　（2）甲方获取乙方的公钥，然后用它对信息加密。
　　（3）乙方得到加密后的信息，用私钥解密。
　　如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
　　03RSA非对称加密算法
　　1977年，三位数学家Rivest、Shamir和Adleman设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。
　　从那时直到现在，RSA算法一直是最广为使用的非对称加密算法。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。
　　公钥加密私钥解密
　　只有私钥持有方可以正确解密，保证通信安全
　　私钥加密公钥解密
　　所有人都可以正确解密，信息一定是公钥所对应的私钥持有者发出的，可以做签名
　　04质数的前置知识
　　RSA的安全性是由大数的质因数分解保证的。下面是一些质数的性质：
　　1、任意两个质数构成素质关系，比如：11和17；
　　2、一个数是质数，另一个数只要不是前者的倍数，两者就构成素质关系，比如3和10；
　　3、如果两个数之中，较大的那个是质数，则两者构成互质关系，比如97和57；
　　4、1和任意一个自然数都是互质关系，比如1和99；
　　5、p是大于1的整数，则p和p1构成互质关系，比如57和56；
　　6、p是大于1的奇数，则p和p2构成互质关系，比如17和15
　　05RSA密钥生成步骤
　　举个栗子，假如通信双方为Alice和Bob，Alice要怎么生成公钥和私钥呢？
　　Step1：随机选择两个不相等的质数p和q；
　　Alice选择了3和11。（实际情况中，选择的越大，就越难破解）
　　Step2：计算p和q的乘积n；
　　n31133，将33转化为二进制：100001，这个时候密钥长度就是6位。
　　Step3：计算n的欧拉函数（n）；
　　因为n可以写为两个质数相乘的形式，欧拉函数对于可以写成两个质数形式有简单计算方式
　　（n）（p1）（q1）
　　Step4：随机选择一个整数e，条件是1e（n），且e与（n）互质；
　　爱丽丝就在1到20之间，随机选择了3
　　Step5：计算e对于（n）的模反元素d
　　所谓模反元素，就是指有一个整数d，可以使得ed被（n）除的余数为1
　　Step6：将n和e封装成公钥，n和d封装成私钥；
　　在上面的例子中，n33，e3，d7，所以公钥就是（33，3），私钥就是（33，7）。
　　密钥生成步骤中，一共出现了六个数字，分别为：
　　素质的两个数p和q，乘积n，欧拉函数（n），随机质数e，模反元素d
　　这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的，可以删除。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。
　　那么，有无可能在已知n和e的情况下，推导出d？
　　（1）ed1（mod（n））。只有知道e和（n），才能算出d。
　　（2）（n）（p1）（q1）。只有知道p和q，才能算出（n）。
　　（3）npq。只有将n因数分解，才能算出p和q。
　　结论是如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。
　　BUT！
　　大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。
　　维基百科这样写道：
　　对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
　　假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有较短的RSA密钥才可能被暴力破解。到现在为止，世界上还没有任何可靠的攻击RSA算法的方式。
　　只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。
　　06RSA加密和解密过程
　　1、加密要用公钥（n，e）
　　假设鲍勃要向爱丽丝发送加密信息m，他就要用爱丽丝的公钥（n，e）对m进行加密。
　　所谓加密，就是算出下式的c：
　　爱丽丝的公钥是（33，3），鲍勃的m假设是5，那么可以算出下面的等式：
　　于是，c等于26，鲍勃就把26发给了爱丽丝。
　　2、解密要用私钥（n，d）
　　爱丽丝拿到鲍勃发来的26以后，就用自己的私钥（33，7）进行解密。下面的等式一定成立（至于为什么一定成立，证明过程比较复杂，略）：
　　也就是说，c的d次方除以n的余数为m。现在，c等于26，私钥是（33，7），那么，爱丽丝算出：
　　因此，爱丽丝知道了鲍勃加密前的原文就是5。
　　至此，加密和解密的整个过程全部完成。整个过程可以看到，加密和解密使用不用的密钥，且不用担心密钥传递过程中的泄密问题，这一点上与对称加密有很大的不同。由于非对称加密要进行的计算步骤复杂，所以通常情况下，是两种算法混合使用的。
　　07一些其它的
　　在Part5的第五步，要求一定要解出二元一次方程的一对正整数解，如果不存在正整数解，这该怎么办？
　　扩展欧几里得算法给出了解答：
　　对于不完全为0的非负整数a，b，gcd（a，b）表示a，b的最大公约数，必然存在整数对x，y，使得gcd（a，b）
　　第五步其实等价于：edk（n）1，e与（n）又互质，形式上完全与扩展欧几里得算法的一致，所以一定有整数解存在。
　　Reference：
　　http：www。ruanyifeng。comblog201307rsaalgorithmparttwo。html