【数据结构与算法】之深入解析RSA加密算法的实现原理

一、密码学历史

密码学的历史大致可以追溯到两千年前，相传古罗马名将凯撒大帝为了防止敌方截狱情报，用密码传送情报。凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表，这样，如果不知道密码本，即使截获一段信息也看不懂。从凯撒大帝时代到上世纪70年代这段很长的时间里，密码学的发展非常的缓慢，因为设计者基本上靠经验，没有运用数学原理。1976 年以前，所有的加密方法都是同一种模式： 甲方选择某一种加密规则（简称密钥），对信息进行加密； 乙方使用同一种规则，对信息进行解密。 由于加密和解密使用同样规则（简称“密钥”），这被称为“对称加密算法”（Symmetric-key algorithm）。这种加密模式有一个最大弱点：甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥，就成了最头疼的问题。1976 年，两位美国计算机学家迪菲（W.Diffie）、赫尔曼（ M.Hellman）提出了一种崭新构思，可以在不直接传递密钥的情况下，完成密钥交换，这被称为“Diffie-Hellman密钥交换算法（迪菲赫尔曼密钥交换）”，开创了密码学研究的新方向。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了