小学时学过的质数
小学数学课上我们都学过质数，也叫素数，就是大于1的整数，除了1和它自身外没有别的因子。很明显4不是质数，因为4=1×4=2×2，除了1和它本身外，2也是它的因子。
“质数”是咱们中国的称呼，老外那边叫“prime number”。
那么，小学时学的“质数”到底有什么用？什么时候用呢？
我们每天都在用质数
其实我们每天上网的时候都会用到质数，比如上百度，淘宝，京东，微博、拼多多等网站时。（如果你是使用Git的程序员的话，就更会用到质数-SSH公钥体系）
“上网时没有用质数啊”这应该是大多数人的想法。不过，你确实用了。这些网址的开头都是“https”，在你登录这些网站的时候，浏览器和网站之间的信息传输就用到了质数进行加解密。小学数学老师没告诉我们，但这是真的。
不光人类使用质数，动物也会使用质数。
懂数学的蝉
其实动物对质数的应用要早于人类，最有名的例子就是北美的周期蝉。周期蝉有两种，13年蝉和17年蝉（注意，都是质数）。以美国乔治亚州的17年蝉为例，2000年的时候出现过一次，再次出现就是2017年（从2002~2016年间没有出现），下一次就是2034年......很奇怪的一个现象。
为这么周期蝉总是间隔质数年后出现？科学家猜测其原因是：避开周期性出现的天敌。蝉的天敌也有周期，如果生命周期不是质数，和天敌周期重合的概率就会大很多。假设蝉的周期是12年，就会和周期为2、3、4、6年的天敌重合。所以有些人把周期蝉称为懂数学的蝉。
但上述理论并不完美，因为有些天敌是年年有的，比如鸟，17年蝉也无法幸免于难。所以现在科学家也没完全解释13年蝉和17年蝉周期性出现的原因。而且，中国南方的蝉是年年有的。尽管如此，人们还是把周期蝉称为“懂数学的蝉”。
周期蝉的生命周期为什么是质数仍是个谜，但人类使用质数的原因就非常确定。除了前面提到的上网，我们还在哪些领域使用质数呢？
在齿轮啮合上。相邻的两个齿轮是互质的（比如48/17），避免齿轮中固定的两个齿反复接触，延长齿轮的寿命（如果是48/16的话，某些齿会频繁接触，而某两个齿永远都不会接触，这对齿轮寿命不利）。
从上面的例子看，质数还是挺有用的。
从“玩具”到影响世界
尽管现在我们每天都会使用质数，但在历史上很长一段时间里质数只是数学家们的“玩具”，没有任何实用性。
“很长一段时间”到底是多长呢？可以负责任的告诉你，至少两千多年。
古希腊的数学家欧几里得在公元前300年左右（中国的战国时期，那时屈原还健在，秦始皇要等到59年后才会出生）就证明了存在无数个质数。但是人们（包括数学家们）始终不知道质数除了让数学家消遣娱乐之外还有啥用（不得不说，古代数学家们消遣娱乐的方式真是奇特）。英国的大数学家哈代（不是写小说的那个托马斯·哈代）就曾经在1940年自豪地说“过去没有人发现这些数（质数）及其理论用在军事上，未来很多年也不会”。
哈代并没有给“未来很多年”加一个期限，所以我们不知道他所认为的“很多年”到底是多少年。但现在我们可以给它加一个期限：33年。
在1973年的时候英国政府通信总部的数学家就提出了公钥加密算法，但当时该算法属于政府绝密信息，直到1997年才被解密。
美国的两个学者在1976年提出了公钥密码学，引起了学术界的轰动。
1977年麻省理工学院的3位密码学家提出了实际的公钥密码学方案，就是使用至今的RSA算法，用他们3人的姓氏的首字母命名。RSA中用的就是质数。
RSA算法中关键的一步就是生成2个大质数p和q。在PKCS# v2.1及后续版本中，允许使用多个质数（PKCS，Public Key Cryptography Standards，公钥密码学标准）。两个大质数求乘积很容易，但是分解该乘积却非常难，这决定了RSA算法的安全性。
RSA算法在全球商业领域取得了巨大的成功（"知识就是力量"——培根），至今仍是全球最流程的公钥加密算法，三位作者也顺势在1982年成立了RSA Security公司（“知识就是金钱”）。
RSA公司很多人都没听过，毕竟它只是一家2B的公司。不过在2013年的“棱镜门”泄密事件中，RSA公司却得到了超高的曝光率。借用《潜伏》里吴站长的一句话：本来想露脸，结果把屁股露出来了！据路透社报道，RSA公司收了NSA（美国国家安全局）1000万美金，在其软件BSafe中默认使用被RSA植入后门的随机数生成算法DUAL_EC_DRBG，这部分内容在“戏说密码学:(2)密码的破译方法”中我们详细讲过。
咱们先看看RSA算法能干啥。
RSA能干啥
RSA算法主要是用来数据加密和数字签名。
RSA的神奇之处在于它有一个公钥和一个私钥，公钥可以公开，任何人都可以用，私钥只能你自己用，必须保护好。公钥加密的信息只能用私钥解密（公钥也解不开，就是这么神奇）。
这根我们平常理解的加密不一样。加密相当于上锁，解密相当于开锁。日常生活中上锁和开锁用的是同一把钥匙（家家的锁都是这样的），没有问题，但是在上网时这样做是有问题的。
有什么问题呢？
假如说你登录网上银行给朋友转账，不幸的是你被黑客盯上了。当你在网银上填写朋友的账号和转账金额后，账号和金额会通过互联网传给银行。当然，这中间需要经过很多路由器（比如你家的路由器）。黑客完全可以截获你发给银行的信息（太容易了），然后把你转账的目标账号修改成他的账号，这样钱就到他那儿了，太危险了。
为了避免上面的情况发生，你填写的目标账号和转账金额都是加密后传给银行（虽然你没有看到，但是浏览器默默帮你加密了），这下黑客没办法了吧？还是有办法的！
你登录网银的时候，银行会把秘钥传给你的浏览器，黑客当然也能截获秘钥。刚才我们说了，加密和解密用同一个秘钥（钥匙），黑客截获了你和银行间的秘钥，就能解开加密的数据，还是可以把你转账的目标账号换成他的账号。这下郁闷了：还能不能开心的用网银转账了？难道非得亲自去银行柜台办理？
先看看问题的根源：由于黑客能截获你和银行之间的所有信息，所以无论发送的是秘钥还是账号，统统都逃不过黑客的眼睛。这时候加密形同虚设了。那怎么才能安全的转账呢？
现在该RSA算法展示真正的技术了！
假设银行放弃了上面的加密方式，转而使用RSA算法。当你登录网银的时候，银行先把它的公钥发给你的浏览器（公钥可以给任何人看，包括黑客），当你输入转账金额和账号后，浏览器先用银行的公钥进行加密，然后发给银行。注意，公钥加密的数据只能用私钥解密，而私钥在银行手里！这时黑客截获了加密数据也无法解密，此时黑客的内心是痛苦的：我没有银行的私钥啊！这样我们就安全的完成了网银转账。
这就是RSA算法的神奇之处。RSA算法实现了在不安全信道上进行数据的安全传输。
RSA算法不仅可以用于银行系统，还可以用于个人间的数据安全分享。比如说你和朋友想分享一些文件，但是你俩的网络被黑客监控了。这时你可以和朋友交换公钥，把要分享的文件先通过他的公钥加密后发给他，黑客由于没有你朋友的私钥而无法解密，只有你朋友能解密。你朋友用同样的方法把他的文件加密分享给你。进一步扩展，任何两个单位/个人之见都可以通过这种方式加密分享数据，而不用担心被黑客解密。
这么看来，RSA算法既神奇又实用！
前些年大起大落的比特币（区块链技术），用的就是公钥密码算法，虽然不是RSA算法，但原理相同。
自从诞生的那一天起，RSA算法就接受来自全球黑客、学者、研究人员的攻击。40多年过去了，事实证明RSA算法很安全，只要你的秘钥够长。RSA秘钥长度通常是1024~4096位。2010年的时候攻破了RSA-768，一些专家认为RSA-1024在不远的未来会被攻破，但没几乎有人认为RS-4096能够在可预见的未来被攻破。
RSA还有一个作用就是数字签名，这是后话。
RSA算法的缺点：慢
是的，尽管RSA算法即安全又神奇，但是它的计算速度很慢，比AES算法慢了不止千倍万倍。以RSA-4096为例（安全强度介于AES-128和AES-192之间）和AES-256做对比，在Intel Core i7-7700 CPU、16GB RAM的Windows 10电脑上，RSA-4096解密1000次大概需要34.7秒（如果在解密软件中让用户等34秒，估计开发人员会饿死），而AES-256解密1000次只需0.44ms。二者之间大概差了十万倍。
所以通常把RSA算法和AES算法一起使用，先用RSA算法在不安全信道上传输AES的秘钥，后续就用AES进行数据加解密。这样既安全又快速——so easy!
为了增强RSA的安全性，还会对数据进行填充，就是掺入一些乱七八糟的数据，让原来的数据看起来更乱。常用的有PKCS#1填充（已经不安全）和OAEP（最优非对称加密填充，Optimal asymmetric encryption padding）填充。
RSA中的因式分解到底有多难？
因式分解的难度决定了RSA算法的安全性，这是RSA算法的命门所在。那么因式分解一个大数据到底有多难呢？
下面是RSA-4096生成的参数，其中n=p*q。如果只知道n而不知道p和q，现有的技术想要分解出p和q，需要很长很长时间。“很长很长”是多长呢？科学家推测地球已经诞生了46亿年了，大约还能再存活50亿年。以目前的技术，分解p和q的时间要比这长多了。现在全球最快的超级计算机是美国的“顶点”（Summit），峰值速度是20亿亿次/秒（200PLOPS，即2×10^17），在p和q未知的情况下，用它来从n中分解出p和q大概需要52万亿年。
如果能够破解RSA-4096，就可以干很多事情：比如全球银行的钱都是你的了，政府可以用这项技术摧毁任何其他国家的金融体系......
n=0xcd07894d8d39ee11e150e840ce0634fe47d6f0202090c4b1fee94281f8c2166088beb6106a1df4643584f44aeda3e0c37882f008f98ad4a5c0a3a03bacf975509cc85a6a94554bd00bcd39650e898271593110f18b231051e3161400c8a0881d91f23a0c3bbd52247d80ad56d21543f6e601eb2a60515b6cb425a2a85efa7832bada6be256cdd444aeb8ed03d2833cd76dec6947a8254c89dd48d6cfb29c67ae222b5f684dfc174aafe34744fb5e562a240f276ade902f93d314bde97dd11a3e8b2b8312a7e69be6a6e09a4ed7ac33712ac2d52c0d120b8dc801d177ebca47d4945c760e6b523f8a21e23208a8b73babb382048176754cd4c7c19c24eeafdf4ef337bf61fc6aa180105071bef50deb25adfb36139e71faa885b0c0a9709af7bad9da5523dfe336b336884f72adb5379b7bf50165255babb4c11e1b86a5545ce637fb044c7cd6b820a442d18dbe526e22a121cbdaf4fb824ff041203ca61b0cb545fb531963167566f7e92bb1492342567e2c93e0003299f2a02a035f03f675c992361a19b471cbf93d7adc21c5d63c97cbac26b0ac746f521c1611b29393b30dabf9968bd5a8ac8e6c996f90bd907e2841c6531dffbd11f53551a09632f1c779c905101e3bb2fadc6403dca7bf5cc86dffa52548546e09dfe7eeb71ce02ee8090ea813dfeb4ed2c376025f204432a2e91581ff9209ea670d8007d0157ebe74f9
p=0xdf6f823ed432354aa21d2847947a7d01b2cf436ef17e7a91e49dcd6fd579c9706628477b1584cdc4a284b3cc960638d8c4352fc9efd826f6106d1d4feb75541adc84d0a2a7d59e7f43c6338488319ff5d7e90f5e26380e4253f0e94df51fe924bcacf4cf61729a52a757cc64faa334942cbf72fcef71fff105db5be1f9a3876467d2813529afae6a824f69243f9d5b880127ccc055cedb32d66cacb811027f9f228a9c99d06ecd533bcca752ded278c9ed34ff79ac2e67ba0a925d09aae38bfad7a10a81cc8335b1e8258640f3e620645c9abc37d6299464ab98daf8dc811c5b7898b2be6af53769b23306dc6be0e17d2d352d77fad11cb199fa67c71c207c5f
q=0xeae9490d7f7f3de71beb33c3c4d5ea51464e9a82747e5901040c2b08d9e6012acfd20abb0402f6eb06e0472c45091c7cfde6e7c9b024aad1cb4aea8327919c52e97250cac80ad3776c31f6f5ca2af8d9862f58fc3a7a5e442b2e441241f8e4a5a518c47ff9a2b923fb8b2e4be5793788618bdfc2a4117dc44811e6227b1be7e6d7ab8d250ee3f2d1ad69e929bfc3f8ee736ae85d716d70fb776f6888a64d6ee823fd9665eb2f85577c193316f4d4c4fd27932100e9783b6bfff76402f504a17858ae2e80cf0d2c953e7395adfb42490f4a61a060bf8dce3fb69c5af9baee89663d58e6de22fdac6982579c8f411f6586c7b8f4a9ddd2a10a4390c4d2ba138da7
当然，如果黑客能偷偷把银行的公钥换成自己的公钥，网银转账就还是不安全。于是网络安全人员提出了“证书”的概念，来证明哪个公钥是银行的，哪个不是，以此来防范黑客。
RSA算法还可以用来数字签名，我们下次再聊。
参考：
[1]质数. https://zh.wikipedia.org/wiki/素数
[2]Prime Number. https://en.wikipedia.org/wiki/Prime_number
[3]RSA加密算法. https://zh.wikipedia.org/wiki/RSA加密演算法
[4]RSA(Cryptosystem)https://en.wikipedia.org/wiki/RSA_(cryptosystem)
[5]PKCS #1: RSA Cryptography Specifications Version 2.2. https://www.rfc-editor.org/rfc/pdfrfc/rfc8017.txt.pdf
[6]周期蝉.https://zh.wikipedia.org/wiki/周期蝉
[7]Periodical cicadas. https://en.wikipedia.org/wiki/Periodical_cicadas
[8]RSA Security. https://en.wikipedia.org/wiki/RSA_Security
徐红伟@百香果科技
