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

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