密码学协议举例[3]–另类的密钥交换协议

另类的密钥交换协议

这是密码学协议的第三篇文章, 前面两篇的链接分别为:

• 密码学协议举例[1]–秘密共享的门限方案
• 密码学协议举例[2]–带有防欺骗的承诺

想法与简单的想法

密钥是密码的命根，一切不安全的秘密交换都源于不安全的密钥交换。目前，绝大多数协议采取RSA算法进行密钥交换，但在RSA算法出现之前，人们又是怎么做的呢？

据说，第一个密钥交换算法是一个名叫Ralph Merkel的人在1974年发明的，算法叫做Merkle's Puzzles。这是一个非常奇特、非常邪恶的密钥交换协议。

假设A和B想进行秘密通信，他们需要选取一个密钥。A准备好很多很多个形如"密钥编号为X_i，密钥是Y_i"的消息，其中X_i是一个随机标识符，Y_i是一个随机密钥。消息的个数越多越好，起码要有几十万几百万条。

然后，A把这些消息都编码为一个个难题，比方说对第i条消息异或一个大质数P_i，并宣称P_i是某个数N_i最小的那个质因子。A把所有编码后的消息全部发给B。B收到这些消息之后，随便选择一条消息进行暴力破解（在上例中就是暴力分解某个N_i），得到某一对对应的x和y。B用明文给A发一个消息，说"我们就用编号为x的密钥吧"。

由于A知道这个x对应的是哪个y，因此A知道B说的密钥是哪个。

这个协议的核心就是，第三者不知道B当时选的是哪条消息。如果有第三者截获了他们之间的通信，要想获得密钥y，他必须一一破解所有的难题，直至解开了那个编号为x的密钥消息。由于这样的难题数量大得惊人，第三者要花费的努力是B的上百万倍。假如用计算机暴力破解一个难题需要一个小时的时间，那么第三者即使有百倍于B的计算能力，他也需要平均一年多才能解到正确的x和y。

举例说明

• A告诉B：P100是613798637的最小质因子，其中613798637 = 79 * 97 * 173 * 463
• B收到后，随机抽一个，假设就是抽中了这个，计算得到P100=79，再通过计算得到x100和y100, x100是一个随机标识符, y100是随机密钥
• B将x100发给A, A就知道B用哪个加密了.
• A收到后，使用y100进行加密，发给B，此时B也知道密钥为y100了。