前言

目前主流的非对称加密算法主要有几类：RSA、DHKE、Elliptic Curve。

虽然大类分成这几类，实际上他们底层的原理都是依赖于素数和同余原理来做的。素数是除了他本身和1以外，无法被其他任何正整数整除的数字。这样的数字有多少呢？无穷个。我们知道，一个数字的因式分解，最终都能分解成n个素数的相乘，由于素数有无穷多个，也就意味着一些巨大的数是很难分解的，特别是两个大的素数（例如几百位、上千位）的乘积就更难因式分解了，催生了很多在理论上不可行，但在经济上可行的加解密算法。为什么说是理论上不可行呢？因为数字再大，只要有恒心（例如几百年、上千年甚至几百亿年）总能把一个大数因式分解，也就是基本假设不成立，一旦能因式分解，所有的这类密码都将被破解。经济上可行是因为，因式分解一个这样的大数字花费的经济成本（计算机、电力等）太高，以至于不会有人去尝试暴力破解。当然，据说有可以破解这类的量子算法，基于量子计算机多维度并发计算，还是有机会的。目前量子计算机造价昂贵且还没有大规模商用，用于破解这类的密码成本也是相当高的，暂时还是安全的。对应的策略是，a：发明后量子加密算法，在量子计算机流行之后也能用后量子算法来加解密，保障量子计算机破解不了这类的密码；b：用量子纠缠实现通信，可以完全杜绝中间人攻击，此时密钥不是最重要的了。目前美国为主的西方国家主要在主导后量子密码学，而我国科学家更多在主导量子通信。

下面我会用相对易懂的预言推导一下这几类算法的原理，一些不太好理解的定理，不会太深入去推导。