基于双钥技术的现代加密方法

 
我们先讲解一下双钥技术的工作原理，然后再介绍几个着名的加密方法。

　　工作原理分析
　　双钥技术就是公共密钥加密PKE(Public Key Encryption)技术，它使用两把密钥，一把公共密钥(Public Key)和一把专用密钥(Private Key)，前者用于加密，后者用于解密。这种方法也称为“非对称式”加密方法，它解决了传统加密方法的根本性问题，极大地简化了密钥分发的工作量。它与传统加密方法相结合，还可以进一步增强传统加密方法的可靠性。更为突出的是，利用公共密钥加密技术可以实现数字签名。

　　为说明公共密钥技术的工作原理，我们还得从传统加密方法的工作原理说起。

　　传统加密方法的工作过程包括如下几部分：

　　(1) 设置一个保险箱，并装置一把嵌入箱子的暗锁，这种锁只能使用钥匙才能锁上，再准备2把相同的钥匙。这对应于加密方法，钥匙对应于密钥。

　　(2) 发信方和收信方必须各自持有1把开锁的钥匙。这对应于密钥分发过程。

　　(3) 发信方将通信文件放入保险箱，并使用自己持有的钥匙把锁锁起来。这对应于加密过程。

　　(4) 运送保险箱。这对应于信息传输过程。

　　(5) 保险箱送到目的地后，收信人用自己持有的钥匙打开锁，取出通信文件。这对应于解密过程。

　　全部过程的根本困难是第(2)步，即通信双方必须都获得1把统一的钥匙，前文已经述及，这一步实现起来要付出很大代价。如果我们仔细分析一下，可以发现，发信人真正需要的仅仅是一个能装秘密文件并能锁上的保险箱，没有必要也持有1把钥匙。之所以要有钥匙，是因为使用了嵌入箱子的暗锁。显然，只要不使用这种锁，而使用一种不用钥匙也能锁上的锁，则发信人就可以在没有钥匙的情况下，锁住保险箱。基于这种思想，可以按如下过程进行加密：

　　(1) 设置一个保险箱，并设置一把不需使用钥匙就能锁上的锁，再准备1把钥匙。这对应于加密方法，钥匙对应于专用密钥。

　　(2) 收信方持有这把开锁的钥匙，同时准备该钥匙可以开的锁，锁可以不止有1把，然后把锁公开发放出去。这里锁对应于公共钥匙，这个过程对应于公共密钥分发过程。

　　(3) 任何人想与收信方通信，只需将通信文件放入保险箱，并使用收信方承认的锁锁起来。这对应于加密过程。

　　(4) 运送保险箱。这对应于信息传输过程。

　　(5) 保险箱达到目的地后，收信人用自己持有的唯一的钥匙打开锁，取出通信文件。这对应于解密过程。

　　由于可以开锁的钥匙只有一把，而且掌握在收信人手里。因此可以确信除收信人本人外，没有任何人能够打开锁着的保险箱并偷阅其中通信文件的内容，发信人对此也不例外。更为重要的是，密钥分发的难题也不复存在了，而是代之以锁的分发问题。分发锁是无须保密的，这无疑使以前的艰难工作简单了许多。这就是公共密钥加密技术的工作原理。

　　公共密钥加密系统中，收信人首先生成在数学上相互关联、但又不相同的两把钥匙，一把公共密钥用于加密，另一把专用密钥用于解密，这一过程称为密钥配制过程。其中公共密钥相当于例子中不需使用钥匙就能锁上的锁，用于以后通信的加密；另一把专用密钥相当于例中提到的那把开锁的唯一的钥匙，用于通信的解密。收信人将唯一的专用密钥掌握和保存起来，把公共密钥通过各种方式公布出去，让想与收信人通信的人都能够得到。这个过程就是公共密钥的分发过程。发信人使用收信人的公共密钥对通信文件进行加密，加密后的密文发信人自己也无法解开，这相当于把信件十分可靠地锁在保险箱里。收信人在收到密文以后，用自己的专用密钥解开密文获得明文信息。

　　公共密钥加密系统的优点
　　与传统加密方法相比，公共密钥加密系统具有3方面比较突出的优点：

　　(1) 用户可以把用于加密的密钥，公开地分发给任何需要的其他用户。谁都可以使用这把公共的加密密钥与该用户秘密通信。除了持有解密密钥的收件方用户外，没有人能够解开密文。这样，传统加密方法中令人头痛的、代价沉重的密钥分发问题就转变为一个性质完全不同的“公共密钥分发”的问题。

　　(2) 公共密钥加密系统允许用户事先把公共密钥发表或刊登出来。譬如，用户可以把它和电话号码、产品说明等一起刊登出来，让任何人都可以查找并使用到。这使得公共密钥应用的范围不再局限于信息加密，还可以应用于身份鉴别、权限区分等各种领域。例如，大家熟知的各种应用软件，如Windows 95/98等系统安装时需要的产品序列号，其实就是公共密钥，它通常印在产品授权书的封面或封底上，供安装时鉴别用户的授权身份。

　　(3) 公共密钥加密不仅改进了传统加密方法，而且还提供了传统加密方法所不具备的应用，即是数字签名的公开鉴定系统。有关数字签名的工作原理与过程我们将在后面介绍。

　　自从1976年第一个正式的公共密钥加密算法提出，又有几个算法被相继提出。下面我们就简要介绍几个主要的公共密钥加密算法。

　　Ralph Merkle猜谜法
　　虽然这个方法并没有付诸实施，但它是第一个认真思考公共密钥加密问题的算法。该算法于1974年由美国加州大学伯克利分校的学生Ralph Merkle提出，核心是做100万个猜谜题，每道谜题藏有一个密码，求解一道迷题大约需要2分钟时间。该算法的工作流程是这样的：甲方先随机地产生100万把密钥，并藏在100万道谜题里，然后把这100万道谜题发送给乙方；乙方收到后，随意挑选并求解一道谜题，取出其中的那把密钥，再用该密钥对一个双方事先统一的报文加密，这段报文可以任意，且无需保密；加密后，把密文发送给甲方；甲方并不知道乙方选择了哪把密钥，于是使用自己保存的100万把密钥逐一进行尝试解密；其中必有一个是可行的，这把密钥不为其他人所知，所以可以作为以后通信使用的密钥。

　　如果传输过程中被人窃取，那么窃取者可能窃取到甲方发出的100万道谜题，也可能窃取到乙方返回的密文。但要想知道乙方选中了哪把密钥，窃取者只能去求解100万道谜题，由于解开一个谜题需要2分钟时间，按50%的解出概率计算，窃取者平均需要23个月的时间才能找到答案。不过那时通信双方早已结束了通信，完成了秘密任务或改换了密码，窃取者的工作已经没有多大意义了。

　　Ralph Merkle方法有一个弊端，那就是收发双方之间的通信系统必须能够在合理的时间内传送100万道谜题，而且甲方应拥有快速的计算机以产生100万道谜题和尝试100万次搜索，找出乙方选择的密码。如果计算机性能不佳，显然这种方法就不太实用。

　　Diffie-Hellman指数密钥交换加密算法
　　该算法于1976年由美国斯坦福大学的Whitfield Diffie和Martin Hellman提出，利用了离散指数易求而反函数难求的特性来设计加密系统，是专门为双方主动参与的通信过程设计的。该算法非常简捷。它让通信双方共同参与一个数学运算过程，并统一一把用于以后加密的密钥。即使监听者能窃取到全部交换信息，但由于没有参与运算，他也无法获得最终的密钥。通信双方首先各自挑选一个秘密的数，然后交换一些由此数导出的信息；接下来利用这些信息，通过离散指数和质数求余等运算就可以进一步推导出一把统一的密钥，用于加密以后的通信。该密钥交换加密算法的工作过程如下：

　　(1) 通信双方统一两个数D和H。D与H无须对外保密。

　　(2) 双方各自选择一个秘密的数X，并把包括D，H和X的计算结果Y发送给对方。例如：假设甲方选中了X1，则发出了Y1；乙方选中了X2，则发出了Y2。

　　(3) 根据算法，双方各自使用自己选择的X和收到的Y，计算出一个统一的数字K。K就是双方进一步通信的会话密钥。具体地讲，K可以从(X1，Y2)或(X2，Y1)中导出，但却不能从(Y1，Y2)中得到。这一点的重要意义在于，窃听者虽然可以得到D，H，Y1和Y2，甚至密文，但由于不知道X1和X2的值，因此无法获得导出正确的会话密钥K，从而也就无法破解密文。

　　(4) 以后通信时，双方便使用K进行加密和解密。

　　Diffie-Hellman算法的弊端在于它需要收发双方必须同时参与密码的生成过程，所以它不适合于电子函件的加密，因为电子函件在收信人不在场时也应当能够发送过去。

　　Merkle-Hellman背包算法
　　该算法是根据数学上的背包问题设计的。背包问题是一个最优化问题，即对一个给定空间或负重的背包和许多大小不一的物体，哪些物体放入背包才能使得浪费的背包空间或负重最小？在背包很小和物体数目较少时，这个问题还比较容易解决；但当背包很大且有很多个物体时，问题的求解就十分困难。通常，这个问题会有一个或者多个解，也有可能根本没有解。

　　1977年，Merkle与Hellman合作设计了使用背包问题实现信息加密的方法。其工作原理是：假定甲想加密，则先产生一个较易求解的背包问题，并用它的解作为专用密钥；然后从这个问题出发，生成另一个难解的背包问题，并作为公共密钥。如果乙想向甲发送报文，乙就可以使用难解的背包问题对报文进行加密，由于这个问题十分难解，所以一般没有人能够破译密文；甲收到密文后，可以使用易解的专用密钥解密。

　　该算法提出以后，经过多年的探讨和研究，最终发现了它的一个致命错误，使之失去了任何保密的实用价值