88、密码（1 / 2）

人与人之间相互传递和交流信息是一种基本的需求，可是在很多情况下，人们希望信息能够传递给特殊的人，而且不希望在信息的传递过程中泄露出去。于是，密码诞生了。通过对信息进行加密，然后传送加密后的信息，接收人再按照一定的规则解密就可以实现安全通信了。即使加密后的信息被截获，呈现出来的也是一团难以读懂的乱码。

在人类历史的发展过程中，信息的安全传递是至关重要的。最早的加密方法一般是将组成信息的符号依照约定的表格逐个替换，苏格兰玛丽女王就是用这种方式加密的。显然，这种密码太原始和简陋，尽管信息这样加密后，乍一看去还是蛮不错的，但是每个符号出现在文中的概率分布没有变化，通过统计符号出现的概率，就可以破译密码，玛丽女王也因为一封这样的加密信件被破译而丢掉了生命。后来，密码学不断进化和发展，伴随着加密方式的更新，破译手段也是层出不穷，直到NP问题被应用于信息加密，密码学才迎来了真正的春天。

计算机与互联网时代，对信息进行加密的需求变得极为迫切起来，因为无论是在计算机网络中，还是在由电磁波构建的移动互联网中，想截获信息是一件很容易的事情。这样，信息的加密技术就成为保护信息最重要的方式。计算机科学的发展，诞生了一门被称为计算复杂度的分支，用于将问题按照计算复杂度进行分类。

通俗的讲，可以很容易求解的问题被称为P类问题；而难以求解但是给定一个解可以很容易验证解的问题称为NP问题；NP问题中有一类最难的问题称为NPPC问题集有一个让人惊讶的特点，只要其中一个NPC问题有简单解法，所有的NP问题也都有了简单的解法。NP问题的性质正是密码学所需要的，难以求解的具体数学问题保证了加密方式的安全性，因为只有解出这类数学难题，才能破译密码，而NP问题求解难度的单向性使没有权限的信息截获者无法获取信息。

如今最常用的RSA公钥加密方式就是一类NP问题，许多人相信，它的难度还没有达到NPC的程度。这种加密方式利用的就是问题难度的不对称性，给定两个素数求解它们的乘积非常容易，而如果给定乘积求解是哪两个素数则会随着数字位数的增加，其难度也迅速增加，从而通过数学问题的难度保证了信息安全。

虽然从道理上说，凡是基于NP问题的密码理论上都是可以破译的，只要解决了其中关键性的数学难题即可，但是通常情况下解决这类难题的最好算法也需要漫长的宇宙年龄级别的时间，从而保证了信息的安全。如果能够实现量子计算，因式分解问题会由困难问题转化为简单问题，我们也就可以通过量子shor算法破译这类密码体系，但是对于更难的由NPC问题构造的密码体系是否也可以通过量子计算的方式解密，暂时还不得而知。能否通过量子计算机或其它任何方式将任何一个NPC问题的复杂度降低到多项式时间，也就是解决P=NP？问题，我们还不知道，但是如果一旦这个问题得到肯定的回答，现有的所有基于NP问题的密码体系将会陷入崩溃状态。量子效应不仅提供了一种破译部分密码的可能性，而且给出了一种理论上永远无法破译的加密方式。