非对称加密算法

前言

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

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

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