质数和网络安全-简单科普

数学中的质数只能被1和自身整除，而且有无穷个。这个已经被欧几里德证明过了，除此之外，谜一样的质数也是网络安全方面重要的一个角色。

目前正在进行中的因特网梅森素数大搜索（GIMPS）项目就是为了发现更多的质数，已知最大的质数具有23249425个位数，要写完这个质数需要9000页张纸，而目前已知的原子数量不会超过100个位数。

这个由一个志愿者花了14年的时间计算后得出的质数写作2⁷⁷²³²⁹¹⁷-1。有人会提出疑问，需要知道这么大位数的质数吗？知道这些质数有什么用？

质数在网络安全领域的应用之一就是RSA加密。

1978年Ron Rivest，Adi Shamir，Leonard Adleman三人创建的RSA加密，其中就利用了质数的组合。现在的加密网络传输协议中应用到了RSA加密原理。在这个原理中需要使用2个质数，质数越大加密越安全。

以数字70来举例，可以分解为2个35，35分解为5×7，因此70可以看作由2、5、7这几个数字构成，而这几个数字都是不可再进行分解，因此将这个过程称为70的质因数分解。

通常两数相乘比较简单，而要对一个数进行质因数分解却非常困难，这也是RSA加密为什么需要利用质数的原理。

视频：

http://v.youku.com/v_show/id_XMzMyNjE1MDY2MA==.html?spm=a2h3j.8428770.3416059.1

假设Alice和Bob两人，在网上希望进行加密通信，这就需要使用加密系统。

如果两人第一次见面可以商定一个只有他们才知道的加密解密系统，而在网上却做不到这点，两人一开始必须通过不加密的网络连接后才能加载加密系统，这个过程非常危险。

这时就用到RSA算法。下面用通俗一点的行文简单介绍一下它的原理：

Alice的儿子想和Bob的女儿处朋友，Alice就公开在网上问了Bob一句：“你女儿多少斤？”

为了得到这个答案，Alice首先选择2个大的质数得到一个乘积N（公钥，可以在网络上公开传播，第三方也可以截获），将“100”加密后发送给Bob；

Bob接收到数据后，他也不知道Alice的原信息是什么（因为Bob虽然知道公钥N，但他没有产生N的2个大质数，所以解不开Alice给他发的信息），所以他就不理了，直接把他女儿的真实体重“180”混合在Alice的原信息中，用之前的公钥N加密之后发回给Alice。

这样折腾一圈有什么好处呢？好处就是即使有第三方截获了信息，而且还知道了公钥N，例如Eve，他儿子也想和Bob的女儿处朋友，也想知道Bob的女儿有多重，就偷听了他们俩的对话。

这时候Eve截获的信息用公钥N解密之后发现是“280”，这时候估计就放弃了。

如果Eve聪明一点的话可能会猜测到Alice往里面“掺水”了，但他也没办法啊，他破译不了Alice的原始信息，不知道掺了多少水。

现在Alice接收到Bob发回的混合信息“280”，再减去之前自己放的“100”，就知道Bob他女儿有多重了。

（以上只是做个简单的类比，真实的细节会更复杂，大家有兴趣可以去了解一下）

随着技术的发展，电脑的运行速度越来越快，因此简单的质数已经不能满足加密的需求，所以需要不停寻找更大的质数。

目前找到的最大质数由于位数太多，无法用于现实生活中的加密，而且量子计算机的出现可能会打破这种定律。

当然数学家最初并不是为了加密才去寻找最大质数，而是为了寻求探索过程中不断发现新宝藏的那种感觉。

更多时候数学家并不关心找到的质数是不是有用或是不是最大质数，而是为了满足人类的求知欲。